0.3 Polynomial description of signals

Polynomials are important in digital signal processing because calculating the DFT can be viewed as a polynomial evaluationproblem and convolution can be viewed as polynomial multiplication [link] , [link] . Indeed, this is the basis for the important results of Winograd discussed in Winograd’s Short DFT Algorithms . A length-N signal $x\left(n\right)$ will be represented by an $N-1$ degree polynomial $X\left(s\right)$ defined by

This polynomial $X\left(s\right)$ is a single entity with the coefficients being the values of $x\left(n\right)$ . It is somewhat similar to the use of matrix or vector notation to efficiently represent signals whichallows use of new mathematical tools.

The convolution of two finite length sequences, $x\left(n\right)$ and $h\left(n\right)$ , gives an output sequence defined by

$n=0,1,2,\cdots ,2N-1$ where $h\left(k\right)=0$ for $k<0$ . This is exactly the same operation as calculating the coefficients whenmultiplying two polynomials. Equation [link] is the same as

In fact, convolution of number sequences, multiplication of polynomials, and the multiplication of integers (except for thecarry operation) are all the same operations. To obtain cyclic convolution, where the indices in [link] are all evaluated modulo $N$ , the polynomial multiplication in [link] is done modulo the polynomial $P\left(s\right)=s^N-1$ . This is seen by noting that $N=0$ mod $N$ , therefore, $s^N=1$ and the polynomial modulus is $s^N-1$ .

Polynomial reduction and the chinese remainder theorem

Residue reduction of one polynomial modulo another is defined similarly to residue reduction for integers. A polynomial $F\left(s\right)$ has a residue polynomial $R\left(s\right)$ modulo $P(s$ ) if, for a given $F\left(s\right)$ and $P\left(s\right)$ , a $Q\left(S\right)$ and $R\left(s\right)$ exist such that

with $degree\left\{R\right(s\left)\right\}<degree\left\{P\right(s\left)\right\}$ . The notation that will be used is

For example,

The concepts of factoring a polynomial and of primeness are an extension of these ideas for integers. For a givenallowed set of coefficients (values of $x\left(n\right)$ ), any polynomial has a unique factored representation

where the $F_i\left(s\right)$ are relatively prime. This is analogous to the fundamental theorem of arithmetic.

There is a very useful operation that is an extension of the integer Chinese Remainder Theorem (CRT) which says that if themodulus polynomial can be factored into relatively prime factors

then there exist two polynomials, $K_1\left(s\right)$ and $K_2\left(s\right)$ , such that any polynomial $F\left(s\right)$ can be recovered from its residues by

where $F_1$ and $F_2$ are the residues given by

and

if the order of $F\left(s\right)$ is less than $P\left(s\right)$ . This generalizes to any number of relatively prime factors of $P\left(s\right)$ and can be viewed as a means of representing $F\left(s\right)$ by several lower degree polynomials, $F_i\left(s\right)$ .

This decomposition of $F\left(s\right)$ into lower degree polynomials is the process used to break a DFT or convolution into several simpleproblems which are solved and then recombined using the CRT of [link] . This is another form of the “divide and conquer" or “organize and share"approach similar to the index mappings in Multidimensional Index Mapping .

One useful property of the CRT is for convolution. If cyclic convolution of $x\left(n\right)$ and $h\left(n\right)$ is expressed in terms of polynomials by