An improved bit-reversal algorithm for the fast Fourier transform
Jeffrey J. Rodrı́guez · 2003
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.>