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

A system for transforming an input sequence of length N, comprising:

• a memory;
• and
• at least one processor, coupled to the memory, operative to:
• extend said input sequence to an extended input sequence of length M, where M is greater than N;
• perform a discrete Fourier Transform (DFT) on said extended input sequence to obtain an interpolated sequence;
• and
• apply a conversion matrix to said interpolated sequence to obtain a DFT output for said input sequence of length N.

A circuit for transforming an input sequence of length N, comprising:

• a first logic block for extending said input sequence to an extended input sequence of length M, where M is greater than N;
• a second logic block for performing a discrete Fourier Transform (DFT) on said extended input sequence to obtain an interpolated sequence;
• and
• a third logic block for applying a conversion matrix to said interpolated sequence to obtain a DFT output for said input sequence of length N.

An article of manufacture for transforming an input sequence of length N, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

• extending said input sequence to an extended input sequence of length M, where M is greater than N;
• performing a discrete Fourier Transform (DFT) on said extended input sequence to obtain an interpolated sequence;
• and
• applying a conversion matrix to said interpolated sequence to obtain a DFT output for said input sequence of length N.