An efficient FFT algorithm based on the discrete sine transform

The authors earlier developed a fast recursive algorithm for the discrete sine transform (see IEEE Trans. Acoust. Speech Signal Process., vol.38, no.3, p.553-7, 1990). This algorithm is used as the basic building block for developing the real valued fast Fourier transform (FFT). It is assumed that the input sequence is real and of length N, an integer power of 2. The N-point discrete Fourier transform (DFT) of a real sequence can be implemented via the real (cos DFT) and imaginary (sin DFT) components. The N-point cos DFT in turn can be developed from N/2-point cos DFT and N/4-point discrete sine transform (DST). Similarly, the N-point sin DFT can be developed from N2-point sin DFT and N/4-point DST. Using this approach, an efficient algorithm (involving real arithmetic only) for N-point DFT is developed.>