# FFT of a $N$-length real sequence via FFT of a $N/2$-length complex sequence

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.

## 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).