Vector-radix FFT algorithm: Difference between revisions

Revision as of 13:30, 29 February 2020

Revision as of 04:14, 29 May 2023

Line 8:

== 2-D DIT case ==

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" factorfactors.

A decimation-in-time ('''DIT''') algorithm means the decomposition is based on time ___domain <math>x</math>, see more in [[Cooley–Tukey FFT algorithm]].

We suppose the 2-D DFT is defined

:<math>X(k_1,k_2) = \sum_{n_1=0}^{N_1-1} \sum_{n_2=0}^{N_2-1} x[n_1, n_2] \cdot W_{N_1}^{k_1 n_1} W_{N_2}^{k_2 n_2}, </math>

where <math>k_1 = 0,\dots,N_1-1</math>,and <math>k_2 = 0,\dots,N_2-1</math>, and <math>x[n_1, n_2]</math> is aan <math>N_1 \times N_2</math> matrix, and <math>W_N = \exp(-j 2\pi /N)</math>.

For simplicity, let us assume that <math>N_1=N_2=N</math>, and the radix-<math>(r\times r)</math>( is such that <math>N/r</math> areis integers)an integer.

Using the change of variables:

Line 24:

:<math> X(u_1+v_1 N/r,u_2+v_2 N/r)=\sum_{q_1=0}^{r-1} \sum_{q_2=0}^{r-1} \left[ \sum_{p_1=0}^{N/r-1} \sum_{p_2=0}^{N/r-1} x[rp_1+q_1, rp_1+q_1] W_{N/r}^{p_1 u_1} W_{N/r}^{p_2 u_2} \right] \cdot W_N^{q_1 u_1+q_2 u_2} W_r^{q_1 v_1} W_r^{q_2 v_2},</math>

[[File:2-D2x2 radix DIT-FFT-butterfly diagram.pngsvg|thumb|400px|One stage "butterfly" for DIT vector-radix 2x2 FFT]]

The equation above defines the basic structure of the 2-D DIT radix-<math>(r\times r)</math> "butterfly". (See 1-D "butterfly" in [[Cooley–Tukey FFT algorithm]])

When <math>r=2</math>, the equation can be broken into four summations: one over those samples of x for which both <math>n_1</math> and <math>n_2</math> are even, one for which <math>n_1</math> is even and <math>n_2</math>this isleads odd, one of which <math>n_1</math> is odd and <math>n_2</math> is even, and one for which both <math>n_1</math> and <math>n_2</math> are odd,to<ref name=Dudgeon83/> and this leads to:

:<math> 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}</math> for <math>0\leq k_1, k_2 < \frac{N}{2}</math>,

where <math>S_{ij}(k_1,k_2)=\sum_{n_1=0}^{N/2-1} \sum_{n_2=0}^{N/2-1} x[2 n_1 + i, 2 n_2 + j] \cdot W_{N/2}^{n_1 k_1} W_{N/2}^{n_2 k_2}.</math>.

The <math>S_{ij}</math> can be viewed as the <math>N/2</math>-dimensional DFT, each over a subset of the original sample:

* <math>S_{00}</math> is the DFT over those samples of <math>x</math> for which both <math>n_1</math> and <math>n_2</math> are even;

* <math>S_{01}</math> is the DFT over the samples for which <math>n_1</math> is even and <math>n_2</math> is odd;

* <math>S_{10}</math> is the DFT over the samples for which <math>n_1</math> is odd and <math>n_2</math> is even;

* <math>S_{11}</math> is the DFT over the samples for which both <math>n_1</math> and <math>n_2</math> are odd.

Thanks to the [[List of trigonometric identities#Shifts and periodicity|periodicity of the complex exponential]], we can obtain the the following additional identities, valid for <math>0\leq k_1, k_2 < \frac{N}{2}</math>:

* <math>X\biggl(k_1+\frac{N}{2},k_2\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}</math>;

* <math>X\biggl(k_1,k_2+\frac{N}{2}\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}</math>;

* <math>X\biggl(k_1+\frac{N}{2},k_2+\frac{N}{2}\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}</math>.

== 2-D DIF case ==