Basis-vector-decomposition based two-stage computational algorithms for DFT and DHT

Discrete Fourier transform (DFT)/discrete Hartley transform (DHT) algorithms based on the basis-vector decomposition of the corresponding transform matrices are derived. The computations of DFT are divided into two stages: an add/subtract preprocessing and a block-diagonal postprocessing. Both stages can be computed effectively. It can be proved that the computational complexity of the proposed DFT algorithm is identical to that of the most popular split-radix FFT, yet requires real number arithmetics only. Generation and storage of the real multiplicative coefficients are easier than that in conventional FFTs. Connections of the proposed approach with several well-known DFT algorithms are included. Furthermore, many variations of the proposed algorithm are also pointed out.>