FAST GENERALIZED DFT AND DHT ALGORITHMS

This paper presents fast algorithms for complex and real generalized d iscrete Fourier transform (GDFT). It shows that the length-N GDFT can be computed by a split-radix algorithm of discrete Fourier transform ( DFT) whose input and output sequences are rotated by twiddle factors. It also reveals that the odd-time, odd-frequency and odd-squared DFTs are closely related to the discrete cosine transform (DCT). Compared w ith recently reported split-radix GDFT algorithm, the proposed one pro vides a simpler computational structure and significant savings on the number of arithmetic operations. (C) 1998 Elsevier Science B.V. All r ights reserved.