Question 4 of 5: Four-point DFTs and circular convolution

Question 4: Four-point DFTs and circular convolution (25 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 four-point sequences,

Find. $X[k]$, $H[k]$, the four-point circular convolution $y[n]$ computed directly, and the same $y[n]$ recovered through $Y[k] = X[k]H[k]$ and an inverse DFT.

Approach. With $N = 4$ the twiddle factor is $W_4 = e^{-j\pi/2} = -j$, so every DFT term is $\pm 1$ or $\pm j$ and the transforms can be written down without a calculator; the circular convolution is then done twice, once in the time domain and once in the frequency domain, and the two must agree exactly.

1. Evaluate $x[n]$ and note its structure. The cosine sampled at $\pi/2$ per step gives $x[n] = \{1, 0, -1, 0\}$, that is $x[n] = \delta[n] - \delta[n-2]$. This makes every later step short: convolving with $x$ is a difference of two circular shifts.
2. Compute the four-point DFT of $x[n]$ (part a). With $W_4 = -j$, $$X[k] = \sum_{n=0}^{3} x[n]\,(-j)^{nk} = 1 - (-j)^{2k} = 1 - (-1)^{k},$$ so odd $k$ gives $2$ and even $k$ gives $0$: $$\boxed{\;X[k] = \{\,0,\; 2,\; 0,\; 2\,\}\;}$$ The result is the discrete counterpart of a cosine at exactly bin $k = 1$: all the energy of $\cos(2\pi n/4)$ lands in bins $1$ and $3 \equiv -1$, and the DFT of a real even sequence is real, as obtained.
3. Compute the four-point DFT of $h[n]$ (part b). Summing the four terms of $H[k] = \sum_n (1/2)^{n}(-j)^{nk}$ bin by bin, $$\begin{aligned} H[0] &= 1 + \tfrac12 + \tfrac14 + \tfrac18 = \tfrac{15}{8} = 1.875,\\ H[1] &= 1 - j\tfrac12 - \tfrac14 + j\tfrac18 = 0.75 - j\,0.375,\\ H[2] &= 1 - \tfrac12 + \tfrac14 - \tfrac18 = \tfrac58 = 0.625,\\ H[3] &= H^{*}[1] = 0.75 + j\,0.375 . \end{aligned}$$ $$\boxed{\;H[k] = \{\,1.875,\;\; 0.75 - j0.375,\;\; 0.625,\;\; 0.75 + j0.375\,\}\;}$$ The conjugate symmetry $H[3] = H^{*}[1]$ is the expected signature of a real sequence and is a free check on the arithmetic.
4. Set up the circular convolution (part c). By definition $$y[n] = \sum_{m=0}^{3} x[m]\,h[\langle n - m\rangle_4] .$$ Since $x[m]$ is non-zero only at $m = 0$ (value $+1$) and $m = 2$ (value $-1$), the sum collapses to $$y[n] = h[\langle n\rangle_4] - h[\langle n-2\rangle_4],$$ a difference between the sequence and its two-step circular rotation.
5. Evaluate the four output samples. $$\begin{aligned} y[0] &= h[0] - h[2] = 1 - 0.25 = 0.75, &\qquad y[1] &= h[1] - h[3] = 0.5 - 0.125 = 0.375,\\ y[2] &= h[2] - h[0] = -0.75, &\qquad y[3] &= h[3] - h[1] = -0.375 . \end{aligned}$$ $$\boxed{\;y[n] = \{\,0.75,\;\; 0.375,\;\; -0.75,\;\; -0.375\,\}\;}$$ The antisymmetry $y[n+2] = -y[n]$ is inherited directly from $x[n]$, whose own period-4 pattern repeats with a sign change every two samples.

6. Multiply the transforms (part d). The circular convolution theorem states that $y[n] = x[n] \,\text{(4)}\, h[n]$ has DFT $Y[k] = X[k]\,H[k]$. Because $X[0] = X[2] = 0$, only two bins survive: $$Y[k] = \{\,0,\;\; 2(0.75 - j0.375),\;\; 0,\;\; 2(0.75 + j0.375)\,\} = \{\,0,\;\; 1.5 - j0.75,\;\; 0,\;\; 1.5 + j0.75\,\}.$$
7. Invert the transform. With $y[n] = \tfrac14 \sum_k Y[k]\,j^{\,nk}$ and only $k = 1, 3$ contributing, $$y[n] = \tfrac14\Bigl[Y[1]\,j^{\,n} + Y[1]^{*}\,j^{-n}\Bigr] = \tfrac12\,\mathrm{Re}\bigl\{Y[1]\,j^{\,n}\bigr\}.$$ Evaluating for $n = 0,1,2,3$ with $Y[1] = 1.5 - j0.75$: $$\begin{aligned} y[0] &= \tfrac12(1.5) = 0.75, &\qquad y[1] &= \tfrac12\,\mathrm{Re}\{(1.5 - j0.75)j\} = \tfrac12(0.75) = 0.375,\\ y[2] &= -0.75, &\qquad y[3] &= -0.375 . \end{aligned}$$ $$\boxed{\;y[n] = \{\,0.75,\;\; 0.375,\;\; -0.75,\;\; -0.375\,\} \quad\text{(identical to part c)}\;}$$ The two routes agree sample for sample, which is the intended point of the question: multiplying DFTs performs circular, not linear, convolution, and here that is exactly what was asked for.
8. Note what the linear convolution would have been. A useful contrast: the linear convolution of these two length-4 sequences has $4 + 4 - 1 = 7$ samples, so recovering it through DFTs would require transforms of length at least $7$ (in practice $8$). Using $N = 4$ folds the last three samples back onto the first three, which is precisely the difference between $y[n]$ above and the linear result.