Show how to compute the DFT of four real, even, length- \(N\) sequences using only one length- \(N\) transform, using the results of Exercise 3.9.

Exercise 3.9

Show how to compute the DFT of two even complex length- \(N\) sequences performing only one length \(N\) transform calculation. Follow the steps below:

(i) Build the auxiliary sequence \(y(n)=W_{N}^{n} x_{1}(n)+x_{2}(n)\).

(ii) Show that \(Y(k)=X_{1}(k+1)+X_{2}(k)\).

(iii) Using properties of symmetric sequences, show that \(Y(-k-1)=X_{1}(k)+X_{2}(k+1)\).

(iv) Use the results of (ii) and (iii) to create a recursion to compute \(X_{1}(k)\) and \(X_{2}(k)\). Note that \(X(0)=\sum_{n=0}^{N-1} x(n)\).