The fast generalized discrete Fourier transforms: A unified approach to the discrete sinusoidal transforms computation

Special forms of the generalized discrete Fourier transform (GDFT) matrices are investigated and their sparse matrix factorizations are presented to c omplete Wang's set of real sparse matrix factorizations for the family of d iscrete sinusoidal transforms. Different versions of the GDFT, different ve rsions of the generalized discrete Hartley transform (GDHT) or equivalently of the discrete W transform (DWT), various versions of the discrete cosine transform (DCT) and discrete sine transform (DST) are members of the discr ete sinusoidal transform family. There are intrinsic relationships among co rresponding versions of the GDFT, GDHT (DWT), DCT and DST for real data seq uences. A real sparse matrix factorization of GDFT matrices leads to simple fast algorithms for their computation, where only real arithmetic is invol ved, The resulting generalized signal flow graphs for the computation of di fferent versions of the GDFT represent simple and compact unified approach to the fast discrete sinusoidal transforms computation. It is also shown th at all algorithms are based on the universal DCT-II/DST-II (DCT-III/DST-III ) computational structure which is used as the basic processing component. (C) 1999 Elsevier Science B.V. All rights reserved.