2.10 Filtering with the dft

Regular vs. circular convolution

To begin with, we are given the following two length-3 signals: $$x(n)=\{1, 2, 3\}$$ $$h(n)=\{1, 0, 2\}$$ We can zero-pad these signals so that we have the following discrete sequences: $$x(n)=\{, 0, 1, 2, 3, 0, \}$$ $$h(n)=\{, 0, 1, 0, 2, 0, \}$$ where $x(0)=1$ and $h(0)=1$ .

• Regular Convolution:
  $y(n)=\sum_{m=0}^2 x(m)h(n-m)$
  Using the above convolution formula (refer to the link if you need a review of convolution ), we can calculate the resulting value for $y(0)$ to $y(4)$ . Recall that because we have two length-3 signals, our convolved signal will be length-5.
  • $n=0$ $$\{, 0, 0, 0, 1, 2, 3, 0, \}$$ $$\{, 0, 2, 0, 1, 0, 0, 0, \}$$
    $y(0)=1\times 1+2\times 0+3\times 0=1$
  • $n=1$ $$\{, 0, 0, 1, 2, 3, 0, \}$$ $$\{, 0, 2, 0, 1, 0, 0, \}$$
    $y(1)=1\times 0+2\times 1+3\times 0=2$
  • $n=2$ $$\{, 0, 1, 2, 3, 0, \}$$ $$\{, 0, 2, 0, 1, 0, \}$$
    $y(2)=1\times 2+2\times 0+3\times 1=5$
  • $n=3$
    $y(3)=4$
  • $n=4$
    $y(4)=6$

• Circular Convolution:
  $\tilde{y}(n)=\sum_{m=0}^2 x(m)h({((nm))}_N)$
  And now with circular convolution our $h(n)$ changes and becomes a periodically extended signal:
  $h({((n))}_N)=\{, 1, 0, 2, 1, 0, 2, 1, 0, 2, \}$
  • $n=0$ $$\{, 0, 0, 0, 1, 2, 3, 0, \}$$ $$\{, 1, 2, 0, 1, 2, 0, 1, \}$$
    $\tilde{y}(0)=1\times 1+2\times 2+3\times 0=5$
  • $n=1$ $$\{, 0, 0, 0, 1, 2, 3, 0, \}$$ $$\{, 0, 1, 2, 0, 1, 2, 0, \}$$
    $\tilde{y}(1)=1\times 1+2\times 1+3\times 2=8$
  • $n=2$
    $\tilde{y}(2)=5$
  • $n=3$
    $\tilde{y}(3)=5$
  • $n=4$
    $\tilde{y}(4)=8$

illustrates the relationship between circular convolution and regularconvolution using the previous two figures: