Why is discrete fourier transform used

There are several different ways of understanding the fourier transform, this page will explain it in terms of correlation between a signal and sinusoids of various frequencies. For a more rigorous explanation of the DFT I can recommend either of these two text books: Understanding Digital Signal Processing by Lyons - very readable and good for first timers Digital Signal Processing - Principles, Algorithms and Applications by Proakis and Manolakis - more comprehensive but harder to follow without a bit of mathematical maturity.

So what is the DFT? It is an algorithm that takes a signal and determines the 'frequency content' of the signal. For the following discussion, a 'signal' is any sequence of numbers, e. We refer to these signals with x n where n is the index into the signal.

Signals such as this arise in many situations, for example all digital audio signals consist of sequences of numbers exactly like the one above.

We will consider zero-mean signals, which means if you calculate the mean of the signal you get 0. An explanation for why we do this can be found at the end of the page. When we try to determine the 'frequency content', we are trying to decompose a complicated signal into simpler parts. Many signals are best described as a sum of many individual frequency components instead of time domain samples. The job of the Discrete Fourier Transform is to determine which frequencies a complicated signal is composed of.

Correlation is a widely used concept in signal processing, which at its heart is a measure of how similar two signals are. If the correlation is high, then the signals are similar, if the correlation is near zero the signals are not very similar. In general, if you ever see an equation that looks like this:. We are calculating the correlation or similarity between x and y! How does such a simple looking equation calculate the similarity between two signals?

If x is very similar to y , then when x i is positive, y i will also be positive, and when x i is negative, y i will usually also be negative since the signals are similar. If we multiply 2 positive numbers x i and y i , we get another positive number. If we multiply two negatives, we get another positive number. This is a direct examination of information encoded in the frequency, phase, and amplitude of the component sinusoids.

For example, human speech and hearing use signals with this type of encoding. Second, the DFT can find a system's frequency response from the system's impulse response, and vice versa. This allows systems to be analyzed in the frequency domain , just as convolution allows systems to be analyzed in the time domain. Write a function DFT x which takes in one argument, x - input 1 dimensional real-valued signal.

Apply this function to the signal we generated above and plot the result. We can see from here that the output of the DFT is symmetric at half of the sampling rate you can try different sampling rate to test. This half of the sampling rate is called Nyquist frequency or the folding frequency, it is named after the electronic engineer Harry Nyquist.

He and Claude Shannon have the Nyquist-Shannon sampling theorem, which states that a signal sampled at a rate can be fully reconstructed if it contains only frequency components below half that sampling frequency, thus the highest frequency output from the DFT is half the sampling rate.

We can see by plotting the first half of the DFT results, we can see 3 clear peaks at frequency 1 Hz, 4 Hz, and 7 Hz, with amplitude 3, 1, 0.

This is how we can use the DFT to analyze an arbitrary signal by decomposing it to simple sine waves. The main issue with the above DFT implementation is that it is not efficient if we have a signal with many data points. Improve this question. Add a comment. Active Oldest Votes. Improve this answer. FFTs are of great importance to a wide variety of applications, from digital signal processing to solving partial differential equations to algorithms for quickly multiplying large integers.

Combined with the Convolution theorem, it lets you do magic. Laurent Duval Laurent Duval Sign up or log in Sign up using Google. Sign up using Facebook.