Question 5 of 6: Computing an inverse DFT with a forward FFT subroutine

Question 5: Computing an inverse DFT with a forward FFT subroutine (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 forward $N$-point DFT subroutine $\mathrm{DFT}\{\cdot\}$ implementing $X[k] = \sum_{n=0}^{N-1} x[n]W_{N}^{kn}$ with $W_{N} = e^{-j2\pi/N}$, the four-step procedure above, and the hint that swapping real and imaginary parts of $A$ is the operation $\mathcal{S}\{A\} = (-jA)^{*}$.

Find. Whether the four steps return $x[n] = \frac{1}{N}\sum_{k}X[k]W_{N}^{-kn}$; a proof if they do, or the smallest repair if they do not.

Approach. Convert the swap into algebra with the hint, push it through the DFT sum using the fact that conjugation turns $W_{N}^{+kn}$ into $W_{N}^{-kn}$, and compare the result with the definition of the inverse DFT.

1. Put the swap into algebra. Writing $A = a + jb$, the swap must return $b + ja$. Check the hint: $$(-jA)^{*} = \left(-j(a+jb)\right)^{*} = (b - ja)^{*} = b + ja \;=\; \mathcal{S}\{A\},$$ and the same operation may be written more compactly as $$\boxed{\;\mathcal{S}\{A\} = (-jA)^{*} = j\,A^{*}\;}$$ The second form is the convenient one, because it separates a conjugation (which will flip the DFT kernel) from a constant factor $j$ (which will simply be carried along).
2. Step 1 — the swapped input. Applying $\mathcal{S}$ to every DFT value gives the array $$X_{1}[k] = \mathcal{S}\{X[k]\} = j\,X^{*}[k].$$
3. Step 2 — run the forward FFT on it. Using linearity to pull the constant $j$ out, and then the identity $\left(X[k]e^{+j2\pi kn/N}\right)^{*} = X^{*}[k]e^{-j2\pi kn/N}$ to fold the kernel into the conjugate, $$Y[n] = \sum_{k=0}^{N-1} X_{1}[k]\,W_{N}^{kn} = j\sum_{k=0}^{N-1} X^{*}[k]\,e^{-j2\pi kn/N} = j\left[\sum_{k=0}^{N-1} X[k]\,e^{+j2\pi kn/N}\right]^{*}.$$ The bracket is precisely $N$ times the inverse DFT of $X[k]$, i.e. $N x[n]$. Hence $$\boxed{\;Y[n] = j\,N\,x^{*}[n]\;}$$ This is the crux of the question: conjugating the input converts the subroutine's forward kernel $W_{N}^{+kn}$ into the inverse kernel $W_{N}^{-kn}$, at the cost of leaving the answer conjugated and multiplied by $j$.
4. Step 3 — the second swap removes both blemishes. Applying $\mathcal{S}\{A\} = jA^{*}$ once more, $$Y_{2}[n] = \mathcal{S}\{Y[n]\} = j\left(j N x^{*}[n]\right)^{*} = j\left(-j N x[n]\right) = N\,x[n].$$ The conjugation in the second swap undoes the conjugation left by step 2, and the two factors of $j$ combine as $j\cdot(-j) = 1$.
5. Step 4 — scale. Dividing by $N$ gives $$\boxed{\;\frac{1}{N}Y_{2}[n] = x[n]\;}$$ so the procedure does work exactly as claimed, for arbitrary complex $x[n]$ and any $N$ — no modification is required.
6. Two remarks that the marker is looking for. First, the result is independent of the sign convention chosen for "swap": if one instead defines $\mathcal{S}'\{A\} = -\mathcal{S}\{A\} = -jA^{*}$, then step 2 returns $-jNx^{*}[n]$ and step 3 returns $-j(-jNx^{*}[n])^{*} = -j(jNx[n]) = Nx[n]$ again. The two swaps always cancel each other's sign, which is why the method is robust in practice. Second, a single swap would not do: applying the forward DFT directly to $X[k]$ and scaling by $1/N$ gives the circular time reversal $$\frac{1}{N}\sum_{k}X[k]W_{N}^{kn} = x\!\left[\langle -n\rangle_{N}\right],$$ not $x[n]$ — which is the well-known "DFT applied twice" identity. It is the pair of swaps, one before and one after, that turns the reversal into a genuine inversion.
7. Numerical confirmation, $N = 4$. Take $x[n] = \{1,\,2,\,-1,\,3\}$, whose 4-point DFT is $X[k] = \{5,\;2+j,\;-5,\;2-j\}$. Step 1 swaps to $X_{1}[k] = \{j,\;1+2j,\;-5j,\;-1+2j\}$; step 2 returns $Y[n] = \{4j,\;8j,\;-4j,\;12j\} = j\cdot4\cdot x^{*}[n]$ since $x$ is real; step 3 swaps to $\{4,\,8,\,-4,\,12\}$; and step 4 divides by $N = 4$ to recover $\{1,\,2,\,-1,\,3\} = x[n]$ exactly.

The practical value of the result is that no separate inverse-FFT routine is needed: a single forward FFT plus $2N$ real data moves and one scaling gives the inverse, so the arithmetic cost is the same $O(N\log_{2}N)$ and the extra work is negligible. The same reasoning underlies the more familiar conjugate-based recipe $x[n] = \frac{1}{N}\left(\mathrm{DFT}\{X^{*}[k]\}\right)^{*}$, which is the identical argument with the factors of $j$ omitted.