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