Content deleted Content added
Citation bot (talk | contribs) Removed parameters. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox3 | #UCB_webform_linked 1848/1947 |
m clean up spacing around commas and other punctuation, replaced: ,and → , and , ,N → , N (2), ,k → , k (29), ,r → , r (5), ,u → , u |
||
| (3 intermediate revisions by 2 users not shown) | |||
Line 1:
{{Short description|Multidimensional fast Fourier transform algorithm}}
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.<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>
Line 14 ⟶ 15:
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 an <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> is an integer.
Line 22 ⟶ 23:
* <math>k_i=u_i+v_i N/r</math>, where <math>u_i=0,\ldots,(N/r)-1; v_i = 0,\ldots,r-1;</math>
where <math>i = 1</math> or <math>2</math>, then the two dimensional DFT can be written as:<ref name="Chan92">{{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}}</ref>
:<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,
[[File:2x2 radix butterfly diagram.svg|thumb|400px|One stage "butterfly" for DIT vector-radix 2x2 FFT]]
Line 52 ⟶ 53:
* <math>k_i=r u_i+v_i</math>, where <math>u_i=0,\ldots,(N/r)-1; v_i = 0,\ldots,r-1;</math>
where <math>i = 1</math> or <math>2</math>, and the DFT equation can be written as:<ref name=Chan92/>
:<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,
== Other approaches ==
| |||