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

Each of the stages can be clearly seen in the flow graphs for the DFTs. [link] shows the flow graph for a length 17 DFT algorithm that was automatically drawn by the program.

The programs that accomplish this process are written in Matlab and C. Those that compute the appropriate matrices are written in Matlab. These matrices are then stored as two ASCIIfiles, with the dimensions in one and the matrix elements in the second. A C program then readsthe flies and compiles them to produce the final FFT program in C [link]

The reduction stage

The reduction of an $N^{th}$ degree polynomial, $X\left(s\right)$ , modulo the cyclotomic polynomial factors of $(s^N-1)$ requires only additions for many N, however, the actual number of additions depends upon the way in which the reduction proceeds. The reduction is most efficientlyperformed in steps. For example, if $N=4$ and $({\left(X\left(s\right)\right)}_{s-1}$ , $({\left(X\left(s\right)\right)}_{s+1}$ and $({\left(X\left(s\right)\right)}_{s^2+1}$ where the double parenthesis denote polynomial reduction modulo $(s-1)$ , $s+1$ , and $s^2+1)$ , then in the first step ${\left(\left(X\left(s\right)\right)\right)}_{s^2-1}$ , and ${\left(\left(Xs\right)\right))}_{s^2+1}$ should be computed. In the second step, ${\left(\left(Xs\right)\right))}_{s-1}$ and ${\left(\left(Xs\right)\right))}_{s+1}$ can be found by reducing ${\left(\left(X\left(s\right)\right)\right)}_{s^2-1}$ This process is described by the diagram in [link] .

When $N$ is even, the appropriate first factorization is $(S^{N/2}-1)(s^{N/2}+1)$ , however, the next appropriate factorization is frequently less obvious. The following procedurehas been found to generate a factorization in steps that coincides with the factorization that minimizes the cumulative number of additions incurred by the steps.The prime factors of $N$ are the basis of this procedure and their importance is clear from the useful well-known equation $s^N-1={\prod }_{n|N}{C}_n\left(s\right)$ where $C_n\left(s\right)$ is the $n^{th}$ cyclotomic polynomial.

We first introduce the following two functions defined on the positive integers,

and $\psi \left(1\right)=1$ .

Suppose $P\left(s\right)$ is equal to either $(s^N-1)$ or an intermediate noncyclotomic polynomial appearing in the factorization process, for example, $(a^2-1)$ , above. Write $P\left(s\right)$ in terms of its cyclotomic factors,

define the two sets, $G$ and $G$ , by

and define the two integers, $t$ and $T$ , by

Then form two new sets,

The factorization of $P\left(s\right)$ ,

has been found useful in the procedure for factoring $(s^N-1)$ . This is best illustrated with an example.

Example: $N=36$

Step 1. Let $P\left(s\right)=s^{36}-1$ . Since $P=C_1{C}_2{C}_3{C}_4{C}_6{C}_9{C}_{12}{C}_{18}{C}_{36}$

Hence the factorization of $s^{36}-1$ into two intermediate polynomials is as expected,

If a 36th degree polynomial, $X\left(s\right)$ , is represented by a vector of coefficients, $X={(x_{35},\cdots ,x_0)}^{\text{'}}$ , then $({\left(X\left(s\right)\right)}_{s^{18}-1}$ (represented by X') and $({\left(X\left(s\right)\right)}_{s^{18}+1}$ (represented by X") is given by

which entails 36 additions.

Step 2. This procedure is repeated with $P\left(s\right)=s^{18}-1$ and $P\left(s\right)=s^{18}+1$ . We will just show it for the later. Let $P\left(s\right)=s^{18}+1$ . Since $P=C_4{C}_{12}{C}_{36}$