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??
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.
