9.1: Introduction

Skills to Develop

• To study the Prime Factor Algorithm and the Winograd Fourier Transform Algorithm

The prime factor algorithm (PFA) and the Winograd Fourier transform algorithm (WFTA) are methods for efficiently calculating the DFT which use, and in fact, depend on the Type-1 index map from Multidimensional Index Mapping. The use of this index map preceded Cooley and Tukey's paper but its full potential was not realized until it was combined with Winograd's short DFT algorithms.

The number theoretic basis for the indexing in these algorithms may, at first, seem more complicated than in the Cooley-Tukey FFT; however, if approached from the general index mapping point of view of Multidimensional Index Mapping, it is straightforward, and part of a common approach to breaking large problems into smaller ones. The development in this section will parallel that in The Cooley-Tukey Fast Fourier Transform Algorithm.

The general index maps of Multidimensional Index Mapping must satisfy the Type-1 conditions which are

$K_1=aN_2\; \text{and}\; K_2=bN_1\; \text{with}\; (K_1N_1)=(K_2N_2)=1$

$K_3=cN_2\; \text{and}\; K_4=dN_1\; \text{with}\; (K_3N_1)=(K_4N_2)=1$

The row and column calculations in The Index Map are uncoupled by which for this case are

$((K_1K_4))_N=((K_2K_3))_N=0$

In addition, to make each short sum a DFT, the $$K_i$$ must also satisfy

$((K_1K_3))_N=N_2\; \text{and}\; ((K_2K_4))_N=N_1$

In order to have the smallest values for $$K_i$$, the constants in the equation are chosen to be

$a=b=1,\; c=((N_{2}^{-1}))_N,\; d=((N_{1}^{-1}))_N$

which gives for the index maps in the equation

$n=((N_2n_1+N_1n_2))_N$

$k=((K_3k_1+K_4k_2))_N$

The frequency index map is a form of the Chinese remainder theorem. Using these index maps, the DFT in Multidimensional Index Mapping becomes

$X=\sum_{n_2=0}^{N_2-1}\sum_{n_1=0}^{N_1-1}xW_{N_1}^{n_1k_1}W_{N_2}^{n_2k_2}$

which is a pure two-dimensional DFT with no twiddle factors and the summations can be done in either order. Choices other than the equation could be used. For example $$a=b=c=d=1$$ will cause the input and output index map to be the same and, therefore, there will be no scrambling of the output order. The short summations in (96), however, will no longer be short DFT's.

An important feature of the short Winograd DFT's described in Winograd's Short DFT Algorithms that is useful for both the PFA and WFTA is the fact that the multiplier constants in Winograd's Short DFT Algorithms are either real or imaginary, never a general complex number. For that reason, multiplication by complex data requires only two real multiplications, not four. That is a very significant feature. It is also true that the $$j$$ multiplier can be commuted from the $$D$$ operator to the last part of the $$A^T$$ operator. This means the $$D$$ operator has only real multipliers and the calculations on real data remains real until the last stage.

Contributor

• ContribEEBurrus