A unified approach to FAST computation of discrete sinusoidal transforms I: DCT and DST transforms

Abstract

A unified approach to the fast computation of orthogonal discrete sinusoidal transforms for real data sequences is presented. Various types of discrete sinusoidal transforms (DCT) and discrete sine transform (DST are members of discrete sinusoidal transform family. The unified approach  takes advantage of a regular universal computational structure both for the DCT/DST type II (DCT-II(DST-II) and type III (DCT-III/DST-III) computation 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.