For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Generalized Treatment of the DIT and the DIF Algorithms Using Recursive Polynomial Factorization
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1996/08/25
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)>>
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.