Information Technology Reference
In-Depth Information
multiplication the polynomials
a
(
2
)
and
b
(
2
)
represent binary numbers; convolution is related
to the computation of their product.
The
convolution theorem
is one of the most important applications of the DFT. It
demonstrates that convolution, which appears to require
O
(
n
2
)
operations when
n
=
m
,
can in fact be computed by a circuit with
O
(
n
)
operations plus a small multiple of the number
needed to compute the DFT and its inverse.
THEOREM
6.7.2
Let
R
=(
R
,
+
,
∗
,
0
,
1
)
be a commutative ring and let
a
,
b
∈ R
n
.L t
F
2
n
:
R
2
n
R
2
n
and
F
−
1
2
n
:
R
2
n
R
2
n
be the
2
n
-point DFT and its inverse over
R
.Let
→
→
F
2
n
(
a
)
F
2
n
(
b
)
denote the
2
n
-tuple obtained from the term-by-term product of the components
of
F
2
n
(
a
)
and
F
2
n
(
b
)
. Then, the convolution
a
×
⊗
b
satisfies the following identity:
b
=
F
−
1
a
⊗
2
n
(
F
2
n
(
a
)
×
F
2
n
(
b
))
Proof
The
n
-point DFT
F
n
:
R
n
R
n
→
transforms the
n
-tuple of coefficients
a
of the
polynomial
p
(
x
)
of degree
n
1intothe
n
-tuple
f
=
F
n
(
a
)
. In fact, the
r
th component
of
f
,
f
r
, is the value of the polynomial
p
(
x
)
at the
r
th of the
n
roots of unity, namely
f
r
=
p
(
ω
r
)
.The
n
-point inverse DFT
F
−
1
−
R
n
invertstheprocessthrougha
similar computation. If
q
(
x
)
is the polynomial of degree
n
:
R
n
→
n
1whose
l
th coefficient is
f
l
/n
,
then the
s
th component of the inverse DFT on
f
,namely
F
−
n
(
f
)
,is
a
s
=
q
(
ω
−s
)
.
As stated above, to compute the convolution of
n
-tuples
a
and
b
it suffices to compute
the coefficients of the product polynomial
c
(
x
)=
a
(
x
)
b
(
x
)
. Since the product
c
(
x
)
is of
degree 2
n
−
−
2, we can treat it as a polynomial of degree 2
n
−
1 and take the 2
n
-point
DFT,
F
2
n
, of it and its inverse,
F
−
1
2
n
, of the result. This seemingly futile process leads to an
efficient algorithm for convolution. Since the DFT is obtained by evaluating a polynomial
Figure 6.9
The DAG associated with the straight-line program resulting from the application
of the FFT to the convolution theorem with sequences of length 8.
Search WWH ::
Custom Search