11.11. Discrete Fourier Transform (DFT)

In real-world applications (such as sensor data in structural health monitoring), signals are sampled. The Discrete Fourier Transform (DFT) is used to analyze such sampled signals.

The Discrete Fourier Transform (DFT) is a method used to convert a sequence of sampled signals into their frequency components. This is essential because in practical applications, we often deal with digital signals that are sampled at discrete time intervals rather than continuous signals. The DFT helps us to analyze these sampled sequences by transforming them from the time domain into the frequency domain, allowing us to study their frequency characteristics.

Imagine you're trying to understand the musical notes of a song that has been recorded. Each note is played for a short moment, and the recording captures discrete sound samples. The DFT will take these samples and break down the song into its component notes (frequencies), enabling you to see which notes are present and how loud each one is.

For a finite sequence f_0, f_1, ..., f_{N−1}, the DFT is:

N−1 X F_k = f_n e^{-2πikn/N}, k = 0, 1, ..., N − 1 n=0

The formula for the Discrete Fourier Transform specifies that each output frequency component, denoted as F_k, is calculated by summing (adding together) the products of the sample values f_n with complex exponentials. The variable k indicates which frequency component you are calculating, while n indexes each sample in the sequence. The term e^{-2πikn/N} represents a rotating wave, which helps in mapping the time-domain signal to its frequency-domain representation.

Think of the DFT like a chef making a salad. Each ingredient (sample value) is added to the mix in a specific way (multiplied by the complex exponential), and the final dish (F_k) is the unique mix of flavors (frequency components) that result from combining these ingredients in the right amounts.

Inverse DFT:

1/N X f_n = F_k e^{2πikn/N}

N k=0

The Inverse Discrete Fourier Transform (IDFT) allows us to reconstruct the original signal from its frequency components (F_k). This formula shows that each sample in the original time-domain signal, f_n, can be recreated by summing the contributions of all frequency components, each multiplied by a complex exponential. Just like the DFT, this process goes through all frequency components but reverses the calculation to come back to the original time-domain signal.

Consider a recipe that uses multiple ingredients to create a smoothie. If you blend all the ingredients together (DFT), you get a tasty smoothie (frequency domain representation). However, if you take that smoothie and want to identify its components (inverse operation), you need to 'unblend' it, which can be compared to the process of the Inverse DFT to find the original ingredients (samples).

This is implemented efficiently using the Fast Fourier Transform (FFT) algorithm.

The Fast Fourier Transform (FFT) is an advanced algorithm that computes the DFT much faster than the straightforward computation. While the DFT involves a lot of repeated calculations—resulting in higher computational complexity—the FFT reduces this to a much more manageable level, making it feasible to analyze large datasets or signals in real-time applications.

Imagine you have to organize a massive library of books. If you do it manually, it can take a lot of time. However, using an efficient cataloging system (like the FFT), you can quickly sort through the books and find everything you need without going through each book individually. This time-saving approach is vital in applications like structural health monitoring where timely data analysis is critical.

--