Given an 8 point FFT processor, which can be used only once, compute the DFTs of the sequence. $x_1(n)=[1,8,6,7,4,2,3,1]$ $x_2(n)=[1,4,3,2,8,7,6,1]$
FFT processor which can only be used once
-
0I'll let you do the writing, since you seem to have figured it out on your own from my hint... – 2012-09-13
1 Answers
Let $y(n)=x_1(n)+jx_2(n)$. $\therefore y(n)=[(1+1j), (8+4j), (6+3j), (7+2j), (4+8j), (2+7j), (3+6j), (1+1j)]$
Now we can calculate the DFT of $y(n)$ by using the single 8 point FFT processor. $\begin{align} \therefore Y(k) & = \sum_{n=0}^{N-1}{y(n)e^{-{2\pi{}jnk\over N}}} \\ & =\begin{bmatrix} (32 + 32j) \\ \left(-6 - \sqrt{2} +j \left(- 8 \sqrt{2} -10\right)\right) \\ (4 - 2j) \\ (- \sqrt{2} +j \left(- 4 \sqrt{2} -4\right)) \\ (-4 + 4j) \\ (-6 + \sqrt{2} +j \left(-10 + 8 \sqrt{2}\right)) \\ (-12 + 2j) \\ (\sqrt{2} +j \left(-4 + 4 \sqrt{2}\right)) \end{bmatrix} \end{align}$
Since DFTs are linear, $\begin{align} Y(k) & =DFT\big(x_1(n)+jx_2(n)\big) \\ & =X_1(k)+jX_2(k) \tag{1}\\ \end{align}$ where $X_1(k)$ and $X_2(k)$ are the DFTs of $x_1(n)$ and $x_2(n)$ respectively.
Taking conjugate on both sides we have, $Y^*(k) = X_1^*(k)-jX_2^*(k)$ where $X^*$ denotes complex conjugation.
Also trivially, $Y^*(N-k) = X_1^*(N-k)-jX_2^*(N-k)$ where $N$ is the length of the DFT, which is $8$ here.
By the property of symmetry, if $x(n)$ consists of real numbers only, then, $X(k)=X^*(N-k)$ where $N$ is the length of the DFT. $\therefore Y^*(N-k)=X_1(k)-jX_2(k) \tag{2}$ From equations (1) & (2), we have, $\begin{align} X_1(k) & ={Y(k)+Y^*(N-k)\over 2}\\ X_2(k) & ={Y(k)-Y^*(N-k)\over 2j}\\ \text{and, } Y^*(N-k) & =\begin{bmatrix} (32 - 32j) \\ (\sqrt{2} -j \left(-4 + 4 \sqrt{2}\right))\\ (-12 - 2j) \\ (-6 + \sqrt{2} -j \left(-10 + 8 \sqrt{2}\right)) \\ (-4 - 4j) \\ (- \sqrt{2} -j \left(- 4 \sqrt{2} -4\right)) \\ (4 + 2j) \\ \left(-6 - \sqrt{2} -j \left(- 8 \sqrt{2} -10\right)\right) \end{bmatrix}\\ \therefore X_1(k) & = \begin{bmatrix} 32\\ -3 +j \left(- 6 \sqrt{2} -3\right)\\ -4 - 2j\\ -3 +j \left(- 6 \sqrt{2} + 3\right)\\ -4\\ -3 +j \left(-3 + 6 \sqrt{2}\right)\\ -4 + 2j\\ -3 +j \left(3 + 6 \sqrt{2}\right) \end{bmatrix}\\ \text{and, }X_2(k) & =\begin{bmatrix} 32\\ -7 - 2 \sqrt{2} +j \left(\sqrt{2} + 3\right)\\ - 8j\\ -7 + 2 \sqrt{2} +j \left(-3 + \sqrt{2}\right)\\ 4\\ -7 + 2 \sqrt{2} +j \left(- \sqrt{2} + 3\right)\\ 8j\\ -7 - 2 \sqrt{2} +j \left(-3 - \sqrt{2}\right) \end{bmatrix} \end{align}$