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