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

Corollary: If the modulus polynomial is $P\left(s\right)=s^N-1$ , then $2N-t\left(N\right)$ multiplications are necessary to compute $x\left(s\right)h\left(s\right)$ modulo $P\left(s\right)$ , where $t\left(N\right)$ is the number of positive divisors of $N$ .

Theorem 5 is very general since it allows a general modulus polynomial. The proof of the upper boundinvolves reducing $x\left(s\right)$ and $h\left(s\right)$ modulo the $k$ factors of $P\left(s\right)$ . Each of the $k$ irreducible residue polynomials is then multiplied using the method of Theorem 4 requiring $2Ni-1$ multiplies and the products are combined using the CRT. The total number of multiplies from the $k$ parts is $2N-k$ . The theorem also states the structure of these optimal algorithms is essentiallyunique. The special case of $P\left(s\right)=s^N-1$ is interesting since it corresponds to cyclic convolution and, as stated in the corollary, $k$ is easily determined. The factors of $s^N-1$ are called cyclotomic polynomials and have interesting properties [link] , [link] , [link] .

Theorem 6 [link] , [link] Consider calculating the DFT of a prime length real-valued number sequence. If $G$ is chosen as the field of rational numbers, the number of realmultiplications necessary to calculate a length-P DFT is $u\left(DFT\right(N\left)\right)=2P-3-t(P-1)$ where $t(P-1)$ is the number of divisors of $P-1$ .

This theorem not only gives a lower limit on any practical prime length DFT algorithm, it also gives practicalalgorithms for $N=3,5$ , and 7. Consider the operation counts in [link] to understand this theorem. In addition to the real multiplications counted by complexity theory, each optimalprime-length algorithm will have one multiplication by a rational constant. That constant corresponds to the residue modulo (s-1)which always exists for the modulus $P\left(s\right)=s^{N-1}-1$ . In a practical algorithm, this multiplication must be carried out, andthat accounts for the difference in the prediction of Theorem 6 and count in [link] . In addition, there is another operation that for certain applications must be counted as amultiplication. That is the calculation of the zero frequency term $X\left(0\right)$ in the first row of the example in The DFT as Convolution or Filtering: Matrix 1 . For applications to the WFTA discussed in The Prime Factor and Winograd Fourier Transform Algorithms: The Winograd Fourier Transform Algorithm , that operation must be counted as a multiply. For lengths longer than 7,optimal algorithms require too many additions, so compromise structures are used.

Theorem 7 [link] , [link] If $G$ is chosen as the field of rational numbers, the number of real multiplicationsnecessary to calculate a length-N DFT where N is a prime number raised to an integer power: $N=Pm$ , is given by

where $t(P-1)$ is the number of divisors of $(P-1)$ .

This result seems to be practically achievable only for $N=9$ , or perhaps 25. In the case of $N=9$ , there are two rational multiplies that must be carried out and arecounted in [link] but are not predicted by Theorem 7 . Experience [link] indicates that even for $N=25$ , an algorithm based on a Cooley-Tukey FFT using a type 2 index map givesan over-all more balanced result.

Theorem 8 [link] If $G$ is chosen as the field of rational numbers, the number of real multiplications necessary tocalculate a length-N DFT where $N=2m$ is given by