Introduction

Imagine a wave on the ocean, constantly changing as it moves. The Fourier Transform is like a special tool that can break down that wave into its smaller components, like ripples and gentle swells.

It turns out any complex signal, like sound, light, or even brainwaves, can be understood as a mix of these simpler "waves" called frequencies. Each frequency captures a specific part of the overall signal, contributing to its unique character.

Think of it like looking at a painting with a magnifying glass. You see the whole picture, but the glass lets you focus on the individual brushstrokes, colors, and textures that make it up. The Fourier Transform does the same thing for signals, taking us from the "big picture" (time domain) to the "brushstrokes" (frequencies) that create it.

It's all thanks to the magic of math, using special functions called "sines" and "cosines" to represent these building blocks of signals. By understanding these frequencies, we unlock a deeper understanding of everything from music and speech to medical scans and even the cosmos!

Fun Example: Line Drawing of Joseph Fourier

Press the thumbnail to see the video.

A Brief Introduction:

The Fast Fourier Transform, both continuous and discrete, has a wide range of applications across various fields. In Signal Processing, FFT is used for spectral analysis (music, speech, weather patterns, differentiating earthquakes from nuclear bomb detection), data compression (audio and image), data filtering (background noise filtering and image blur). FFTs are also used in the biomedical field, most notably, analyzing EEG brain activity, visualizing blood flow through MRI, and reconstructing images through CT scans.

Before we can dive into FFT, we first need to understand the basics - DTFS (DT Fourier Series) and DTFT (DT Fourier Transform). FFTs are derived from DTFT, and DTFTs are derived from DTFS. First, we will briefly cover what is the DTFS, and then we will cover what is DTFT. After covering both DTFS and DTFT, we will dive into FFTs.

Basics of Discrete-Time Fourier Series and Fourier Transform in Discrete-Time

The Discrete Time Fourier Series (DTFS) and the Discrete Time Fourier Transform (DTFT) are both mathematical tools used in signal processing to analyze discrete-time signals, but they serve different purposes and are applied under different conditions. Here’s a detailed comparison:

1. Definition and Purpose

• DTFS (Discrete Time Fourier Series): DTFS is like a musical decoder for periodic signals. It breaks them down into fundamental building blocks: simple sine waves at specific frequencies. These frequencies are all multiples of a single base rate, like having a limited set of notes. By analyzing how much of each frequency is present, DTFS reveals the recipe for creating the original signal.

• DTFT (Discrete Time Fourier Transform): DTFT goes beyond the limitations of DTFS. Instead of just analyzing repeating signals, DTFT can handle any kind of discrete signal, even those that never repeat. It acts like a translator, taking the signal and revealing a continuous spectrum of frequencies. This spectrum shows how much each frequency contributes to the overall signal, providing a more comprehensive understanding of its makeup compared to DTFS, which is restricted to specific frequencies.

2. Mathematical Representation of DTFS and DTFT

DTFS is designed for periodic signals, while DTFT is designed more for both non-periodic and periodic signals.

• DTFS: For a discrete-time periodic signal $x[n]$ with period $N$, the DTFS coefficients $c_k$ are calculated using the formula, or DTFS Analysis Equation:

$$ c_k = \frac{1}{N} \sum_{n=0}^{N-1} x[n] \cdot e^{-j\frac{2\pi}{N}kn}, \quad k = 0, 1, 2, ..., N-1 $$

The signal $x[n]$ can then be reconstructed from its DTFS coefficients using this formula, or the DTFS Synthesis Equation, or inverse DTFS (IDTFS):

$$x[n] = \sum_{k=0}^{N-1} c_k \cdot e^{j\frac{2\pi}{N}kn}$$

The DTFS Analysis and Synthesis Equations can alternatively be expressed in terms of $X(k)$, or simply the magnitude of the frequencies.

$$X(k) = N \cdot c_k$$

Then, the new DTFS Analysis Equation is:

$$ X(k) = \sum_{n=0}^{N-1} x[n] \cdot e^{-j\frac{2\pi}{N}kn}, \quad k = 0, 1, 2, ..., N-1 $$

And the new DTFS Synthesis Equation is:

$$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X(k) \cdot e^{j\frac{2\pi}{N}kn}$$

• DTFT: For a discrete-time signal $x[n]$, the DTFT is given by the following DTFT Analysis Equation. Note that the DTFT is a modification of the 2nd DTFS Analysis equation. The range changed from 0 to N-1 to $[-\infty, +\infty]$ and $\frac{2\pi}{N}k$ was replaced with $\omega$ due to the aperiodicity.

$$ X(\omega) = \sum_{n=-\infty}^{\infty} x[n] \cdot e^{-j\omega n}, \quad \omega = \frac{2\pi}{N}k$$

The inverse DTFT, or IDTFT, used to reconstruct $x[n]$ from $X(\omega)$, is the DTFT Synthesis Equation. We can use the IDTFS to derive the IDTFT. The bounds always have the difference of $2\pi$.

$$ x[n] = \lim_{N \to \infty}\frac{1}{N} \sum_{k=0}^{N-1} X(k) \cdot e^{j\frac{2\pi}{N}kn}=\frac{1}{2\pi} \int_{0}^{2\pi} X(\omega) \cdot e^{j\omega n} d\omega = \frac{1}{2\pi} \int_{\omega_A}^{\omega_B} X(\omega) \cdot e^{j\omega n} d\omega $$

$$ (\omega_B-\omega_A)=2\pi$$

3. Comparison of DTFS, DTFT, and FFT

There is no one superior method. The applications of each method depends on the context.

1. DTFS: Because DTFS designed for periodic signals, DTFS is particularly useful analayzing music. Most musical instruments have periodic signals, such as the human voice. An exception is percussive sound such as cymbals. DTFS is also widely used in telecommunications, audio signal processing, and other areas where signal periodicity is a key factor.
2. DTFT: DTFT much more versatile due to its ability to handle aperiodic signals. It is great at analyzing transients in a signal which is mostly periodic. However, the computational cost is often high due to the expanded range of computation. Here is an analogy: Imagine analyzing a car engine. DTFS is like focusing on the engine's core components like pistons and valves, which repeat their motions. DTFT is like having a more comprehensive toolbox that allows you to examine even the one-time spark from a spark plug or the changing sounds as the engine revs up (Transients). They both provide valuable insights, but the choice depends on the specific aspect you want to understand.
3. FFT: The FFT algorithm reduces the computational complexity of DTFT from $O(N^2)$ to $O(N*log(N))$ (for radix-2 FFT). The next section will cover the basics of the theory behind FFT, beginning with its simplest form, in radix-2. For a semi-periodic signal with large sample size N, FFT is the preferred method for signals analysis.

Deriving the Radix-2 Fast Fourier Transform

1. History of Radix-2 FFT

The motivation for the discovery of the FFT was driven by our country’s national security interest in surveillance or detection of foreign adversaries’ nuclear tests, specifically potential underground nuclear tests conducted by Soviet powers. The Fourier Transform method was implemented initially, but a major obstacle was the vast amount of computation required to Fourier Transform signals picked up from seismometers. Since seismometer data is real-valued, it is discrete and finite necessitating the use of the DFT. The issue in using the DFT is its complexity and number of calculations required to execute. Given computer technology at the time, this method was inefficient and would take too long. In a sense, it defeats the purpose of detecting whether a nuclear bomb was tested and how big the explosion was once detonated, since analyzing that data would take years to complete leaving plenty room for the US to fall behind. At a meeting of the President’s Science Advisory Committee in 1963, Tukey made a breakthrough, finding alternative methods of executing discrete Fourier transforms with substantially fewer computations.

Despite this seemingly new discovery, FFT was first discovered in 1805 when Carl Gauss was studying the newly discovered asteroids of Pallas, Ceres, and Juno. To determine the orbit of Juno, Gauss derived a novel approach to harmonic analysis and jotted it down in his notes but later used a different method. Gauss never analyzed the computational cost and never published the first insight. Gauss had figured out the discrete Fourier Transform even before Joseph Fourier published it in 1807! Incredible! Unfortunately, it only appeared posthumously after his death in volume three of his collected works written in non-standard notation in a 19th century version of Latin. It was seemingly overlooked until it is later rediscovery.

In 1965, John Tukey and James Cooley published the radix-2 FFT in the paper "An Algorithm for the Machine Calculation of Complex Fourier Series". Between 1961 and 1963, Tukey came up with the general idea of radix-2 FFT during a US Science Advisory Committee meeting where top scientists discussed methods for nuclear detonations. Richard Garwin, a scientist from IBM, recognized the idea's potential to end the nuclear arms race and paired Cooley with Tukey to further develop the idea. The rest is history.

2. Starting Definitions

We first define the N-point DFT, $X(k)$, and N-point IDFT, $x(n)$. They are nothing but the new DTFS/IDTFS equations we derived before getting the DTFT/IDTFT equations. In this tutorial, we only find the forward FFT.

$$ X(k) = \sum_{n=0}^{N-1} x[n] \cdot e^{-j\frac{2\pi}{N}kn}, \quad k = 0, 1, 2, ..., N-1 $$ $$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X(k) \cdot e^{j\frac{2\pi}{N}kn}$$

3. Zero-pad x(n) to 2^P

Radix-2 FFT only works when the length of x(n) is $2^P$, where P is a positive integer. So next, we zero pad x(n) to be of length $2^P$. For example, if x(n) is of length 15, we will add 1 zero to the end so that the length is 16, or $2^4$. If the length is 33, we will add zeros to the end until the length is 64, or $2^6$.

4. Properties of the Twiddle Factor, Phase Factor

Next, we define the twiddle factor $W_N= e^{-j\frac{2\pi}{N}}$ and note three essential properties that will be used to derive the FFT.

1. $(W_N)^q = W_{N/q}$ Proof: $(W_N)^q=e^{-j\frac{2\pi}{N}q}=e^{-j\frac{2\pi}{N/q}}=W_{N/q}$
2. $W_{q+N/2} = -(W_{N})^q$ Proof: $W_{q+N/2}=e^{-j\frac{2\pi}{N}(q+\frac{N}{2})} =e^{-j\frac{2\pi}{N}q}\cdot e^{-j\frac{2\pi}{N}(\frac{N}{2})}=-(W_{N})^q$
3. $(W_N)^{q\cdot N/2} = (-1)^q$ Proof: $(W_N)^{q\cdot \frac{N}{2}}=e^{-j\frac{2\pi}{N}(q\cdot \frac{N}{2})}=(e^{-j\pi})^q=(-1)^q$

5. Get the N/2 point DFT

First, we find the N/2 point DFT.

$$X(k) = \sum_{n=even}^{}x(n)(W_N)^{k\cdot 2m} + \sum_{n=odd}^{} x(n)W^{k\cdot (2m+1)} $$ $$= \sum_{n=even}^{\frac{N}{2}-1}x(2m)(W_N)^{k\cdot 2m} + \sum_{n=odd}^{\frac{N}{2}-1} x(2m+1)(W_N)^{k\cdot (2m+1)} $$ $$= \sum_{n=even}^{\frac{N}{2}-1} x(2m)(W_{N/2})^{k\cdot m} + (W_N)^{k}\sum_{n=odd}^{\frac{N}{2}-1} x(2m+1)(W_{N/2})^{km} $$ $$X(k) = X_e(k) + (W_N)^{k}\cdot X_o(k)$$ Length of $X_e(k)$, $X_o(k)=\frac{N}{2}$ Hence: $$X_e(k)=X_e(k+N/2)$$ $$X_o(k)=X_o(k+N/2)$$ $$X(k+N/2)=X_e(k+N/2)+(W_N)^{k+N/2}X_o(k+N/2)$$ $$=X_e(k)+(W_N)^{k}(W_N)^{N/2}X_o(k)$$ $$X(k+N/2)=X_e(k)-(W_N)^{k}X_o(k)$$ Hence, we have now have $\frac{N}{2}$-point DFT's. The total cost is determined with the following steps:

1. 2*((N/2)^2) multiplications for each even and odd functions
2. N/2 multiplications of $W_N$ with the odd function
3. 2*(N/2) additions for both $X(k)$ and $X(k-N/2)$ The total cost is about $O(\frac{N^2}{2})$ for N/2 point DFT. The lower order terms are negligible for large samples.

6. Find the N/4, N/16,..., until the 2-point DFT

Repeat the same steps to get the N/4 point DFT by decomposing the even function into its even and odds and the odd function into its even and odds (2 -> 4) The total length of each even and odd functions will be N/4. So, the total complexity will be approximately $O(4*(\frac{N}{4})^2)$ = $O(\frac{N^2}{16})$. We repeat the process until we we get to 2-length samples. Then, we can combine the DFTs to obtain the x(k)'s. Here is a pictorial example of an FFT with length 8.

Mathematically, the result will be the following: $$X(0) = X_{e}(0)+X_{o}(0) $$ $$X(1) = X_e(1) + W_8^1 * X_o(1) $$ $$X(2) = X_e(2) + W_8^2 * X_o(2)$$ $$X(3) = X_e(3) + W_8^3 * X_o(3)$$ $$X(4) = X_e(0) - X_o(0)$$ $$X(5) = X_e(1) - W_8^1 * X_o(1)$$ $$X(6) = X_e(2) - W_8^2 * X_o(2)$$ $$X(7) = X_e(3) - W_8^3 * X_o(3)$$

The total cost of radix-2 FFT is $O(N\cdot logN)$ vs. $O(N^2)$ for DFT.

7. Implications

A calculation that would have taken over three years could now be carried out in 35 minutes. Now, instead of a calculation that scales N^2 (with N being the number of samples). A calculation scales as Nlog_2(N) meaning larger data sets would see greater savings in computations. For example, a signal with a million samples would require 50,000 times fewer calculations. By identifying which of these calculations are redundant and eliminating them, we need to split our samples into even and odd index points. By exploiting symmetries of sinusoidal functions, you can calculate the odd and even sums for the lower half of the frequencies you can reuse these values to find the upper half. By repeating this process until you reach single data points, cutting the number of calculations in half at each step.

8. Applications

The FFT technique that Tukey and others rediscovered has been integral to many modern technologies and advancements we take for granted. Without the FFT, achieving these milestones would have been considered impractical or impossible let alone ubiquitous. One important one is the Orthogonal Frequency Division Multiplexing or OFDM modulation technique used in modern communication systems. This technique is implemented in 4G, 5G, and Wi-Fi relying on the FFT for efficient modulation and demodulation of signals. In its absence, it would be unfeasible or at the very least not economically possible to garner widespread adoption of these wireless forms of communication. Another area of life where the FFT would be sorely missed is audio compression, specifically MP3 players like the iPod. These devices would exploit the FFT algorithm to transform audio signals into frequency domain, enabling efficient compression with the removal of less audible components. Without it, the audio files on your iPod would have been significantly larger, reducing your storage capacity as well as your battery life due to the increased computational power. Streaming services like Spotify, Apple Music, and Netflix would be unimaginable let alone profitable.

Conclusion

This exploration of the Fourier Transform has unveiled a powerful lens for dissecting signals. We've seen how the seemingly complex can be understood through its fundamental building blocks. From analyzing medical scans to unlocking the secrets of sound and image compression, the applications of the Fourier Transform are far-reaching and ever-expanding.

This foundational knowledge empowers us to not only analyze existing signals but also forge new paths in technology and scientific discovery. As we delve deeper, the hidden world of signals promises even greater revelations.

Sources:

[1] https://www.thefouriertransform.com/  

[2] An Interactive Guide To The Fourier Transform  

https://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/  

[3] Fourier Transform - Science Direct  

https://www.sciencedirect.com/topics/chemistry/fourier-transform  

[4] Fast Fourier Transform Explained  

https://builtin.com/articles/fast-fourier-transform

[5] An Algorithm for the Machine Calculation of Complex Fourier Series https://www.ams.org/journals/mcom/1965-19-090/S0025-5718-1965-0178586-1/S0025-5718-1965-0178586-1.pdf

[6] Lecture Notes on Discrete-Time Signal Processing by Ali H. Sayed, 1996

[7] Lecture 12 Notes - ECE 113 taught by Professor Danijela Cabric, Winter 2024, Wed, 03.12.2024

[8] The Remarkable Story Behind The Most Important Algorithm Of All Time - Veritasium https://www.youtube.com/watch?v=nmgFG7PUHfo