Question 5 of 5: Six-Point DFT Properties — Circular Shift, Symmetry and Frequency Decimation

Question 5: Six-Point DFT Properties — Circular Shift, Symmetry and Frequency Decimation (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. From Figure 4, the real six-point sequence $x[n] = \{4,\,3,\,2,\,1,\,0,\,0\}$ for $n = 0,1,2,3,4,5$ (the stems at $n = -2, -1, 4, 5$ are drawn on the axis, i.e. zero), and $X[k]$ is its six-point DFT, with $W_6 = e^{-j2\pi/6}$.

Find. The three finite-length sequences $y[n]$, $w[n]$ and $q[n]$ whose DFTs are the stated modifications of $X[k]$, each sketched with its sample values labelled.

[Figure not reproduced: Figure 4 redrawn: the given real sequence x[n] = 4, 3, 2, 1, 0, 0 for n = 0 to 5. See the official exam paper.]

Approach. Each part is a standard DFT property read backwards: a linear-phase factor is a circular shift; taking the imaginary part of the transform of a real sequence isolates its circular odd part; and keeping every second DFT sample is decimation in frequency, which folds the time sequence.

1. Identify the circular-shift pair. The six-point DFT property is $x[((n-m))_6] \;\longleftrightarrow\; W_6^{km}X[k]$. Matching $Y[k] = W_6^{5k}X[k]$ gives $m = 5$, so $y[n] = x[((n-5))_6]$: the sequence is shifted right circularly by five samples, which for $N = 6$ is the same as a circular shift left by one.
2. Evaluate the shifted samples. Reading $x[((n-5))_6]$ for $n = 0 \ldots 5$ gives $x[1], x[2], x[3], x[4], x[5], x[0]$, hence $$\boxed{\,y[n] = \{3,\,2,\,1,\,0,\,0,\,4\},\quad n = 0,\dots,5\,}$$ The sample that "falls off" the left end reappears at $n = 5$: that wrap-around is exactly what distinguishes a circular from a linear shift.

Part (b) uses the symmetry properties of the DFT of a real sequence. The imaginary part of a transform is never arbitrary: for real x[n] it is the transform of a specific real sequence, up to a factor of j.

3. Split $x[n]$ into its circular even and odd parts. For a real sequence, $X[((-k))_6] = X^{*}[k]$, and the circular odd part $x_o[n] = \tfrac12\left(x[n] - x[((-n))_6]\right)$ transforms to $\tfrac12\left(X[k]-X^{*}[k]\right) = j\operatorname{Im}\{X[k]\}$. Evaluating $x[((-n))_6] = \{4, 0, 0, 1, 2, 3\}$ and subtracting gives $$x_o[n] = \{0,\ 1.5,\ 1,\ 0,\ -1,\ -1.5\}.$$
4. Remove the factor of $j$. Since $\mathrm{DFT}\{x_o[n]\} = j\operatorname{Im}\{X[k]\}$, the sequence whose DFT is $\operatorname{Im}\{X[k]\}$ alone is $x_o[n]$ divided by $j$: $$\boxed{\,w[n] = -j\,x_o[n] = \{0,\ -1.5j,\ -j,\ 0,\ +j,\ +1.5j\}\,}$$ so $w[n]$ is purely imaginary and circularly odd. Its real part is identically zero, and the sketch below plots $\operatorname{Im}\{w[n]\}$.
5. Check the consistency of the result. A purely imaginary, circularly odd sequence must have a purely real DFT — which is what $\operatorname{Im}\{X[k]\}$ is. Recomputing the six-point DFT of $w[n]$ reproduces $\operatorname{Im}\{X[k]\}$ exactly, confirming both the sign and the factor of $j$.

Part (c) keeps only the odd-indexed DFT samples, which is one half of a decimation-in-frequency FFT butterfly stage.

6. Write the odd DFT samples as a three-point DFT. By definition $$X[2k+1] = \sum_{n=0}^{5}x[n]W_6^{(2k+1)n} = \sum_{n=0}^{5}\left(x[n]W_6^{\,n}\right)W_6^{2kn},$$ and since $W_6^{2kn} = e^{-j2\pi kn/3} = W_3^{kn}$, the right-hand side is a three-point DFT of the modulated sequence $g[n] = x[n]W_6^{\,n}$, provided the two halves of $g$ are folded together.
7. Fold the two halves. Splitting the sum at $n = 3$ and using $W_3^{k(n+3)} = W_3^{kn}$ together with $W_6^{\,3} = e^{-j\pi} = -1$, $$Q[k] = \sum_{n=0}^{2}\Bigl(g[n] + g[n+3]\Bigr)W_3^{kn}, \qquad g[n] + g[n+3] = W_6^{\,n}\bigl(x[n]-x[n+3]\bigr),$$ so $q[n] = W_6^{\,n}\left(x[n]-x[n+3]\right)$ for $n = 0,1,2$.
8. Substitute the sample values. The differences are $x[0]-x[3] = 3$, $x[1]-x[4] = 3$ and $x[2]-x[5] = 2$, and $W_6^{\,0}=1$, $W_6^{\,1} = e^{-j\pi/3}$, $W_6^{\,2} = e^{-j2\pi/3}$. Hence $$\boxed{\,q[n] = \{\,3,\ 3e^{-j\pi/3},\ 2e^{-j2\pi/3}\,\} = \{\,3,\ 1.5 - j2.598,\ -1 - j1.732\,\}\,}$$ a complex three-point sequence with magnitudes $3, 3, 2$ and angles $0^\circ, -60^\circ, -120^\circ$. Taking the three-point DFT of this $q[n]$ returns $X[1], X[3], X[5]$ exactly.