Methods and apparatus for performing reduced complexity discrete fourier transforms using interpolation

摘要

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.