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
NM
2M-1 | |
2M |
NMlog2N
MNM | |
2 |
log2N
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
x
We suppose the 2-D DFT is defined
X(k1,k2)=
N1-1 | |
\sum | |
n1=0 |
N2-1 | |
\sum | |
n2=0 |
x[n1,n2] ⋅
k1n1 | |
W | |
N1 |
k2n2 | |
W | |
N2 |
,
k1=0,...,N1-1
k2=0,...,N2-1
x[n1,n2]
N1 x N2
WN=\exp(-j2\pi/N)
For simplicity, let us assume that
N1=N2=N
(r x r)
N/r
Using the change of variables:
ni=rpi+qi
pi=0,\ldots,(N/r)-1;qi=0,\ldots,r-1;
ki=ui+viN/r
ui=0,\ldots,(N/r)-1;vi=0,\ldots,r-1;
i=1
2
X(u1+v1N/r,u2+v2
r-1 | |
N/r)=\sum | |
q1=0 |
r-1 | |
\sum | |
q2=0 |
\left[
N/r-1 | |
\sum | |
p1=0 |
N/r-1 | |
\sum | |
p2=0 |
x[rp1+q1,rp2+q2]
p1u1 | |
W | |
N/r |
p2u2 | |
W | |
N/r |
\right] ⋅
q1u1+q2u2 | |
W | |
N |
q1v1 | |
W | |
r |
q2v2 | |
W | |
r |
,
The equation above defines the basic structure of the 2-D DIT radix-
(r x r)
When
r=2
X(k1,k2)=S00(k1,k2)+S01(k1,k2)
k2 | |
W | |
N |
+S10(k1,k2)
k1 | |
W | |
N |
+S11(k1,k2)
k1+k2 | |
W | |
N |
0\leqk1,k2<
N | |
2 |
where
Sij(k1,k2)=\sum
N/2-1 | |
n1=0 |
N/2-1 | |
\sum | |
n2=0 |
x[2n1+i,2n2+j] ⋅
n1k1 | |
W | |
N/2 |
n2k2 | |
W | |
N/2 |
The
Sij
N/2
S00
x
n1
n2
S01
n1
n2
S10
n1
n2
S11
n1
n2
Thanks to the periodicity of the complex exponential, we can obtain the following additional identities, valid for
0\leqk1,k2<
N | |
2 |
Xl(k | ||||
|
,k2r)=S00(k1,k2)+S01(k1,k2)
k2 | |
W | |
N |
-S10(k1,k2)
k1 | |
W | |
N |
-S11(k1,k2)
k1+k2 | |
W | |
N |
Xl(k1,k
|
r)=S00(k1,k2)-S01(k1,k2)
k2 | |
W | |
N |
+S10(k1,k2)
k1 | |
W | |
N |
-S11(k1,k2)
k1+k2 | |
W | |
N |
Xl(k | ||||
|
,k | ||||
|
r)=S00(k1,k2)-S01(k1,k2)
k2 | |
W | |
N |
-S10(k1,k2)
k1 | |
W | |
N |
+S11(k1,k2)
k1+k2 | |
W | |
N |
Similarly, a decimation-in-frequency (DIF, also called the Sande–Tukey algorithm) algorithm means the decomposition is based on frequency domain
X
Using the change of variables:
ni=pi+qiN/r
pi=0,\ldots,(N/r)-1;qi=0,\ldots,r-1;
ki=rui+vi
ui=0,\ldots,(N/r)-1;vi=0,\ldots,r-1;
i=1
2
X(ru1+v1,ru2+v2)=\sum
N/r-1 | |
p1=0 |
N/r-1 | |
\sum | |
p2=0 |
\left[
r-1 | |
\sum | |
q1=0 |
r-1 | |
\sum | |
q2=0 |
x[p1+q1N/r,p2+q2N/r]
q1v1 | |
W | |
r |
q2v2 | |
W | |
r |
\right] ⋅
p1v1+p2v2 | |
W | |
N |
p1u1 | |
W | |
N/r |
p2u2 | |
W | |
N/r |
,
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
k1,k2
\begin{array}{lcl} X(2k1,2k2)&:&even-even\\ X(2k1,2k2+1)&:&even-odd\\ X(2k1+1,2k2)&:&odd-even\\ X(2k1+1,2k2+1)&:&odd-odd \end{array}
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:
\begin{array}{lcl} X(2k1,2k2)&:&even-even\\ X(2k1,2k2+1)&:&even-odd\\ X(2k1+1,2k2)&:&odd-even\\ X(4k1+1,4k2+1)&:&odd-odd\\ X(4k1+1,4k2+3)&:&odd-odd\\ X(4k1+3,4k2+1)&:&odd-odd\\ X(4k1+3,4k2+3)&:&odd-odd\end{array}
That means the fourth term in 2-D DIT radix-
(2 x 2)
S11(k1,k2)
k1+k2 | |
W | |
N |
A11(k1,k2)
k1+k2 | |
W | |
N |
+A13(k1,k2)
k1+3k2 | |
W | |
N |
+A31(k1,k2)
3k1+k2 | |
W | |
N |
+A33(k1,k2)
3(k1+k2) | |
W | |
N |
,
where
Aij(k1,k2)=\sum
N/4-1 | |
n1=0 |
N/4-1 | |
\sum | |
n2=0 |
x[4n1+i,4n2+j] ⋅
n1k1 | |
W | |
N/4 |
n2k2 | |
W | |
N/4 |
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
1024 x 1024