Fast Fourier Transform Algorithm Analysis

This academic project was assigned in a digital signal processing mathematics course taken at DigiPen Institute of Technology. It consists of a GUI application that benchmarks three approaches to the Discrete Fourier Transform and was built to measure the performance gap between O(N²) and O(N log N) algorithms.

Motivation

The Fourier Transform is foundational to signal processing, but the jump from the textbook DFT definition to the Cooley-Tukey FFT can feel abstract. This project bridges that gap by letting you run all three algorithms side-by-side on the same input, see their outputs, and compare wall-clock execution times — all within a GUI.

Purpose

The project demonstrates and benchmarks:

  1. DFT - Brute force O(N²) matrix approach
  2. Recursive FFT - Divide-and-conquer using recursion
  3. Cooley-Tukey FFT (CTFFT) - Iterative FFT with bit-reversal permutation

Algorithm Breakdowns

1. DFT (Brute Force)

Step Description
1 Read N complex input values from file
2 Construct N×N DFT matrix: DFT[row][col] = e^(-2πi·row·col/N)
3 Multiply DFT matrix with input vector (dot product)
4 Output result with timing

Complexity: O(N²) time, O(N²) space

2. Recursive FFT

Step Description
1 Base case: If N=1, return input
2 Divide: Split into even indices x[0], x[2], ... and odd indices x[1], x[3], ...
3 Conquer: Recursively compute FFT on both halves
4 Merge: Combine using twiddle factors: X[k] = even[k] + W·odd[k] and X[k+N/2] = even[k] - W·odd[k]

Complexity: O(N log N) time

3. Cooley-Tukey FFT (Main Algorithm)

Step Description
1 Bit-Reversal Permutation (lines 251-258): Reorder inputs by reversing binary indices
2 Precompute Twiddle Factors (lines 263-268): Calculate W_M = e^(2πi/M) for each stage
3 Iterative Butterfly Processing (lines 271-299): Process log₂(N) stages with butterfly operations
4 Output Results (lines 301-305): Extract final values from last stage

Complexity: O(N log N) time

Key Concepts

Bit-Reversal Permutation

Reorders input by reversing binary representation of indices:

Index:  0   1   2   3   4   5   6   7
Binary: 000 001 010 011 100 101 110 111
Rev:    000 100 010 110 001 101 011 111
Output: 0   4   2   6   1   5   3   7

Butterfly Operation

The fundamental FFT computation:

A' = A + W·B   (top output)
B' = A - W·B   (bottom output)

Where W is the twiddle factor (complex exponential).

Twiddle Factors

Roots of unity used in combining FFT stages:

W_N = e^(-2πi/N) = cos(-2π/N) + i·sin(-2π/N)

Data Structures

Structure Purpose
std::complex<double> Complex number representation
dataMtx Input signal array
outputMtx 2D vector storing all log₂(N)+1 stages
wArray Pre-computed twiddle factors

Input/Output Format

Input file (e.g., test1024.txt):

-0.11887804064691854 -0.41564076899182023
0.6102279938948054 -0.7324642563588262

Output format: a+bi or a-bi with 4 decimal precision

GUI Components

The JUCE interface provides: