US3702393A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Cascade digital fast fourier analyzer
Assignee: AT&T Inc
•
Filing: 1970-10-21
•
Granted: 1972-11-07
•
Expires: 1990-10-21
Abstract
Abstract A single input channel cascade FFT processor includes a plurality of substantially identical arithmetic units connected by a delay and switching arrangement for selectively delaying subsets of input data samples and intermediate results. By reordering an input sequence and thus selectively delaying, all components are operated at full capacity at all times, while a reduced amount of storage (delay) is required. Alternate embodiments provide for multiplexing a plurality of input data channels and multiplexing arithmetic units among a plurality of stages.
Inventors
- 👤 Peter Siegfried Fuss
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 10:57
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/14; G06F17/141; G06F17/142
Claims Analysis
Total Claims: 46
Claim 1
Independent Claim
259 words
A fast Fourier transform processor for forming Fourier coefficient signals corresponding to one sequence of N input samples, N > 2, said input samples in said sequence having been reordered in digits-reversed order to form a reordered input sequence, comprising A. a plurality of ordered cascaded processing stages, each stage comprising 1. a pair of input terminals, 2. a pair of output terminals, 3. first delay means for delaying signals applied at one of said input terminals, 4. computing means for forming output signals corresponding to selected pairs of signals applied at said input terminals, as selectively delayed by said first delay means, said computer means comprising a. a source of trigonometric function signals, b. a multiplier for forming product signals corresponding to the product of a first one of each of said pair of signals applied at said input terminals and selected ones of said trigonometric function signals, thereby to form a first product signal, and c. means for forming sum and difference output signals corresponding respectively to the sum of said first product signal and the second of each of said pairs of signals applied at said input terminals, and the difference between said second of said pair of signals applied at said input terminals and said first product signals, 5. second delay means for selectively delaying said output signals prior to applying said output signals to said output terminals, and B. means for applying alternate samples from said reordered input sequence to corresponding alternate ones of said input terminals of the first of said processing stages.
Claim 2
Dependent Claim
259 words
A fast Fourier transform processor for forming Fourier coefficient signals corresponding to one sequence of N input samples, N > 2, said input samples in said sequence having been reordered in digits-reversed order to form a reordered input sequence, comprising A. a plurality of ordered cascaded processing stages, each stage comprising 1. a pair of input terminals, 2. a pair of output terminals, 3. first delay means for delaying signals applied at one of said input terminals, 4. computing means for forming output signals corresponding to selected pairs of signals applied at said input terminals, as selectively delayed by said first delay means, said computer means comprising a. a source of trigonometric function signals, b. a multiplier for forming product signals corresponding to the product of a first one of each of said pair of signals applied at said input terminals and selected ones of said trigonometric function signals, thereby to form a first product signal, and c. means for forming sum and difference output signals corresponding respectively to the sum of said first product signal and the second of each of said pairs of signals applied at said input terminals, and the difference between said second of said pair of signals applied at said input terminals and said first product signals, 5. second delay means for selectively delaying said output signals prior to applying said output signals to said output terminals, and B. means for applying alternate samples from said reordered input sequence to corresponding alternate ones of said input terminals of the first of said processing stages.
Claim 3
Dependent Claim
5 words
a pair of output terminals,
Claim 4
Dependent Claim
5 words
a pair of output terminals,
Claim 5
Dependent Claim
5 words
a pair of output terminals,
Claim 6
Dependent Claim
5 words
a pair of output terminals,
Claim 7
Dependent Claim
17 words
The processor of claim 1 wherein said first and second delay means each comprise serial delay units.
Claim 8
Dependent Claim
5 words
a pair of output terminals,
Claim 9
Dependent Claim
5 words
a pair of output terminals,
Claim 10
Dependent Claim
5 words
a pair of output terminals,
Claim 11
Dependent Claim
5 words
a pair of output terminals,
Claim 12
Dependent Claim
33 words
a computer for forming at said output terminals Fourier series coefficient output signals based on pairs of data signals presented at said input terminals and on selected trigonometric function signals from said source,
Claim 13
Dependent Claim
33 words
a computer for forming at said output terminals Fourier series coefficient output signals based on pairs of data signals presented at said input terminals and on selected trigonometric function signals from said source,
Claim 14
Dependent Claim
33 words
a computer for forming at said output terminals Fourier series coefficient output signals based on pairs of data signals presented at said input terminals and on selected trigonometric function signals from said source,
Claim 15
Dependent Claim
33 words
a computer for forming at said output terminals Fourier series coefficient output signals based on pairs of data signals presented at said input terminals and on selected trigonometric function signals from said source,
Claim 16
Dependent Claim
47 words
The processor of claim 2 wherein at the ith of said stages, i 2, 3, . . . ,m, m log2N, said first delay means comprises means for delaying selected output signals from the (i - 1)th stage by an amount equal to 2i 2 sample periods.
Claim 17
Dependent Claim
13 words
first delay means for delaying signals applied at one of said input terminals,
Claim 18
Dependent Claim
13 words
first delay means for delaying signals applied at one of said input terminals,
Claim 19
Dependent Claim
12 words
first delay means for selectively delaying signals applied at said input terminals,
Claim 20
Dependent Claim
12 words
first delay means for selectively delaying signals applied at said input terminals,
Claim 21
Dependent Claim
125 words
computing means for forming output signals corresponding to said signals selectively delayed by said delaying means, said computing means comprising a. a source of trigonometric function signals, b. a multiplier for forming product signals corresponding to the product of a first one of each of said pair of signals applied at said input terminals and selected ones of said trigonometric function signals, thereby to form a first product signal, and c. means for forming sum and difference output signals corresponding respectively to the sum of said first product signal and the second of each of said pairs of signals applied at said input terminals, and the difference between said second of said pair of signals applied at said input terminals and said first product signals,
Claim 22
Dependent Claim
125 words
computing means for forming output signals corresponding to said signals selectively delayed by said delaying means, said computing means comprising a. a source of trigonometric function signals, b. a multiplier for forming product signals corresponding to the product of a first one of each of said pair of signals applied at said input terminals and selected ones of said trigonometric function signals, thereby to form a first product signal, and c. means for forming sum and difference output signals corresponding respectively to the sum of said first product signal and the second of each of said pairs of signals applied at said input terminals, and the difference between said second of said pair of signals applied at said input terminals and said first product signals,
Claim 23
Dependent Claim
16 words
first delay means for selectively delaying the presentation of said output signals at said output terminals,
Claim 24
Dependent Claim
16 words
first delay means for selectively delaying the presentation of said output signals at said output terminals,
Claim 25
Dependent Claim
16 words
first delay means for selectively delaying the presentation of said output signals at said output terminals,
Claim 26
Dependent Claim
16 words
first delay means for selectively delaying the presentation of said output signals at said output terminals,
Claim 27
Dependent Claim
134 words
computing means for forming output signals corresponding to selected pairs of signals applied at said input terminals, as selectively delayed by said first delay means, said computer means comprising a. a source of trigonometric function signals, b. a multiplier for forming product signals corresponding to the product of a first one of each of said pair of signals applied at said input terminals and selected ones of said trigonometric function signals, thereby to form a first product signal, and c. means for forming sum and difference output signals corresponding respectively to the sum of said first product signal and the second of each of said pairs of signals applied at said input terminals, and the difference between said second of said pair of signals applied at said input terminals and said first product signals,
Claim 28
Dependent Claim
134 words
computing means for forming output signals corresponding to selected pairs of signals applied at said input terminals, as selectively delayed by said first delay means, said computer means comprising a. a source of trigonometric function signals, b. a multiplier for forming product signals corresponding to the product of a first one of each of said pair of signals applied at said input terminals and selected ones of said trigonometric function signals, thereby to form a first product signal, and c. means for forming sum and difference output signals corresponding respectively to the sum of said first product signal and the second of each of said pairs of signals applied at said input terminals, and the difference between said second of said pair of signals applied at said input terminals and said first product signals,
Claim 29
Dependent Claim
55 words
A single-channel cascade FFT processor for generating Fourier series coefficients corresponding to a sequence of N periodic input data signals, N>2, said input signals in said sequence having been reordered in digits-reversed order to form a reordered input sequence, comprising A. a source of trigonometric function signals, B. a plurality of ordered stages each comprising
Claim 30
Dependent Claim
55 words
A single-channel cascade FFT processor for generating Fourier series coefficients corresponding to a sequence of N periodic input data signals, N>2, said input signals in said sequence having been reordered in digits-reversed order to form a reordered input sequence, comprising A. a source of trigonometric function signals, B. a plurality of ordered stages each comprising
Claim 31
Dependent Claim
96 words
second delay means for selectively delaying signals presented at said input terminals prior to their application to said computer, C. means for selectively connecting the output terminals of each of said stages except the last to the input terminals of a succeeding stage in such manner that each of said delay means delays a different equal length subset of signals during each succeeding period of said input sequence, and D. means for applying alternate signals in said input sequence to corresponding alternate ones of said pair of input terminals of the first of said ordered stages.
Claim 32
Dependent Claim
96 words
second delay means for selectively delaying signals presented at said input terminals prior to their application to said computer, C. means for selectively connecting the output terminals of each of said stages except the last to the input terminals of a succeeding stage in such manner that each of said delay means delays a different equal length subset of signals during each succeeding period of said input sequence, and D. means for applying alternate signals in said input sequence to corresponding alternate ones of said pair of input terminals of the first of said ordered stages.
Claim 33
Dependent Claim
66 words
A fast Fourier transform processor for concurrently forming a sequence of N Fourier coefficient signals corresponding to each of L input sequences, L>3, each of said input sequences including N input samples, N>2, said input samples in each of said input sequences having been reordered in digits-reversed order to form corresponding reordered input sequences, comprising A. a plurality of ordered cascaded processing stages, each stage comprising
Claim 34
Dependent Claim
66 words
A fast Fourier transform processor for concurrently forming a sequence of N Fourier coefficient signals corresponding to each of L input sequences, L>3, each of said input sequences including N input samples, N>2, said input samples in each of said input sequences having been reordered in digits-reversed order to form corresponding reordered input sequences, comprising A. a plurality of ordered cascaded processing stages, each stage comprising
Claim 35
Dependent Claim
46 words
second delay means for selectively delaying said output signals prior to applying said output signals to said output terminals, and B. means for applying alternate samples from said reordered input sequence to corresponding alternate ones of said input terminals of the first of said processing stages.
Claim 36
Dependent Claim
46 words
second delay means for selectively delaying said output signals prior to applying said output signals to said output terminals, and B. means for applying alternate samples from said reordered input sequence to corresponding alternate ones of said input terminals of the first of said processing stages.
Claim 37
Dependent Claim
89 words
second delay means for selectively delaying signals presented at said input terminals prior to their application to said computer, D. means for applying said reordered input sequence to the input terminals of the first of said plurality of stages, and E. means for selectively connecting the output terminals of each of said stages except the last to the input terminals of a succeeding stage in such manner that each of said delay means delays a different equal length subset of signals during each succeeding period of said input sequence.
Claim 38
Dependent Claim
89 words
second delay means for selectively delaying signals presented at said input terminals prior to their application to said computer, D. means for applying said reordered input sequence to the input terminals of the first of said plurality of stages, and E. means for selectively connecting the output terminals of each of said stages except the last to the input terminals of a succeeding stage in such manner that each of said delay means delays a different equal length subset of signals during each succeeding period of said input sequence.
Claim 39
Dependent Claim
47 words
second delay means for selectively delaying said output signals prior to applying said output signals to said output terminals, and B. means for sequentially applying pairs of signals from each of said L reordered input sequences to said input terminals of the first of said processing stages.
Claim 40
Dependent Claim
47 words
second delay means for selectively delaying said output signals prior to applying said output signals to said output terminals, and B. means for sequentially applying pairs of signals from each of said L reordered input sequences to said input terminals of the first of said processing stages.
Claim 41
Dependent Claim
46 words
The processor of claim 5 wherein said means for applying subsets of signals comprises a switch for directing alternate consecutive ones of said reordered input samples from a given input sequence to corresponding alternate ones of said input terminals of said first of said processing stages.
Claim 42
Dependent Claim
17 words
The processor of claim 5 wherein said first and second delay means each comprise serial delay units.
Claim 43
Dependent Claim
61 words
The processor of claim 5 wherein said subsets of signals from each of said reordered input sequences each comprise two input sample signals, and Wherein said first delay means at the first of said stages comprises means for delaying the first of said two input sample signals until the time of arrival of the second of said two input sample signals.
Claim 44
Dependent Claim
46 words
The processor of claim 8 wherein at the ith of said stages, i 2,3, . . . ,m, m log2N, said first delay means comprises means for delaying selected output signals from the (i - 1)th stage by an amount equal to L.2i 2 sample periods.
Claim 45
Dependent Claim
56 words
A single-channel cascade FFT processor for generating Fourier series coefficients corresponding to a sequence of N periodic input data signals, N>2, comprising A. means for forming a reordered input sequence by reordering said sequence of input data signals in digits-reversed order, B. a source of trigonometric function signals, C. a plurality of ordered stages each comprising
Claim 46
Dependent Claim
56 words
A single-channel cascade FFT processor for generating Fourier series coefficients corresponding to a sequence of N periodic input data signals, N>2, comprising A. means for forming a reordered input sequence by reordering said sequence of input data signals in digits-reversed order, B. a source of trigonometric function signals, C. a plurality of ordered stages each comprising
References Cited (Backward Citations)
US3544775A
Cited
US3588460A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1975-11-07 | 1976-05-08 | 1976-11-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1979-11-07 | 1980-05-08 | 1980-11-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1983-11-07 | 1984-05-08 | 1984-11-07 | $7700.00 | Window Closed / Lapsed |