A new multidimensional FFT based on one-dimensional decompositions

Author

Bernardini, R.

Author_Institution

Sezione Staccata Agli Esposti, Padova, Italy

Volume

47

Issue

10

fYear

2000

fDate

10/1/2000 12:00:00 AM

Firstpage

1123

Lastpage

1126

Abstract

This work proposes an original multidimensional fast Fourier transform (FFT) algorithm where the computation is first organized into multiplier-free butterflies and then completed by 1-D FFTs. The properties of well-known 1-D FFT algorithms blend in quite nicely with those of the proposed multidimensional FFT scheme, extending their computational and structural characteristics to it. Strong points of the proposed method are that its total computational cost decreases as the signal space dimensions increase and that its efficiency is superior to that of any other multidimensional FFT algorithm

Keywords

computational complexity; fast Fourier transforms; multidimensional signal processing; computational characteristics; multidimensional FFT; multiplier-free butterflies; one-dimensional decompositions; signal space dimensions; structural characteristics; total computational cost; Algorithm design and analysis; Arithmetic; Computational efficiency; Discrete Fourier transforms; Fast Fourier transforms; Flexible printed circuits; Lattices; Multidimensional systems; Polynomials; Signal processing algorithms;

fLanguage

English

Journal_Title

Circuits and Systems II: Analog and Digital Signal Processing, IEEE Transactions on

Publisher

ieee

ISSN

1057-7130

Type

jour

DOI

10.1109/82.877157

Filename

877157