Vector-radix FFT algorithm

The vector-radix FFT algorithm, is a multidimensional fast Fourier transform (FFT) algorithm, which is a generalization of the ordinary Cooley–Tukey FFT algorithm that divides the transform dimensions by arbitrary radices. It breaks a multidimensional (MD) discrete Fourier transform (DFT) down into successively smaller MD DFTs until, ultimately, only trivial MD DFTs need to be evaluated.
The most common multidimensional FFT algorithm is the row-column algorithm, which means transforming the array first in one index and then in the other, see more in FFT. Then a radix-2 direct 2-D FFT has been developed, and it can eliminate 25% of the multiplies as compared to the conventional row-column approach. And this algorithm has been extended to rectangular arrays and arbitrary radices, which is the general vector-radix algorithm.
Vector-radix FFT algorithm can reduce the number of complex multiplications significantly, compared to row-vector algorithm. For example, for a formula_1 element matrix (M dimensions, and size N on each dimension), the number of complex multiples of vector-radix FFT algorithm for radix-2 is formula_2, meanwhile, for row-column algorithm, it is formula_3. And generally, even larger savings in multiplies are obtained when this algorithm is operated on larger radices and on higher dimensional arrays.
Overall, the vector-radix algorithm significantly reduces the structural complexity of the traditional DFT having a better indexing scheme, at the expense of a slight increase in arithmetic operations. So this algorithm is widely used for many applications in engineering, science, and mathematics, for example, implementations in image processing, and high speed FFT processor designing.
2-D DIT case.
As with Cooley–Tukey FFT algorithm, two dimensional vector-radix FFT is derived by decomposing the regular 2-D DFT into sums of smaller DFT's multiplied by "twiddle" factor.
A decimation-in-time (DIT) algorithm means the decomposition is based on time domain formula_4, see more in Cooley–Tukey FFT algorithm.
We suppose the 2-D DFT
where formula_6,and formula_7, and formula_8 is a formula_9 matrix, and formula_10.
For simplicity, let us assume that formula_11, and radix-formula_12(formula_13 are integers).
Using the change of variables:
where formula_18 or formula_19, then the two dimensional DFT can be written as:
The equation above defines the basic structure of the 2-D DIT radix-formula_12 "butterfly". (See 1-D "butterfly" in Cooley–Tukey FFT algorithm)
When formula_22, the equation can be broken into four summations: one over those samples of x for which both formula_23 and formula_24 are even, one for which formula_23 is even and formula_24 is odd, one of which formula_23 is odd and formula_24 is even, and one for which both formula_23 and formula_24 are odd, and this leads to:
where formula_32
2-D DIF case.
Similarly, a decimation-in-frequency (DIF, also called the Sande–Tukey algorithm) algorithm means the decomposition is based on frequency domain formula_33, see more in Cooley–Tukey FFT algorithm.
Using the change of variables:
where formula_18 or formula_19, and the DFT equation can be written as:
Other approaches.
The split-radix FFT algorithm has been proved to be a useful method for 1-D DFT. And this method has been applied to the vector-radix FFT to obtain a split vector-radix FFT.
In conventional 2-D vector-radix algorithm, we decompose the indices formula_41 into 4 groups:
By the split vector-radix algorithm, the first three groups remain unchanged, the fourth odd-odd group is further decomposed into another four sub-groups, and seven groups in total:
That means the fourth term in 2-D DIT radix-formula_44 equation, formula_45 becomes:
where formula_47
The 2-D N by N DFT is then obtained by successive use of the above decomposition, up to the last stage.
It has been shown that the split vector radix algorithm has saved about 30% of the complex multiplications and about the same number of the complex additions for typical formula_48 array, compared with the vector-radix algorithm.