Polynomials are important in digital signal processing because calculating the DFT can be viewed as a polynomial evaluation problem and convolution can be viewed as polynomial multiplication 1, 5. Indeed, this is the basis for the important results of Winograd discussed in Winograd’s Short DFT Algorithms. A length-N signal x(n) will be represented by an N–1 degree polynomial X(s) defined by
This polynomial X(s) is a single entity with the coefficients being the values of x(n). It is somewhat similar to the use of matrix or vector notation to efficiently represent signals which allows use of new mathematical tools.
The convolution of two finite length sequences, x(n) and h(n), gives an output sequence defined by
n=0,1,2,⋯,2N–1 where h(k)=0 for k<0. This is exactly the same operation as calculating the coefficients when multiplying two polynomials. Equation Equation 4.2 is the same as
In fact, convolution of number sequences, multiplication of polynomials, and the multiplication of integers (except for the carry operation) are all the same operations. To obtain cyclic convolution, where the indices in Equation 4.2 are all evaluated modulo N, the polynomial multiplication in Equation 4.3 is done modulo the polynomial P(s)=sN–1. This is seen by noting that N=0 mod N, therefore, sN=1 and the polynomial modulus is sN–1.
Residue reduction of one polynomial modulo another is defined similarly to residue reduction for integers. A polynomial F(s) has a residue polynomial R(s) modulo P(s) if, for a given F(s) and P(s), a Q(S) and R(s) exist such that
with degree{R(s)}<degree{P(s)}. 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 given allowed set of coefficients (values of x(n)), any polynomial has a unique factored representation
where the Fi(s) 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 the modulus polynomial can be factored into relatively prime factors
then there exist two polynomials, K1(s) and K2(s), such that any polynomial F(s) can be recovered from its residues by
where F1 and F2 are the residues given by
and
if the order of F(s) is less than P(s). This generalizes to any number of relatively prime factors of P(s) and can be viewed as a means of representing F(s) by several lower degree polynomials, Fi(s).
This decomposition of F(s) into lower degree polynomials is the process used to break a DFT or convolution into several simple problems which are solved and then recombined using the CRT of Equation 4.9. 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(n) and h(n) is expressed in terms of polynomials by
where P(s)=sN–1, and if P(s) is factored into two relatively prime factors P=P1P2, using residue reduction of H(s) and X(s) modulo P1 and P2, the lower degree residue polynomials can be multiplied and the results recombined with the CRT. This is done by
where
and K1 and K2 are the CRT coefficient polynomials from Equation 4.9. 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(s) at s=x, F(s) is reduced modulo s–x.
This is easily seen from the definition in Equation 4.4
Evaluating s=x gives R(s)=F(x) which is a constant. For the DFT this becomes
Details of the polynomial algebra useful in digital signal processing can be found in 1, 4, 5.
The Z-transform of a number sequence x(n) is defined as
which is the same as the polynomial description in Equation 4.1 but with a negative exponent. For a finite length-N sequence Equation 4.18 becomes
This N–1 order polynomial takes on the values of the DFT of x(n) when evaluated at
which gives
In terms of the positive exponent polynomial from Equation 4.1, the DFT is
where
is an Nth root of unity (raising W to the Nth power gives one). The N values of the DFT are found from X(s) evaluated at the N Nth roots of unity which are equally spaced around the unit circle in the complex s plane.
One method of evaluating X(z) is the so-called Horner's rule or nested evaluation. When expressed as a recursive calculation, Horner's rule becomes the Goertzel algorithm which has some computational advantages especially when only a few values of the DFT are needed. The details and programs can be found in 7, 2 and The DFT as Convolution or Filtering: Goertzel's Algorithm (or A Better DFT Algorithm)
Another method for evaluating X(s) is the residue reduction
modulo 
as shown in Equation 4.17. Each evaluation requires
N multiplications and therefore, N2 multiplications for the N
values of C(k).
A considerable reduction in required arithmetic can be achieved if some operations can be shared between the reductions for different values 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 Equation 4.25.
The N values of the DFT are values of X(s) evaluated at s equal to the N roots of the polynomial P(s)=sN–1 which are Wk. First, assuming N is even, factor P(s) as
X(s) is reduced modulo thes