A Generalized Treatment of the DIT and the DIF Algorithms Using Recursive Polynomial Factorization


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.8   pp.1243-1245
Publication Date: 1996/08/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Digital Signal Processing)
the discrete Fourier transform,  fast algorithm,  orthogonal expansion,  

Full Text: PDF(208KB)>>
Buy this Article

THe decimation-in-time (DIT) and the decimation-in-frequency (DIF) algorithms are the most well-known fast algorithms for computing the discrete Fourier transform(DFT). These algorithms constitute the basis of the fast Fourier transform (FFT) implementations, including the pipeline implementation and other parallel configurations. This paper derives an alternative generalization of the algorithms which applies for sequences whose lengths are not a power of two. The treatment is consistent with the radix-two DIF and DIT algorithms, and the generalization is useful for utilizing the accumulated technologies of the FFT algorithm for such sequences.