A connection between bit reversal and matrix transposition: hardware and software consequences

A simple connection between bit reversal and matrix transposition is explained in the context of two-dimensional fast Fourier transform (FFT). This connection is then shown to be useful for hardware and software implementations of two-dimensional FFTs based on the row-column algorithm: the bit-reversal operations involved in the row and column one-dimensional transforms of length M can merge with the matrix transposition in between, to form a single bit reversal of length N=M/sup 2/, which is more efficient than considering these operations separately. Furthermore, this connection is also the base of new bit-reversal algorithms that are explained. The first one can be implemented in two different versions, depending on the availability of an auxiliary memory of size square root N. One of these versions turns out to be as fast as a recently proposed algorithm by D.M. Evans (1987), while the second is twice as fast as the usual one. The second algorithm is a divide-and-conquer approach to the problem that allows easy parallelization.>