Methods and apparatus for performing reduced complexity discrete fourier transforms using interpolation
View Patent ↗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.
1. A method for transforming an input sequence of length N, comprising:
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, wherein one or more of said extending, performing and applying steps are performed by a hardware device.
2. The method of claim 1 , wherein M is a power of two greater than N.
3. The method of claim 1 , wherein said extending step further comprises the step of employing a zero padding technique to extend said input sequence.
4. The method of claim 1 , wherein said extending step further comprises the step of employing a cyclic extension technique to extend said input sequence.
5. The method of claim 1 , wherein said extending step further comprises the step of employing a windowing of a cyclic extended sequence technique to extend said input sequence.
6. The method of claim 1 , wherein said extending step further comprises the step of employing a resample-based interpolation technique to extend said input sequence.
7. The method of claim 1 , wherein said conversion matrix is substantially a sparse matrix.
8. 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.
9. The system of claim 8 , wherein M is a power of two greater than N.
10. The system of claim 8 , wherein said input sequence is extended by employing a zero padding technique to extend said input sequence.
11. The system of claim 8 , wherein said input sequence is extended by employing a cyclic extension technique to extend said input sequence.
12. The system of claim 8 , wherein said input sequence is extended by employing a windowing of a cyclic extended sequence technique to extend said input sequence.
13. The system of claim 8 , wherein said conversion matrix is substantially a sparse matrix.
14. 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.
15. The circuit of claim 14 , wherein M is a power of two greater than N.
16. The circuit of claim 14 , wherein said input sequence is extended by employing a zero padding technique to extend said input sequence.
17. The circuit of claim 14 , wherein said input sequence is extended by employing a cyclic extension technique to extend said input sequence.
18. The circuit of claim 14 , wherein said input sequence is extended by employing a windowing of a cyclic extended sequence technique to extend said input sequence.
19. The circuit of claim 14 , wherein said conversion matrix is substantially a sparse matrix.
20. 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.