Question 5 of 6: Circular versus linear convolution, and the FFT route (12 marks)

Question 5: Circular versus linear convolution, and the FFT route (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.

Given. Two finite-length sequences read from the printed stem plots, both zero outside the interval shown.

[Figure not reproduced: Figure 5.1 — x1[n] as printed: eight samples on 0. See the official exam paper.]

[Figure not reproduced: Figure 5.2 — x2[n] as printed: a four-point sequence whose only non-zero samples are at n = 1, 2 and 3. See the official exam paper.]

Find. (a) the eight-point circular convolution $x_3[n]$; (b) the length of the linear convolution $x_4[n]$; (c) the explicit relationship between the two; (d) an FFT-based computation of $x_4[n]$, with the number of transforms, their length, and the zero padding required.

Approach. Compute the linear convolution first — it is the more informative of the two — then obtain the circular result by folding its tail back by eight samples, which is exactly the time-aliasing relation part (c) asks for; part (d) then follows by choosing a transform length long enough that no folding occurs.

1. Set up the linear convolution. Because $x_2$ has only three non-zero samples, the convolution sum collapses to three terms: $$x_4[n]=\sum_{k}x_1[k]\,x_2[n-k]=1\cdot x_1[n-1]+3\cdot x_1[n-2]+2\cdot x_1[n-3].$$ The output is a weighted sum of three shifted copies of $x_1$.
2. Evaluate it sample by sample. Sweeping $n$ from 0 to 10 and reading $x_1$ from the table, $$\begin{aligned} x_4[0]&=0, & x_4[4]&=1+3(1)+2(2)=8, & x_4[8]&=2+3(1)+2(1)=7,\\ x_4[1]&=1, & x_4[5]&=2+3(1)+2(1)=7, & x_4[9]&=0+3(2)+2(1)=8,\\ x_4[2]&=2+3(1)=5, & x_4[6]&=1+3(2)+2(1)=9, & x_4[10]&=0+0+2(2)=4,\\ x_4[3]&=1+3(2)+2(1)=9, & x_4[7]&=1+3(1)+2(2)=8. & & \end{aligned}$$ Collecting the samples, $$x_4[n]=\{\,0,\,1,\,5,\,9,\,8,\,7,\,9,\,8,\,7,\,8,\,4\,\},\qquad 0\le n\le 10 .$$ A useful arithmetic check: the samples of a convolution must sum to the product of the two input sums, and indeed $\left(\sum x_1\right)\left(\sum x_2\right)=11\times 6=66$, which is exactly $\sum x_4$.
3. Answer part (b) directly. Linear convolution of sequences of length $L_1$ and $L_2$ has length $L_1+L_2-1$. With $x_1$ an eight-point sequence and $x_2$ a four-point sequence, $$\boxed{\,L_4=L_1+L_2-1=8+4-1=11\ \text{samples},\ 0\le n\le 10\,}$$ Because $x_2[0]=0$ the result happens to start with a zero, so only ten samples are actually non-zero; the length asked for is nevertheless 11, because $x_2$ is specified as a four-point sequence on $0\le n\le 3$.

4. Fold the tail to obtain the circular result (part a). An $N$-point circular convolution equals the linear convolution time-aliased with period $N$. With $N=8$ and a linear result of length 11, the last three samples wrap onto the first three: $$\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]$ for $3\le n\le 7$ because nothing folds onto those positions. Hence $$\boxed{\,x_3[n]=\{\,7,\,9,\,9,\,9,\,8,\,7,\,9,\,8\,\},\qquad 0\le n\le 7\,}$$ The same total applies as a check, $\sum x_3 = 66$, since aliasing rearranges the samples but conserves their sum. The result was also confirmed independently by evaluating $x_3=\mathrm{IDFT}\{X_1[k]X_2[k]\}$ on eight points.

Part (c): the relationship. The general statement, and the one the marks are for, is that circular convolution is the linear convolution aliased in time with period $N$:

$$\boxed{\,x_3[n]=\sum_{r=-\infty}^{\infty}x_4[n+8r],\qquad 0\le n\le 7\,}$$

Only the terms $r=0$ and $r=1$ contribute here, because $x_4$ occupies $0\le n\le 10$, so the relation reduces to $x_3[n]=x_4[n]+x_4[n+8]$ for $n=0,1,2$ and $x_3[n]=x_4[n]$ for $n=3,\dots,7$. The underlying reason is that the $N$-point DFT of a sequence samples its DTFT at $N$ equally spaced frequencies; multiplying two such sampled spectra and inverting recovers the linear convolution only if the linear result is short enough to fit within one period of $N$. Here $11 \gt 8$, so the three overhanging samples reappear at the start of the block. The direct consequence for part (d) is the design rule: choose $N\ge L_1+L_2-1$ and the two convolutions coincide.

Part (d): computing $x_4[n]$ with a radix-2 FFT.

5. Choose the transform length (part d-ii). To avoid all time aliasing the transform length must satisfy $N\ge L_1+L_2-1=11$, and a radix-2 algorithm requires a power of two. The smallest admissible choice is $$\boxed{\,N=16\ \text{points for every transform}\,}$$ An eight-point transform would not do: it reproduces the aliased $x_3[n]$ of part (a) rather than $x_4[n]$.
6. Count the transforms (part d-i). The scheme needs the spectrum of each input and one inversion: $$\boxed{\,\text{3 uses: two forward 16-point FFTs and one inverse 16-point FFT}\,}$$ Since only a forward algorithm was supplied, the inverse is obtained from the same routine by the conjugation identity $$x_4[n]=\frac{1}{16}\left(\mathrm{FFT}\left\{Y^{*}[k]\right\}\right)^{*},\qquad Y[k]=X_1[k]X_2[k],$$ so the hardware cost really is three passes through one block.
7. Prepare the inputs (part d-iii). Zero padding is required, and it is what makes the circular result equal the linear one: $$x_1[n]:\ 8\ \text{samples}+8\ \text{zeros},\qquad x_2[n]:\ 4\ \text{samples}+12\ \text{zeros}.$$ Both padded blocks are then fed to the FFT in natural order, since bit-reversal is built in. After the inverse transform the first eleven output samples are $x_4[0]$ through $x_4[10]$ and the remaining five are zero — a convenient confirmation that the padding was sufficient.

The FFT route is also the faster one here: direct evaluation of the convolution sum costs $L_1L_2=32$ real multiplications, while three 16-point radix-2 transforms cost about $3\times\tfrac{16}{2}\log_2 16=96$ complex multiplications plus 16 for the spectral product. For sequences this short the direct sum wins; the FFT route becomes the economical one once the sequences run to a few hundred samples, which is the practical point of the question.