# complex multiplier in divide and combine FFT

I am studying radix 2 algorith from Proakis' book.

But I'm a bit confusied why 1st DFT $$G_1$$ is not multiplied by complex entity while 2nd DFT $$G_2$$ is being multiplied by complex entity $$W$$ as shown highlighted in attached figure.

• Hi! Have you tried wiriting the DFT of x[n] by dividing it into even and odd sampled sequences g1[n] and g2[n] ? The weight will come from that DFT. – Fat32 Dec 2 '18 at 17:48

## 1 Answer

Now as the document says, let $$x[n]$$ be a length $$N$$ (even) sequence whose even and odd indexed samples are denoted as $$g_1[n]$$ and $$g_2[n]$$ of length $$N/2$$ each.

Then the $$N$$-point DFT $$X[k]$$ of $$x[n]$$ can be written as folows:

\begin{align} X[k] &= \sum_{n=0}^{N-1} x[n] e^{ -j \frac{2\pi}{N} n k} ~~~,~~ k = 0,1,...,N-1 \\\\ &= \sum_{n=0,2,4}^{N-1} x[n] e^{ -j \frac{2\pi}{N} n k} + \sum_{n=1,3,5}^{N-1} x[n] e^{ -j \frac{2\pi}{N} n k}\\\\ &= \sum_{m=0}^{N/2-1} x[2m] e^{ -j \frac{2\pi}{N} 2m k} + \sum_{m=0}^{N/2-1} x[2m+1] e^{ -j \frac{2\pi}{N} (2m+1) k}\\\\ &= \sum_{m=0}^{N/2-1} g_1[m] e^{ -j \frac{2\pi}{N/2} m k} + e^{ -j \frac{2\pi}{N} k} \sum_{m=1}^{N/2-1} g_2[m] e^{ -j \frac{2\pi}{N/2} m k} \\\\ &= \left( \sum_{m=0}^{N/2-1} g_1[m] e^{ -j \frac{2\pi}{N/2} m k} \right) + e^{ -j \frac{2\pi}{N} k} \left( \sum_{m=1}^{N/2-1} g_2[m] e^{ -j \frac{2\pi}{N/2} m k} \right) \\\\ &= G_1[k] + W_N^k G_2[k] ~~~,~~ k = 0,1,2...,N-1 \\ \end{align}

Where we have recognized the summations inside the parenthesis as the $$N/2$$ point DFTs of the sequences $$g_1[n]$$ and $$g_2[n]$$ respectively. Note that when $$k$$ spans the range $$k=0,1,...,N-1$$, the $$N/2$$ point DFTs will repeat twice.