Question 7 of 7: Computing the IDFT with a Forward-DFT Block

Question 7: Computing the IDFT with a Forward-DFT Block (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. A hardware block that computes only the forward transform $X[k] = \sum_{n} x[n] W_N^{kn}$, with separate real and imaginary input and output rails; the IDFT is defined as $x[n] = \frac{1}{N}\sum_{k} X[k] W_N^{-kn}$; the worked case is $X[k] = \{1, 1+2j, 1, 1-2j\}$ with $N = 4$.

Find. (a) external wiring that turns the forward box into an inverse transform; (b) a proof that the real/imaginary swap of Figure 4 does the same job; (c) the sequence $x[n]$ obtained by that second method.

Approach. Both schemes exploit the single fact that the inverse kernel $W_N^{-kn}$ is the conjugate of the forward kernel $W_N^{kn}$. Conjugation can be realised either by negating the imaginary rail (part a) or by exchanging the real and imaginary rails, which is conjugation followed by multiplication by $j$ (part b).

1. (a) Conjugate in, conjugate out, scale by $1/N$. Start from the IDFT definition and conjugate the whole expression:
   $$x[n] = \frac{1}{N}\sum_{k=0}^{N-1} X[k] W_N^{-kn} = \frac{1}{N}\left[\sum_{k=0}^{N-1} X^{*}[k] W_N^{kn}\right]^{*} = \frac{1}{N}\Big(\text{DFT}\big\{X^{*}[k]\big\}\Big)^{*}.$$

   The bracketed sum is precisely what the box computes, so the required external modifications are:

   (i) negate the imaginary input rail, feeding $\mathrm{Re}\{X[k]\}$ and $-\mathrm{Im}\{X[k]\}$ into the box; (ii) negate the imaginary output rail; (iii) scale both output rails by $1/N$.

   Part (a): the conjugate-transform-conjugate route. Two sign inversions on the imaginary rail and a 1/N gain on each output turn the forward DFT block into an IDFT.

   The box itself is untouched, which is the point of the question: a fixed-function FFT peripheral can serve both directions with three trivial external operations and no extra transform hardware.

2. (b) Prove the real/imaginary swap of Figure 4. The defining relations (8) say that $q[n]$ takes the imaginary part of $X$ as its real part and vice versa. Writing $X[n] = a + jb$ gives $q[n] = b + ja = j(a - jb)$, that is
   $$q[n] = j\,X^{*}[n].$$

   Transforming $q[n]$ with the forward kernel and pulling the conjugation outside the sum,

   $$Q[k] = \sum_{n=0}^{N-1} j X^{*}[n] W_N^{kn} = j\left[\sum_{n=0}^{N-1} X[n] W_N^{-kn}\right]^{*} = j\left[N x[k]\right]^{*} = jN\,x^{*}[k],$$

   where the middle step used the IDFT definition with the roles of the index names exchanged. Now write $x[k] = c + jd$; then $jN x^{*}[k] = jN(c - jd) = N(d + jc)$, so

   $$\mathrm{Re}\{Q[k]\} = N\,\mathrm{Im}\{x[k]\}, \qquad \mathrm{Im}\{Q[k]\} = N\,\mathrm{Re}\{x[k]\}.$$

   Dividing by $N$ and reading the two lines the other way round gives exactly Equation (9):

   $$\boxed{\mathrm{Re}\{x[n]\} = \frac{1}{N}\mathrm{Im}\{Q[k]\}\Big|_{k=n}, \qquad \mathrm{Im}\{x[n]\} = \frac{1}{N}\mathrm{Re}\{Q[k]\}\Big|_{k=n}.}$$

   The swap therefore has to appear twice — once on the way in and once on the way out — which is exactly the crossed wiring drawn in Figure 4, together with the $1/N$ gains.

   Part (b): the real/imaginary swap route of Figure 4. The rails cross before and after the box, and each output is scaled by 1/N. No sign inverters are needed at all.

   Compared with (a) this version needs no negation hardware — on a fixed-point machine a wire crossing is free whereas a two's-complement negation is not — which is why it is the version usually built.

3. (c) Apply the part-(b) method to $X[k] = \{1,\, 1+2j,\, 1,\, 1-2j\}$. First form $q[n]$ by swapping the real and imaginary parts of each element:
   $$q[n] = \{\,j,\;\; 2 + j,\;\; j,\;\; -2 + j\,\}.$$

   Now take the 4-point forward DFT of $q[n]$, using $W_4 = e^{-j\pi/2} = -j$ so that $W_4^{kn} = (-j)^{kn}$:

   $$\begin{aligned}Q[0] &= q[0] + q[1] + q[2] + q[3] = (0 + 2 + 0 - 2) + j(1+1+1+1) = 4j,\\Q[1] &= q[0] - j q[1] - q[2] + j q[3] = -4j,\\Q[2] &= q[0] - q[1] + q[2] - q[3] = 0,\\Q[3] &= q[0] + j q[1] - q[2] - j q[3] = 4j.\end{aligned}$$

   Finally apply Equation (9): the real part of $x[n]$ is $\tfrac{1}{4}\mathrm{Im}\{Q[n]\}$ and its imaginary part is $\tfrac{1}{4}\mathrm{Re}\{Q[n]\}$. Since every $Q[k]$ here is purely imaginary, every $x[n]$ comes out purely real:

   $$\boxed{x[n] = \left\{1,\; -1,\; 0,\; 1\right\}, \quad n = 0, 1, 2, 3.}$$

   The answer is self-checking: transforming $\{1, -1, 0, 1\}$ forward returns $X[0] = 1$, $X[1] = 1 + 2j$, $X[2] = 1$, $X[3] = 1 - 2j$, the given data. The fact that $x[n]$ is real also had to show up in the given $X[k]$ as conjugate symmetry, $X[3] = X^{*}[1]$, which it does.