0.3 Polynomial description of signals  (Page 2/2)

where $P\left(s\right)=s^N-1$ , and if $P\left(s\right)$ is factored into two relatively prime factors $P=P_1{P}_2$ , using residue reduction of $H\left(s\right)$ and $X\left(s\right)$ modulo $P_1$ and $P_2$ , the lower degree residue polynomials can be multiplied and the results recombined with theCRT. This is done by

where

and $K1$ and $K2$ are the CRT coefficient polynomials from [link] . This allows two shorter convolutions to replace one longer one.

Another property of residue reduction that is useful in DFT calculation is polynomial evaluation. To evaluate $F\left(s\right)$ at $s=x$ , $F\left(s\right)$ is reduced modulo $s-x$ .

This is easily seen from the definition in [link]

Evaluating $s=x$ gives $R\left(s\right)=F\left(x\right)$ which is a constant. For the DFT this becomes

Details of the polynomial algebra useful in digital signal processing can be found in [link] , [link] , [link] .

The dft as a polynomial evaluation

The Z-transform of a number sequence $x\left(n\right)$ is defined as

which is the same as the polynomial description in [link] but with a negative exponent. For a finite length-N sequence [link] becomes

This $N-1$ order polynomial takes on the values of the DFT of $x\left(n\right)$ when evaluated at

which gives

In terms of the positive exponent polynomial from [link] , the DFT is

where

is an $N^{th}$ root of unity (raising $W$ to the $N^{th}$ power gives one). The $N$ values of the DFT are found from $X\left(s\right)$ evaluated at the N $N^{th}$ roots of unity which are equally spaced around the unit circle in the complex $s$ plane.

One method of evaluating $X\left(z\right)$ is the so-called Horner's rule or nested evaluation. When expressed as a recursivecalculation, Horner's rule becomes the Goertzel algorithm which has some computational advantages especially when only a few values ofthe DFT are needed. The details and programs can be found in [link] , [link] and The DFT as Convolution or Filtering: Goertzel's Algorithm (or A Better DFT Algorithm)

Another method for evaluating $X\left(s\right)$ is the residue reduction modulo $(s-W^k)$ as shown in [link] . Each evaluation requires $N$ multiplications and therefore, $N^2$ multiplications for the $N$ values of $C\left(k\right)$ .

A considerable reduction in required arithmetic can be achieved if some operations can be shared between the reductions for differentvalues of $k$ . This is done by carrying out the residue reduction in stages that can be shared rather than done in one step for each $k$ in [link] .

The $N$ values of the DFT are values of $X\left(s\right)$ evaluated at s equal to the $N$ roots of the polynomial $P\left(s\right)=s^N-1$ which are $W^k$ . First, assuming $N$ is even, factor $P\left(s\right)$ as

$X\left(s\right)$ is reduced modulo these two factors to give two residue polynomials, $X_1\left(s\right)$ and $X_2\left(s\right)$ . This process is repeated by factoring $P_1$ and further reducing $X_1$ then factoring $P_2$ and reducing $X_2$ . This is continued until the factors are of first degree which gives the desired DFT values as in [link] . This is illustrated for a length-8 DFT. The polynomial whose roots are $W^k$ , factors as

where $a^2=j$ . Reducing $X\left(s\right)$ by the first factoring gives two third degree polynomials

gives the residue polynomials

Two more levels of reduction are carried out to finally give the DFT. Close examination shows the resulting algorithm to be thedecimation-in-frequency radix-2 Cooley-Tukey FFT [link] , [link] . Martens [link] has used this approach to derive an efficient DFT algorithm.

Other algorithms and types of FFT can be developed using polynomial representations and some are presented in the generalization in DFT and FFT: An Algebraic View .