Question 4 of 7: One Output, Four Methods: Iteration, Convolution, Circular Convolution and the DFT

Question 4: One Output, Four Methods: Iteration, Convolution, Circular Convolution and the DFT (20 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. A first-difference system $y[n] = x[n] - x[n-1]$ driven by $x[n] = \{1, 0, -1\}$ for $n = 0, 1, 2$ and zero elsewhere.

Find. The impulse response, and then the same output computed four different ways — iteratively, by linear convolution, by circular convolution in the time domain, and via the DFT/IDFT — with all four agreeing.

Approach. Get $h[n]$ by inspection, then run each of the four routes. The only decision worth making is the circular-convolution block length, and part (d) turns entirely on choosing it correctly.

1. (a) Impulse response by inspection. Setting $x[n] = \delta[n]$ in (5),
   $$h[n] = \delta[n] - \delta[n-1] \;\Rightarrow\; \boxed{h[n] = \{1, -1\}, \; n = 0, 1.}$$

   The system is a causal two-tap FIR differencer; its transfer function is $H(z) = 1 - z^{-1}$, with a single zero at $z = 1$ (it removes d.c.) and a pole at the origin.

2. (b) Iterative solution of the difference equation. Marching (5) forward with $x[n] = 0$ outside $0 \le n \le 2$:
   $$\begin{aligned}y[0] &= x[0] - x[-1] = 1 - 0 = 1,\\y[1] &= x[1] - x[0] = 0 - 1 = -1,\\y[2] &= x[2] - x[1] = -1 - 0 = -1,\\y[3] &= x[3] - x[2] = 0 - (-1) = +1,\\y[n] &= 0 \quad \text{for } n \ge 4.\end{aligned}$$

   Note that $y[3]$ is non-zero even though the input has already ended — the memory of $x[2]$ is still in the delay when $n = 3$. That is why the output is four samples long, not three.

3. (c) Linear convolution. With $y[n] = \sum_{k} x[k]h[n-k]$ and lengths $L_x = 3$, $L_h = 2$, the result has $L_x + L_h - 1 = 4$ samples:
   $$\begin{aligned}y[0] &= x[0]h[0] = (1)(1) = 1,\\y[1] &= x[0]h[1] + x[1]h[0] = (1)(-1) + (0)(1) = -1,\\y[2] &= x[1]h[1] + x[2]h[0] = (0)(-1) + (-1)(1) = -1,\\y[3] &= x[2]h[1] = (-1)(-1) = +1.\end{aligned}$$$$\boxed{y[n] = \{1, -1, -1, 1\}, \quad n = 0, 1, 2, 3,}$$

   identical to the iterative march, as it must be for an LTI system.

4. (d) Circular convolution — the block length is the whole question. An $N$-point circular convolution reproduces the linear convolution only if $N \ge L_x + L_h - 1 = 4$. Choose $N = 4$ and zero-pad both sequences to that length: $x = \{1, 0, -1, 0\}$, $h = \{1, -1, 0, 0\}$. Then
   $$y[n] = \sum_{m=0}^{3} x[m]\,h[\langle n - m \rangle_4] = \{1, -1, -1, 1\},$$

   matching part (c) exactly. It is worth showing what happens if the block is too short. With $N = 3$ (no padding) the tail sample $y[3]$ wraps around and adds onto $y[0]$:

   $$y_{3\text{-pt}}[n] = \{2, -1, -1\} \quad \text{instead of} \quad \{1, -1, -1, 1\}.$$

   The first sample is wrong by exactly the discarded $y[3] = 1$. This time-domain aliasing is the reason overlap-add and overlap-save exist.

5. (e) DFT / IDFT route. Circular convolution in time is multiplication in the DFT domain, so with $N = 4$ and $W_4 = -j$:
   $$X[k] = \{0,\; 2,\; 0,\; 2\}, \qquad H[k] = 1 - W_4^{k} = \{0,\; 1+j,\; 2,\; 1-j\}.$$

   Multiplying bin by bin,

   $$Y[k] = X[k]H[k] = \{0,\; 2+2j,\; 0,\; 2-2j\},$$

   and the 4-point IDFT $y[n] = \frac{1}{4}\sum_{k} Y[k] W_4^{-kn}$ returns

   $$\boxed{y[n] = \{1, -1, -1, 1\},}$$

   the same sequence for the fourth time. Note $Y[0] = 0$: the differencer has a zero at d.c. and the output samples must therefore sum to zero, which is a one-line sanity check on the whole answer ($1 - 1 - 1 + 1 = 0$).