A unified approach to FAST computation of discrete sinusoidal transforms II: DFT and DWT transforms

Abstract

Discrete Fourier transforms (DFT), discrete Hartley transform (DHT), and various types of discrete W transform (DWT) are also members of discrete sinusoidal transform family. A unified approach to the fast computation of the DFT and DWT transforms for real data sequences is presented. It takes advantage of the regular universal DCT-II/DST-II/DST-III computational structure in existing real sparse matrix factorizations leading to simple, numerically stable, in  place and efficient algorithms for any N = 2m, m > 0. The computational complexity of all algorithms both in the sense of the number of arithmetic operations and structural simplicity is better or identical compared with the best known algorithms. The proposed generalized signal flow graphs are regular and confirm the importance of the universal DC-/II/DST-II (DCT/III/DST-III) computational structure for its implementation on one VLSI chip.