On computing the discrete Fourier transform of a linear phase sequence

Efficient fast Fourier transform (FFT) algorithms to compute the forward and inverse discrete Fourier transforms (DFT) of a sequence with linear-phase characteristic are examined. These reduce the computational requirements as regards a complex FFT by large factors and should be used whenever applicable. The case when the DFT coefficients are real-valued leads to further reductions in computational requirements. Though the redundancy in the linear-phase situation is exactly 50%, the computational requirements and implementation are quite different from the real-valued FFT which uses a similar symmetry relation. The code for such implementations can be easily written by simple restructuring of a complex FFT algorithm