0
$\begingroup$

I can't understand the basic principle on which the Cooley Tukey algorithm is based, the algorithm says I can split in two parts the DFT computation like in the following

$\begin{matrix} X_k= \underbrace{\sum \limits_{m=0}^{N/2-1} x_{2m} e^{-\frac{2\pi i}{N/2} mk}}_{\mathrm{DFT\;of\;even-indexed\;part\;of\;} x_m} {} + e^{-\frac{2\pi i}{N}k} \underbrace{\sum \limits_{m=0}^{N/2-1} x_{2m+1} e^{-\frac{2\pi i}{N/2} mk}}_{\mathrm{DFT\;of\;odd-indexed\;part\;of\;} x_m} = E_k + e^{-\frac{2\pi i}{N}k} O_k.\end{matrix}$ Formula 1.0

The algorithm then says that I may avoid the computation process of half the data because it is valid

$\begin{matrix} X_k & =& \left\{\begin{matrix}E_k + e^{-\frac{2\pi i}{N}k} O_k & \mbox{if } k < N/2 \\ \\E_{k-N/2} - e^{-\frac{2\pi i}{N} (k-N/2)} O_{k-N/2} & \mbox{if }k \geq N/2. \end{matrix} \right. \end{matrix}$ Formula 1.1

But I can't understand this.

I tried with an example: I took a simple vector

x=[0 1]

to transform with a DFT with Cooley Tukey, here's what I did: following the basic DFT formula

$X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} nk}$

I'm getting

$X_0 = 0 + 1$

$X_1 = 0 + e^{-\pi i}$

And this should be the classic approach. Now if I split the x vector in two elements, I'll have two parts: one (the 0 element) with even indices and the other (the 1 element) with odd indices. Applying the 1.0 formula everything is going well, but the 1.1 formula isn't working.. I can't obtain X0 and X1 by using that

Where am I getting wrong?

  • 0
    Than$k$ you for your help, the post below solved the problem.. I'm just stupid :(2011-05-15

1 Answers 1

1

Formula 1.1 seems to be working fine. We have $E_0=x_0=0$ and $O_0=x_1=1$. Since $N/2=1$, the upper row of 1.1 applies for $k=0$ and the lower row applies for $k=1$. Plugging $k=0$ into the upper row yields $X_0=E_0+O_0=x_0+x_1=0+1$, and plugging $k=1$ into the lower row yields $x_1=E_0-O_0=x_0-x_1=0-1$, which is the same as what you wrote, since $\mathrm e^{-\pi i}=-1$.

  • 0
    Sorry for that too2011-05-15