Fast Fourier Transform

The fast Fourier transform (FFT) is a powerful tool for analyzing time series data. It can be used to decompose a time series into its constituent frequencies, which can then be used to identify trends, seasonality, and other patterns in the data.

The discrete Fourier Transform converts a time domain series x into a frequency domain representation X through the formula:

\(\begin{equation} X(k) = \sum_{n=1}^{N} x(n) \cdot e^{-j2\pi k*n/N} \end{equation}\)

where \(k= 0:N-1\) and \(N\) is the number of sampled points.

Then, fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of the time series sequence.

For more visit: https://www.youtube.com/@RVStats_ENG

Chapter 1: Introduction to Fast Fourier Transform

The Fast Fourier Transform (FFT) is a powerful technique used in signal analysis to convert a time-domain signal into its frequency-domain representation. FFT enables efficient computation of the discrete Fourier transform and it’s preferred over traditional methods for frequency analysis and signal processing.

Source: nti-audio.com
Source: nti-audio.com


Why to use it?

It efficiently calculates the discrete Fourier transform, making it ideal for various applications, including signal processing, audio analysis, and more.

Some key advantages of using FFT are:

  • Computational Efficiency and Speed.

  • Spectral Analysis

  • Real-time Processing

  • Noise Reduction

  • Inverse Transform

  • Widely Supported

That is, FFT can help separate signal components from noise by revealing the frequency structure of the signal as well as it provides a clear visualization of signal components in the frequency domain.

FFT algorithms are available in various programming languages and libraries, making them accessible and easy to integrate into different applications.

Chapter 2: Key Functions for FFT in R

The fft() function in R is the cornerstone for performing FFT operations. It takes a time-domain signal as input and returns its frequency-domain representation.

It takes a vector of time series data as its input and returns a vector of complex numbers, where each number represents the amplitude of a particular frequency in the time series.

For example, the following code uses the fft() function to decompose a time series of monthly temperatures:

# Example of using the fft() function
signal <-  c(10, 12, 15, 18, 21, 24, 27, 25, 22, 18, 15, 12)

fft_result <- fft(signal)

print(fft_result)
##  [1]  2.190000e+02+0.000000e+00i -4.515064e+01+1.366025e+00i
##  [3]  1.000000e+00-1.732051e+00i -4.000000e+00+1.000000e+00i
##  [5]  2.220446e-16-2.220446e-16i -1.849365e+00-3.660254e-01i
##  [7]  1.000000e+00+0.000000e+00i -1.849365e+00+3.660254e-01i
##  [9] -1.110223e-16+0.000000e+00i -4.000000e+00-1.000000e+00i
## [11]  1.000000e+00+1.732051e+00i -4.515064e+01-1.366025e+00i

However, to understand better the dominant frequencies present in the data we must apply the function mod() or abs() to the fft results to obtain the magnitude of each frequency.

# Visualization
par(mfrow = c(2, 1))
plot(signal, type = "l", main = "Original Signal")
plot(Mod(fft_result), type = "l", main = "FFT Magnitudes")

Notice that there is a dominant frequency in the first index (frequency = 0), as well as one noticeable peak at index 2. The small peak at position 12 is not taken into consideration because we can reconstruct the signal with half of the points.

Chapter 3: Analyzing a Sine Wave with FFT

In this chapter, let’s analyze a simple sine wave using FFT.

We’ll create a synthetic sine wave and then apply FFT to identify its frequency components.

# Analyzing a sine wave using FFT

period <- 4  ## that is freq is 1/4

time <- seq(0, 10, by = 0.1)
sine_wave <- sin(2 * pi * time / period)

## Apply fft function
fft_result <- fft(sine_wave)

Visualization of the frequency domain representation versus original data:

# Visualization
par(mfrow = c(2, 1))
plot(time, sine_wave, type = "l", main = "Original Sine Wave")
plot(Mod(fft_result), type = "l", main = "FFT Magnitudes")

One dominant frequency with the highest peak is detected as shown in the figure, as well as another next to it.Moreover, we can notice that at index = 1 we have a not negligible value that corresponds to frequency = 0 (DC component) :the average value of signal.

Let’s identify the position of the highest frequency value.

magnitudes<- abs(fft_result)  ## or mod()

# Find the frequency with the largest amplitude
max_index_sine <- which.max(magnitudes)

paste("magnitude value: ", magnitudes[max_index_sine] )
## [1] "magnitude value:  34.0785278077598"
paste("index position: ",max_index_sine)
## [1] "index position:  3"

At the end, to reconstruct the signal we have to include the most important frequencies: DC signal at frequency= 0, as well the main harmonic (top frequency). If we consider to increase the accuracy we must include more harmonics to our fitting model.

Conclusion

Overall, the FFT algorithm’s efficiency, speed, and ability to provide a clear frequency-domain representation make it an essential tool in signal analysis, image processing, audio processing, communications, and various scientific and engineering fields.

For more visit: https://www.youtube.com/@RVStats_ENG