TOC prev next

Part 4 - example calculations

Now that you know how to calculate DFT and IDFT and what they do, time for some practice in calculating their values.

Important formula

Before doing calculations let's derive a formula for complex sinusoid with negative exponential that is used every time you compute DFT.

$$ e^{-j*2\pi*k/N*n} = cos(-2\pi*k/N*n) + j*sin(-2\pi*k/N*n) = \\ cos(2\pi*k/N*n) - j*sin(2\pi*k/N*n) $$

For making transition above I have used symmetry properties of sine and cosine that are

$$cos(-x) = cos(x)$$

$$sin(-x) = -sin(x)$$

Example 1.

Let's say we have a signal $x = (1,2)$. So number of samples in the signal is $N=2$. This is our first time doing calculations so let's take everything in baby steps.

For remainder

$$DFT(x) = y = (y_0, y_1, y_2, ..., y_{N-1})$$

$$y_k = \sum_{n=0}^{N-1}x_n*e^{-j*2\pi*k/N*n}$$

Because $k=0,1,...,N-1$, there are only two coefficents to compute: $y_0$ and $y_1$.

$$y_0 = \sum_{n=0}^{2-1}x_n*e^{-j*2\pi*0/2*n} = \sum_{n=0}^{1}x_n*e^{0} = \sum_{n=0}^{1}x_n*1 = x_0 + x_1 = 1 + 2 = 3$$

$$y_1 = \sum_{n=0}^{2-1}x_n*e^{-j*2\pi*1/2*n} = \sum_{n=0}^{1}x_n*e^{-j*2\pi*1/2*n} = x_0 e^{-j*2\pi*1/2*0} + x_1 e^{-j*2\pi*1/2*1} = \\ x_0 e^{0} + x_1 e^{-j*2\pi*1/2} = x_0 * 1 + x_1 (cos(2\pi * 1/2) - jsin(2\pi * 1/2)) = \\ x_0 + x_1 (-1 - j * 0) = x_0 - x_1 = 1 - 2 = -1$$

So $DFT(x) = DFT((1,2)) = y = (3, -1)$.

 

And now the other way.

$$IDFT(y) = x = (x_0, x_1, x_2, ..., x_{N-1})$$

$$x_n = \frac{1}{N} \sum_{k=0}^{N-1}y_k * e^{j*2\pi*k/N*n}$$

$n = 0,1,...,N-1$, so there are only two samples to compute: $x_0$ and $x_1$.

$$x_0 = \frac{1}{2} \sum_{k=0}^{2-1}y_k * e^{j*2\pi*k/2*0} = \frac{1}{2} \sum_{k=0}^{1}y_k * e^{0} = \frac{1}{2} \sum_{k=0}^{1}y_k * 1 = \frac{1}{2} (y_0 + y_1) = \\ \frac{1}{2} (3 + (-1)) = \frac{1}{2} * 2 = 1 $$

$$x_1 = \frac{1}{2} \sum_{k=0}^{2-1}y_k * e^{j*2\pi*k/2*1} = \frac{1}{2} \sum_{k=0}^{1}y_k * e^{j*2\pi*k/2} = \frac{1}{2} (y_0 * e^{j*2\pi*0/2} + y_1 * e^{j*2\pi*1/2}) = \\ \frac{1}{2} (y_0 * e^{0} + y_1 * (cos(2\pi*1/2) + jsin(2\pi*1/2)) ) = \\ \frac{1}{2} (y_0 * 1 + y_1 * (-1 + j*0) ) = \frac{1}{2} (y_0 - y_1) = \\ \frac{1}{2} (3 - (-1)) = \frac{1}{2} * 4 = 2 $$

So $IDFT(y) = IDFT((3,-1)) = x = (1,2)$ which matches with original signal $x$.

Example 2.

Let our signal be $x=(6,3,5,1)$. There are 4 samples in the signal so $N=4$. This time I will show only key points during computation.

Forward DFT

$$y_k = \sum_{n=0}^{N-1}x_n*e^{-j*2\pi*k/N*n}$$

$$y_0 = \sum_{n=0}^{4-1}x_n*e^{-j*2\pi*0/4*n} = x_0 + x_1 + x_2 + x_3 = 15$$

$$y_1 = \sum_{n=0}^{4-1}x_n*e^{-j*2\pi*1/4*n} = x_0 * 1 + x_1 * (-j) + x_2 * (-1) + x_3 * j = 1 - 2j$$

$$y_2 = \sum_{n=0}^{4-1}x_n*e^{-j*2\pi*2/4*n} = x_0 * 1 + x_1 * (-1) + x_2 * 1 + x_3 * (-1) = 7$$

$$y_3 = \sum_{n=0}^{4-1}x_n*e^{-j*2\pi*3/4*n} = x_0 * 1 + x_1 * j + x_2 * (-1) + x_3 * (-j) = 1 + 2j$$

$DFT((6,3,5,1)) = (15, 1-2j, 7, 1+2j)$.

Let's have a closer look at how $y_1$ is computed to make sure you understand everything that is going on.

$$y_1 = \sum_{n=0}^{4-1}x_n*e^{-j*2\pi*1/4*n} = \sum_{n=0}^{3}x_n*e^{-j*2\pi*1/4*n} = \\ x_0*e^{-j*2\pi*1/4*0} + x_1*e^{-j*2\pi*1/4*1} + x_2*e^{-j*2\pi*1/4*2} + x_3*e^{-j*2\pi*1/4*3} = \\ x_0 (cos(2\pi*1/4*0) - jsin(2\pi*1/4*0)) + \\ x_1 (cos(2\pi*1/4*1) - jsin(2\pi*1/4*1)) + \\ x_2 (cos(2\pi*1/4*2) - jsin(2\pi*1/4*2)) + \\ x_3 (cos(2\pi*1/4*3) - jsin(2\pi*1/4*3)) = \\ x_0 (1-j*0) + x_1 (0-j*1) + x_2 (-1-j*0) + x_3 (0-j*(-1)) = \\ x_0 * 1 + x_1 * (-j) + x_2 * (-1) + x_3 * j = \\ 6 * 1 + 3 * (-j) + 5 * (-1) + 1 * j = 6 -3j -5 +j = 1 -2j $$

If you are doing calculations yourself and have $y_1=1+2j$ and $y_3=1-2j$ then you are forgetting minus sign in exponential or before sin().

 

And inverse DFT.

$$x_n = \frac{1}{N} \sum_{k=0}^{N-1}y_k * e^{j*2\pi*k/N*n}$$

$$x_0 = \frac{1}{4} \sum_{k=0}^{4-1}y_k * e^{j*2\pi*k/4*0} = \frac{1}{4} (y_0 + y_1 + y_2 + y_3) = 6$$

$$x_1 = \frac{1}{4} \sum_{k=0}^{4-1}y_k * e^{j*2\pi*k/4*1} = \frac{1}{4} (y_0 * 1 + y_1 * j + y_2 * (-1) + y_3 * (-j)) = 3$$

$$x_2 = \frac{1}{4} \sum_{k=0}^{4-1}y_k * e^{j*2\pi*k/4*2} = \frac{1}{4} (y_0 * 1 + y_1 * (-1) + y_2 * 1 + y_3 * (-1)) = 5$$

$$x_3 = \frac{1}{4} \sum_{k=0}^{4-1}y_k * e^{j*2\pi*k/4*3} = \frac{1}{4} (y_0 * 1 + y_1 * (-j) + y_2 * (-1) + y_3 * j) = 1$$

$IDFT((15, 1-2j, 7, 1+2j)) = (6,3,5,1)$

Exercises

You cannot learn to do DFT just by reading about it just as your body won't get fit by reading about exercises. Here I have put some signals and their transforms so you can compute them yourself and check results.

$DFT((0,1)) = (1,-1)$

$DFT((2,5)) = (7,-3)$

$DFT((5,2)) = (7,3)$

$DFT((3+j,2-j)) = (5+0j, 1+2j)$

$DFT((3,2,4,1)) = (10+0j, -1-1j, 4+0j, -1+1j)$

$DFT((2,5,1,8)) = (16+0j, 1+3j, -10+0j, 1-3j)$

next part