Circular Convolution Circular Convolution
Linear Convolution
The output of an LTI system is the linear convolution of the input $x[n]$ and the impulse response $h[n]$ of the system:
\[y[n] = x[n] * h[n] = \sum_{m=-\infty}^{\infty} x[m] \, h[n-m] \tag{1}\]Each term of the sum comes from one sample of the input. Suppose a single sample of size $1$ enters the system at $n=0$. The output is then $h[n]$. A sample $x[m]$ has size $x[m]$ and enters at $n=m$, so the output is $x[m]h[n-m]$: the same shape, multiplied by $x[m]$ and moved $m$ samples later.
Adding these up for every sample gives the output $y[n]$.
The samples of $x[m]$ enters the system one at a time. Each response has the color of its sample, and the responses add up to $y[n]$.
In the example above, $x[n]=\lbrace2,1,3\rbrace$ and $h[n]=\lbrace1,1\rbrace$ give $y[n]=\lbrace2,3,4,3\rbrace$. The output is longer than the input: the last sample enters at $n=$, but its response continues until $n=$. In general, if the two signals have lengths $L_x$ and $L_h$, their linear convolution has length $L_x+L_h-1$.
Multiplying Two DFTs
In the DTFT, convolution in time becomes multiplication in frequency:
\[x[n] * h[n] \quad\longleftrightarrow\quad X(e^{j\omega}) \, H(e^{j\omega})\]The DFT is a sampled version of the DTFT. So can we compute a convolution by multiplying two DFTs?
Let us try this with the two signals from the example above, using a $3$-point DFT. We add one zero to $h[n]$, so that $h[n]=\lbrace1,1,0\rbrace$ and both signals have length $3$. We then task the two DFTs, multiply them value by value, and return to the time domain with the synthesis equation.
The results is
\[y[n] = \{4,3,5\}\]This is not the linear convolution $\lbrace2,3,4,3\rbrace$. It has length $3$ instead of $4$, and its first value is $5$ instead of $2$. Notice that $5=2+3$: the first value is the sum of the first and last values of the linear convolution.
The reason is that the DFT treats a signal of $N$ samples as if it repeated every $N$ samples. To see how this leads to the result above, let us convolve a repeating signal.
Circular Convolution
Convolution of a Repeating Signal
The DFT treats a signal of $N$ samples as one period of a signal that repeats every $N$ samples. So let us repeat $x[n]=\lbrace 2,1,3\rbrace$ every $3$ samples and convolve it with $h[n]=\lbrace 1,1\rbrace$ in the ordinary way.
For this $h[n]$, the convolution sum has only two terms:
\[y[n] = x[n] + x[n-1]\]Each output sample is the current input sample plus the one before it.
| $n=-1$ | $n=0$ | $n=1$ | $n=2$ | $n=3$ | $n=4$ | $n=5$ | |
|---|---|---|---|---|---|---|---|
| $x[n]$ | $3$ | $2$ | $1$ | $3$ | $2$ | $1$ | $3$ |
| $y[n]$ | - | $2+3=5$ | $1+2=3$ | $3+1=4$ | $2+3=5$ | $1+2=3$ | $3+1=4$ |
The output also repeats every $3$ samples, and one period of it is $\lbrace 5,3,4\rbrace$. This is exactly what we obtained by multiplying the two DFTs.
Look at $y[0]=x[0]+x[-1]$. If the signal did not repeat, $x[-1]$ would be $0$ and $y[0]$ would be $2$, as in the linear convolution. Because the signal repeats, $x[-1]$ is the last sample of the previous period, which is $3$. So $y[0]=2+3=5$.
Circular convolution is ordinary convolution applied to a signal that repeats. The response to the last sample of one period continues into the next period, where it is added to the first sample.
Every period is the same, so we can describe this inside a single period: the part of the response that goes beyond the last sample comes back in at the first sample. This is why the result is said to wrap around.
Definition
In a signal that repeats every $N$ samples, the sample at any index is equal to one of the samples at $n=0,\dots,N-1$. For example, $x[-1]=x[2]$ when $N=3$. The matching index is the remainder after dividing by $N$, written $n \bmod N$:
\[x[n] = x[n \bmod N]\]Using this index in the convolution sum, and adding over one period only, gives the circular convolution of two signals of length $N$:
\[x[n] \circledast h[n] = \sum_{m=0}^{N-1} x[m] \, h[(n-m) \bmod N]\]Two things differ from linear convolution. The index $n-m$ is taken modulo $N$, and the sum runs over $N$ samples only. As a result, circular convolution always has length $N$.
The same input with $N=3$. The output has only the samples $n=0,1,2$, so the part of the last copy that falls past $n=2$ wraps around and is added at $n=0$.
This is the convolution property of the DFT:
\[x[n] \circledast h[n] \quad\longleftrightarrow\quad X[k] \, H[k]\]Multiplying two DFTs gives the circular convolution of the two signals, not their linear convolution.
Why does circular convolution become multiplication?
Apply the DFT analysis equation to the circular convolution and change the order of the two sums:
\[\begin{aligned} \sum_{n=0}^{N-1} \left( \sum_{m=0}^{N-1} x[m] \, h[(n-m) \bmod N] \right) e^{-j\frac{2\pi k}{N}n} &= \sum_{m=0}^{N-1} x[m] \left( \sum_{n=0}^{N-1} h[(n-m) \bmod N] \, e^{-j\frac{2\pi k}{N}n} \right) \end{aligned}\]The sum in parentheses is the DFT of $h[n]$ circularly shifted by $m$. By the time shift property of the DFT, it is $e^{-j(2\pi k/N)m}H[k]$. Therefore, the right side is
\[H[k] \sum_{m=0}^{N-1} x[m] e^{-j\frac{2\pi k}{N}m} = X[k] \, H[k]\]Linear Convolution Using the DFT
In our example, the circular convolution $\lbrace 5,3,4\rbrace$ is the linear convolution $\lbrace 2,3,4,3\rbrace$ with its last value added to the first. The same holds in general: the circular convolution is the linear convolution repeated every $N$ samples and added together. If we write $y_l[n]$ for the linear convolution and $y_c[n]$ for the circular one,
\[y_c[n] = \sum_{r=-\infty}^{\infty} y_l[n-rN] \,,\qquad 0\le n\le N-1\]This is the same equation as the one for $\tilde{x}[n]$ in the DFT post. When the copies overlap, we get the time-domain aliasing we saw there, now in the result of a convolution.
Why is circular convolution the linear convolution wrapped around?
The DFT values $X[k]$ and $H[k]$ are samples of the DTFTs $X(e^{j\omega})$ and $H(e^{j\omega})$. So their product $X[k]H[k]$ consists of $N$ samples of $X(e^{j\omega})H(e^{j\omega})$, which is the DTFT of the linear convolution $y_l[n]$.
As shown in the DFT post, returning to the time domain from $N$ samples of a DTFT gives the signal repeated every $N$ samples. Here that signal is $y_l[n]$.
The copies do not overlap if they are far enough apart. The linear convolution has length $L_x+L_h-1$, so this is the case when
\[N \ge L_x+L_h-1\]Then nothing wraps around, and the circular convolution is equal to the linear convolution. So we can compute a linear convolution with the DFT if we make $N$ large enough by zero-padding both signals.
- Choose $N \ge L_x+L_h-1$.
- Add zeros to the end of $x[n]$ and $h[n]$ so that both have length $N$.
- Compute the $N$-point DFTs $X[k]$ and $H[k]$.
- Multiply them: $Y[k]=X[k]H[k]$.
- Return to the time domain with the synthesis equation.
[Example] Linear convolution with $N=4$
For $x[n]=\lbrace 2,1,3\rbrace$ and $h[n]=\lbrace 1,1\rbrace$, we need $N\ge 3+2-1=4$. After zero-padding,
\[x[n] = \{2,1,3,0\} \,,\qquad h[n] = \{1,1,0,0\}\]Their circular convolution with $N=4$ is
\[\begin{aligned} y[0] &= 2\cdot 1 + 1\cdot 0 + 3\cdot 0 + 0\cdot 1 = 2 \\ y[1] &= 2\cdot 1 + 1\cdot 1 + 3\cdot 0 + 0\cdot 0 = 3 \\ y[2] &= 2\cdot 0 + 1\cdot 1 + 3\cdot 1 + 0\cdot 0 = 4 \\ y[3] &= 2\cdot 0 + 1\cdot 0 + 3\cdot 1 + 0\cdot 1 = 3 \end{aligned}\]The result $\lbrace 2,3,4,3\rbrace$ is the linear convolution. The zeros we added leave room for the last value, so nothing wraps around.
Why take this detour instead of computing the convolution directly? For long signals, the direct sum needs about $L_x L_h$ multiplications. The DFT can be computed much faster than that with an algorithm called the Fast Fourier Transform (FFT), which makes this method the faster one for long signals.