0.9 The prime factor and winograd fourier transform algorithms  (Page 20/5)

The prime factor algorithm (PFA) and the Winograd Fourier transform algorithm (WFTA) are methods for efficiently calculatingthe DFT which use, and in fact, depend on the Type-1 index map from Multidimensional Index Mapping: Equation 10 and Multidimensional Index Mapping: Equation 6 . The use of this index map preceded Cooley and Tukey's paper [link] , [link] but its full potential was not realized until it was combined with Winograd's short DFT algorithms.The modern PFA was first presented in [link] and a program given in [link] . The WFTA was first presented in [link] and programs given in [link] , [link] .

The number theoretic basis for the indexing in these algorithms may, at first, seem more complicated than in theCooley-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 intosmaller 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: Equation 6 and Multidimensional Index Mapping: Equation 12 must satisfy the Type-1 conditions of Multidimensional Index Mapping: Equation 7 and Multidimensional Index Mapping: Equation 10 which are

The row and column calculations in Multidimensional Index Mapping: Equation 15 are uncoupled by Multidimensional Index Mapping: Equation 16 which for this case are

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

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

which gives for the index maps in [link]

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

which is a pure two-dimensional DFT with no twiddle factors and the summations can be done in either order. Choices other than [link] 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 [link] .

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: Equation 6 or Winograd’s Short DFT Algorithms: Equation 8 are either real or imaginary, never a general complex number. For thatreason, multiplication by complex data requires only two real multiplications, not four. That is a very significant feature. It isalso 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. This can be seen by examining theshort DFT modules in [link] , [link] and in the appendices.