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

There are other modifications of the basic structure of the Type-1 index map DFT algorithm. One is to use the same indexstructure and conversion of the short DFT's to convolution as the PFA but to use some other method for the high-speed convolution.Table look-up of partial products based on distributed arithmetic to eliminate all multiplications [link] looks promising for certain very specific applications, perhaps for specialized VLSIimplementation. Another possibility is to calculate the short convolutions using number-theoretic transforms [link] , [link] , [link] . This would also require special hardware. Direct calculation of short convolutions is faster on certainpipelined processor such as the TMS-320 microprocessor [link] .

Evaluation of the pfa and wfta

As for the Cooley-Tukey FFT's, the first evaluation of these algorithms will be on the number of multiplications and additionsrequired. The number of multiplications to compute the PFA in [link] is given by Multidimensional Index Mapping: Equation 3 . Using the notation that $T(N$ ) is the number of multiplications or additions necessary to calculate alength-N DFT, the total number for a four-factor PFA of length-N, where $N=N_1{N}_2{N}_3{N}_4$ is

The count of multiplies and adds in [link] are calculated from (105) with the counts of the factors taken from Winograd’s Short DFT Algorithms: Table 1 . The list of lengths are those possible with modules in the program of length 2,3, 4, 5, 7, 8, 9 and 16 as is true for the PFA in [link] , [link] and the WFTA in [link] , [link] . A maximum of four relatively prime lengths can be used from this group giving 59 different lengths overthe range from 2 to 5040. The radix-2 or split-radix FFT allows 12 different lengths over the same range. If modules of length 11 and13 from [link] are added, the maximum length becomes 720720 and the number of different lengths becomes 239. Adding modules for17, 19 and 25 from [link] gives a maximum length of 1163962800 and a very large and dense number of possible lengths.The length of the code for the longer modules becomes excessive and should not be included unless needed.

The number of multiplications necessary for the WFTA is simply the product of those necessary for the required modules,including multiplications by unity. The total number may contain some unity multipliers but it is difficult to remove them in apractical program. [link] contains both the total number (MULTS) and the number with the unity multiplies removed (RMULTS).

Calculating the number of additions for the WFTA is more complicated than for the PFA because of the expansion of the datamoving through the algorithm. For example the number of additions, TA, for the length-15 example in [link] is given by

where $N_1=3$ , $N_2=5$ , $T{M}_1$ = the number of multiplies for the length-3 module and hence the expansion factor. As mentionedearlier there is an optimum ordering to minimize additions. The ordering used to calculate [link] is the ordering used in [link] , [link] which is optimal in most cases and close to optimal in the others.

from [link] we see that compared to the PFA or any of the Cooley-Tukey FFT's, the WFTA has significantly fewer multiplications. For the shorterlengths, the WFTA and the PFA have approximately the same number of additions; however for longer lengths, the PFA has fewer and theCooley-Tukey FFT's always have the fewest. If the total arithmetic, the number of multiplications plus the number of additions, iscompared, the split-radix FFT, PFA and WFTA all have about the same count. Special versions of the PFA and WFTA have been developed forreal data [link] , [link] .

The size of the Cooley-Tukey program is the smallest, the PFA next and the WFTA largest. The PFA requires the smallest numberof stored constants, the Cooley-Tukey or split-radix FFT next, and the WFTA requires the largest number. For a DFT of approximately1000, the PFA stores 28 constants, the FFT 2048 and the WFTA 3564. Both the FFT and PFA can be calculated in-place and the WFTA cannot.The PFA can be calculated in-order without an unscrambler. The radix-2 FFT can also, but it requires additional indexing overhead [link] . The indexing and data transfer overhead is greatest for the WFTA because the separate preweave and postweave sections eachrequire their indexing and pass through the complete data. The shorter modules in the PFA and WFTA and the butterflies in the radix2 and 4 FFT's are more efficient than the longer ones because intermediate calculations can be kept in cpu registers rathergeneral memory [link] . However, the shorter modules and radices require more passes through the data for a given approximatelength. A proper comparison will require actual programs to be compiled and run on a particular machine. There are many openquestions about the relationship of algorithms and hardware architecture.