0.6 Winograd's short dft algorithms  (Page 11/11)

This yields the two intermediate polynomials,

In the notation used above,

entailing 24 additions. Continuing this process results in a factorization in steps

In order to see the number of additions this scheme uses for numbers of the form $N=P-1$ (which is relevant to prime length FFT algorithms) figure 4 shows the number of additions the reduction process uses when the polynomialX(s) is real.

Figure 4: Number of Additions for Reduction Stage

The polynomial product stage

The iterated convolution algorithm can be used to construct an $N$ point linear convolution algorithm from shorter linear convolution algorithms [link] . Suppose the linear convolution $y$ , of the $n$ point vectors $x$ and $h$ ( $h$ known) is described by

where $E_n$ is an “expansion" matrix the elements of which are $\pm l$ 's and 0's and $D$ is an appropriate diagonal matrix. Because the only multiplications in thisexpression are by the elements of $D$ , the number of multiplications required, $M\left(n\right)$ , is equal to the number of rows of $E_n$ . The number of additions is denoted by $A\left(n\right)$ .

Given a matrix $E_{n_1}$ and a matrix $E_{n_2}$ , the iterated algorithm gives a method for combining $E_{n_1}$ and $E_{n_2}$ to construct a valid expansion matrix, $E_n$ , for $N\le n_1{n}_2$ . Specifically,

The product $n_1{n}_2$ may be greater than $N$ , for zeros can be (conceptually) appended to $x$ . The operation count associated with $E_{n_1,n_2}$ is

Although they are both valid expansion matrices, $E_{n_1,n_2}\ne E_{n_2,n_1}$ and $A_{n_1,n_2}\ne A_{n_2,n_1}$ Because $M_{n_1,n_2}\ne M_{n_2,n_1}$ it is desirable to chose an ordering of factors to minimize the additions incurred by the expansion matrix.The following [link] , [link] follows from above.

Multiple factors

Note that a valid expansion matrix, $E_N$ , can be constructed from $E_{n_1,n_2}$ and $E_{n_3}$ , for $N\le n_1{n}_2{n}_3$ . In general, any number of factors can be used to create larger expansion matrices.The operation count associated with $E_{n_1,n_2,n_3}$ is

These equations generalize in the predicted way when more factors are considered. Because the ordering of the factors is relevant in the equation for $A(.)$ but not for $M(.)$ , it is again desirable to order the factors to minimize the number of additions. By exploiting the following property of the expressionsfor $A(.)$ and $M(.)$ , the optimal ordering can be found [link] .

reservation of Optimal Ordering. Suppose $A(n_1,n_2,n_3)\le min\{A(n_{k_1},n_{k_2},n_{k_3}):k_1,k_2,k_3\in \{1,2,3\}$ and distinct}, then

1. $A(n_1,n_2)\le A(n_2,n_1)$
2. $A(n_2,n_3)\le A(n_3,n_2)$
3. $A(n_1,n_3)\le A(n_3,n_1)$

The generalization of this property to more than two factors reveals that an optimal ordering of $\{n_1,\cdots ,n_{L-i}\}$ is preserved in an optimal ordering of $\{n_1,\cdots n_L\}$ . Therefore, if $(n_1,\cdots n_L)$ is an optimal ordering of $\{n_1,\cdots n_L\}$ , then $(n_k,n_{k+1})$ is an optimal ordering of $\{n_k,n_{k+1}\}$ and consequently

for all $k=1,2,\cdots ,L-1$ .

This immediately suggests that an optimal ordering of $\{n_1,\cdots n_L\}$ is one for which

is nondecreasing. Hence, ordering the factors, $\{n_1,\cdots n_L\}$ , to minimize the number of additions incurred by $E_{n_1,\cdots ,n_L}$ simply involves computing the appropriate ratios.

Discussion and conclusion

We have designed prime length FFTs up to length 53 that are as good as the previous designs that only went up to 19. Table 1 gives theoperation counts for the new and previously designed modules, assuming complex inputs.

It is interesting to note that the operation counts depend on the factorability of $P-1$ . The primes 11, 23, and 47 are all of the form $1+2P_1$ making the design of efficient FFTs for these lengths more difficult.

Further deviations from the original Winograd approach than we have made could prove useful for longer lengths. We investigated, for example,the use of twiddle factors at appropriate points in the decomposition stage; these can sometimes be used to divide the cyclic convolutioninto smaller convolutions. Their use means, however, that the 'center* multiplications would no longer be by purely real or imaginary numbers.

The approach in writing a program that writes another program is a valuable one for several reasons. Programming the design process for the design ofprime length FFTs has the advantages of being practical, error-free, and flexible. The flexibility is important because it allows for modificationand experimentation with different algorithmic ideas. Above all, it has allowed longer DFTs to be reliably designed.

More details on the generation of programs for prime length FFTs can be found in the 1993 Technical Report.