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
    A tiny note on quoting formulae from Wikipedia: usually there is (not always optimal) $\TeX$ code within the "image properties" for a formula (obtainable through right-clicking).2011-05-15
  • 0
    I didn't think about that, thank you2011-05-15
  • 0
    Note that the scheme for Cooley-Tukey is to "decimate" until you reach the point where you have to take the DFT of a single number, which is equivalent to the identity operation...2011-05-15
  • 0
    Anyway should be possible to use the 1.1 formula for a two-items vector, right? Despite of having just two elements, the x vector can still be splitted in two parts2011-05-15
  • 0
    Yes, so what should $E_0$ and $O_0$ be? You can then use the "splitting formula" (the second one in your post).2011-05-15
  • 0
    Thank 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
    $e^{−\pi i}=−1$ goddamn this, I'm an idiot. Thank you joriki, you solved my problem2011-05-15
  • 0
    Er, the rough language is frowned upon in these parts, @Paul. ;) (I don't mind, but others do.)2011-05-15
  • 0
    Sorry for that too2011-05-15