Content deleted Content added
m copyedit |
|||
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 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
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 as 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, 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.
'''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> element 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|pages=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|pages=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 ==
As with [[Cooley–Tukey FFT algorithm]], two dimensional vector-radix FFT is derived by decomposing the regular 2-D DFT into sums of smaller DFT's multiplied by "twiddle" factor.
A decimation-in-time ('''DIT''') algorithm means the decomposition is based on time ___domain <math>x</math>, see more in [[Cooley–Tukey FFT algorithm]].
Line 31 ⟶ 35:
== 2-D DIF case ==
Similarly, a decimation-in-frequency ('''DIF''', also called the
Using the change of variables:
Line 73 ⟶ 77:
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.
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/>
| |||