A split-radix algorithm for 2-D DFT

In this paper, the split-radix approach for computing the one-dimensional (1-D) discrete Fourier transform (DFT) is extended for the vector-radix fast Fourier transform (FFT) to compute the two-dimensional (2-D) DFT of size 2(r₁)×2(r₂), using a radix-2×2 index map and a radix-8×8 map instead of a radix-2×2 index map and a radix-4×4 map as is done in the classical split vector radix FFT algorithms. Since a radix-8×8 index map and a method for combining the twiddle factors are used, the new algorithm provides significant savings compared to the 2-D FFT algorithms previously reported in terms of the arithmetic complexity, data transfer, index generation and twiddle factor evaluation or access to the lookup table. In addition, since the algorithm is expressed in a simple matrix form using the Kronecker product, it facilitates an easy implementation of the algorithm, and allows for an extension to the multidimensional case.