<< Chapter < Page | Chapter >> Page > |
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 .
Notification Switch
Would you like to follow the 'Fast fourier transforms' conversation and receive update notifications?