This calculator is online sandbox for playing with Discrete Fourier Transform (DFT). It uses real DFT, that is, the version of Discrete Fourier Transform which uses real numbers to represent the input and output signals. DFT is part of Fourier analysis, which is 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 input signal a bit. Now this sandbox can answer such questions. By default, it is filled with 32 samples, with all zeroes except second one which is set to 5. For this set of samples, calculator displays graphs for real values, imaginary values, magnitude values and phase values. It also draws graphs with all sinusoids and with summed signal. You can change samples as you wish - graphs will be updated accordingly.
Now it is time for some theory. The base for Fourier analysis 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 that the original signal, or any other form of waves. And they have an useful 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 computer, we have finite number of samples. So, to use Fourier Transforms we just pretend that our finite samples have infinite number of samples on the left and on the right of our actual data. And these samples just 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 signal requires infinite number of sinusoids. Of course we can't use it in computer algorithms).
Also note that each of Fourier Transform has real and complex version. The real version is the simplest and uses ordinary numbers for input (signal samples, etc) and output. Complex version uses complex numbers with imaginary part. Here we stick with real DFT, because it is easier to visualize and understand.
The DFT changes an N points of input signal into two N/2+1 points of output signals. Input signal is, well, input signal, and two output signals are the amplitudes of the sine and cosine waves. For example, in order to represent 32 points time domain signal in frequency domain, you need 17 cosine waves and 17 since waves.
The input signal is in the time domain, the output signals are in the frequency domain. The process of calculating 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 lowercase letter, i.e. x[ ], and frequency domain signal is represented by 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 values of Im X[ ] are amplitudes of sine waves. The names real and imaginary comes 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 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 fast method for computing Re and Im values.
However, FFT is based on the complex DFT, more general version of DFT. For N complex points (with real and imaginary parts) of input signal it calculates N complex points of output signal. The question is, how we can relate it to real DFT.
Happily, it is quite easy. If you have N-points signal, you place these points into real part of complex input signal, set the imaginary part of input signal to all zeroes, apply FFT, and the first N/2+1 points of real part and N/2+1 points of imaginary part of output signal will correspond to your real DFT.