Vector-radix FFT algorithm: Difference between revisions

Revision as of 11:28, 4 December 2019

Revision as of 13:30, 29 February 2020

Line 5:

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

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|issue=6|pages=420–424|doi=10.1109/TASSP.1974.1162620}}</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=https://ieeexplore.ieee.org/document/7150901|year=2015|isbn=978-1-4799-7165-7}}</ref>

== 2-D DIT case ==

Line 21:

* <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|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, 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>