vector-radix FFT algorithm

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$, see more in Cooley–Tukey FFT algorithm.

We suppose the 2-D DFT is defined

:$X(k\_1,k\_2)\; =\; \backslash sum\_\{n\_1=0\}^\{N\_1-1\}\; \backslash sum\_\{n\_2=0\}^\{N\_2-1\}\; x[n\_1,\; n\_2]\; \backslash cdot\; W\_\{N\_1\}^\{k\_1\; n\_1\}\; W\_\{N\_2\}^\{k\_2\; n\_2\},$

where $k\_1\; =\; 0,\backslash dots,N\_1-1$,and $k\_2\; =\; 0,\backslash dots,N\_2-1$, and $x[n\_1,\; n\_2]$ is an $N\_1\; \backslash times\; N\_2$ matrix, and $W\_N\; =\; \backslash exp(-j\; 2\backslash pi\; /N)$.

For simplicity, let us assume that $N\_1=N\_2=N$, and the radix-$(r\backslash times\; r)$ is such that $N/r$ is an integer.

Using the change of variables:

• $n\_i=rp\_i+q\_i$, where $p\_i=0,\backslash ldots,(N/r)-1;\; q\_i\; =\; 0,\backslash ldots,r-1;$
• $k\_i=u\_i+v\_i\; N/r$, where $u\_i=0,\backslash ldots,(N/r)-1;\; v\_i\; =\; 0,\backslash ldots,r-1;$

where $i\; =\; 1$ or $2$, then the two dimensional DFT can be written as:{{cite journal|last1=Chan|first1=S. C.|last2=Ho|first2=K. L.|title=Split vector-radix fast Fourier transform|journal=IEEE Transactions on Signal Processing|volume=40|issue=8|pages=2029–2039|doi=10.1109/78.150004|bibcode=1992ITSP...40.2029C|year=1992}}

:$X(u\_1+v\_1\; N/r,u\_2+v\_2\; N/r)=\backslash sum\_\{q\_1=0\}^\{r-1\}\; \backslash sum\_\{q\_2=0\}^\{r-1\}\; \backslash left[\; \backslash sum\_\{p\_1=0\}^\{N/r-1\}\; \backslash sum\_\{p\_2=0\}^\{N/r-1\}\; x[rp\_1+q\_1,\; rp\_2+q\_2]\; W\_\{N/r\}^\{p\_1\; u\_1\}\; W\_\{N/r\}^\{p\_2\; u\_2\}\; \backslash right]\; \backslash cdot\; W\_N^\{q\_1\; u\_1+q\_2\; u\_2\}\; W\_r^\{q\_1\; v\_1\}\; W\_r^\{q\_2\; v\_2\},$

File:2x2 radix butterfly diagram.svg

The equation above defines the basic structure of the 2-D DIT radix-$(r\backslash times\; r)$ "butterfly". (See 1-D "butterfly" in Cooley–Tukey FFT algorithm)

When $r=2$, the equation can be broken into four summations, and this leads to:

:$X(k\_1,k\_2)\; =\; S\_\{00\}(k\_1,k\_2)\; +\; S\_\{01\}(k\_1,k\_2)\; W\_N^\{k\_2\}\; +S\_\{10\}(k\_1,k\_2)\; W\_N^\{k\_1\}\; +\; S\_\{11\}(k\_1,k\_2)\; W\_N^\{k\_1+k\_2\}$ for ,

where $S\_\{ij\}(k\_1,k\_2)=\backslash sum\_\{n\_1=0\}^\{N/2-1\}\; \backslash sum\_\{n\_2=0\}^\{N/2-1\}\; x[2\; n\_1\; +\; i,\; 2\; n\_2\; +\; j]\; \backslash cdot\; W\_\{N/2\}^\{n\_1\; k\_1\}\; W\_\{N/2\}^\{n\_2\; k\_2\}$.

The $S\_\{ij\}$ can be viewed as the $N/2$-dimensional DFT, each over a subset of the original sample:

• $S\_\{00\}$ is the DFT over those samples of $x$ for which both $n\_1$ and $n\_2$ are even;
• $S\_\{01\}$ is the DFT over the samples for which $n\_1$ is even and $n\_2$ is odd;
• $S\_\{10\}$ is the DFT over the samples for which $n\_1$ is odd and $n\_2$ is even;
• $S\_\{11\}$ is the DFT over the samples for which both $n\_1$ and $n\_2$ are odd.

Thanks to the periodicity of the complex exponential, we can obtain the following additional identities, valid for :

• $X\backslash biggl(k\_1+\backslash frac\{N\}\{2\},k\_2\backslash biggr)\; =\; S\_\{00\}(k\_1,k\_2)\; +\; S\_\{01\}(k\_1,k\_2)\; W\_N^\{k\_2\}\; -S\_\{10\}(k\_1,k\_2)\; W\_N^\{k\_1\}\; -\; S\_\{11\}(k\_1,k\_2)\; W\_N^\{k\_1+k\_2\}$;
• $X\backslash biggl(k\_1,k\_2+\backslash frac\{N\}\{2\}\backslash biggr)\; =\; S\_\{00\}(k\_1,k\_2)\; -\; S\_\{01\}(k\_1,k\_2)\; W\_N^\{k\_2\}\; +S\_\{10\}(k\_1,k\_2)\; W\_N^\{k\_1\}\; -\; S\_\{11\}(k\_1,k\_2)\; W\_N^\{k\_1+k\_2\}$;
• $X\backslash biggl(k\_1+\backslash frac\{N\}\{2\},k\_2+\backslash frac\{N\}\{2\}\backslash biggr)\; =\; S\_\{00\}(k\_1,k\_2)\; -\; S\_\{01\}(k\_1,k\_2)\; W\_N^\{k\_2\}\; -S\_\{10\}(k\_1,k\_2)\; W\_N^\{k\_1\}\; +\; S\_\{11\}(k\_1,k\_2)\; W\_N^\{k\_1+k\_2\}$.

Similarly, a decimation-in-frequency (DIF, also called the Sande–Tukey algorithm) algorithm means the decomposition is based on frequency domain $X$, see more in Cooley–Tukey FFT algorithm.

Using the change of variables:

• $n\_i=p\_i+q\_i\; N/r$, where $p\_i=0,\backslash ldots,(N/r)-1;\; q\_i\; =\; 0,\backslash ldots,r-1;$
• $k\_i=r\; u\_i+v\_i$, where $u\_i=0,\backslash ldots,(N/r)-1;\; v\_i\; =\; 0,\backslash ldots,r-1;$

where $i\; =\; 1$ or $2$, and the DFT equation can be written as:

:$X(r\; u\_1+v\_1,r\; u\_2+v\_2)=\backslash sum\_\{p\_1=0\}^\{N/r-1\}\; \backslash sum\_\{p\_2=0\}^\{N/r-1\}\; \backslash left[\; \backslash sum\_\{q\_1=0\}^\{r-1\}\; \backslash sum\_\{q\_2=0\}^\{r-1\}\; x[p\_1+q\_1\; N/r,\; p\_2+q\_2\; N/r]\; W\_\{r\}^\{q\_1\; v\_1\}\; W\_\{r\}^\{q\_2\; v\_2\}\; \backslash right]\; \backslash cdot\; W\_\{N\}^\{p\_1\; v\_1+p\_2\; v\_2\}\; W\_\{N/r\}^\{p\_1\; u\_1\}\; W\_\{N/r\}^\{p\_2\; u\_2\},$

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.{{cite book|last1=Pei|first1=Soo-Chang|last2=Wu|first2=Ja-Lin|title=ICASSP '87. IEEE International Conference on Acoustics, Speech, and Signal Processing |chapter=Split vector radix 2D fast Fourier transform |volume=12|date=April 1987|pages=1987–1990|doi=10.1109/ICASSP.1987.1169345|s2cid=118173900 }}

In conventional 2-D vector-radix algorithm, we decompose the indices $k\_1,k\_2$ into 4 groups:

: $$

\begin{array}{lcl}

X(2 k_1, 2 k_2) & : & \text{even-even} \\

X(2 k_1, 2 k_2 +1) & : & \text{even-odd} \\

X(2 k_1 +1, 2 k_2) & : & \text{odd-even} \\

X(2 k_1+1, 2 k_2+1) & : & \text{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(2 k_1, 2 k_2) & : & \text{even-even} \\

X(2 k_1, 2 k_2 +1) & : & \text{even-odd} \\

X(2 k_1 +1, 2 k_2) & : & \text{odd-even} \\

X(4 k_1+1, 4 k_2+1) & : & \text{odd-odd} \\

X(4 k_1+1, 4 k_2+3) & : & \text{odd-odd} \\

X(4 k_1+3, 4 k_2+1) & : & \text{odd-odd} \\

X(4 k_1+3, 4 k_2+3) & : & \text{odd-odd}

\end{array}

That means the fourth term in 2-D DIT radix-$(2\backslash times\; 2)$ equation, $S\_\{11\}(k\_1,k\_2)\; W\_\{N\}^\{k\_1+k\_2\}$ becomes:{{cite journal|last1=Wu|first1=H.|last2=Paoloni|first2=F.|title=On the two-dimensional vector split-radix FFT algorithm|journal=IEEE Transactions on Acoustics, Speech, and Signal Processing|date=Aug 1989|volume=37|issue=8|pages=1302–1304|doi=10.1109/29.31283}}

: $A\_\{11\}(k\_1,k\_2)\; W\_N^\{k\_1+k\_2\}\; +\; A\_\{13\}(k\_1,k\_2)\; W\_N^\{k\_1+3\; k\_2\}\; +A\_\{31\}(k\_1,k\_2)\; W\_N^\{3\; k\_1+k\_2\}\; +\; A\_\{33\}(k\_1,k\_2)\; W\_N^\{3(k\_1+k\_2)\},$

where $A\_\{ij\}(k\_1,k\_2)=\backslash sum\_\{n\_1=0\}^\{N/4-1\}\; \backslash sum\_\{n\_2=0\}^\{N/4-1\}\; x[4\; n\_1\; +\; i,\; 4\; n\_2\; +\; j]\; \backslash cdot\; W\_\{N/4\}^\{n\_1\; k\_1\}\; W\_\{N/4\}^\{n\_2\; k\_2\}$

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\backslash times\; 1024$ array, compared with the vector-radix algorithm.

{{reflist|30em}}

Category:FFT algorithms

Category:Digital signal processing

Category:Discrete transforms