The Prime Factor and Winograd Fourier Transform Algorithms

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: Equation 10 and Multidimensional Index Mapping: Equation 6. 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 modern PFA was first presented in and a program given in . The WFTA was first presented in and programs given in , . 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: 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 K 1 = a N 2 and K 2 = b N 1 with ( K 1 , N 1 ) = ( K 2 , N 2 ) = 1 K 3 = c N 2 and K 4 = d N 1 with ( K 3 , N 1 ) = ( K 4 , N 2 ) = 1 The row and column calculations in Multidimensional Index Mapping: Equation 15 are uncoupled by Multidimensional Index Mapping: Equation 16 which for this case are ( ( K 1 K 4 ) ) N = ( ( K 2 K 3 ) ) N = 0 In addition, to make each short sum a DFT, the Ki must also satisfy ( ( K 1 K 3 ) ) N = N 2 a n d ( ( K 2 K 4 ) ) N = N 1 In order to have the smallest values for Ki, the constants in are chosen to be a = b = 1 , c = ( ( N 2 - 1 ) ) N , d = ( ( N 1 - 1 ) ) N which gives for the index maps in n = ( ( N 2 n 1 + N 1 n 2 ) ) N k = ( ( K 3 k 1 + K 4 k 2 ) ) N 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 X = ∑ n 2 = 0 N 2 - 1 ∑ n 1 = 0 N 1 - 1 x W N 1 n 1 k 1 W N 2 n 2 k 2 which is a pure two-dimensional DFT with no twiddle factors and the summations can be done in either order. Choices other than 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: Equation 5 or Winograd’s Short DFT Algorithms: Equation 8 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 AT 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 the short DFT modules in , and in the appendices.

The Prime Factor Algorithm If the DFT is calculated directly using , the algorithm is called a prime factor algorithm , and was discussed in Winograd’s Short DFT Algorithms and Multidimensional Index Mapping: In-Place Calculation of the DFT and Scrambling. When the short DFT's are calculated by the very efficient algorithms of Winograd discussed in Factoring the Signal Processing Operators, the PFA becomes a very powerful method that is as fast or faster than the best Cooley-Tukey FFT's , . A flow graph is not as helpful with the PFA as it was with the Cooley-Tukey FFT, however, the following representation in which combines Figures Multidimensional Index Mapping: Figure 1 and Winograd’s Short DFT Algorithms: Figure 2 gives a good picture of the algorithm with the example of Multidimensional Index Mapping: Equation 25

If N is factored into three factors, the DFT of would have three nested summations and would be a three-dimensional DFT. This principle extends to any number of factors; however, recall that the Type-1 map requires that all the factors be relatively prime. A very simple three-loop indexing scheme has been developed which gives a compact, efficient PFA program for any number of factors. The basic program structure is illustrated in with the short DFT's being omitted for clarity. Complete programs are given in and in the appendices.

C---------------PFA INDEXING LOOPS--------------
                DO 10 K = 1, M
                   N1 = NI(K)
                   N2 = N/N1
                   I(1) = 1
                   DO 20 J = 1, N2
                      DO 30 L=2, N1
                         I(L) = I(L-1) + N2
                         IF (I(L .GT.N)  I(L) = I(L) - N
           30         CONTINUE
                      GOTO (20,102,103,104,105), N1
                      I(1) = I(1) + N1
           20      CONTINUE
           10   CONTINUE
                RETURN
        C----------------MODULE FOR N=2-----------------
          102   R1       = X(I(1))
                X(I(1))  = R1 + X(I(2))
                X(I(2))  = R1 - X(I(2))
                R1       = Y(I(1))
                Y(I(1))  = R1 + Y(I(2))
                Y(I(2))  = R1 - Y(I(2))
                GOTO 20
        C----------------OTHER MODULES------------------
          103   Length-3 DFT
          104   Length-4 DFT
          105   Length-5 DFT
                etc.
 
 
Part of a FORTRAN PFA Program

As in the Cooley-Tukey program, the DO 10 loop steps through the M stages (factors of N) and the DO 20 loop calculates the N/N1 length-N1 DFT's. The input index map of is implemented in the DO 30 loop and the statement just before label 20. In the PFA, each stage or factor requires a separately programmed module or butterfly. This lengthens the PFA program but an efficient Cooley-Tukey program will also require three or more butterflies. Because the PFA is calculated in-place using the input index map, the output is scrambled. There are five approaches to dealing with this scrambled output. First, there are some applications where the output does not have to be unscrambled as in the case of high-speed convolution. Second, an unscrambler can be added after the PFA to give the output in correct order just as the bit-reversed-counter is used for the Cooley-Tukey FFT. A simple unscrambler is given in , but it is not in place. The third method does the unscrambling in the modules while they are being calculated. This is probably the fastest method but the program must be written for a specific length , . A fourth method is similar and achieves the unscrambling by choosing the multiplier constants in the modules properly . The fifth method uses a separate indexing method for the input and output of each module , .

The Winograd Fourier Transform Algorithm The Winograd Fourier transform algorithm (WFTA) uses a very powerful property of the Type-1 index map and the DFT to give a further reduction of the number of multiplications in the PFA. Using an operator notation where F1 represents taking row DFT's and F2 represents column DFT's, the two-factor PFA of is represented by X = F 2 F 1 x It has been shown , that if each operator represents identical operations on each row or column, they commute. Since F1 and F2 represent length N1 and N2 DFT's, they commute and can also be written X = F 1 F 2 x If each short DFT in F is expressed by three operators as in Winograd’s Short DFT Algorithms: Equation 8 and Winograd’s Short DFT Algorithms: Figure 2, F can be factored as F = A T D A where A represents the set of additions done on each row or column that performs the residue reduction as Winograd’s Short DFT Algorithms: Equation 30. Because of the appearance of the flow graph of A and because it is the first operator on x, it is called a preweave operator . D is the set of M multiplications and AT (or BT or CT) from Winograd’s Short DFT Algorithms: Equation 5 or Winograd’s Short DFT Algorithms: Equation 6 is the reconstruction operator called the postweave. Applying to gives X = A 2 T D 2 A 2 A 1 T D 1 A 1 x This is the PFA of and where A1D1A1 represents the row DFT's on the array formed from x. Because these operators commute, can also be written as X = A 2 T A 1 T D 2 D 1 A 2 A 1 x or X = A 1 T A 2 T D 2 D 1 A 2 A 1 x but the two adjacent multiplication operators can be premultiplied and the result represented by one operator D=D2D1 which is no longer the same for each row or column. Equation becomes X = A 1 T A 2 T D A 2 A 1 x This is the basic idea of the Winograd Fourier transform algorithm. The commuting of the multiplication operators together in the center of the algorithm is called nesting and it results in a significant decrease in the number of multiplications that must be done at the execution of the algorithm. Pictorially, the PFA of becomes the WFTA in .

The rectangular structure of the preweave addition operators causes an expansion of the data in the center of the algorithm. The 15 data points in become 18 intermediate values. This expansion is a major problem in programming the WFTA because it prevents a straightforward in-place calculation and causes an increase in the number of required additions and in the number of multiplier constants that must be precalculated and stored. From and the idea of premultiplying the individual multiplication operators, it can be seen why the multiplications by unity had to be considered in Winograd’s Short DFT Algorithms: Table 1. Even if a multiplier in D1 is unity, it may not be in D2D1. In with factors of three and five, there appear to be 18 multiplications required because of the expansion of the length-5 preweave operator, A2, however, one of multipliers in each of the length three and five operators is unity, so one of the 18 multipliers in the product is unity. This gives 17 required multiplications - a rather impressive reduction from the 152=225 multiplications required by direct calculation. This number of 17 complex multiplications will require only 34 real multiplications because, as mentioned earlier, the multiplier constants are purely real or imaginary while the 225 complex multiplications are general and therefore will require four times as many real multiplications. The number of additions depends on the order of the pre- and postweave operators. For example in the length-15 WFTA in , if the length-5 had been done first and last, there would have been six row addition preweaves in the preweave operator rather than the five shown. It is difficult to illustrate the algorithm for three or more factors of N, but the ideas apply to any number of factors. Each length has an optimal ordering of the pre- and postweave operators that will minimize the number of additions. A program for the WFTA is not as simple as for the FFT or PFA because of the very characteristic that reduces the number of multiplications, the nesting. A simple two-factor example program is given in and a general program can be found in , . The same lengths are possible with the PFA and WFTA and the same short DFT modules can be used, however, the multiplies in the modules must occur in one place for use in the WFTA.

Modifications of the PFA and WFTA Type Algorithms In the previous section it was seen how using the permutation property of the elementary operators in the PFA allowed the nesting of the multiplications to reduce their number. It was also seen that a proper ordering of the operators could minimize the number of additions. These ideas have been extended in formulating a more general algorithm optimizing problem. If the DFT operator F in is expressed in a still more factored form obtained from Winograd’s Short DFT Algorithms: Equation 30, a greater variety of ordering can be optimized. For example if the A operators have two factors F 1 = A 1 T A 1 ' T D 1 A 1 ' A 1 The DFT in becomes X = A 2 T A ' 2 T D 2 A ' 2 A 2 A 1 T A ' 1 T D 1 A ' 1 A 1 x The operator notation is very helpful in understanding the central ideas, but may hide some important facts. It has been shown , that operators in different Fi commute with each other, but the order of the operators within an Fi cannot be changed. They represent the matrix multiplications in Winograd’s Short DFT Algorithms: Equation 30 or Winograd’s Short DFT Algorithms: Equation 8 which do not commute. This formulation allows a very large set of possible orderings, in fact, the number is so large that some automatic technique must be used to find the “best". It is possible to set up a criterion of optimality that not only includes the number of multiplications but the number of additions as well. The effects of relative multiply-add times, data transfer times, CPU register and memory sizes, and other hardware characteristics can be included in the criterion. Dynamic programming can then be applied to derive an optimal algorithm for a particular application . This is a very interesting idea as there is no longer a single algorithm, but a class and an optimizing procedure. The challenge is to generate a broad enough class to result in a solution that is close to a global optimum and to have a practical scheme for finding the solution. Results obtained applying the dynamic programming method to the design of fairly long DFT algorithms gave algorithms that had fewer multiplications and additions than either a pure PFA or WFTA . It seems that some nesting is desirable but not total nesting for four or more factors. There are also some interesting possibilities in mixing the Cooley-Tukey with this formulation. Unfortunately, the twiddle factors are not the same for all rows and columns, therefore, operations cannot commute past a twiddle factor operator. There are ways of breaking the total algorithm into horizontal paths and using different orderings along the different paths , . In a sense, this is what the split-radix FFT does with its twiddle factors when compared to a conventional Cooley-Tukey FFT. There are other modifications of the basic structure of the Type-1 index map DFT algorithm. One is to use the same index structure 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 looks promising for certain very specific applications, perhaps for specialized VLSI implementation. Another possibility is to calculate the short convolutions using number-theoretic transforms , , . This would also require special hardware. Direct calculation of short convolutions is faster on certain pipelined processor such as the TMS-320 microprocessor .

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 additions required. The number of multiplications to compute the PFA in is given by Multidimensional Index Mapping: Equation 3. Using the notation that T(N) is the number of multiplications or additions necessary to calculate a length-N DFT, the total number for a four-factor PFA of length-N, where N=N1N2N3N4 is T ( N ) = N 1 N 2 N 3 T ( N 4 ) + N 2 N 3 N 4 T ( N 1 ) + N 3 N 4 N 1 T ( N 2 ) + N 4 N 1 N 2 T ( N 3 ) The count of multiplies and adds in 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 , and the WFTA in , . A maximum of four relatively prime lengths can be used from this group giving 59 different lengths over the 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 and 13 from are added, the maximum length becomes 720720 and the number of different lengths becomes 239. Adding modules for 17, 19 and 25 from 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 a practical program. 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 data moving through the algorithm. For example the number of additions, TA, for the length-15 example in is given by T A ( N ) = N 2 T A ( N 1 ) + T M 1 T A ( N 2 ) where N1=3, N2=5, TM1 = the number of multiplies for the length-3 module and hence the expansion factor. As mentioned earlier there is an optimum ordering to minimize additions. The ordering used to calculate is the ordering used in , which is optimal in most cases and close to optimal in the others. Length PFA PFA WFTA WFTA WFTA N Mults Adds Mults RMults Adds 10 20 88 24 20 88 12 16 96 24 16 96 14 32 172 36 32 172 15 50 162 36 34 162 18 40 204 44 40 208 20 40 216 48 40 216 21 76 300 54 52 300 24 44 252 48 36 252 28 64 400 72 64 400 30 100 384 72 68 384 35 150 598 108 106 666 36 80 480 88 80 488 40 100 532 96 84 532 42 152 684 108 104 684 45 190 726 132 130 804 48 124 636 108 92 660 56 156 940 144 132 940 60 200 888 144 136 888 63 284 1236 198 196 1394 70 300 1336 216 212 1472 72 196 1140 176 164 1156 80 260 1284 216 200 1352 84 304 1536 216 208 1536 90 380 1632 264 260 1788 105 590 2214 324 322 2418 112 396 2188 324 308 2332 120 460 2076 288 276 2076 126 568 2724 396 392 3040 140 600 2952 432 424 3224 144 500 2676 396 380 2880 168 692 3492 432 420 3492 180 760 3624 528 520 3936 210 1180 4848 648 644 5256 240 1100 4812 648 632 5136 252 1136 5952 792 784 6584 280 1340 6604 864 852 7148 315 2050 8322 1188 1186 10336 336 1636 7908 972 956 8508 360 1700 8148 1056 1044 8772 420 2360 10536 1296 1288 11352 504 2524 13164 1584 1572 14428 560 3100 14748 1944 1928 17168 630 4100 17904 2376 2372 21932 720 3940 18276 2376 2360 21132 840 5140 23172 2592 2580 24804 1008 5804 29100 3564 3548 34416 1260 8200 38328 4752 4744 46384 1680 11540 50964 5832 5816 59064 2520 17660 82956 9504 9492 99068 5040 39100 179772 21384 21368 232668

from we see that compared to the PFA or any of the Cooley-Tukey FFT's, the WFTA has significantly fewer multiplications. For the shorter lengths, the WFTA and the PFA have approximately the same number of additions; however for longer lengths, the PFA has fewer and the Cooley-Tukey FFT's always have the fewest. If the total arithmetic, the number of multiplications plus the number of additions, is compared, the split-radix FFT, PFA and WFTA all have about the same count. Special versions of the PFA and WFTA have been developed for real data , . The size of the Cooley-Tukey program is the smallest, the PFA next and the WFTA largest. The PFA requires the smallest number of stored constants, the Cooley-Tukey or split-radix FFT next, and the WFTA requires the largest number. For a DFT of approximately 1000, 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 . The indexing and data transfer overhead is greatest for the WFTA because the separate preweave and postweave sections each require their indexing and pass through the complete data. The shorter modules in the PFA and WFTA and the butterflies in the radix 2 and 4 FFT's are more efficient than the longer ones because intermediate calculations can be kept in cpu registers rather general memory . However, the shorter modules and radices require more passes through the data for a given approximate length. A proper comparison will require actual programs to be compiled and run on a particular machine. There are many open questions about the relationship of algorithms and hardware architecture.