Fast fourier transform architecture using hybrid n-bit-serial arithmetic
US4868776A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Sep 14, 1987 |
| Grant date | Sep 19, 1989 |
| Priority date | — |
| Expiry date | Sep 14, 2007 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F17/142
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A fast Fourier transform circuit, including an illustrative radix-eight discrete Fourier transform (DFT) kernel that operates on an n-bit-serial data format, for an efficient serial-like, pipelined operation within the DFT. The circuit performs a four-point DFT on half of the input data words at a time, stores intermediate results from the four-point DFT in a commutation stage, then combines the intermediate results in two two-point DFTs. Internal multiplication in the eight-point DFT is effected in delay registers that also serve to store the intermediate results, thereby providing an economy of timing and circuit routing. Interleaving and deinterleaving operations convert the data format between three-bit-serial and conventional bit-parallel used outside the eight-point DFT kernel, which may therefore be easily cascaded for more complex FFT operations. The DFT kernel also includes means for selectively bypassing butterfly computation modules to perform shorter-length DFTs.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.