Question 2 of 6: Six-Point DFT, Circular Shift and Circular Convolution

Question 2: Six-Point DFT, Circular Shift and Circular 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.

Given. A six-sample ramp-down sequence and a three-tap moving-sum filter.

Find. The six-point DFT, the sequence produced by a linear-phase multiplication of that DFT, the six-point circular convolution with $h[n]$, and the smallest DFT length that makes the circular result equal the linear one.

Approach. Write the DFT sum directly in powers of $W_6$ and close it with a geometric identity, then use the circular time-shift property for part (b), time-aliasing of the linear convolution for part (c), and the length rule $N\ge L_1+L_2-1$ for part (d).

1. Write the analysis sum. By definition, with $W_6=e^{-j2\pi/6}$, $$X[k]=\sum_{n=0}^{5}x[n]W_6^{kn}=6+5W_6^{k}+4W_6^{2k}+3W_6^{3k}+2W_6^{4k}+W_6^{5k},\qquad k=0,1,\dots,5 .$$ This already answers part (a) in the requested form.
2. Close the sum to a compact expression. Writing $x[n]=6-n$ and splitting the sum, $$X[k]=6\sum_{n=0}^{5}W_6^{kn}-\sum_{n=0}^{5}n\,W_6^{kn}.$$ For $k\neq0$ the first sum vanishes and the second evaluates with $\sum_{n=0}^{N-1}n\,w^{n}=N/(w-1)$ for $w^{N}=1$, $w\neq1$. With $w=W_6^{k}$ this gives $$\boxed{X[0]=21,\qquad X[k]=\frac{6}{1-W_6^{k}}\ \ (k=1,\dots,5)}$$ which is a convenient closed form for evaluating the samples.
3. Evaluate the six samples. Substituting $W_6^{k}=e^{-j\pi k/3}$ gives the numerical DFT, conjugate-symmetric as it must be for a real sequence:

   Six-point DFT of the given sequence

   $k$	0	1	2	3	4	5
   $X[k]$	$21$	$3-j5.196$	$3-j1.732$	$3$	$3+j1.732$	$3+j5.196$
   polar	$21\angle0^{\circ}$	$6\angle-60^{\circ}$	$3.464\angle-30^{\circ}$	$3\angle0^{\circ}$	$3.464\angle30^{\circ}$	$6\angle60^{\circ}$

   The value $X[0]=21$ is simply the sum of the samples, which is a useful independent check.
4. Part (b): recognise the multiplier as a circular shift. The DFT shift property reads $x[((n-m))_{6}]\leftrightarrow W_6^{km}X[k]$. Here the multiplier is $W_6^{-2k}$, so $m=-2$ and $$\boxed{w[n]=x[((n+2))_{6}]=\{4,\ 3,\ 2,\ 1,\ 6,\ 5\},\qquad n=0,\dots,5}$$ i.e. the sequence rotated two samples to the left, with the two evicted samples wrapping round to the end. No values change; only their positions do.
   Figure 2.2 — w[n], the given sequence circularly advanced by two samples.
5. Part (c): compute the linear convolution first. Since $h[n]$ is a three-tap moving sum, each output is the sum of three consecutive input samples (zeros outside the block): $$x[n]\ast h[n]=\{6,\ 11,\ 15,\ 12,\ 9,\ 6,\ 3,\ 1\},\qquad n=0,\dots,7 .$$
6. Alias the tail back to obtain the circular result. An $N$-point circular convolution equals the linear convolution with its tail wrapped: $y_c[n]=\sum_r y_{\text{lin}}[n+rN]$. With $N=6$ only the samples at $n=6,7$ wrap, onto $n=0,1$: $$y_c[0]=6+3=9,\qquad y_c[1]=11+1=12,$$ and the remaining four samples are unchanged, so $$\boxed{x[n]\circledast_{6}h[n]=\{9,\ 12,\ 15,\ 12,\ 9,\ 6\}}$$ A quick check: the samples must sum to $\left(\sum x\right)\left(\sum h\right)=21\times3=63$, and $9+12+15+12+9+6=63$.
   Figure 2.3 — the eight-sample linear convolution (top) and the six-point circular convolution (bottom); the last two linear samples wrap onto n = 0 and 1.
7. Part (d): choose $N$ so that nothing wraps. The linear convolution of an $L_1$-point and an $L_2$-point sequence occupies $L_1+L_2-1$ samples. Circular convolution of length $N$ reproduces it exactly if and only if no non-zero sample has to be aliased, i.e. $$N\ \ge\ L_1+L_2-1=6+3-1=8\quad\Rightarrow\quad\boxed{N_{\min}=8}$$ Any $N\ge8$ works (the extra positions simply hold zeros); $N=7$ already corrupts the sample at $n=0$. This is the rule behind block convolution schemes such as overlap-add.