Generalized and Partial FFT

Todor COOKLEV  Akinori NISHIHARA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E77-A   No.9   pp.1466-1474
Publication Date: 1994/09/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Papers Selected from the 8th Digital Signal Processing Symposium)
Category: Orthogonal Transform
Keyword: 
fast Fourier transforms,  orthogonal transforms,  digital signal processing,  

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




Summary: 
The relation between computing part of the FFT spectrum and the so-called generalized FFT (GFFT) is clarified, leading to a new algorithm for performing partial FFTs. The method can be applied when only part of the output is required or when the input data sequence contains many zeros. Such cases arize for example in decimation and interpolation and also in computing linear convolutions. The technique consists of decomposing the DFT into several generalized DFTs. Efficient algorithms for these generalized DFTs exist. The computational complexity of the new approach is roughly equal to the complexity of previous techniques, but the structure is superior, because only one type of butterfly is used and a few lines of code are sufficient. The theoretical properties of the GDFT are given. The case of multidimensional signals, defined on arbitrary sampling lattices is also considered.