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

Discrete Fourier transform (DFT), discrete Hartley transform (DHT), and var ious types of discrete W transform (DWT) are also members of discrete sinus oidal transform family. A unified approach to the fast computation of the D FT and DWT transforms for real data sequences is presented. It takes advant age of the regular universal DCT-II/DST-II and DCT-II/DST-III compatational structure in existing real sparse matrix factorizations leading to simple, numerically stable; in place and efficient algorithms for any N = 2(m), m > 0. The computational complexity of all algorithms both in the sense of th e number of arithmetic operations and structural simplicity is better or id entical compared with the best known algorithms. The proposed generalized s ignal flow graphs are regular and confirm the importance of the universal D CT-II/DST-II (DCT-III/DST-III) computational structure for its implementati on on one VLSI chip.