Title :
An improved bit-reversal algorithm for the fast Fourier transform
Author :
Rodríguez, Jeffrey J.
Author_Institution :
Dept. of Electr. Eng., Texas Univ., Austin, TX, USA
Abstract :
The recording effect of the fast Fourier transform is considered which requires that the elements of the data array be permuted by bit-reversing the array index. The bit-reversal algorithm given by B. Gold and C.M. Rader (1969) is referred to. Several improvements are made to this algorithm that result in improved efficiency. A closed-form expression is derived for the largest index that must be bit-reversed. A computational analysis is given, comparing the original and modified algorithms
Keywords :
fast Fourier transforms; array index; bit-reversal algorithm; closed-form expression; computational analysis; data array; fast Fourier transform; recording effect; Algorithm design and analysis; Closed-form solution; Computer aided instruction; Data flow computing; Fast Fourier transforms; Flow graphs; Gold; Iterative algorithms; Upper bound; Writing;
Conference_Titel :
Acoustics, Speech, and Signal Processing, 1988. ICASSP-88., 1988 International Conference on
Conference_Location :
New York, NY
DOI :
10.1109/ICASSP.1988.196862
