Methods and apparatus for performing reduced complexity discrete fourier transforms using interpolation
US8015226B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Sep 21, 2007 |
| Grant date | Sep 6, 2011 |
| Priority date | — |
| Expiry date | Jul 6, 2030 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F17/141
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Methods and apparatus are provided for performing reduced complexity discrete Fourier transforms using interpolation An input sequence of length N is transformed by extending the input sequence to an extended input sequence of length M, where M is greater than N (a power of two greater than N); performing a discrete Fourier Transform (DFT), such as a power-of-two DFT, on the extended input sequence to obtain an interpolated sequence; and applying a conversion matrix to the interpolated sequence to obtain a DFT output for the input sequence of length N. The input sequence of length N can be extended to an extended input sequence of length M, for example, by employing a zero padding technique, a cyclic extension technique, a windowing of a cyclic extended sequence technique or a resampling-based interpolation technique to extend the input sequence. The conversion matrix is substantially a sparse matrix.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.