New radix-(2×2×2)/(4×4×4) and radix-(2×2×2)/(8×8×8) DIF FFT algorithms for 3-D DFT

In this paper, new three-dimensional (3-D) radix-(2×2×2)/(4×4×4) and radix-(2×2×2)/(8×8×8) decimation-in-frequency (DIF) fast Fourier transform (FFT) algorithms are developed and their implementation schemes discussed. The algorithms are developed by introducing the radix-2/4 and radix-2/8 approaches in the computation of the 3-D DFT using the Kronecker product and appropriate index mappings. The butterflies of the proposed algorithms are characterized by simple closed-form expressions facilitating easy software or hardware implementations of the algorithms. Comparisons between the proposed algorithms and the existing 3-D radix-(2×2×2) FFT algorithm are carried out showing that significant savings in terms of the number of arithmetic operations, data transfers, and twiddle factor evaluations or accesses to the lookup table can be achieved using the radix-(2×2×2)/(4×4×4) DIF FFT algorithm over the radix-(2×2×2) FFT algorithm. It is also established that further savings can be achieved by using the radix-(2×2×2)/(8×8×8) DIF FFT algorithm.