Data storage patterns for fast fourier transforms
US6728742B1 · kind B1 · utility
Inventor
Key dates
| Filing date | Aug 7, 2000 |
| Grant date | Apr 27, 2004 |
| Priority date | — |
| Expiry date | Apr 22, 2022 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F17/142
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method of performing a FFT of a sequence of N=Bn numbers, where B is a power of 2 and n is a positive integer. A pattern of storage locations for the Bn numbers in M in-place memories is selected recursively, where M is a power of 2 that is less than B, wherein, if n=1, each in-place memory has storage locations for a different B/M of the B numbers, and wherein, if n is greater than 1, the pattern for storing Bn numbers is a concatenation of B patterns for storing Bn−1 numbers, there being B/M successive sets of the patterns for storing Bn−1 numbers in the pattern for storing Bn numbers when n is greater than 1, the patterns, for storing Bn−1 numbers, within each of the B/M successive sets, is mutually identical and is different from the patterns, for storing B numbers, of any other the set. The numbers are stored in the storage locations. An in-place radix-B DFT is performed on each of N/B groups of values stored in the storage locations. If n is greater than 1, a length N/B DFT is performed on each of B groups of N/B values stored in the storage locations, each group including N/(MB) values stored in each of the in-place memories.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.