2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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: enter image description here

We calculate "butterflies" in following manner:

enter image description here

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!

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.