Title :
An efficient FFT algorithm based on the radix-2/4 DIF approach for computing 3D DFT
Author :
Bouguezel, Saad ; Ahmad, M. Omair ; Swamy, M.N.S.
Author_Institution :
Dept. of Electr. & Comput. Eng., Concordia Univ., Montreal, Que., Canada
Abstract :
We propose a 3D split vector-radix decimation-in-frequency (DIF) FFT algorithm for computing the 3D DFT, based on a mixture of radix-(2×2×2) and radix-(4×4×4) index maps. It is shown that the proposed algorithm reduces the computational complexity significantly in comparison to the existing 3D vector radix FFT algorithms as well as algorithms that are based on row-column decomposition. In addition, since the proposed algorithm is expressed in a simple matrix form using the Kronecker product, it facilitates easy software or hardware implementation of the algorithm.
Keywords :
computational complexity; digital arithmetic; discrete Fourier transforms; matrix decomposition; multidimensional signal processing; 3D DFT; 3D signal processing; FFT algorithm; Kronecker product; computational complexity; decimation-in-frequency approach; index maps; matrix form; row-column decomposition; split vector-radix algorithm; Computational complexity; Computer vision; Discrete Fourier transforms; HDTV; Hydrogen; Matrix decomposition; Signal analysis; Software algorithms; TV; Telephony;
Conference_Titel :
Electrical and Computer Engineering, 2004. Canadian Conference on
Print_ISBN :
0-7803-8253-6
DOI :
10.1109/CCECE.2004.1345319