<< Chapter < Page | Chapter >> Page > |
Since, $$\sum_{m=0}^{N-1} x(m)h(n-m)\mod N=y(n)\mathrm{is\; equivalent\; to}Y(k)=X(k)H(k)$$ $y(n)$ can be computed as $y(n)=\mathrm{IDFT}(\mathrm{DFT}(x(n))\mathrm{DFT}(h(n)))$
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 $N\ge L+M-1$
Choose shortest convenient $N()$ (usually smallest power-of-two greater than or equal to $L+M-1$ ) $$y(n)={\mathrm{IDFT}}_{N}({\mathrm{DFT}}_{N}(x(n)){\mathrm{DFT}}_{N}(h(n)))$$
Suppose $L$∞ , as in a real time filter application, or $(L, M)$ . There are efficient block methods for computing fast convolution.
Note that if a length- $M$ filter $h(n)$ is circularly convulved with a length- $N$ segment of a signal $x(n)$ ,
the first $M-1$ samples are wrapped around and thus is incorrect . However, for $M-1\le n\le N-1$ ,the convolution is linear convolution, so these samples are correct. Thus $N-M+1$ good outputs are produced for each length- $N$ circular convolution.The Overlap-Save Method: Break long signal into successive blocks of $N$ samples, each block overlapping the previous block by $M-1$ samples. Perform circular convolution of each block with filter $h(m)$ . Discard first $M-1$ points in each output block, and concatenate the remaining points to create $y(n)$ .
Computation cost for a length- $N$ equals $2^{n}$ FFT per output sample is (assuming precomputed $H(k)$ ) 2 FFTs and $N$ multiplies $$\frac{2\frac{N}{2}\log_{2}N+N}{N-M+1}=\frac{N(\log_{2}N+1)}{N-M+1}\mathrm{complex\; multiplies}$$ $$\frac{2N\log_{2}N}{N-M+1}=\frac{2N\log_{2}N}{N-M+1}\mathrm{complex\; adds}$$
Compare to $M$ mults, $M-1$ adds per output point for direct method. For a given $M$ , optimal $N$ can be determined by finding $N$ minimizing operation counts. Usualy, optimal $N$ is $4M\le {N}_{\mathrm{opt}}\le 8M$ .
Zero-pad length- $L$ blocks by $M-1$ samples.
Add successive blocks, overlapped by $M-1$ samples, so that the tails sum to produce the complete linear convolution.
Computational Cost: Two length $N=L+M-1$ FFTs and $M$ mults and $M-1$ adds per $L$ output points; essentially the sames as OLS method.Notification Switch
Would you like to follow the 'Pdf generation problem modules' conversation and receive update notifications?