<< Chapter < Page | Chapter >> Page > |
Since, can be computed as
DFT produces cicular convolution. For linear convolution, we must zero-pad sequences so that circular wrap-around alwayswraps over zeros.
To achieve linear convolution using fast circular convolution, we must use zero-padded DFTs of length
Choose shortest convenient (usually smallest power-of-two greater than or equal to )
Suppose , as in a real time filter application, or . There are efficient block methods for computing fast convolution.
Note that if a length-
filter
is circularly convulved with a
length-
segment of a signal
,
The Overlap-Save Method: Break long signal into successive
blocks of
samples, each block overlapping the previous block by
samples. Perform circular convolution of each
block with filter
. Discard first
points in each output block, and concatenate the remaining
points to create
.
Computation cost for a length- equals FFT per output sample is (assuming precomputed ) 2 FFTs and multiplies
Compare to mults, adds per output point for direct method. For a given , optimal can be determined by finding minimizing operation counts. Usualy, optimal is .
Zero-pad length-
blocks by
samples.
Add successive blocks, overlapped by
samples, so that the tails sum to produce the
complete linear convolution.
Notification Switch
Would you like to follow the 'Pdf generation problem modules' conversation and receive update notifications?