As far as I know, the 3 steps of FFT while solving $F_nc = y$ :

  1. Split c into c', c'' such that c' contains elements with even indexes from c and c'' contains the odd ones.

  2. Now we have $F_mc' = y'$ and $F_mc' = y''$ where $m = n/2$

  3. To combine $y',y''$ we use the formula

but while I was solving a problem, the solution was just: $\begin{bmatrix} y' \\ y'' \end{bmatrix} = y$


Let $n=2m$. $$F_k=\sum_{j=0}^{n-1} \omega^{kj}f_j=\sum_{j=0}^{m-1}\omega^{k(2j)}f_{2j}+\sum_{j=0}^{m-1} \omega^{k(2j+1)}f_{2j+1}=\sum_{j=0}^{m-1}(\omega^2)^{kj}(f_{2j}+\omega^kf_{2j+1})=\sum_{j=0}^{m-1}(\omega^2)^{kj}g_j$$

where $\omega$ is an $n^{th}$ root of unity. Notice that $\omega^2$ is an $m^{th}$ root of unity and we have $$\omega^{k+m}=-\omega^k.$$

This shows that the DFT on the $n$ points $f_j$ can be computed by concateneting two DFTs on the $m$ points $f_{2j}+\omega^kf_{2j+1}$ and $f_{2j}-\omega^kf_{2j+1}$ respectively, which are linear combinaisons of the even and odd elements of the initial sequence.

E.g., with $n=4$, $\omega=i$ and for $k=0,1$,

$$F_k=f_0+i^kf_1+i^{2k}f_2+i^{3k}f_3=(f_0+i^kf_1)+i^{2k}(f_2+i^kf_3) \\=(f_0+i^kf_1)+(-1)^k(f_2+i^kf_3), \\F_{k+2}=(f_0+i^{k+2}f_1)+(-1)^k(f_2+i^{k+2}f_3) \\=(f_0-i^kf_1)+(-1)^k(f_2-i^kf_3).$$

  • $\begingroup$ sorry but my question is that I saw 2 ways of solving this question and they don't give the same result. Which one of them is the correct one ? :| $\endgroup$ – Mohamad Ziad Alkabakibi Apr 9 at 7:35
  • $\begingroup$ @MohamadZiadAlkabakibi: it is unclear what your two solutions are. Please explain. $\endgroup$ – Yves Daoust Apr 9 at 7:39

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.