# Problems calculating 8-point FFT of an 8-point sine wave by hand

I need a small help for my assignment, which is to solve the 8-point FFT without using Matlab or C.

Preliminary information:

8-point sine wave: [0, 0.7071, 1, 0.7071, 0, -0.7071, -1, -0.7071]

8-point complex exponential: [1, 0.7071-j0.7071, -j, -0.7071-j0.7071]

So here's the attempts I did:

1.) Bit reversing the 8-point sine wave and rearrange it to:

[0, 0, 1, -1, 0.7071, -0.7071, 0.7071, -0.7071]

2.) Perform each butterfly calculation:

First pass: [0, 0, 0, 2, 0, 1.414, 0, 1.414]

Second pass: [0, -j2, 0, 2, 0, 1.414-j1.414, 0, 1.414+j1.414]

And the last: [0, -j4, 0, 2-j2, 0, 2.828, 0, 2.828-j2.828]

However, the last pass which is the result does not match with the actual FFT result in Matlab:

[0, -j4, 0, 0, 0, 0, 0, j4]

Any steps I might have missed? Opinions and pointers are greatly appreciated. Thanks.

I will start from very beginning. So having signal: $x[n] = [0; \ 0.7071; \ 1; \ 0.7071; \ 0; \ -0.7071; \ -1; \ -0.7071]$ and given exponent: $w[n] = [1; \ 0.7071 - 0.7071i; \ -i; \ -0.7071 - 0.7071i;\ -1;\ -0.7071 + 0.7071i; \ i; \ 0.7071 + 0.7071i]$.

First we need to inverse the bits and rearrange our signal. For 8 samples we will obtain following change in indices: $[0;\ 1;\ 2;\ 3;\ 4;\ 5;\ 6;\ 7] \Rightarrow [0;\ 4;\ 2;\ 6;\ 1;\ 5;\ 3;\ 7]$, thus our signal becomes: $x[n] = [0; \ 0; \ 1; \ -1; \ 0.7071; \ -0.7071; \ 0.7071; \ -0.7071]$.

Now according to following schematic:

We calculate "butterflies" in following manner:

Where: $W_{N}^{k} = e^{\dfrac{-2\pi i k}{N}}$ (rotating vector on our complex plane with step angle of $2 \pi/N$ )

Starting from a first butterfly in first stage ($x[0]$ and $x[4]$ as the inputs) we have following:

$A = 0, B = 0, W_8^0=w[0]=1$, giving output: $[0; 0]$, next butterfly:

$A = 1, B = -1, W_8^0=w[0]=1$, giving output: $[0; 2]$, next butterfly:

$A = 0.7071, B = -0.7071, W_8^0=w[0]=1$, giving output: $[0; 1.4142]$, next butterfly is the same with output: $[0; 1.4142]$.

So now, after first pass our vector is as follows (same to the one obtained by Peter Griffin):

$x'[n]=[0; \ 0; \ 0; \ 2; \ 0; \ 1.4142; \ 0; \ 1.4142]$

At second stage, first butterfly consists of samples: $x'[0]$ and $x'[2]$, where $W_8^0=1$. We can therefore calculate the output as: $[0+1\cdot 0; \ 0-1\cdot 0] = [0; \ 0]$. These are outputs $x''[0]$ and $x''[2]$ of the second stage.

Next butterfly is given by inputs $x'[1]$ and $x'[3]$, where $W_8^2=w[2]=-i$. We calculate output $x''[1]$, $x''[3]$ as: $[0-i\cdot 2; \ 0-(-i)\cdot 2] = [-2i; \ 2i]$

Two following butterflies are calculated in the same manner:

$[0+1\cdot 0; \ 0-1\cdot 0] = [0; \ 0] \Rightarrow x''[4]$, $x''[6]$

$[1.4142-i\cdot 1.4142; \ 1.4142-(-i)\cdot 1.4142] = [1.4142-1.4142i; \ 1.4142+1.4142 i] \Rightarrow x''[4], \ x''[6]$

So our vector after second stage is following:

$x''[n] = [0; \ -2i; \ 0; \ 2i; \ 0; \ 1.4142-1.4142i; \ 0; \ 1.4142+1.4142i]$ - you've made a mistake here.

Finally, we calculate results for third stage. By looking at the main schematic, first butterfly consists of samples: $x''[0], x''[4] = [0; 0]$. The $W_N^k$ coefficient is given by $W_8^0=w[0]=1$.

Calculating butterfly we obtain:

$[0+1\cdot 0; \ 0+(-1)\cdot 0] = [0; \ 0]$ - these are final FFT values $X[0], X[4]$.

Moving to next butterfly based on samples $x''[1], x''[5] = [-2i; 1.4142-1.4142i]$ with coefficient $W_8^1=w[1]=0.7071 - 0.7071i$. Result: $[-2i+(0.7071 - 0.7071i)\cdot (1.4142-1.4142i); \ -2i-(0.7071 - 0.7071i)\cdot (1.4142-1.4142i)] = [-4i; \ 0]$

And next butterfly based on samples $x''[2], x''[6] = [0; \ 0]$, with $W_8^2=w[2]=-i$ will give $[0+(-i)0; \ 0-(-i)0] = [0; \ 0]$

And the last butter fly based on samples $x''[3], x''[7] = [2i; \ 1.4142+1.4142i]$, with $W_8^3=w[2]=-0.7071 - 0.7071i$ will result in: $[2i+(-0.7071 - 0.7071i)\cdot (1.4142+1.4142i); \ 2i-(-0.7071 - 0.7071i)\cdot (1.4142+1.4142i)] = [0; \ 4i]$

So our final vector is following:

$X[k] = [0; \ -4i; \ 0; \ 0; \ 0; \ 0; \ 0; \ 4i]$

Which means MATLAB is calculating FFT correctly ;)

One final remark - always take care about $W_N^k$ factor - look on the schematic and it's pretty obvious.

Good luck!

The problem is the second pass. The fourth element should be $2i$ instead of $2$. Then everything works out properly. Because the signal is real-valued you have some form of conjugate symmetry in each pass.