Eight-point circular convolution versus linear convolution: 22-Elec-B1 Digital Signal Processing, May 2018, Q2

Question 2: Eight-point circular convolution versus linear convolution (12 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

[Figure not reproduced: Figure 2.1 — the two exam sequences redrawn from the source figure: $x_1[n]$ occupies $0 \le n \le 7$ and $x_2[n]$ occupies $1 \le n \le 3$. See the official exam paper.]

Given.

$n$	0	1	2	3	4	5	6	7
$x_1[n]$	1	2	1	1	2	1	1	2
$x_2[n]$	0	1	3	2	0	0	0	0

Both sequences are zero outside the interval shown, and the circular convolution length is $N = 8$.

Find. The eight-point circular convolution $x_3[n]$, the support end-points and the sample values of the linear convolution $x_4[n]$, and a demonstration that aliasing $x_4$ with period 8 reproduces $x_3$.

Approach. Use the circular convolution theorem — a product of DFTs corresponds to a circular convolution — in its time-domain form, exploiting the fact that $x_2$ has only three non-zero taps; then compute the linear convolution and fold it modulo 8.

State the theorem in the form that does the work. The circular convolution theorem says that if $X_1[k]$ and $X_2[k]$ are the eight-point DFTs of the two sequences, then $$X_3[k] = X_1[k]\,X_2[k] \quad\Longleftrightarrow\quad x_3[n] = \sum_{m=0}^{7} x_1[m]\,x_2\big[((n-m))_8\big].$$ Multiplying two eight-point DFTs by hand is far more work than evaluating the right-hand sum, and the theorem is precisely the licence to use one in place of the other.
Collapse the sum using the three non-zero taps of $x_2$. Because $x_2[1] = 1$, $x_2[2] = 3$, $x_2[3] = 2$ and $x_2$ is zero elsewhere, the circular sum reduces to three circularly shifted copies of $x_1$: $$x_3[n] = 1\cdot x_1\big[((n-1))_8\big] + 3\cdot x_1\big[((n-2))_8\big] + 2\cdot x_1\big[((n-3))_8\big].$$ Every index is taken modulo 8, which is the only difference between this and the ordinary linear convolution.
Evaluate sample by sample. Reading $x_1$ periodically, $x_1 = [\,1,2,1,1,2,1,1,2\,]$ repeated: $$\begin{aligned} x_3[0] &= x_1[7] + 3x_1[6] + 2x_1[5] = 2 + 3 + 2 = 7, \\ x_3[1] &= x_1[0] + 3x_1[7] + 2x_1[6] = 1 + 6 + 2 = 9, \\ x_3[2] &= x_1[1] + 3x_1[0] + 2x_1[7] = 2 + 3 + 4 = 9, \\ x_3[3] &= x_1[2] + 3x_1[1] + 2x_1[0] = 1 + 6 + 2 = 9, \\ x_3[4] &= x_1[3] + 3x_1[2] + 2x_1[1] = 1 + 3 + 4 = 8, \\ x_3[5] &= x_1[4] + 3x_1[3] + 2x_1[2] = 2 + 3 + 2 = 7, \\ x_3[6] &= x_1[5] + 3x_1[4] + 2x_1[3] = 1 + 6 + 2 = 9, \\ x_3[7] &= x_1[6] + 3x_1[5] + 2x_1[4] = 1 + 3 + 4 = 8. \end{aligned}$$ Hence $$\boxed{\,x_3[n] = \{\,7,\;9,\;9,\;9,\;8,\;7,\;9,\;8\,\}, \qquad n = 0,1,\dots,7.\,}$$ A quick area check confirms the arithmetic: $X_1[0]X_2[0] = 11 \times 6 = 66$, and the eight values above sum to 66.
Locate the support of the linear convolution. Linear convolution adds the supports. The earliest non-zero product pairs $x_1[0]$ with $x_2[1]$, and the latest pairs $x_1[7]$ with $x_2[3]$: $$\boxed{\,n_{\text{first}} = 0 + 1 = 1\,} \qquad\text{and}\qquad \boxed{\,n_{\text{last}} = 7 + 3 = 10.\,}$$ So $x_4[n]$ occupies $1 \le n \le 10$, a run of ten samples — two more than the eight-point circular result can hold, which is exactly why parts (a) and (e) differ.
Compute the linear convolution. With the same three-tap collapse but without the modulo, $$x_4[n] = x_1[n-1] + 3x_1[n-2] + 2x_1[n-3],$$ which gives, for $n = 1$ through $10$, $$x_4[n] = \{\,1,\;5,\;9,\;8,\;7,\;9,\;8,\;7,\;8,\;4\,\}.$$ The total again checks against the product of the two DC sums, $\sum x_4 = 66 = 11 \times 6$.
Fold the linear result to recover the circular one. An $N$-point circular convolution is the linear convolution aliased with period $N$: $$x_3[n] = \sum_{r=-\infty}^{\infty} x_4[n + 8r], \qquad 0 \le n \le 7.$$ Only $x_4[8] = 7$, $x_4[9] = 8$ and $x_4[10] = 4$ lie outside the eight-point window, so they wrap onto $n = 0, 1, 2$ respectively: $$\begin{aligned} x_3[0] &= x_4[0] + x_4[8] = 0 + 7 = 7, \\ x_3[1] &= x_4[1] + x_4[9] = 1 + 8 = 9, \\ x_3[2] &= x_4[2] + x_4[10] = 5 + 4 = 9, \end{aligned}$$ while $x_3[n] = x_4[n]$ untouched for $3 \le n \le 7$. The result is $\{7,9,9,9,8,7,9,8\}$, identical to part (a), which is the verification part (e) asks for.

Figure 2.2 — top: the linear convolution $x_4[n]$ on $1 \le n \le 10$ (part d). Bottom: the eight-point circular convolution $x_3[n]$, obtained either directly (part a) or by wrapping the three tail samples of $x_4$ back onto $n = 0,1,2$ (part e).

Quantity	Result
(a) $x_3[n]$, $n = 0\ldots7$	7, 9, 9, 9, 8, 7, 9, 8
(b) First non-zero sample of $x_4$	$n = 1$
(c) Last non-zero sample of $x_4$	$n = 10$
(d) $x_4[n]$, $n = 1\ldots10$	1, 5, 9, 8, 7, 9, 8, 7, 8, 4
(e) Samples corrupted by wrap-around	$n = 0,1,2$ only; $x_3[n] = x_4[n]$ for $3 \le n \le 7$
Area check	$\sum x_4 = \sum x_3 = 66 = (\sum x_1)(\sum x_2) = 11 \times 6$

Topic. The circular convolution theorem and time-domain aliasing when a DFT of insufficient length is used for filtering.

Key relations. Circular convolution theorem: $x_1[n] \circledast x_2[n] \;\leftrightarrow\; X_1[k]X_2[k]$ for $N$-point DFTs. Support of a linear convolution: $[n_{1,\min}+n_{2,\min},\; n_{1,\max}+n_{2,\max}]$, of length $L_1 + L_2 - 1$. Aliasing identity: $x_1 \circledast x_2 = \sum_r (x_1 * x_2)[n + rN]$. Circular convolution equals linear convolution when $N \ge L_1 + L_2 - 1$.

Why this works. Multiplying DFTs is multiplying two periodic spectra sampled at $N$ points, and sampling in frequency is periodic extension in time. The eight-point product therefore cannot represent a ten-sample answer; the two samples that will not fit are not lost but folded back to the start of the block. Here $L_1 + L_2 - 1 = 8 + 3 - 1 = 10 \gt 8$, so exactly $10 - 8 = 2$ positions are corrupted — and indeed $n = 0$ and $n = 1$ pick up wrapped energy, with $n = 2$ also affected because the last non-zero sample sits at $n = 10$. Everything from $n = 3$ onwards is the true filter output, which is the observation the overlap-add and overlap-save block-filtering methods are built on.

Common pitfall. Assuming the circular and linear answers must differ in every sample, or conversely assuming they agree everywhere because the sequences "look short enough". The disciplined check is arithmetic: compare $L_1 + L_2 - 1$ against $N$, and only that many leading samples can be wrong. A second frequent slip is starting $x_2$ at $n = 0$ because it has three non-zero values; it starts at $n = 1$, which shifts the whole answer by one sample and moves the support end-points from $(0,9)$ to $(1,10)$.

Source. Oppenheim & Schafer, Discrete-Time Signal Processing, 3rd ed., §8.6–8.7 (circular convolution, linear convolution using the DFT).

Question 2 of 6: Eight-point circular convolution versus linear convolution

Question 2: Eight-point circular convolution versus linear convolution (12 marks)