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.

enter image description here

  • 1
    $\begingroup$ 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. $\endgroup$ – Fat32 Dec 2 '18 at 17:48

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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