Interleaved method for parallel implementation of the fast fourier transform
US8606839B2 · kind B2 · utility
3Cited by
4References
3Claims
0Family size
Assignee
Inventors
Key dates
| Filing date | Aug 21, 2008 |
| Grant date | Dec 10, 2013 |
| Priority date | — |
| Expiry date | Apr 21, 2032 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F17/142
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method for computing a fast Fourier transform (FFT) in a parallel processing structure uses an interleaved computation process. In particular, the interleaved FFT computation process intertwines the output of two different shifted Fourier matrices to obtain a Fourier transform of an input vector. Next, an even-odd extension process is applied to the transformed input vector, whereupon various terms are grouped in a computational tree. As such, the resulting segmentation of the computation allows the fast Fourier transform to be computed in a parallel manner.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.