COFDM, the modulation method used by most terrestrial DTV standards, depends on implementation of the Fast Fourier Transform (FFT) for demodulating the thousands of carriers used in OFDM system. An announcement Wednesday of The faster-than-fast Fourier transform raises the possibility of more powerful and more efficient OFDM modulation methods, although its application to current OFDM demodulation isn't clear. (The fast-Fourier-transform (FFT) provides a technique for deconstructing a complex waveform into its component sine wave frequencies of different amplitude.)
The new algorithm relies on two key ideas. The first is to divide a signal into narrower slices of bandwidth, sized so that a slice will generally contain only one frequency with a heavy weight. The problem, however, is that filters don't have distinct boundaries--signals near the limits of a filter's pass band will be attenuated, complicating measurement of the weight of signals in this region. The researchers came up with a computationally efficient way to combine filters so they overlap, ensuring no frequencies inside the target range are unduly attenuated but boundaries between slices of spectrum are still fairly sharp.
The next step is identifying the most heavily weighted frequency in a specific slice. Researchers were able to do this by repeatedly cutting the slice of spectrum into smaller pieces, keeping only those in which most of the signal power is concentrated. To do this efficiently, they power on a signal processing strategy from 4G cellular networks. By sampling the same slice of bandwidth at different times, the researchers can determine where the dominant frequency is in its "oscillatory cycle."
The MIT researchers will present the new algorithm at the Association for Computing Machinery's Symposium on Discrete Algorithms (SODA). They claim that it improves FFT technology in a wide range of important applications. In some circumstances, the up to a ten times improvement in speed can be achieved.
The article said the new algorithm should be particularly useful for image compression. Two University of Michigan researchers--Anne Gilbert and Martin Strauss--previously proposed an algorithm that improved on the FFT for very sparse signals.
"Some of the previous work, including my own with Anna Gilbert and so on, would improve upon the fast Fourier transform algorithm, but only if the 'sparsity k'--the number of heavily weighted frequencies--"was considerably smaller than the input size 'n,'" said Strauss. He observed that the MIT researchers' algorithm "greatly expands the number of circumstances where one can beat the traditional FFT."
A short abstract of the paper is available in Nearly Optimal Sparse Fourier Transform by Haitham Hassanish, Piotr Indyk, Dina Katabi, and Eric Price.
