Patent ID: 6732058
Filing Date: 2004-05-04
Classification: G06F

Abstract:
A method of performing a radix-M FFT (Fast Fourier Transform), wherein M is an integer satisfying M&gE;2, the method comprising:sampling a signal, containing tones, with a sampling frequency, fs, to produce N time domain samples each initializing a respective one of N data points, wherein N is an integer; and to produce frequency domain samples having a frequency bandwidth &Dgr;f=fs/N and center frequencies of frequency spacing Mw&Dgr;f with w being an integer satisfying w&gE;1: performing, for each one of k stages wherein k=logM(N), radix-M computations upon a respective subset of the N data points, wherein the respective subset contains only data points upon which the frequency domain samples that contain the tones are dependent; wherein the sampling frequency, fs, is such that the frequency domain samples contain the tones.