Further Symmetries of in-Place FFTs
William L. Briggs · SIAM Journal on Scientific and Statistical Computing · 1987
It has long been known that an in-place version of the Fast Fourier Transform (FFT) exists for real sequences of data. More recently, in-place FFTs have been devised for real sequences with even, odd, or quarter wave symmetries. All of these symmetric FFTs take the input sequence in scrambled (bit-reversed) order and produce the transform sequence in natural order. For many applications, this is the opposite of what is needed, i.e., one would like to provide the input sequence in natural order. In this paper, an in-place version of the FFT is presented which takes a real sequence in natural order and produces the transform in scrambled order. The algorithm requires half of the operations and storage of the complex algorithms. Analogous in-place algorithms are also given for naturally ordered even, odd, quarter wave even and quarter wave odd sequences.