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.
[1] 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,[2] 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,[3] which is the general vector-radix algorithm.
Vector-radix FFT algorithm can reduce the number of complex multiplications significantly, compared to row-vector algorithm.
element matrix (M dimensions, and size N on each dimension), the number of complex multiples of vector-radix FFT algorithm for radix-2 is
, meanwhile, for row-column algorithm, it is
And generally, even larger savings in multiplies are obtained when this algorithm is operated on larger radices and on higher dimensional arrays.
[3] 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,[4] and high speed FFT processor designing.
[5] As with the Cooley–Tukey FFT algorithm, the two dimensional vector-radix FFT is derived by decomposing the regular 2-D DFT into sums of smaller DFT's multiplied by "twiddle" factors.
A decimation-in-time (DIT) algorithm means the decomposition is based on time domain
, see more in Cooley–Tukey FFT algorithm.
We suppose the 2-D DFT is defined where
= exp ( − j 2 π
For simplicity, let us assume that
, then the two dimensional DFT can be written as:[6] The equation above defines the basic structure of the 2-D DIT radix-
(See 1-D "butterfly" in Cooley–Tukey FFT algorithm) When
, the equation can be broken into four summations, and this leads to:[1] where
-dimensional DFT, each over a subset of the original sample: Thanks to the periodicity of the complex exponential, we can obtain the following additional identities, valid for
: Similarly, a decimation-in-frequency (DIF, also called the Sande–Tukey algorithm) algorithm means the decomposition is based on frequency domain
, see more in Cooley–Tukey FFT algorithm.
, and the DFT equation can be written as:[6] 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.
[6][7] In conventional 2-D vector-radix algorithm, we decompose the indices
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-
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
array, compared with the vector-radix algorithm.
