I'm trying to figure out how the FFT splitting algorithm works. I've pretty much understood the general idea, but when I try to compute it, I get something completely different than what I expect
$ x = [ 3, 2, 1, 2, 1, 2 ] $
Therefore the frequency spectrum is (computed with MATLAB),
$ X = [ 11, 2, 2, -1, 2, 2 ] $
Computing the FFT on even and odds indices separately, I get
$ Y = fft(x(2:2:N)) = fft([2,2,2]) = [ 6, 0, 0 ] $
and
$ Z = fft(x(1:2:N)) = fft([3,1,1]) = [ 5, 2, 2 ] $
combining with the butterfly scheme $ X_n = Y_n + w^n_N Z_n $ and $ X_{n+\frac{N}{2}} = Y_n - w^n_N Z_n $ I get
$ X_0 = Y_0 + e^{i2\pi 0/6} Z_0 = 6 + 1*5 = 11 $ correct
$ X_1 = Y_1 + e^{i2\pi 1/6} Z_1 = 0 + (0.5 + 0.86i)*2 = 1 + 1.17i $ wrong
$ X_2 = Y_2 + e^{i2\pi 2/6} Z_2 = 0 + (0.5 - 0.86i)*2 = 1 - 1.17i $ wrong
$ X_3 = Y_3 - e^{i2\pi 1/6} Z_3 = 6 - (11)5 = -1 $ correct
$ X_4 = Y_4 - e^{i2\pi 2/6} Z_4 = 0 - (0.5 + 0.86i)*2 = - 1 + 1.17i $ wrong
$ X_5 = Y_5 - e^{i2\pi 3/6} Z_5 = 0 - (0.5 - 0.86i)*2 = - 1 - 1.17i $ wrong
How can that be? Do you see any mistake?
Thanks in advance
The values you have are correct, but they are assigned to the wrong variables. You say $Y$ is the transform of the even indices, but the values you have are for the transform of the odd indices. And the values you have for $Z$ are actually the values for the even indices.
Are arrays in Matlab 1-indexed (i.e. the indices start at 1)? Then you should consider that usually arrays are considered to be 0-indexed when dealing with FFT.
The formulas are, for $0 \leq k < \frac{N}{2}$: $$X_k = E_k + e^{\frac{2\pi i}{N} k} O_k$$ $$X_{k + N/2} = E_k - e^{\frac{2\pi i}{N} k} O_k$$ where $E_k$ is the $k$:th element in the transform of the even indices and $O_k$ is the $k$:th element in the transform of the odd indices. What you have done is swap the places of $E_k$ and $O_k$, multiplying $E_k$ with the exponential.
Your calculation for $X_3$ also looks wrong in other ways, but that's probably just a copying error or something like that.
Thus you get:
$$\begin{align} X_0 &= E_0 + e^0O_0 = 5 + 6 = 11 \\ X_1 &= E_1 + e^{\frac{2\pi i}{6}}O_1 = 2 + 0 = 2 \\ X_2 &= E_2 + e^{\frac{2\pi i}{3}}O_2 = 2 + 0 = 2 \\ X_3 &= E_0 - e^0O_0 = 5 - 6 = -1 \\ X_4 &= E_1 - e^{\frac{2\pi i}{6}}O_1 = 2 - 0 = 2 \\ X_5 &= E_2 -e^{\frac{2\pi i}{3}}O_2 = 2 - 0 = 2 \end{align}$$