Computationally efficient methods for analysis and synthesis of real signals using FFT and IFFT

摘要

The discrete Fourier transform (DFT) and the inverse discrete Fourier transform (IDFT) are used in a wide variety of signal processing applications. Even with the increased speed of modern processors, there is an ongoing need to further develop more efficient methods for computing DFT and IDFT, with a particular effort to reduce the number of complex multiplications. The properties of certain complex sequences are extraordinarily useful in the sense that they lead to data manipulation schemes that result in the sequences to which traditional but much shorter fast Fourier transform (FFT) algorithms may be applied. This is achieved by exploiting a certain regularity in the complex data. The index-reversed complex conjugate sequence and the mirror symmetric complex conjugate sequence were defined. A significant reduction in the number of complex computations is achieved if a sequence in either domain exhibits such symmetry.