This calculator is an online sandbox for playing with Discrete Fourier Transform (DFT). It uses real DFT, the version of Discrete Fourier Transform, which uses real numbers to represent the input and output signals. DFT is part of Fourier analysis, a set of math techniques based on decomposing signals into sinusoids. While numerous books list graphs to illustrate DFT, I always wondered how these sinusoids look like or how they will be changed if we change the input signal a bit. Now, this sandbox can answer such questions. By default, it is filled with 32 samples, with all zeroes except the second one, set to 5. The calculator displays graphs for real values, imaginary values, magnitude values, and phase values for this set of samples. It also draws graphs with all sinusoids and with the summed signal. You can change samples as you wish - graphs will be updated accordingly.
Now it is time for some theory. Fourier analysis's base is the claim that signal could be represented as the sum of properly chosen sinusoidal waves. Why are sinusoids used? Because they are easier to deal with the original signal or any other form of waves. And they have a valuable property - sinusoidal fidelity; that is, a sinusoidal input to a system is guaranteed to produce sinusoidal output. Only amplitude and phase can change; frequency and wave shape will remain.
There are four types of Fourier Transform: Fourier Transform (for aperiodic continuous signal), Fourier series (for periodic continuous signal), Discrete Time Fourier Transform (for aperiodic discrete signal), Discrete Fourier Transform (for periodic discrete signal). All transforms deal with signals extended to infinity. In the computer, we have a finite number of samples. So, to use Fourier Transforms, we pretend that our finite samples have an infinite number of samples on the left and the right of our actual data. And these samples keep repeating our actual data. Thus, by pretending that our samples are discrete periodic signal, in computer algorithms, we use Discrete Fourier Transform (DFT). (If we pad our actual data with zeroes, for example, instead of repeating, we will get discrete aperiodic signal. Such a signal requires an infinite number of sinusoids. Of course, we can't use it in computer algorithms).
Also, note that each Fourier Transform has real and complex version. The real version is the simplest and uses ordinary numbers for input (signal samples, etc.) and output. The complex version uses complex numbers with the imaginary part. Here we stick with real DFT because it is easier to visualize and understand.
The DFT changes N points of an input signal into two N/2+1 points of output signals. The input signal is, well, input signal, and two output signals are the amplitudes of the sine and cosine waves. For example, to represent 32 points time domain signal in the frequency domain, you need 17 cosine waves and 17 since waves.
The input signal is in the time domain, and the output signals are in the frequency domain. The process of calculating the frequency domain is called decomposition, analysis, the forward DFT, or simply DFT. The opposite process is called synthesis or the inverse DFT.
Time domain signal is represented by a lowercase letter, i.e., x[ ], and frequency domain signal is represented by an uppercase letter, i.e., X[ ]. Two parts of output signal are called Real part of X[ ] or Re X[ ], and Imaginary part pf X[ ] or Im X[ ]. Values of Re X[ ] are amplitudes of cosine waves, and Im X[ ] values are amplitudes of sine waves. The names real and imaginary come from general DFT, which operates on complex numbers. For real DFT, they are just amplitudes of cosine and sine waves.
The sine and cosine waves are called DFT basic functions - they are waves with unity amplitude. The DFT basic functions have the following equations:
where i changes from 0 to N-1, k changes from 0 to N/2.
Each amplitude from Re X and Im X is assigned to proper sine or cosine wave and the result can be summed to form the time domain signal again. The synthesis equation is:
That is, any point from N-points signal can be created by adding N/2+1 cosine wave values and N/2+1 sine wave values at the same point.
Note the bar over X in the formula above. This is because the amplitudes for synthesis should be obtained by scaling original frequency domain amplitude values. These amplitudes should be normalized using the following equations:
with two special cases:
Real and imaginary parts can be represented in polar notation using the following relation:
M and theta and called Magnitude and Phase and can be computed from Re and Im using the following relations:
Thus, in polar notation, DFT decomposes an N-point signal into N/2+1 cosine waves with specified amplitude and phase shift. Sometimes graphs for Mag and Phase makes more sense than graphs for Re and Im.
Now, let's get back to original synthesis equation:
It can explain why we actually can perform DFT, that is, find amplitudes Re and Im. Note that in this equation, ImX and ImX[N/2] will always be zero. Thus, for each of N points, equation contains only N terms.
So we have a system of linear equations with N equations for N unknown coefficients, which can be solved, for example, using Gauss elimination.
Of course, for big N, nobody uses Gaussian elimination because it is too slow. This is where Fast Fourier Transformation (FFT) actually shines. It is a fast method for computing Re and Im values.
However, FFT is based on the complex DFT, a more general DFT version. For N complex points (with real and imaginary parts) of the input signal, it calculates N complex points of the output signal. The question is, how we can relate it to real DFT.
Happily, it is relatively easy. If you have an N-points signal, you place these points into the complex input signal's real part, set the imaginary part of the input signal to all zeroes, and apply FFT. The first N/2+1 points of the real part and N/2+1 points of the imaginary part of the output signal will correspond to your real DFT.
|Sample Number||Sample Value|