Question 3 of 7: Applying the DFT Twice: Recovering the Original Sequence

Question 3: Applying the DFT Twice: Recovering the Original Sequence (20 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. The forward DFT kernel $W_N = e^{-j2\pi/N}$ is applied twice in succession; the worked case is $\mathbf{x} = \{0, 1, -1, 2\}$ with $N = 4$; the orthogonality relation $\frac{1}{N}\sum_{k=0}^{N-1} W_N^{(n-l)k} = 1$ when $n = \langle l \rangle_N$ and $0$ otherwise is supplied; part (d) assumes $N = 2^{q}$.

Find. $\mathbf{y}$ for the worked sequence; the general closed-form relation between $\mathbf{y}$ and $\mathbf{x}$ and hence the recovery rule; the explicit element mapping for $N = 16$; and the real-multiplication cost by both the direct and the radix-2 route.

Approach. Substitute (1) into (2), exchange the order of summation, and collapse the inner sum with the supplied orthogonality relation. Everything else — the numerical case, the $N = 16$ mapping and the recovery statement — is a corollary of the single identity that falls out.

1. (a) Compute the double transform for $\mathbf{x} = \{0, 1, -1, 2\}$. With $N = 4$, $W_4 = e^{-j\pi/2} = -j$. The first DFT gives
   $$X[0] = 2, \quad X[1] = -2 - j, \quad X[2] = -4, \quad X[3] = -2 + j,$$

   and transforming that sequence again with the same kernel yields

   $$\mathbf{y} = \{0,\; 8,\; -4,\; 4\}.$$

   Comparing element by element with $4\mathbf{x} = \{0, 4, -4, 8\}$, the entries are the same numbers in a different order: $y[0] = 4x[0]$, $y[1] = 4x[3]$, $y[2] = 4x[2]$, $y[3] = 4x[1]$. So $\mathbf{y}$ is $\mathbf{x}$ scaled by 4 and circularly reversed in time. Nothing has been lost, and $\mathbf{x}$ is trivially recoverable.

2. (b) Prove the general relation. Substituting (1) into (2) and exchanging the finite sums,
   $$y[m] = \sum_{k=0}^{N-1}\left(\sum_{n=0}^{N-1} x[n] W_N^{kn}\right)W_N^{mk} = \sum_{n=0}^{N-1} x[n] \sum_{k=0}^{N-1} W_N^{(n+m)k}.$$

   The inner sum is exactly the supplied relation (3) with $l = -m$: it equals $N$ when $n = \langle -m \rangle_N$ and vanishes for every other $n$. Only one term of the outer sum survives, giving

   $$\boxed{y[m] = N\, x\!\left[\langle -m \rangle_N\right], \qquad m = 0, 1, \ldots, N-1.}$$

   Applying the DFT twice therefore performs a circular time-reversal and a gain of $N$ — it is not a destructive operation. Inverting is immediate, since circular reversal is its own inverse:

   $$x[n] = \frac{1}{N}\, y\!\left[\langle -n \rangle_N\right].$$

   The result checks against part (a): $y[1] = 4x[\langle -1 \rangle_4] = 4x[3] = 8$, as computed. Note the engineer's mistake costs one extra transform, not the data.

3. (c) Write the mapping out for $N = 16$. Since $\langle -m \rangle_{16} = 16 - m$ for $m \ge 1$ and $0$ for $m = 0$,
   $$y[0] = 16\,x[0], \qquad y[m] = 16\,x[16-m] \quad (m = 1, 2, \ldots, 15),$$

   that is

   $$\mathbf{y} = 16\left\{x[0],\, x[15],\, x[14],\, \ldots,\, x[2],\, x[1]\right\}.$$

   Only $x[0]$ stays where it was; the remaining fifteen samples are read out backwards. Recovering $\mathbf{x}$ needs no arithmetic beyond one division by 16 and a re-indexing.

4. (d) Count the real multiplications. Evaluating (1) directly requires one complex multiply-accumulate for each of the $N$ terms in each of the $N$ outputs, i.e. $N^{2}$ complex multiplications; the second transform costs the same. Since one complex multiplication is four real multiplications,
   $$M_{direct} = 2 \times N^{2} \times 4 = 8N^{2} \;\text{real multiplications.}$$

   A radix-2 FFT of length $N = 2^{q}$ has $q = \log_2 N$ stages of $N/2$ butterflies, each butterfly costing one complex twiddle multiplication, so $\tfrac{N}{2}\log_2 N$ complex multiplications per transform. For the two transforms,

   $$M_{FFT} = 2 \times \frac{N}{2}\log_2 N \times 4 = 4N\log_2 N = 4Nq \;\text{real multiplications.}$$

   The saving grows without bound with block length:

   $$\boxed{\frac{M_{direct}}{M_{FFT}} = \frac{8N^{2}}{4Nq} = \frac{2N}{q} = \frac{2N}{\log_2 N}.}$$

   For a representative $N = 1024$ ($q = 10$) that is $8\,388\,608$ real multiplications directly against $40\,960$ by FFT — a factor of $204.8$. (Counting the trivial twiddles $W_N^{0} = 1$ as free would reduce both figures slightly; the ratio is essentially unchanged, and the un-pruned count is the standard textbook answer.)