Jtdylktuy

Given the following data:

Two period sine; samples = [0, 1, 0, -1, 0, 1, 0, -1];

I am asked to calculate the FFT of the sampled data to find the complex coefficients.

I don't necessarily want the answer to the problem, just the general steps that are used to calculate FFT and why they are useful.

I've tried looking up ways to calculate these but I find them all to be very confusing and full of unrelated jargon.

If your signal is $sin(4pi t)$ sampled at $8$ Hz, and you compute the DFT with the formula

$$ F_k = sum_{0 leq m < n} f_m e^{-i2pifrac{k}{n}{m}} enspace,$$

you know right away that the DFT is

$$[0, 0, -4i, 0, 0, 0, 4i, 0]^T enspace. $$

The coefficients can only be $0$ for frequencies different from $2$ Hz and its conjugate $6$ Hz. The two remaining coefficients must be imaginary and conjugates, because the signal is a sine, with the negative sign coming from the negative sign in $e^{-i2pifrac{k}{n}{m}}$. The $n/2 = 4$ factor is there because there is no "scaling" in the direct transform. (The division is in the inverse transform.)

Armed with these simple observations, you can transform simple signals for which you know the "recipe" (in this case, one sine wave at $2$ Hz) in a matter of seconds.

If you've been asked to show the FFT computation, follow @rafa11111's answer, but even then, before you start, you'll find it convenient to know what should come out of the computation.

Let $f = [0,1,0,-1,0,1,0,-1]^T$ be the sample values and $hat{f}$ be the transformed values. The DFT is given by $hat{f} = F_8 cdot f$, with $F_{8mn} = w_8^{mn}$, $w_8 = e^{-2pi i/8}$.

We split the even and the odd components of $f$ as
$$
f_{ev} = [0,0,0,0]^T, f_{od} = [1,-1,1,-1]^T,
$$
And $hat{f}$ is given by
$$
hat{f}_n = hat{f}_{ev,n} + w_8^n hat{f}_{od,n}, hat{f}_{n+4} = hat{f}_{ev,n} - w_8^n hat{f}_{od,n}
$$
with
$$
hat{f}_{ev} =F_4 cdot f_{ev}, hat{f}_{od} =F_4 cdot f_{od}.
$$

We can split $f_{ev}$ as
$$
f_{ev}^{ev} = [0,0]^T, f_{ev}^{od} = [0,0]^T,
$$
and $f_{od}$ as
$$
f_{od}^{ev} = [1,1]^T, f_{od}^{od} = [-1,-1]^T.
$$
Therefore,
$$
hat{f}_{ev,n} = hat{f}_{ev,n}^{ev} + w_4^n hat{f}_{ev,n}^{od}, hat{f}_{ev,n+2} = hat{f}_{ev,n}^{ev} - w_4^n hat{f}_{ev,n}^{od},
$$
$$
hat{f}_{od,n} = hat{f}_{od,n}^{ev} + w_4^n hat{f}_{od,n}^{od}, hat{f}_{od,n+2} = hat{f}_{od,n}^{ev} - w_4^n hat{f}_{od,n}^{od},
$$
with
$$
hat{f}_{ev}^{ev} = F_2 {f}_{ev}^{ev}, hat{f}_{ev}^{od} = F_2 {f}_{ev}^{od}, hat{f}_{od}^{ev} = F_2 {f}_{od}^{ev}, hat{f}_{od}^{od} = F_2 {f}_{od}^{od}
$$

$$
F_2 = begin{bmatrix}w_2^0 & w_2^0\w_2^0 & w_2^1end{bmatrix} = begin{bmatrix}1 & 1\ 1 & -1end{bmatrix}
$$
Therefore, with $w_2 = e^{-2pi i/2}=-1$,
$$
hat{f}_{ev}^{ev} = begin{bmatrix}1 & 1\ 1 & -1end{bmatrix} begin{bmatrix}0 \0 end{bmatrix} = begin{bmatrix}0 \0 end{bmatrix}
$$
$$
hat{f}_{ev}^{od} = begin{bmatrix}1 & 1\ 1 & -1end{bmatrix} begin{bmatrix}0 \0 end{bmatrix} = begin{bmatrix}0 \0 end{bmatrix}
$$
$$
hat{f}_{od}^{ev} = begin{bmatrix}1 & 1\ 1 & -1end{bmatrix} begin{bmatrix}1 \1 end{bmatrix} = begin{bmatrix}2 \0 end{bmatrix}
$$
$$
hat{f}_{od}^{od} = begin{bmatrix}1 & 1\ 1 & -1end{bmatrix} begin{bmatrix}-1 \-1 end{bmatrix} = begin{bmatrix}-2 \0 end{bmatrix}
$$

And, with $w_4 = e^{-2pi i/4} = -i$,
$$
hat{f}_{ev,0} = 0 + (-i)^0 0 = 0
$$
$$
hat{f}_{ev,1} = 0 + (-i)^1 0 = 0
$$
$$
hat{f}_{ev,2} = 0 - (-i)^0 0=0
$$
$$
hat{f}_{ev,3} = 0 - (-i)^1 0=0
$$

$$
hat{f}_{od,0} = 2 + (-i)^0 (-2) = 0
$$
$$
hat{f}_{od,1} = 0 + (-i)^1 0 = 0
$$
$$
hat{f}_{od,2} = 2 - (-i)^0 (-2) = 4
$$
$$
hat{f}_{od,3} = 0 - (-i)^1 0 = 0
$$
Therefore,
$$
hat{f}_{ev} = [0,0,0,0]^T, hat{f}_{od} = [0,0,4,0]^T
$$

Finally, with $w_8=e^{-2pi i/8} = sqrt{2}/2 - isqrt{2}/2$,
$$
hat{f}_0 = hat{f}_{ev,0} + w_8^0 hat{f}_{od,0} = 0
$$
$$
hat{f}_1 = hat{f}_{ev,1} + w_8^1 hat{f}_{od,1} = 0
$$
$$
hat{f}_2 = hat{f}_{ev,2} + w_8^2 hat{f}_{od,2} = 0 + 4(sqrt{2}/2 - isqrt{2}/2)^2=-4i
$$
$$
hat{f}_3 = hat{f}_{ev,3} + w_8^3 hat{f}_{od,3} = 0
$$
$$
hat{f}_4 = hat{f}_{ev,0} - w_8^0 hat{f}_{od,0} = 0
$$
$$
hat{f}_5 = hat{f}_{ev,1} - w_8^1 hat{f}_{od,1} = 0
$$
$$
hat{f}_6 = hat{f}_{ev,2} - w_8^2 hat{f}_{od,2} = 0 - 4(sqrt{2}/2 - isqrt{2}/2)^2 = 4i
$$
$$
hat{f}_7 = hat{f}_{ev,3} - w_8^3 hat{f}_{od,3} = 0
$$
Then, the Fourier transform of your signal is
$$
hat{f} = [0,0,-4i,0,0,0,4i,0].
$$