Large dft modules: 11, 13, 16, 17, 19, and 25  (Page 3/5)

Length 19 module: 372 adds / 76 mpys

This module closely follows the traditional Winograd prime-length approach.

1. Use the index map $\overline{x}\left(n\right)=x(<2^n{>}_{mod19})$ to convert the DFT into a length 18 convolution plus a correction term for the DC component.
2. Reduce the length 16 convolution modulo $z^9+1$ and $z^9-1$ .
   $$\begin{array}{ccc}\hfill mod{z}^9-1& :& r100-r108\hfill \\ \hfill mod{z}^9+9& :& r109-r117\hfill \end{array}$$
3. Use Nussbaumer's $z^9-1$ convolution algorithm on r100-r108. This is a transposed tensor method, however it again uses an obscure reconstruction procedure. This algorithm computes nineteen intermediate quantities, r31-r319, which are then weighted against nineteen coefficients to produce t11-t119. This data is then partially reconstructed to yield the final result of the $mod{z}^9-1$ convolution, t32-t310.
4. In the course of the $z^9-1$ convolution algorithm the $z^9-1$ data is reduced modulo $z-1$ and stored in r31. This quantity is added to $x\left(i\right(1\left)\right)$ to patch up the DC term.
5. An algebraic trick is used to compute the $z^9+1$ convolution using the $z^9-1$ algorithm. Suppose there exists a ring homomorphism H which maps elements of the ring of real polynomials modulo $z^9+1$ into the ring of polynomials modulo $z^9-1$ . Then $H$ could be used on the $z^9+1$ data, the resulting polynomial could be convolved in the modulo $z^9-1$ domain using the existing procedure, and the output of that procedure could be mapped back through $H^{-1}$ into the modulo $z^9+1$ domain. Such a homomorphism does exist, and moreover it happens to be its own inverse. $H\left(p\right)$ where $p$ is a polynomial (in either $R\left[x\right]/z^9-1$ or $R\left[x\right]/z^9+1$ ) may be formed from $p$ by negating the sign on all odd-numbered coefficients, that is, $H\left(p\right)\left(z\right)=p(-z)$ . The alternate negation of data values going into and coming out of the $mod{z}^9-1$ convolution algorithm is accomplished without an increase in computing time by appropriate placement of negative signs. The nineteen intermediate values formed are r320-r338 which are then weighted by the (purely imaginary) coefficients to produce t120-t138. A partial reconstruction yields the $z^9+1$ convolution result, t311-t319.
6. The $z^{18-1}$ convolution result is reconstructed from the $z^9-1$ (real) and $z^9+1$ (imaginary) vectors and mapped back to the outputs using the reverse of the input map.
7. All coefficients were computed using the author's QR decomposition linear equation solver and are accurate to at least 14 places.

Length 25 module: 420 adds / 132 mpys

This module is a common factor type module which uses length 5 convolutional DFT submodules. The length 5 submodules are implemented in a transposed tensor configuration using an index map $x\left(\overline{n}\right)=x(<2^n{>}_{mod5})$ followed by a reduction modulo all the irreducible factors of $z^4-1$ . The $z^2+1$ convolution is implemented using Toom-Cook factors of $z$ , $1/z$ and $z-1$ . The reconstruction matrix is exactly the transpose of the reduction procedure. The coefficients for the length 5 submodules were found using the author's QR procedure, and the twiddle factors were generated in a special FORTRAN program. The details of saving multiplies by scaling some of the prime length submodules in a common factor algorithm are discussed below in [link] . This length 25 module has a total of 132 multiplies and 420 adds. Using Winograd's decomposition of the length 25 OFT into two length 5 DFT's and a length 20 convolution the best operation count generated by this author was 108 multiplies and 604 adds.