2
$\begingroup$

I am doing FFT. The one way I did is to put real part in one array and the imaginary part as zeros and then calculated the FFT. But this take up lots of resources. Now I want to calculate FFT by Dividing Real Input by 2 in the form of ODD and EVEN samples and put even in real array and odd in Imaginary array. Then calculate the FFT. But after the FFT calculation how can I combine them to get the same results as I got when I used imaginary as zero's.

Any idea??

$\endgroup$
  • $\begingroup$ This answer should also answer your question. $\endgroup$ – Matt L. Apr 18 '16 at 11:11
3
$\begingroup$

You can use Decimation In Time (DIT) to calculate the FFT of single $N$ length sequence, using two $N/2$ sequences and combine them later on with a single butterfly.

Knowing that FFT of an even length, real sequence, can be decomposed into even and odd part as:

$$\begin{align} \mathrm{FFT_N}(x)&=\sum_{m=0}^{N/2-1}x(2m)e^{-2\pi j k(2m)/N} + \sum_{m=0}^{N/2-1}x(2m+1)e^{-2\pi j k(2m+1)/N}\\ &=\sum_{m=0}^{N/2-1}x(2m)e^{\frac{-2 \pi j k m}{N/2}}+e^{-2\pi j k/N} \sum_{m=0}^{N/2-1}x(2m+1)e^{\frac{-2\pi j k m}{N/2}} \\ &= \mathrm{FFT}_{N/2}(x_{even})+e^{-2\pi j k/N}\mathrm{FFT}_{N/2}(x_{odd}) \end{align}$$

and the following holds:

$x_{even}(m)=x(2m)$

$x_{odd}(m)=x(2m+1)$

Now you can form the imaginary signal from both:

$$\hat{x}(m)=x_{even}(m)+jx_{odd}(m)$$ for $m=0\ldots N/2-1$

Calculate the FFT of that complex sequence:

$$\hat{X}=\mathrm{FFT}_{N/2}(\hat{x})$$

Now you can extract corresponding FFT's of both even and odd part:

$$X_{even}(k)=\frac{\hat{X}(k)+\hat{X}(N/2-k)^*}{2}$$ $$X_{odd}(k)=-j\frac{\hat{X}(k)-\hat{X}(N/2-k)^*}{2}$$

And combine them using a butterfly:

$$X(k)=X_{even}(k)+e^{-2\pi j k /N}X_{odd}(k)$$

Keep in mind that those values are for $k=0\ldots N/2-1$. The missing value for $N/2$ can be obtained knowing the symmetry:

$$X(N/2)=\frac{[\hat{X}(0)+\hat{X}^*(0)]+j[\hat{X}(0)-\hat{X}^*(0)]}{2} $$

And that gives you the final result.

$\endgroup$

protected by jojek Apr 18 '16 at 14:03

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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