Generalized and Partial FFT
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E77-A No.9 pp.1466-1474
- Publication Date
- 1994/09/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section of Papers Selected from the 8th Digital Signal Processing Symposium)
- Category
- Orthogonal Transform
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Todor COOKLEV, Akinori NISHIHARA, "Generalized and Partial FFT" in IEICE TRANSACTIONS on Fundamentals,
vol. E77-A, no. 9, pp. 1466-1474, September 1994, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e77-a_9_1466/_p
Copy
@ARTICLE{e77-a_9_1466,
author={Todor COOKLEV, Akinori NISHIHARA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Generalized and Partial FFT},
year={1994},
volume={E77-A},
number={9},
pages={1466-1474},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={September},}
Copy
TY - JOUR
TI - Generalized and Partial FFT
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1466
EP - 1474
AU - Todor COOKLEV
AU - Akinori NISHIHARA
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E77-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 1994
AB - 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.
ER -
English
