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

A unified approach to the fast computation of orthogonal discrete si nusoid al transforms for real data sequences is presented. Various types of discre te cosine transform (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 rea l sparse matrix factorizations leading to simple, numerically stable, in pl ace and efficient algorithms for any N = 2(m), > 0. The computational compl exity of all algorithms both in the sense of the number of arithmetic opera tions and structural simplicity is better or identical compared with the be st known algorithms. The proposed generalized signal flow graphs are regula r and confirm the importance of the universal DCT-II/DST-II (DCT-III/DST-II I) computational structure for its implementation on one VLSI chip.