Symmetric FFTs

Abstract:

In this paper, we examine the FFT of sequences ${x_n} = {x_{N + n}}$ with period N that satisfy certain symmetric relations. It is known that one can take advantage of these relations in order to reduce the computing time required by the FFT. For example, the time required for the FFT of a real sequence is about half that required for the FFT of a complex sequence. Also, the time required for the FFT of a real even sequence ${x_n} = {x_{N - n}}$ requires about half that required for a real sequence. We first define a class of five symmetries that are shown to be "closed" in the sense that if ${x_n}$ has any one of the symmetries, then no additional symmetries are generated in the course of the FFT. Symmetric FFTs are developed that take advantage of these intermediate symmetries. They do not require the traditional pre- and postprocessing associated with symmetric FFTs and, as a consequence, they are somewhat more efficient and general than existing symmetric FFTs.