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

The $h\left(n\right)$ terms are fixed for a digital filter, or they represent the $W$ terms from Multidimensional Index Mapping: Equation 1 if the convolution is being used to calculate a DFT. Because of this, $d=BH$ in [link] can be precalculated and only the $A$ and $C$ operators represent the mathematics done at execution of the algorithm. In order toexploit this feature, it was shown [link] , [link] that the properties of [link] allow the exchange of the more complicated operator $C$ with the simpler operator $B$ . Specifically this is given by

where $H$ ' has the same elements as $H$ , but in a permuted order, and likewise $Y$ ' and $Y$ . This very important property allows precomputing the more complicated $C^{T}H$ ' in [link] rather than $BH$ as in [link] .

Because $BH$ or $C^{T}H$ ' can be precomputed, the bilinear form of [link] and [link] can be written as a linear form. If an $M$ x $M$ diagonal matrix $D$ is formed from $d=C^{T}H$ , or in the case of [link] , $d=BH$ , assuming a commutative property for $o$ , [link] becomes

and [link] becomes

In most cases there is no reason not to use the same reduction operations on $X$ and $H$ , therefore, $B$ can be the same as $A$ and [link] then becomes

In order to illustrate how the residue reduction is carried out and how the A matrix is obtained, the length-5 DFT algorithmstarted in The DFT as Convolution or Filtering: Matrix 1 will be continued. The DFT is first converted to a length-4 cyclic convolution by theindex permutation from The DFT as Convolution or Filtering: Equation 3 to give the cyclic convolution in The DFT as Convolution or Filtering . To avoid confusion from the permuted order of the data $x\left(n\right)$ in The DFT as Convolution or Filtering , the cyclic convolution will first be developed without thepermutation, using the polynomial $U\left(s\right)$

and then the results will be converted back to the permuted $x\left(n\right)$ . The length-4 cyclic convolution in terms of polynomials is

and the modulus factors into three cyclotomic polynomials

Both $U\left(s\right)$ and $H\left(s\right)$ are reduced modulo these three polynomials. The reduction modulo $P_1$ and $P_2$ is done in two stages. First it is done modulo $(s^2-1)$ , then that residue is further reduced modulo $(s-1)$ and $(s+1)$ .

The reduction in [link] of the data polynomial [link] can be denoted by a matrix operation on a vector which has the data asentries.

and the reduction in [link] is

Combining [link] and [link] gives one operator

Further reduction of $v_0+v_{1}s$ is not possible because $P_3=s^2+1$ cannot be factored over the rationals. However $s^2-1$ can be factored into $P_1{P}_2=(s-1)(s+1)$ and, therefore, $w_0+w_{1}s$ can be further reduced as was done in [link] and [link] by

Combining [link] , [link] and [link] gives

The same reduction is done to $H\left(s\right)$ and then the convolution of [link] is done by multiplying each residue polynomial of $X\left(s\right)$ and $H\left(s\right)$ modulo each corresponding cyclotomic factor of $P\left(s\right)$ and finally a recombination using the polynomial Chinese RemainderTheorem (CRT) as in Polynomial Description of Signals: Equation 9 and Polynomial Description of Signals: Equation 13 .