Signals1
Polynomials are important in digital signal processing because cal-
culating the DFT can be viewed as a polynomial evaluation prob-
lem and convolution can be viewed as polynomial multiplication
[27], [261]. Indeed, this is the basis for the important results of
Winograd discussed in Winograd’s Short DFT Algorithms (Chap-
ter 7). A length-N signal x (n) will be represented by an N − 1
degree polynomial X (s) defined by
N−1
X (s) = ∑ x(n) sn
(4.1)
n=0
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),
1This content is available online at <http://cnx.org/content/m16327/1.8/>.
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
27
CHAPTER 4. POLYNOMIAL
28
DESCRIPTION OF SIGNALS
gives an output sequence defined by
N−1
y (n) = ∑ x(k) h(n − k)
(4.2)
k=0
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 (4.2) is the same as
Y (s) = X (s) H (s)
(4.3)
In fact, convolution of number sequences, multiplication of poly-
nomials, and the multiplication of integers (except for the carry
operation) are all the same operations. To obtain cyclic convolu-
tion, where the indices in (4.2) are all evaluated modulo N, the
polynomial multiplication in (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.
4.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 (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
F (s) = Q (s) P (s) + R (s)
(4.4)
with degree{R (s)} < degree{P (s)}. The notation that will be
used is
R (s) = ((F (s)))P(s)
(4.5)
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
29
For example,
(s + 1) =
s4 + s3 − s − 1
(s2−1)
(4.6)
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
M
F (s) = ∏Fi(s)ki
(4.7)
i=1
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
P (s) = P1 (s) P2 (s)
(4.8)
then there exist two polynomials, K1 (s) and K2 (s), such that any
polynomial F (s) can be recovered from its residues by
F (s) = K1 (s) F1 (s) + K2 (s) F2 (s) mod P (s)
(4.9)
where F1 and F2 are the residues given by
F1 (s) = ((F (s)))P1(s)
(4.10)
and
F2 (s) = ((F (s)))P2(s)
(4.11)
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).
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
CHAPTER 4. POLYNOMIAL
30
DESCRIPTION OF SIGNALS
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
(4.9). This is another form of the “divide and conquer" or “organize
and share" approach similar to the index mappings in Multidimen-
sional Index Mapping (Chapter 3).
One useful property of the CRT is for convolution. If cyclic con-
volution of x (n) and h (n) is expressed in terms of polynomials by
Y (s) = H (s) X (s) mod P (s)
(4.12)
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
Y (s) = ((K1H1X1 + K2H2X2))
(4.13)
P
where
H1 = ((H)) , X
,
H
P
1
=
((X ))
2
=
(4.14)
1
P1
((H)) ,
X
P
2 = ((X ))
2
P2
and K1 and K2 are the CRT coefficient polynomials from (4.9).
This allows two shorter convolutions to replace one longer one.
Another property of residue reduction that is useful in DFT calcu-
lation is polynomial evaluation. To evaluate F (s) at s = x, F (s) is
reduced modulo s − x.
F (x) = ((F (s)))
(4.15)
s−x
This is easily seen from the definition in (4.4)
F (s) = Q (s) (s − x) + R (s)
(4.16)
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
31
Evaluating s = x gives R (s) = F (x) which is a constant. For the
DFT this becomes
C (k) = ((X (s)))s−Wk
(4.17)
Details of the polynomial algebra useful in digital signal process-
ing can be found in [27], [233], [261].
4.2 The DFT as a Polynomial Evaluation
The Z-transform of a number sequence x (n) is defined as
∞
X (z) = ∑ x(n) z−n
(4.18)
n=0
which is the same as the polynomial description in (4.1) but with a
negative exponent. For a finite length-N sequence (4.18) becomes
N−1
X (z) = ∑ x(n) z−n
(4.19)
n=0
X (z) = x (0) + x (1) z−1 + x (2) z−2 + · + x (N − 1) z−N+1 (4.20)
This N − 1 order polynomial takes on the values of the DFT of
x (n) when evaluated at
z = e j2πk/N
(4.21)
which gives
N−1
C (k) = X (z) |
x (n) e− j2πnk/N
(4.22)
z=e j2πk/N = ∑
n=0
In terms of the positive exponent polynomial from (4.1), the DFT
is
C (k) = X (s) |s=Wk
(4.23)
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
CHAPTER 4. POLYNOMIAL
32
DESCRIPTION OF SIGNALS
where
W = e− j2π/N
(4.24)
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
[272], [61] and The DFT as Convolution or Filtering: Goertzel’s
Algorithm (or A Better DFT Algorithm) (Section 5.3: Goertzel’s
Algorithm (or A Better DFT Algorithm))
Another method for evaluating X (s) is the residue reduction mod-
ulo s −W k as shown in (4.17). Each evaluation requires N mul-
tiplications and therefore, N2 multiplications for the N values of
C (k).
C (k) = ((X (s)))(s−Wk)
(4.25)
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
(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 W k. First,
assuming N is even, factor P (s) as
P (s) = sN − 1 = P1 (s) P2 (s) = sN/2 − 1
sN/2 + 1
(4.26)
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
33
X (s) is reduced modulo these two factors to give two residue poly-
nomials, X1 (s) and X2 (s). This process is repeated by factoring P1
and further reducing X1 then factoring P2 and reducing X2. This
is continued until the factors are of first degree which gives the
desired DFT values as in (4.25). This is illustrated for a length-8
DFT. The polynomial whose roots are W k, factors as
P (s) = s8 − 1
(4.27)
= s4 − 1
s4 + 1
(4.28)
=
s2 − 1
s2 + 1
s2 − j
s2 + j
(4.29)
= [(s − 1) (s + 1) (s − j) (s + j)] [(s − a) (s + a) (s − ja) (
(4.30) s + ja)]
where a2 = j. Reducing X (s) by the first factoring gives two third
degree polynomials
X (s) = x0 + x1s + x2s2 + ... + x7s7
(4.31)
gives the residue polynomials
X1 (s)
=
((X (s)))
=
(
(
x
s4−1)
0 + x4)
+
(4.32)
(x1 + x5) s + (x2 + x6) s2 + (x3 + x7) s3
X2 (s)
=
((X (s)))
=
(
(
x
s4+1)
0 − x4)
+
(4.33)
(x1 − x5) s + (x2 − x6) s2 + (x3 − x7) s3
Two more levels of reduction are carried out to finally give the
DFT. Close examination shows the resulting algorithm to be the
decimation-in-frequency radix-2 Cooley-Tukey FFT [272], [61].
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
CHAPTER 4. POLYNOMIAL
34
DESCRIPTION OF SIGNALS
Martens [227] has used this approach to derive an efficient DFT
algorithm.
Other algorithms and types of FFT can be developed using polyno-
mial representations and some are presented in the generalization
in DFT and FFT: An Algebraic View (Chapter 8).
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>