Method and system for computing multidimensional fast Fourier transforms
US7483932B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | May 5, 2004 |
| Grant date | Jan 27, 2009 |
| Priority date | — |
| Expiry date | Jan 23, 2026 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F17/142
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Methods, systems, and articles of manufacture consistent with the present invention compute a multidimensional fast Fourier transform of an original matrix having rows and columns of data. The original matrix is divided into a number of blocks of data, each block including at least one datum, the number of rows of data in each block being less than a total number of rows of data in the original matrix. A one-dimensional partial fast Fourier transform of each block in a row of blocks is computed. A result of the computations is stored in a resultant matrix having rows and columns. The resultant matrix is transposed to a transposed matrix having rows and columns. While transposing the resultant matrix, one-dimensional partial fast Fourier transforms of each block of subsequent rows of blocks are simultaneously computed, one row of blocks at a time, until one-dimensional partial fast Fourier transforms are computed for each block.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.