Content deleted Content added
DaltonCastle (talk | contribs) added Category:Discrete transforms using HotCat |
m WP:CHECKWIKI error fix for #61. Punctuation goes before References. Do general fixes if a problem exists. - |
||
Line 1:
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 [[DFT]]s until, ultimately, only trivial MD [[DFT]]s need to be evaluated.<ref name="Dudgeon83">{{cite book|last1=Dudgeon|first1=Dan|last2=Russell|first2=Mersereau|title=Multidimensional Digital Signal Processing|date=September 1983|publisher=Prentice Hall|isbn=0136049591|pages=76}}</ref>
The most common multidimensional [[FFT]] algorithm is 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,<ref name="Rivard77">{{cite journal|last1=Rivard|first1=G.|title=Direct fast Fourier transform of bivariate functions|journal=IEEE Transactions on Acoustics, Speech, and Signal Processing|volume=25|
'''Vector-radix FFT algorithm''' can reduce the number of complex multiplications significantly, compared to row-vector algorithm. For example, for a <math>N^M</math> time matrix (M dimensions, and size N on each dimension), the number of complex multiples of vector-radix FFT algorithm is <math>\frac{2^M -1}{2^M} N^M log_2 N</math>, meanwhile, for row-column algorithm, it is <math>\frac{M N^M}{2} log_2 N</math>. And generally, even larger savings in multiplies are obtained when this algorithm is operated on larger radices and on higher dimensional arrays.<ref name=Harris77/>
== 2-D DIT case ==
Line 9:
We suppose the 2-D [[DFT]]
:<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 a <math>N_1 \times N_2</math> matrix, and <math>W_{N}^{k n} = exp(-j 2\pi /N)</math>.
For simplicity, let us assume that <math>N_1=N_2=N</math>, and radix-<math>(r\times r)</math>(<math>N/r</math> are integers).
Using the change of variables:
* <math>n_i=rp_i+q_i</math>, where <math>p_i=0,\cdots,(N/r)-1; q_i = 0,\cdots,r-1;</math>
* <math>k_i=u_i+v_i N/r</math>, where <math>u_i=0,\cdots,(N/r)-1; v_i = 0,\cdots,r-1;</math>
where <math>i = 1</math> or <math>2</math>.
Then, the two dimensional DFT can be written as:
Line 23:
[[File:2-D DIT-FFT-butterfly.png|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> is 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,<ref name=Dudgeon83/>
:<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>,
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>.
Line 37:
And the DFT equation can be written as:
:<math> X(r u_1+v_1,r u_2+v_2)=\sum_{p_1=0}^{N/r-1} \sum_{p_2=0}^{N/r-1} \left[ \sum_{q_1=0}^{r-1} \sum_{q_2=0}^{r-1} x[p_1+q_1 N/r, p_1+q_1 N/r] W_{r}^{q_1 v_1} W_{r}^{q_2 v_2} \right] \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},</math>
== Other approaches ==
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.<ref name="Pei87">{{cite journal|last1=Pei|first1=Soo-Chang|last2=Wu|first2=Ja-Lin|title=Split vector radix 2D fast Fourier transform|journal=Acoustics, Speech, and Signal Processing, IEEE International Conference on ICASSP '87.|date=April 1987|
In conventional 2-D vector-radix algorithm, we decompose the incident <math>k_1,k_2</math> into 4 groups:<br />
Line 67 ⟶ 65:
That means the fourth term in 2-D DIT radix-<math>(2\times 2)</math> equation, <math>S_{11}(k_1,k_2) W_{N}^{k_1+k_2}</math> becomes:<br />
:<math> 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)}</math>,
where <math>A_{ij}(k_1,k_2)=\sum_{n_1=0}^{N/4-1} \sum_{n_2=0}^{N/4-1} x[4 n_1 + i, 4 n_2 + j] \cdot W_{N/4}^{n_1 k_1} W_{N/4}^{n_2 k_2}</math
The 2-D N by N DFT is then obtained by successive use of the above decomposition, up to the last stage.<br />
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 <math>1024\times 1024</math> array, compared with the vector-radix algorithm.<ref name=Pei87/>
==References==
{{reflist|30em}}
[[Category:FFT algorithms]]
| |||