Question 2 of 6: Recovering the DFT length from a circular shift

Question 2: Recovering the DFT length from a circular shift (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. From the exam figure: $x[n]$ has samples $x[0] = 1$, $x[1] = -1$, $x[2] = 1$ and is zero elsewhere; $x_1[n]$ has samples $x_1[0] = 1$, $x_1[3] = 1$, $x_1[4] = -1$ and is zero elsewhere. Both are transformed with the same, unknown, DFT length $N$.

Find. A value of $N$ for which the stated DFT relation reproduces the second sketch from the first, and whether any other value would do.

[Figure not reproduced: Figure Q2.1 — the two sequences redrawn from the exam figure. The annotations show where the samples of x[n] must land once the circular shift is applied. See the official exam paper.]

Approach. Recognise the exponential as the circular time-shift factor of the DFT, read off the shift, track where each sample of $x[n]$ lands modulo $N$, and match that support against the sketch of $x_1[n]$.

1. Identify the property. Property 5 of the DFT table printed on page 8 of this exam reads $$x[((n-m))_N] \;\longleftrightarrow\; W_N^{km}X[k], \qquad W_N = e^{-j2\pi/N}.$$ A multiplicative exponential in $k$ is always a circular shift in $n$ — never a linear one — because the DFT only knows the sequence over one period.
2. Read off the shift. Writing the given factor in terms of $W_N$, $$e^{j2\pi k 2/N} = e^{-j2\pi k(-2)/N} = W_N^{k(-2)},$$ so $m = -2$ and $$x_1[n] = x[((n+2))_N],$$ a circular shift of $x[n]$ two samples to the left (equivalently $N-2$ samples to the right).
3. Track where each sample lands. Sample $x[i]$ appears in $x_1$ at index $((i-2))_N$. Applying this to the three non-zero samples: $x[2] = 1 \to n = 0$; $x[0] = 1 \to n = ((-2))_N = N-2$; and $x[1] = -1 \to n = ((-1))_N = N-1$. Hence for any $N$ the support of $x_1[n]$ must be exactly $$\{\,0,\; N-2,\; N-1\,\} \quad\text{with values}\quad \{1,\;1,\;-1\}.$$
4. Match against the sketch. The figure shows $x_1[n]$ non-zero at $n = 0$ (value $1$), $n = 3$ (value $1$) and $n = 4$ (value $-1$). Equating the two supports term by term gives $N - 2 = 3$ and $N - 1 = 4$, both of which yield $$\boxed{\,N = 5\,}$$ and the values also agree: $x_1[0] = x[2] = 1$, $x_1[3] = x[0] = 1$, $x_1[4] = x[1] = -1$.
5. Confirm with the transforms themselves. With $N = 5$, $X[k] = 1 - W_5^{k} + W_5^{2k}$. Multiplying by $e^{j4\pi k/5} = W_5^{-2k}$ gives $$X_1[k] = W_5^{-2k} - W_5^{-k} + 1 = 1 - W_5^{4k} + W_5^{3k},$$ using $W_5^{-k} = W_5^{4k}$ and $W_5^{-2k} = W_5^{3k}$. Reading the coefficients as samples, $x_1 = [\,1,\;0,\;0,\;1,\;-1\,]$ — exactly the sketch.
6. Part (b): test uniqueness. The shift is fixed at two samples whatever $N$ may be, because the numeral 2 in the exponent does not depend on $N$. The support of $x_1$ is therefore forced to be $\{0,\,N-2,\,N-1\}$, a set of three indices whose two largest members are consecutive and sit at the top of the period. Demanding that this set equal $\{0,\,3,\,4\}$ admits the single solution $N = 5$; for example $N = 6$ would put the samples at $\{0,\,4,\,5\}$ and $N = 7$ at $\{0,\,5,\,6\}$, neither of which matches the figure.
7. Close the argument. Two side conditions complete the proof. First, $N \ge 5$ is necessary simply because $x_1[n]$ has a non-zero sample at $n = 4$, which must lie inside one period. Second, no $N \lt 5$ can work either, since the wrapped supports for $N = 3$ and $N = 4$ are $\{0,1,2\}$ and $\{0,2,3\}$. Hence the choice is $$\boxed{\text{unique: } N = 5 \text{ is the only consistent length}}$$