Residue reduction of one polynomial modulo another is
defined similarly to residue reduction for integers. A polynomial
F(s)F(s) has a residue polynomial R(s)R(s) modulo P(sP(s) if, for a given
F(s)F(s) and P(s)P(s), a Q(S)Q(S) and R(s)R(s) exist such that
F
(
s
)
=
Q
(
s
)
P
(
s
)
+
R
(
s
)
F
(
s
)
=
Q
(
s
)
P
(
s
)
+
R
(
s
)
(4)with degree{R(s)}<degree{P(s)}degree{R(s)}<degree{P(s)}. The notation that will
be used is
R
(
s
)
=
(
(
F
(
s
)
)
)
P
(
s
)
R
(
s
)
=
(
(
F
(
s
)
)
)
P
(
s
)
(5)For example,
(
s
+
1
)
=
(
(
s
4
+
s
3

s

1
)
)
(
s
2

1
)
(
s
+
1
)
=
(
(
s
4
+
s
3

s

1
)
)
(
s
2

1
)
(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)x(n)), any polynomial has a unique factored representation
F
(
s
)
=
∏
i
=
1
M
F
i
(
s
)
k
i
F
(
s
)
=
∏
i
=
1
M
F
i
(
s
)
k
i
(7)where the Fi(s)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
)
=
P
1
(
s
)
P
2
(
s
)
P
(
s
)
=
P
1
(
s
)
P
2
(
s
)
(8)then there exist two polynomials, K1(s)K1(s) and K2(s)K2(s), such that any
polynomial F(s)F(s) can be recovered from its residues by
F
(
s
)
=
K
1
(
s
)
F
1
(
s
)
+
K
2
(
s
)
F
2
(
s
)
mod
P
(
s
)
F
(
s
)
=
K
1
(
s
)
F
1
(
s
)
+
K
2
(
s
)
F
2
(
s
)
mod
P
(
s
)
(9)where F1F1 and F2F2 are the residues given by
F
1
(
s
)
=
(
(
F
(
s
)
)
)
P
1
(
s
)
F
1
(
s
)
=
(
(
F
(
s
)
)
)
P
1
(
s
)
(10)and
F
2
(
s
)
=
(
(
F
(
s
)
)
)
P
2
(
s
)
F
2
(
s
)
=
(
(
F
(
s
)
)
)
P
2
(
s
)
(11)if the order of F(s)F(s) is less than P(s)P(s). This generalizes to any
number of relatively prime factors of P(s)P(s) and can be viewed as a
means of representing F(s)F(s) by several lower degree polynomials,
Fi(s)Fi(s).
This decomposition of F(s)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 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)x(n) and h(n)h(n) is expressed in terms of
polynomials by
Y
(
s
)
=
H
(
s
)
X
(
s
)
mod
P
(
s
)
Y
(
s
)
=
H
(
s
)
X
(
s
)
mod
P
(
s
)
(12)where P(s)=sN1P(s)=sN1, and if P(s)P(s) is factored into two
relatively prime factors P=P1P2P=P1P2, using residue reduction of
H(s)H(s) and X(s)X(s) modulo P1P1 and P2P2, the lower degree residue
polynomials can be multiplied and the results recombined with the
CRT. This is done by
Y
(
s
)
=
(
(
K
1
H
1
X
1
+
K
2
H
2
X
2
)
)
P
Y
(
s
)
=
(
(
K
1
H
1
X
1
+
K
2
H
2
X
2
)
)
P
(13)where
H
1
=
(
(
H
)
)
P
1
,
X
1
=
(
(
X
)
)
P
1
,
H
2
=
(
(
H
)
)
P
2
,
X
2
=
(
(
X
)
)
P
2
H
1
=
(
(
H
)
)
P
1
,
X
1
=
(
(
X
)
)
P
1
,
H
2
=
(
(
H
)
)
P
2
,
X
2
=
(
(
X
)
)
P
2
(14)and K1K1 and K2K2 are the CRT coefficient polynomials from
Equation 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)F(s) at s=xs=x,
F(s)F(s) is reduced modulo sxsx.
F
(
x
)
=
(
(
F
(
s
)
)
)
s

x
F
(
x
)
=
(
(
F
(
s
)
)
)
s

x
(15)This is easily seen from the definition in Equation 4
F
(
s
)
=
Q
(
s
)
(
s

x
)
+
R
(
s
)
F
(
s
)
=
Q
(
s
)
(
s

x
)
+
R
(
s
)
(16)Evaluating s=xs=x gives R(s)=F(x)R(s)=F(x) which is a constant. For
the DFT this becomes
C
(
k
)
=
(
(
X
(
s
)
)
)
s

W
k
C
(
k
)
=
(
(
X
(
s
)
)
)
s

W
k
(17)Details of the polynomial algebra useful in digital signal
processing can be found in [1], [4], [5].
"The Fast Fourier Transform (FFT) is a landmark algorithm used in fields ranging from signal processing to highperformance computing. First popularized by two American scientists in 1965, the […]"