Circular vs linear convolution

Convolve 1, 2, 3, 4 with 1, 1, 1 directly, and through a DFT of $N$ points. Watch the tail wrap onto the start as $N$ shrinks.

Two convolutions, one product

In Discrete convolution (5.2) you slid a flipped copy of $h$ along $x$ and added up the overlaps. From here on I call that linear convolution, written $y=x*h$. If $x$ has $N_x$ samples and $h$ has $N_h$, the output $y$ has $N_x+N_h-1$ samples.

The DFT offers a shortcut. Pad $x$ and $h$ with zeros to the same length $N$, take the DFT of each, multiply the two spectra bin by bin, and invert. What comes back is called $y_\text{circ}[n]$. It is not always $y[n]$.

The reason is in Sampling the spectrum (13.1). By the convolution rule of Properties of the DTFT (12.3), the DTFT of $y$ is $Y(e^{j\Omega})=X(e^{j\Omega})H(e^{j\Omega})$. The products $X[k]H[k]$ are $N$ samples of that spectrum. And $N$ samples of a spectrum describe the signal repeated every $N$ samples, with overlapping copies added. So $y_\text{circ}$ is $y$ repeated every $N$ samples, one period kept.

If $N$ is at least the length of $y$, the copies do not touch and you see $y$ followed by zeros. If $N$ is shorter, the copies overlap and the tail of $y$ lands on top of its start. This operation has a name from Properties of the DFT (13.3): $y_\text{circ}=x\circledast_N h$, the $N$-point circular convolution.

The tail wraps round

Think of a circular parking garage with $N$ bays. Cars arrive in order, and the first $N$ park in bays 0 to $N-1$. A car that arrives after the last bay is taken goes round to the start and parks in a bay that is already occupied. In the convolution, parking in an occupied bay means adding to it.

The picture at the top of the page convolves $x=1,2,3,4$ with $h=1,1,1$, so $y$ is 1, 3, 6, 9, 7, 4. Its clip stops at four DFT lengths:

• $N=8$: room for all 6 samples, plus 2 zeros. Circular and linear agree: 1, 3, 6, 9, 7, 4.
• $N=6=4+3-1$: just enough room. Still equal.
• $N=5$: the last sample, 4, has no room and wraps onto $n=0$: $1+4=5$. Output 5, 3, 6, 9, 7.
• $N=4$: the last two wrap: $1+7=8$ and $3+4=7$. Output 8, 7, 6, 9. The DFT product gave a circular convolution; pad to $N\ge N_x+N_h-1$ and nothing wraps.

When the clip ends, drag the dashed line, or use the arrow keys, to set the DFT length $N$ from 4 to 10. Notice that the smallest value, 4, is where both sequences just fit. Move up one step at a time and watch the wrapped samples travel back out past the dashed line, until “samples wrapped” reads “none”.

One more thing to notice. Each circular output adds up to 30, the same total as the linear one. Wrapping moves samples; it never loses any.

The wrap rule, in symbols, is

Here $r$ runs over all whole numbers; at most a few terms are not zero. At $N=5$, $n=0$ collects $y[0]$ and $y[5]$, which is $1+4=5$. If $N\ge N_x+N_h-1$, only $r=0$ contributes inside $0\le n\le N-1$, and $y_\text{circ}=y$ followed by zeros.

The recipe

The quickest way to see the shortcut working is to follow one pass at $N=8$, the first stop of the clip. Each strip below shows the sizes of a sequence of eight numbers. The first three are bins $k=0$ to $7$ and the last is samples $n=0$ to $7$.

The sizes multiply bin by bin, and the angles add; the figure shows only the sizes. Bin 0 is the easiest check. $X[0]=10$ is the sum of $x$, $H[0]=3$ is the sum of $h$, and $X[0]H[0]=30$ is the sum of $y$.

Written out for two of the bins, $X[1]\approx-0.414-7.243\mathrm{j}$ and $H[1]\approx1.707-1.707\mathrm{j}$. That is the whole algorithm. In words:

1. Pad $x$ and $h$ with zeros to length $N$.
2. Take the DFT of each.
3. Multiply the two spectra, bin by bin.
4. Take the inverse DFT of the product.

Choosing N

Padding to $N\ge N_x+N_h-1$ leaves room for all of $y$, so nothing wraps and circular equals linear. Here that is $4+3-1=6$, which is why $N=6$ already agrees. Below that, the wrapped samples add onto the start; this is time aliasing, the mirror of the frequency aliasing in Sampling and aliasing (10.1).

Below $\max(N_x,N_h)$ the DFT would not even hold the whole of $x$ or $h$, so that question never arises. For a longer example, take 1000 samples through a filter of 101 taps. You need $N\ge1000+101-1=1100$, and the next power of two is 2048, the usual choice for the FFT.

Why bother? Direct convolution needs about $N_xN_h$ multiplications, which is $1000\times101=101{,}000$ here. The recipe needs three DFTs of length $N$, and the FFT of The FFT (14.1) makes each of those fast. This is fast convolution. For signals too long to transform in one piece, Fast convolution (14.3) does it in blocks.

Worked example

Take $x=1,2,3,4$ and $h=1,1,1$, as in the instrument. The linear output is $y=1,3,6,9,7,4$, and it sums to 30.

Now compute the circular output with $N=5$ by wrapping. Only $y[5]=4$ lies at or beyond $N$, so it adds onto $n=0$:

The inverse DFT of $X[k]H[k]$ with both padded to 5 gives the same numbers. The total is $5+3+6+9+7=30$, as it must be.

Where you’ll meet this

Filters applied through an FFT, such as an audio reverb or an image blur, use this recipe and must choose $N$ with the rule above. A circular result also appears on purpose: a periodic signal passed through a filter gives a circular convolution, with no padding at all.

Reference card