3 a Find DFT of the given image using DIT-FFT.

DFT of the image:

\[F = \begin{bmatrix}33 & -7 & 1 & -7\\ -9 & -1 & -1 & -1\\ 1 & 1 & 1 & 1\\ -9 & -1 & -1 & -1\end{bmatrix}\]

The 2-D DFT is separable: apply a 4-point FFT to every row, then to every column of the result.

4-point DIT-FFT butterfly. Input in bit-reversed order \(x_0, x_2, x_1, x_3\); \(W_4^0 = 1\), \(W_4^1 = -j\).

• Stage 1: \(a = x_0 + x_2\), \(b = x_0 - x_2\), \(c = x_1 + x_3\), \(d = x_1 - x_3\)
• Stage 2: \(X_0 = a + c\), \(X_1 = b - jd\), \(X_2 = a - c\), \(X_3 = b + jd\)

Step 1: FFT of each row

Step 2: FFT of each column of this result

Writing each column result as a column of \(F\) gives the matrix above.

Checks

• \(F(0,0) = 33\) equals the sum of all pixels (0+1+2+1+1+2+3+2+3+3+4+3+1+2+3+2 = 33).
• All values are real because in every row and every column \(x_1 = x_3\) (the image is symmetric), so the \(d\) terms are 0.