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
-
1Hint: what is the relationship between the DFTs of the $x_k$ and the DFT of $x_1+i x_2$? – 2012-09-11
-
0Not sure how that helps, given that DFTs are complex operations and the results will always end up having an imaginary component anyway. – 2012-09-12
-
0Clearly, you don't know about [this](http://books.google.com/books?hl=en&id=48rQQ8v2rKEC&pg=PA32)... – 2012-09-13
-
0That's wonderful. I think I could solve it now. So if you put up an answer, I could accept it. Or should I do that? – 2012-09-13
-
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}$$