US4534009A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pipelined FFT processor
Assignee: United States Department of the Navy
•
Filing: 1982-05-10
•
Granted: 1985-08-06
•
Expires: 2002-05-10
Abstract
Abstract A pipelined Fast Fourier Transform (FFT) processor is described for proceng continuous sets of N samples in a highly efficient manner. Within a single set of N inputs, the samples arrive in pairs (sample 0, and 1, 2 and 3, 4 and 5, etc.). This input sequence can be obtained from a sequential stream of inputs (sample 0 followed by smples 1, 2, 3, 4, etc.) by delaying the even numbered sample by one time unit. Alternately, the device could be made to operate on sequential samples within a set of N samples by internal pipelining of the arithmetic units. The device achieves high arithmetic unit efficiency while minimizing the memory required by allowing each arithmetic unit in the pipeline, with the exception of the last, to operate on the even or odd numbered samples first, after which it will operate on the remaining samples, which have been appropriately delayed and switched through shift registers and switches. The structure of the device, through its novel arrangement of shift registers and switches, allows an internal reordering of the data such that 100 percent arithmetic unit efficiency can be obtained, while requiring only 2(N-1)-(N/2) memory locations.
Inventors
- 👤 Kevin J. McGee
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 14:01
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/14; G06F17/141; G06F17/142
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
248 words
A system of calculating the Fast Fourier Transform of data comprising: a plurality of serially connected subsystems with each subsystem including a subsystem first and second input terminal, a switch having first and second input terminals and first and second output terminals with said switch first input terminal connected directly to said subsystem first input terminal, a first delay having an input and output terminal with said first delay input terminal connected directly to said subsystem second input terminal and said first delay output terminal connected directly to said switch second input terminal, a second delay having an input and output terminal with said second delay input terminal connected directly to said switch first output terminal, and an arithmetic element having a first and second input terminal and a first and second output terminal with said arithmetic element first input terminal connected directly to said second delay output terminal and said arithmetic second input terminal connected directly to said switch second output terminal; the first serially connected subsystem and the last serially connected subsystem have the same number of locations in their respective first and second delays; and each succeeding serially connected subsystem has half the number of locations in their respective first and second delays until the first and second delay each have a predetermined number of locations, then the following subsystem has a first and second delay with the same number of locations as the respective first and second delays of the first serially connected subsystem.
Claim 2
Independent Claim
248 words
A system of calculating the Fast Fourier Transform of data comprising: a plurality of serially connected subsystems with each subsystem including a subsystem first and second input terminal, a switch having first and second input terminals and first and second output terminals with said switch first input terminal connected directly to said subsystem first input terminal, a first delay having an input and output terminal with said first delay input terminal connected directly to said subsystem second input terminal and said first delay output terminal connected directly to said switch second input terminal, a second delay having an input and output terminal with said second delay input terminal connected directly to said switch first output terminal, and an arithmetic element having a first and second input terminal and a first and second output terminal with said arithmetic element first input terminal connected directly to said second delay output terminal and said arithmetic second input terminal connected directly to said switch second output terminal; the first serially connected subsystem and the last serially connected subsystem have the same number of locations in their respective first and second delays; and each succeeding serially connected subsystem has half the number of locations in their respective first and second delays until the first and second delay each have a predetermined number of locations, then the following subsystem has a first and second delay with the same number of locations as the respective first and second delays of the first serially connected subsystem.
Claim 3
Dependent Claim
82 words
A system according to claim 1 wherein said switch has a first and second position wherein said first position has said switch first input terminal connected to one of said switch output terminals and said switch second input terminal connected to the other of said switch output terminals, and said second position has said switch first input terminal connected to the other of said switch output terminals and said switch second input terminal connected to one of said switch first output terminals.
Claim 4
Dependent Claim
27 words
A system according to claim 2 wherein said first delay of each subsystem has the same number of locations as said second delay of the same subsystem.
Claim 5
Dependent Claim
25 words
A system according to claim 3 wherein said first and second delays comprise first and second shift registers and said switch comprises a crossover switch.
Claim 6
Dependent Claim
14 words
A system according to claim 1 wherein said predetermined number of locations is one.
Claim 7
Independent Claim
188 words
A system of calculating the Fast Fourier Transform of data comprising: a plurality of serially connected subsystems with each subsystem including a subsystem first and second input terminal, a switch having first and second input terminals and first and second output terminals with said switch first input terminal connected directly to said subsystem first input terminal, a first delay having an input and output terminal with said first delay input terminal connected directly to said subsystem second input terminal and said first delay output terminal connected directly to said switch second input terminal, a second delay having an input and output terminal with said second delay input terminal connected directly to said switch first output terminal, and an arithmetic element having a first and second input terminal and a first and second output terminal with said arithmetic element first input terminal connected directly to said second delay output terminal and said arithmetic second input terminal connected directly to said switch second output terminal; and the first serially connected subsystem and the last serially connected subsystem have the same number of locations in their respective first and second delays.
Claim 8
Independent Claim
188 words
A system of calculating the Fast Fourier Transform of data comprising: a plurality of serially connected subsystems with each subsystem including a subsystem first and second input terminal, a switch having first and second input terminals and first and second output terminals with said switch first input terminal connected directly to said subsystem first input terminal, a first delay having an input and output terminal with said first delay input terminal connected directly to said subsystem second input terminal and said first delay output terminal connected directly to said switch second input terminal, a second delay having an input and output terminal with said second delay input terminal connected directly to said switch first output terminal, and an arithmetic element having a first and second input terminal and a first and second output terminal with said arithmetic element first input terminal connected directly to said second delay output terminal and said arithmetic second input terminal connected directly to said switch second output terminal; and the first serially connected subsystem and the last serially connected subsystem have the same number of locations in their respective first and second delays.
Claim 9
Dependent Claim
83 words
A system according to claim 6 wherein said switch has a first and second position wherein said first position has said switch first input terminal connected to one of said switch output terminals and said switch second input terminal connected to the other of said switch output terminals, and said second position has said switch first input terminal connected to the other of said switch output terminals and said switch second input terminal connected to the one of said switch first output terminals.
Claim 10
Dependent Claim
27 words
A system according to claim 7 wherein said first delay of each subsystem has the same number of locations as said second delay of the same subsystem.
Claim 11
Dependent Claim
25 words
A system according to claim 8 wherein said first and second delays comprise first and second shift registers and said switch comprises a crossover switch.
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) | 1988-08-05 | 1989-02-04 | 1989-08-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1992-08-05 | 1993-02-04 | 1993-08-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1996-08-05 | 1997-02-04 | 1997-08-06 | $7700.00 | Window Closed / Lapsed |