Frequency-domain sampling and the resulting time aliasing: 22-Elec-B1 Digital Signal Processing, May 2018, Q4

Question 4: Frequency-domain sampling and the resulting time aliasing (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.

Figure 4.1 — top: the ten-point sequence $x[n]$ with the two unknown samples $a = x[1]$ and $b = x[4]$ (drawn at an arbitrary height, as the exam warns). Bottom: the candidate four-point sequence $y[n]$ printed with part (a).

Given.

$n$	0	1	2	3	4	5	6	7	8	9
$x[n]$	2	$a$	$-1$	1	$b$	2	3	0	$-1$	2

The candidate sequence in the second figure is $y[n] = \{1,\,3,\,2,\,1\}$ for $n = 0,1,2,3$, and $Y[k]$ consists of $N = 4$ samples of $X(e^{j\omega})$ spaced $\Delta\omega = \pi/2$ apart.

Find. Whether the printed four-point sequence is consistent with being the 4-point IDFT of those DTFT samples, and if so the values of $a$ and $b$ that make it so.

Approach. Sampling a DTFT at $N$ equally spaced frequencies aliases the sequence in time with period $N$; write $y[n]$ as that alias sum, identify which samples are free of the unknowns, test those against the figure, and then solve the remaining two equations.

Turn frequency sampling into time aliasing. Sampling $X(e^{j\omega})$ at $\omega = 2\pi k/N$ with $N = 4$ and inverting with a 4-point IDFT gives, for any sequence longer than $N$, $$y[n] = \sum_{r=-\infty}^{\infty} x[n + rN] = \sum_{r} x[n + 4r], \qquad 0 \le n \le 3.$$ Since $x[n]$ lives on $0 \le n \le 9$, each $y[n]$ is a sum of at most three samples of $x$, taken every fourth position.
Write out the four alias sums. Collecting the terms, $$\begin{aligned} y[0] &= x[0] + x[4] + x[8] = 2 + b + (-1) = 1 + b, \\ y[1] &= x[1] + x[5] + x[9] = a + 2 + 2 = a + 4, \\ y[2] &= x[2] + x[6] = -1 + 3 = 2, \\ y[3] &= x[3] + x[7] = 1 + 0 = 1. \end{aligned}$$ The key structural observation is that the two unknowns land in different alias sums — $b$ only in $y[0]$ and $a$ only in $y[1]$ — so $y[2]$ and $y[3]$ are completely determined by the data the figure does give.
Test the determined samples against the printed figure (part a). The exam's candidate sequence has $y[2] = 2$ and $y[3] = 1$. Our alias sums give exactly $$y[2] = -1 + 3 = \boxed{2} \qquad\text{and}\qquad y[3] = 1 + 0 = \boxed{1},$$ both matching. Since nothing in the candidate contradicts the two samples that cannot be adjusted, yes — the printed four-point sequence could be $y[n]$. Had either of these disagreed, no choice of $a$ or $b$ could have rescued it and the answer would have been an immediate no.
Solve for the two unknowns (part b). The remaining two samples give one linear equation each: $$1 + b = y[0] = 1 \;\Longrightarrow\; \boxed{b = 0}, \qquad a + 4 = y[1] = 3 \;\Longrightarrow\; \boxed{a = -1}.$$ Both equations are independent and each has a unique solution, so all four printed values (not merely some of them) are simultaneously attainable, and the values are unique.
Confirm the answer directly. With $a = -1$ and $b = 0$ the full sequence is $$x[n] = \{\,2,\,-1,\,-1,\,1,\,0,\,2,\,3,\,0,\,-1,\,2\,\}.$$ Evaluating its DTFT at the four required frequencies and comparing against the 4-point DFT of $\{1,3,2,1\}$ gives agreement to machine precision at $\omega = 0,\ \pi/2,\ \pi,\ 3\pi/2$; at $\omega = 0$, for example, both sides equal $2-1-1+1+0+2+3+0-1+2 = 7 = 1+3+2+1$. The alias sums also reproduce the figure exactly, closing the check.

Quantity	Result
Relationship enforced by the frequency sampling	$y[n] = \sum_r x[n+4r]$, $0 \le n \le 3$
Alias sums	$y[0] = 1+b$, $\;y[1] = a+4$, $\;y[2] = 2$, $\;y[3] = 1$
(a) Could the printed sequence be $y[n]$?	Yes — the two $a$,$b$-independent samples $y[2]=2$ and $y[3]=1$ both match
(b) Required values	$a = x[1] = -1$ and $b = x[4] = 0$, uniquely; all four printed values are met
Resulting sequence	$x[n] = \{2,-1,-1,1,0,2,3,0,-1,2\}$

Topic. Sampling the DTFT: how many frequency samples are needed to represent a finite-length sequence, and what is lost when there are too few.

Key relations. If $Y[k] = X(e^{j\omega})|_{\omega = 2\pi k/N}$ then the $N$-point IDFT returns $y[n] = \sum_r x[n+rN]$ for $0 \le n \le N-1$. Recovery of $x[n]$ from $Y[k]$ is exact if and only if the length of $x$ satisfies $L \le N$. Equivalently, $Y[k]$ is the $N$-point DFT of the time-aliased sequence, never of $x$ itself when $L \gt N$.

Why this works. Sampling in one domain is periodic replication in the other — the same duality that produces spectral replicas when a continuous-time signal is sampled. Taking only four frequency samples of a ten-sample sequence throws away information, and the four numbers that survive are sums of the samples that collide modulo 4. This is why the question can be answered without ever forming a DTFT: the whole content of "sample every $\pi/2$ and take a 4-point IDFT" is the fold-by-four. It is also the reason part (a) is worth eight of the twelve marks — recognising the aliasing is the graded insight, while solving two linear equations is bookkeeping.

Common pitfall. Attempting to compute $X(e^{j\omega})$ symbolically and evaluate it four times; it is correct but enormously longer, and the unknowns make it error-prone. A subtler error is to check only $y[0]$ and $y[1]$ — the two samples that do contain $a$ and $b$ — and conclude that any candidate is admissible. The test that has teeth in part (a) is exactly the pair of samples the unknowns cannot reach.

Source. Oppenheim & Schafer, Discrete-Time Signal Processing, 3rd ed., §8.4 (sampling the Fourier transform) and §8.5 (the DFT of a finite-length sequence).

Question 4 of 6: Frequency-domain sampling and the resulting time aliasing

Question 4: Frequency-domain sampling and the resulting time aliasing (12 marks)