The Fast Fourier Transform (FFT) explained - without formulae - with an example in R

Fourier Transform

For a more detailed explanation of the Fourier analysis take a look at this article.
Long ago, Joseph Fourier (mathematician, physicist, politician, historian and all round smarty pants) discovered that any signal can be represented by a superimposition of sines and cosines.(Strictly speaking, he was talking about periodic signals but the Fourier transform is extended to aperiodic signals as well). The Fast Fourier Transform (FFT) is the most efficient algorithm for computing the Fourier transform of a discrete time signal.

The input signal

The input signal in this example is a combination of two signals

1. frequency of 10 Hz and an amplitude of 2
2. frequency of 20 Hz and an amplitude of 3

We will now delve into how the FFT analyzes the input signal and computes the constituent frequencies with their respective amplitudes.

Sampling frequency

The input signal is generated over a period of 0 to 1 with 1000 samples. In real world scenarios, this would mean that the signal has been sampled 1000 times in a single period. Thus, the sampling frequency fs equals 1000 Hz.

R code to generate the input signals. The comments are (hopefully) self explanatory.

#set the sampling frequency 
 samplingFrequency = 1000;

#create the indexes to sample at
 timeInterval = 1/samplingFrequency;
 signalIndex = seq(0, 1, by=timeInterval);

#define num samples as the dimention of signalIndex. here N = 1000
N = 1000

#amplitude of signal 1 
 a1 = 2;  

#amplitude of signal 2 
 a2 = 3;  

#frequency of signal 1 
 f1 = 10; 

#frequency of signal 2
 f2 = 20; 

#10 Hz Sine wave with peak amplitude 2
 signal1 = a1 * sin(2 * pi * f1 * signalIndex);

#20 Hz Sine wave with peak amplitude 3
 signal2 = a2 * sin(2 * pi * f2 * signalIndex);

#input signal is the sum of two signals in this case with frequencies 10 and 20 Hz
 inputSignal = signal1 + signal2;

#the input signal
 plot(signalIndex, inputSignal);

Fig. 1 - 10 Hz sine wave with an amplitude of 2

Fig. 2 - 20 Hz sine wave with an amplitude of 3

Fig. 3 - The input signal - a sum of the above two sine waves

The FFT

The FFT in this example if performed on all the 1000 points of the input signal. Hence, this is a N = 1000 point FFT. Typically, the number of samples are chosen to be multiples of 8 (e.g 32 point, 64 point) for the sake of efficiency and speed.

FFT Bin Spacing

Each bin in the FFT result corresponds to a frequency of (binindex * fs)/N where binindex is the index of the bin, fs is the frequency with which the input signal is sampled and N is the number of points. In the above example, each bin corresponds to a frequency of 1 Hz (binindex * 1000/1000 = binindex). The first bin - Bin 0 denotes the DC component. Each subsequent bin denotes a frequency component increment of 1 Hz (Second bin corresponds to 1 Hz, the third corresponds to 2 Hz and so on).

#perform the FFT. In this case the number of points (N) will be equal to 1000. Output will be the individual components of the FFT.
 fourierComponents = fft(inputSignal);

#get the absolute value of the coefficients  
 fourierCoefficients = abs(fourierComponents);

Understanding the results of the Fast Fourier Transform (FFT)

Fig. 4 - The absolute value of the fourier coefficients

Astute readers will notice a couple of things that are wrong with the above plot. Interpreting the results of the FFT will be easier once these issues are addressed.

Twin symmetrical spikes

The FFT results (in Fig. 4) show two symmetrical spikes for each input signal - one at bin n and the other at N-n. Since the DFT can accept complex inputs, the result is symmetrical around the frequency axis. When the input is real (as with most real world cases) the output for bins greater than N/2 are redundant and do not add any spectral information. Hence, we can safely ignore the values for bins > N/2.

Amplitude

The amplitude at the bin corresponding to 10 Hz is 1000 and 1500 at the 20 Hz bin. However, the input signals had an amplitude of 2 and 3. The discrepancy arises due to lack of normalization. The results need to be normalized for the sample size which is in this case 1000. Since the input is real valued and the data > N/2 is ignored we need to normalize the results by N/2.

DC Component

Bin 0 contains the value for the DC component that the signal is riding on. In this case there is no DC component and the value of the first bin is zero.

Fig. 5 - Normalized coefficients

#Normalize coefficients fig 5 here N = 1000 samples so N/2 = 500
 normalizedFourierComponents = fourierCoefficients / (N/2);

#get the first 50 coefficients fig 6
 mainCoeffs = normalizedFourierComponents[1:50];

Fig. 6 - The first 50 coefficients

Conclusion

FFT is a fast and efficient algorithm for computing the constituent frequencies of a signal. The magnitude of the FFT gives the peak amplitude of the frequencies contained in a signal. The FFT also contains information on the phase of the signals. These will be tackled in a separate post.