Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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]$$

share|improve this question
1  
Hint: what is the relationship between the DFTs of the $x_k$ and the DFT of $x_1+i x_2$? –  J. M. Sep 11 '12 at 10:15
    
Not sure how that helps, given that DFTs are complex operations and the results will always end up having an imaginary component anyway. –  fayaz Sep 12 '12 at 15:27
    
Clearly, you don't know about this... –  J. M. Sep 13 '12 at 0:06
    
That'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? –  fayaz Sep 13 '12 at 10:01
    
I'll let you do the writing, since you seem to have figured it out on your own from my hint... –  J. M. Sep 13 '12 at 12:23

1 Answer 1

up vote 0 down vote accepted

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}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.