Vector-radix FFT algorithm
Multidimensional fast Fourier transform algorithm From Wikipedia, the free encyclopedia
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. For example, for a 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]
2-D DIT case
Summarize
Perspective
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 ,and , and is an matrix, and .
For simplicity, let us assume that , and the radix- is such that is an integer.
Using the change of variables:
- , where
- , where
where or , then the two dimensional DFT can be written as:[6]

The equation above defines the basic structure of the 2-D DIT radix- "butterfly". (See 1-D "butterfly" in Cooley–Tukey FFT algorithm)
When , the equation can be broken into four summations, and this leads to:[1]
- for ,
where .
The can be viewed as the -dimensional DFT, each over a subset of the original sample:
- is the DFT over those samples of for which both and are even;
- is the DFT over the samples for which is even and is odd;
- is the DFT over the samples for which is odd and is even;
- is the DFT over the samples for which both and are odd.
Thanks to the periodicity of the complex exponential, we can obtain the following additional identities, valid for :
- ;
- ;
- .
2-D DIF case
Summarize
Perspective
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.
Using the change of variables:
- , where
- , where
where or , and the DFT equation can be written as:[6]
Other approaches
Summarize
Perspective
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- equation, becomes:[8]
where
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.[7]
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.