Vector-radix FFT algorithm: Difference between revisions

Revision as of 01:07, 21 November 2016

Revision as of 03:46, 13 December 2016

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><br />

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,<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|pages=250–252|doi=10.1109/TASSP.1977.1162951|url=http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1162951&isnumber=26125}}</ref> and it can eliminate 25% of the multiplies byas compared to the conventional row-column approach. And this algorithm has been extended to rectangular arrays and arbitrary radices,<ref name="Harris77">{{cite journal|last1=Harris|first1=D.|last2=McClellan|first2=J.|last3=Chan|first3=D.|last4=Schuessler|first4=H.|title=Vector radix fast Fourier transform|journal=IEEE International Conference on Acoustics, Speech, and Signal Processing, IEEE International Conference on ICASSP '77|volume=2|pages=548–551|doi=10.1109/ICASSP.1977.1170349|url=http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1170349&isnumber=26347}}</ref> which is the general Vector-Radix algorithm. Perhaps it is the simplest non-row-column [[FFT]] algorithm. <br />

'''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> timeelement matrix (M dimensions, and size N on each dimension), the number of complex multiples of vector-radix FFT algorithm for radix-2 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/><br />

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<ref name="Buijs74">{{cite journal|last1=Buijs|first1=H.|last2=Pomerleau|first2=A.|last3=Fournier|first3=M.|last4=Tam|first4=W.|title=Implementation of a fast Fourier transform (FFT) for image processing applications|journal=IEEE Transactions on Acoustics, Speech, and Signal Processing|date=Dec 1974|volume=22|page=420-424|doi=10.1109/TASSP.1974.1162620|url=http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1162620&isnumber=26107}}</ref>, and high speed FFT processor designing <ref name="Badar15">{{cite journal|last1=Badar|first1=S.|last2=Dandekar|first2=D.|title=High speed FFT processor design using radix −4 pipelined architecture|journal=2015 International Conference on Industrial Instrumentation and Control (ICIC), Pune, 2015|page=1050-1055|doi=10.1109/IIC.2015.7150901|url=http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7150901&isnumber=7150576}}</ref>.

== 2-D DIT case ==

Line 16 ⟶ 17:

* <math>n_i=rp_i+q_i</math>, where <math>p_i=0,\ldots,(N/r)-1; q_i = 0,\ldots,r-1;</math>

* <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|pages=2029–2039|doi=10.1109/78.150004|url=http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=150004&isnumber=3966}}</ref>:

where <math>i = 1</math> or <math>2</math>.

Then, the two dimensional DFT can be written as:

:<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>

Line 37 ⟶ 36:

* <math>n_i=p_i+q_i N/r</math>, where <math>p_i=0,\ldots,(N/r)-1; q_i = 0,\ldots,r-1;</math>

* <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/>:

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=IEEE International Conference on Acoustics, Speech, and Signal Processing, IEEE International Conference on ICASSP '87.|date=April 1987|pages=1987–1990|doi=10.1109/ICASSP.1987.1169345|url=http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1169345&isnumber=26345}}</ref><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|pages=2029–2039|doi=10.1109/78.150004|url=http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=150004&isnumber=3966}}</ref>

In conventional 2-D vector-radix algorithm, we decompose the incidentindices <math>k_1,k_2</math> into 4 groups:

: <math>

Line 70 ⟶ 67:

</math>

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<ref name="Wu89">{{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|page=1302-1304|doi=10.1109/29.31283|url=http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=31283&isnumber=1348}}</ref>:

: <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>