Vector-radix FFT algorithm: Difference between revisions

Revision as of 23:47, 9 August 2023

Revision as of 22:39, 22 August 2023

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 [[Fast Fourier transform|FFT]] algorithm is the row-column algorithm, which means transforming the array first in one index and then in the other, see more in [[Fast Fourier transform|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|issue=3|pages=250–252|doi=10.1109/TASSP.1977.1162951|year=1977}}</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 book|last1=Harris|first1=D.|last2=McClellan|first2=J.|last3=Chan|first3=D.|last4=Schuessler|first4=H.|date=1977 |title=ICASSP '77. IEEE International Conference on Acoustics, Speech, and Signal Processing |chapter=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|year=1977}}</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/>