A different approach to the discrete Fourier transform.

The calculation of the Discrete Fourier Transform (DFT), like filtering, are by far the most common digital signal processing algorithms. When I started to investigate about the DFT, I noticed that I needed a large background before understand well how, first the Fourier Transform works, and then, how the Discrete Fourier Transform works. At that moment, I didn’t realize that the equation of the Fourier transform is the same as the Euler’s Formula, but despite of that, there was some aspects missing, for example, the term 2/N in the DFT in order to obtain the real value of the harmonic of a real signal, except if we are calculating the harmonic zero, where only the gain 1/N must be applied.

In this article I want to show a different approach to understand the Fourier Transform and the Discrete Fourier transform from a practical point of view, only using the Euler’s Formula, and the common sense.

First of all , we have the Euler’s equation.

$$e^{jx}=cos x + jsin x$$

$$e^{-jx}=cos x – jsin x$$

We can replace the term $x$ by $\omega t$ when we are working with sinusoidal signals,

$$e^{jx} \rightarrow e^{j\omega t} $$

therefore, the Euler’s equation will be modify as follows

$$e^{j\omega t}=cos(\omega t) + jsin(\omega t)$$

been $\omega$

$$\omega = 2 \pi f$$

In addition to the Euler’s equation, from algebra, we know that the multiplications of powers ans equal bases have as a result exponential with the same base and the addition of both powers as power.

$$e^{g} \cdot e^{h} = e^{g+h}$$

Adding this to the Euler’s equation, we can multiply two signals and obtain the next result.

$$e^{j\omega t} \cdot e^{j2\cdot \omega t} = e^{j3\cdot \omega t} = cos(3 \cdot \omega t) + jsin(3 \cdot \omega t)$$

This also can be obtain operating with sines and cosines.

$$e^{j 2 \cdot \omega t} \cdot e^{j\omega t} = \left(cos(2\omega t) + jsin(2\omega t) \right) \cdot \left(cos(\omega t) + jsin(\omega t) \right) = $$

$$= cos(2\omega t) \cdot cos(\omega t) + cos(2\omega t) \cdot jsin(\omega t) + jsin(2\omega t) \cdot cos(\omega t) + jsin(2\omega t) \cdot jsin(\omega t)$$

Reordering terms and applying the relations

$$j^2 = -1$$

$$sin\alpha \cdot cos\beta + cos\alpha \cdot sin\beta=sin(\alpha + \beta)$$

$$cos\alpha \cdot cos\beta – sin\alpha \cdot sin\beta=cos(\alpha + \beta)$$

we have

$$cos(2\omega t) \cdot cos(\omega t) + jsin(2\omega t) \cdot jsin(\omega t) + cos(2\omega t) \cdot jsin(\omega t) + jsin(2\omega t) \cdot cos(\omega t)$$

$$ = cos(\omega t + 2\omega t) + jsin(\omega t + 2\omega t) = cos(3\omega t) + jsin(3\omega t)$$

Notice that the product of 2 complex signals has as a result a new complex signal with a different frequency, we have performed a frequency shift. At this point, we can perform a frequency shift that transform our sinusoidal signal to a constant signal. To do that we have to multiply the signal by its conjugate.

$$e^{j\omega t} \cdot e^{-j\omega t} = \left(cos(\omega t) + jsin(\omega t) \right) \cdot \left(cos(\omega t) – jsin(\omega t) \right) = $$

$$= cos^2(\omega t)+ cos(\omega t) \cdot jsin(\omega t) + cos(\omega t) \cdot jsin(\omega t) + sin^2(\omega t) = $$

$$ = cos^2(\omega t) + sin^2(\omega t) = 1$$

We have obtain a constant signal with the same amplitude of the sinusoidal signal. We can see this as the Fourier transform of a complex signal with only one harmonic. Lets do this with several harmonics.

We have a signal with the harmonics one and three, then we are going to multiply that signal by the conjugate of the harmonic one.

$$(e^{j \omega t} + e^{j3 \omega t}) \cdot e^{-j\omega t} = e^0 + e^{j2 \omega t} = 1 + e^{j2 \omega t}$$

This time, we also have a constant signal with the amplitude of the harmonic we have selected with the conjugate, and also we have a signal with a frequency that is the difference between the conjugate and the original signal.

In the real world, we usually have not complex signal. Multiply a real signal by a complex conjugate is also possible, but the resulting signal is a little more complicated. If we have a sine signal with a frequency of $2\omega$, and we want to multiply it by $e^{j \omega t}$, the mathematical development will be the next.

$$sin(2 \omega t) \cdot e^{-j \omega t} = sin(2 \omega t) \cdot ( cos( \omega t) – jsin( \omega t) ) = $$

$$sin(2 \omega t) \cdot cos( \omega t) – sin(2 \omega t) \cdot jsin( \omega t) =$$

Applying the product to sum relations

$$= \frac{sin(3 \omega t)+sin(\omega t)}{2} – j \frac{cos(\omega t)-cos(3 \omega t)}{2}$$

in this case, we don’t have any constant component, so the average will be zero, which means that the harmonic $\omega$, used in the exponential, is not present in the signal.

If we use the same harmonic in both terms, we will obtain a constant component. In the next example we can see this.

$$sin(2 \omega t) \cdot e^{-j 2\omega t} = sin(2 \omega t) \cdot ( cos(2 \omega t) – jsin(2 \omega t) ) = $$

$$sin(2 \omega t) \cdot cos(2 \omega t) – sin(2 \omega t) \cdot jsin(2 \omega t) =$$

$$= \frac{sin(4 \omega t)+sin(0)}{2} – j \frac{cos(0)-cos(4 \omega t)}{2}$$

The signal I have choose is a sine signal, that is actually an imaginary signal, so the term that contains the constant, $cos(0)/2=1/2$ is in the imaginary component of the equation.

Unlike the complex signals, when we are using a real signal in the product, the amplitude of the components is separated in two different terms, so in order to restore the original amplitude, we must multiply by 2.

If we want to obtain the value of the constant signal, we can calculate the average value of the resulting signal. To calculate the average for a constant signal, we have to calculate its integral. Adding the integral to last signal, we have the next equation.

$$X(2) = \int_{- \infty}^{\infty} (sin(2 \omega t)) \cdot e^{-j2 \omega t} dt$$

generalizing the equation, we have

$$X(n) = \int_{- \infty}^{\infty} f(t) \cdot e^{-jn\omega t} dt$$

Which is the equation of the Fourier transform. What I want to show is the the Fourier transform “only” apply a frequency shift in order to convert the desired frequency component in a constant component, using the multiplication by its complex conjugate, then, one the desired signal is a constant, it only compute the average to eliminate the rest of the harmonics.

This could be also applied to the Discrete Fourier Transform (DFT). First of all, we have to discretize the Euler’s formula. To do that, we have to obtain the equivalencies in its terms.

The term $n \omega$ in the continuous equation means the speed of the signal, the times per second that the angle moves from 0 to $2 \pi$, then the term $n$ is used to multiply this speed $n$ times. In the discrete formula, the signal is discretized, so it has N samples in $2 \pi$ radians, we can therefore stablish a relation between $\omega$ and $\frac{2 \pi}{N} \cdot k$. The term $k$, as $n$ in the constant formula, means the times that the angle moves from 0 to $2 \pi$ in N samples.

$$jn\omega = \frac{2 \pi}{N}\cdot k$$

Then, since the time in the discrete world is relative to the sampling frequency, the time will the number of the current sample $n$.

$$t = n$$

Replacing these two terms in the Euler’s formula, we obtain the next equations.

$$e^{j\omega t} \rightarrow e^{j\frac{2 \pi}{N}\cdot k \cdot n}$$

$$e^{-j \frac{2 \pi}{N}\cdot k \cdot n}=cos \left( \frac{2 \pi}{N}\cdot k \cdot n \right) – jsin \left( \frac{2 \pi}{N}\cdot k \cdot n \right)$$

The math using the DFT is the same as the used with the FT, so finally we will obtain a signal for the real and imaginary parts. Then, in order to obtain the average value of the signal, that is the same as the constant component, we have to calculate the average of the signal. If we take a look to the DFT equation we can see that, like the FT, it uses an addition of all the signal, in order to obtain an scaled average .

$$X_k=\sum^{N-1}_{n=0}(x_n \cdot e^{-j\frac{2 \pi}{N}kn})$$

To obtain the real average, and the real value of the harmonic we are looking for, we have to add a division by $N$ since it is the number of samples. In case that we would like to calculate the value of the harmonic $k$ of a real signal, we have to add as well the multiplication by 2, since the harmonics are separated and divided by two. The DFT for complex signals will be the next.

$$X_k=\frac{2}{N} \cdot \sum^{N-1}_{n=0}(x_n \cdot e^{-j\frac{2 \pi}{N}kn})$$

The goal of all of these math is to show that the FT as well as the DFT execute a frequency shift in order to transform the desired harmonic in a constant value, and then, since could there are other harmonics in the signal, they compute the average by summing over the entire period and then dividing by the number of samples in the case of the DFT, or the amount of time in case of the FT.

I hope this article can show you a different method for learning how DFT works, and that it will motivate you to look for other methods that reach the same conclusions, or equations, as the original methods.

Leave a Reply