US4831574A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Device for computing a digital transform of a signal
Assignee: Individual
•
Filing: 1987-09-04
•
Granted: 1989-05-16
•
Expires: 2007-09-04
Abstract
Abstract Most of the useful discrete transforms of a signal X represented by N binary samples x0 . . . , xi . . . , x N-1 (Where N is a power of two) are such that, by combining the samples for obtaining the sum and the difference of couples of samples, the transforms may be converted into two transforms of half-length one of which may again be decomposed into two transforms of half-length. A device for computing such a discrete transform, for instance a discrete cosine transform (DCT) comprises a set of elementary circuits operating in serial arithmetic connected to receive the samples and arranged to provide the sums and differences of couples of the input samples on respective outputs; An additional circuit has inputs connected to the outputs of the elementary circuits for receiving the differences between couples of the input samples and for directly computing one of the two of the samples of the transform in distributed arithmetic. Another computing circuit distinct and different from the additional circuit has inputs connected to the elementary circuits and computes the remaining samples of the transform from the sums.
Inventors
- 👤 Pierre Duhamel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 14:50
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/14; G06F17/147
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
199 words
Device for computing a discrete cosine transform of a signal X represented by N binary samples x o , . . . , x i . . . , x N-1 , where N is a multiple of 2, said transform being such that, by combining said samples for obtaining the sum and the difference of couples of samples, the transforms are convertible into two transforms of half-length one of which is again convertible into two transforms of half-length, if N/2 is a multiple of 2, said device comprising: a set of elementary circuits operating bit per bit in serial arithmetic connected to receive said binary samples and arranged to provide the sums and differences of couples of said input samples on respective outputs; additional circuit means having inputs connected to the outputs of said elementary circuits for receiving said differences between couples of the input samples and for directly computing every other of the samples of the transform in distributed arithmetic; and computing means distinct and different from said additional circuit means having inputs connected to the other outputs of said elementary circuits for receiving said sums and computing the remaining samples of the transform from said sums.
Claim 2
Dependent Claim
199 words
Device for computing a discrete cosine transform of a signal X represented by N binary samples x o , . . . , x i . . . , x N-1 , where N is a multiple of 2, said transform being such that, by combining said samples for obtaining the sum and the difference of couples of samples, the transforms are convertible into two transforms of half-length one of which is again convertible into two transforms of half-length, if N/2 is a multiple of 2, said device comprising: a set of elementary circuits operating bit per bit in serial arithmetic connected to receive said binary samples and arranged to provide the sums and differences of couples of said input samples on respective outputs; additional circuit means having inputs connected to the outputs of said elementary circuits for receiving said differences between couples of the input samples and for directly computing every other of the samples of the transform in distributed arithmetic; and computing means distinct and different from said additional circuit means having inputs connected to the other outputs of said elementary circuits for receiving said sums and computing the remaining samples of the transform from said sums.
Claim 3
Dependent Claim
84 words
Device according to claim 1, for computing said discrete transform of the signal X represented by N binary samples, where N/2 is even, wherein said computing means includes: a set of further elementary circuits operating bit per bit in serial arithmetic arranged for precalculating sums and differences, further additional circuit means connected to receive said differences, for directly computing every other of the remaining samples of the transform in distributed arithmetic, and further computing means for computing the other ones of the remaining samples.
Claim 4
Dependent Claim
44 words
Device according to claim 2, wherein said further additional circuit means include butterfly modules connected to provide data necessary for computation of half of the remaining even terms and data necessary for computation of a polynomial product representing the balance of the even terms.
Claim 5
Dependent Claim
80 words
Device according to claim 1, wherein said additional circuit means comprises N/2 units, with N=2 n , each unit having a ROM for storing 2 2 values, addressing means for addressing the ROMs successively with each of successive bits of the input samples and accumulator means having input means connected to output means of said ROM for receiving a value in said ROM being addressed, and multiplier means feeding back the output of said accumulator means to the input thereof.
Claim 6
Dependent Claim
43 words
Device according to claim 1, wherein said transform has odd terms and even terms and the odd terms are computed directly as a polynomial product of length 2 n -1, the number N of the input samples being equal to 2 n .
Claim 7
Dependent Claim
28 words
Device according to claim 1, wherein said transform has odd terms and even terms and the odd terms are obtained as a polynomial product modulo (z N/2 +1).
Claim 8
Dependent Claim
46 words
Device according to claim 6, wherein the elementary circuits are for precomputation and comprise butterfly modules delivering data necessary for computing the even terms on an output and data necessary for computing a polynomial product representing the odd terms of the transform on an other output.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-05-15 | 1992-11-14 | 1993-05-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-05-15 | 1996-11-14 | 1997-05-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-05-15 | 2000-11-14 | 2001-05-16 | $7700.00 | Window Closed / Lapsed |