Fast Fourier Transform and Fast Bit Reversal Algorithms

Dr. Anne C. Elster
Department of Computer Science
UT Austin

Wednesday, November 10th, 5:00 PM, ENS 602

elster@cs.utexas.edu

Abstract

The Fast Fourier Transform (FFT) is probably the most important algorithm of our time given its wide impact which spans fields ranging from image and signal processing to fields using it in solving partial differential equations. Cooley and Tukey's implementation, published in the mid 1960's, is consequently the most referenced computational article to date. In this talk the speaker will describe the core ideas behind the FFT algorithms, including the newer FFTW algorithms from MIT, as well as discuss the FFT's ongoing impact on modern technologies such as ADSL (Asymmetric Digital Subscriber Line). This talk will also cover highlights of bit-reversal (or, more accurately, shuffle) algorithms which are an essential part of the FFT. The fastest known bit-reversal algorithm to date has been the one proposed by the speaker in 1987. This is a recursive algorithm that was in the 1996 survey paper by Karp shown clearly superior in terms of execution time compared to later algorithms. Recently, the speaker collaborated with Prof. R. Strandh of the Univ. of Bordeaux, France, in developing a new and improved bit-reversal algorithm that generates a bit-reversed sequence of N numbers in less than 5N cycles.

A list of Telecommunications and Signal Processing Seminars is available at from the ECE department Web pages under "Seminars". The Web address for the Telecommunications and Signal Processing Seminars is http://anchovy.ece.utexas.edu/seminars