ABSTRACT
The term Fast Fourier Transform (FFT) is used to describe a computer algorithm that reduces the amount of computer time enormously. The chapter examines in detail the first component of the FFT, bit reversal reordering of the initial data. It describes some methods of performing the bit reversal permutation. These methods are Oscar Buneman's algorithm, and another, faster, algorithm. The chapter shows how to compute some real FFTs simultaneously by performing one complex FFT. The time-saving device will be used to reduce the amount of calculation needed to perform an FFT of real data by about one half. The FFT is one of the greatest contributions to numerical analysis made in the century. Buneman's algorithm is the simplest method for performing the bit reversal permutation. It is based on a simple pattern. While Buneman's method is simple and relatively fast, the algorithm programmed in BITREV runs faster by a considerable percentage.
