7. Discrete Fourier Transform (DFT)

7.1 Definition and Formulation

What is the DFT?
The Discrete Fourier Transform (DFT) is a mathematical tool that converts a finite sequence of equally spaced samples of a function (signal) from the time domain into the frequency domain.
It allows you to analyze the frequency content of discrete signals, like digital audio, images, or any sampled data.

Why Discrete?
Real-world digital signals are sampled at discrete points, so DFT is used instead of the continuous Fourier transform.
It works on N discrete samples (data points) and produces N frequency components.

Mathematical Definition:

Suppose you have a sequence of N complex numbers (samples):
x0, x1, x2, …, xN-1

The DFT produces another sequence X0, X1, X2, …, XN-1, defined as:

X_k = ∑_n=0^N-1 x_n · e^{-j (2π/N) k n}     for k = 0, 1, 2, …, N-1

Explanation of the formula:

• xn = the n-th input sample (time domain data).
• Xk = the k-th output frequency component (frequency domain data).
• N = total number of samples.
• e-j (2π/N) k n = complex exponential (basis function), representing the oscillations at different frequencies.
• j = √-1 (imaginary unit).

The factor (2π/N) defines the spacing between frequency samples.

Intuition:

You can think of the DFT as projecting your input signal onto a set of orthogonal complex sinusoids of different frequencies.
Each Xk tells you how much of the frequency k (out of N frequencies) exists in your signal.

Inverse Discrete Fourier Transform (IDFT):

To recover the original signal from frequency data:

x_n = (1/N) ∑_k=0^N-1 X_k · e^{j (2π/N) k n}     for n=0, 1, …, N-1

This shows DFT is invertible.

7.2 Computational Complexity

Naive computation cost:
For each Xk, we sum N terms.
There are N values of k.
Total computations: N × N = N2 complex multiplications and additions.

So, naive DFT computation has complexity:
O(N2)

Why is this important?
For large N (like thousands or millions of samples), direct DFT is computationally expensive and slow.
This motivated development of Fast Fourier Transform (FFT), which computes the same result in O(N log N) time.

7.3 Applications in Digital Signal Processing (DSP)

1. Frequency Analysis
   Extract frequency components of audio, vibration, or any sampled signal.
   For example, analyzing a recorded sound to find dominant pitches.
2. Filtering
   Design and apply digital filters in the frequency domain.
   Remove unwanted frequencies (noise) by zeroing corresponding Xk components and then applying IDFT.
3. Image Processing
   Use 2D DFT (extension of 1D DFT) to analyze image frequency content.
   Used in compression (JPEG), sharpening, and blurring.
4. Modulation and Demodulation
   Analyze signals in communication systems.
   Extract information encoded in specific frequency bands.
5. Spectral Estimation
   Measure power spectrum to identify energy distribution over frequencies.

Example: Calculate DFT of a simple signal

Suppose N=4, and the signal samples are:

x = [1, 2, 3, 4]

Calculate X0, X1, X2, X3.

Step 1: Write down the formula for Xk:

X_k = ∑_n=0³ x_n · e^{-j (2π/4) k n}

Since 2π/4 = π/2, we simplify exponentials accordingly.

Step 2: Calculate each Xk:

• k=0:
  X₀ = 1·e^-j0 + 2·e^-j0 + 3·e^-j0 + 4·e^-j0 = 1+2+3+4 = 10
• k=1:
  X₁ = 1·e^-j0 + 2·e^-jπ/2 + 3·e^-jπ + 4·e^-j3π/2
  Calculate exponentials:
  e^-j0 = 1
  e^-jπ/2 = 0 - j1 = -j
  e^-jπ = -1
  e^-j3π/2 = 0 + j1 = j
  Substitute:
  X₁ = 1(1) + 2(-j) + 3(-1) + 4(j) = 1 - 2j - 3 + 4j = (1 - 3) + (-2j + 4j) = -2 + 2j
• k=2:
  X₂ = 1·e^-j0 + 2·e^-jπ + 3·e^-j2π + 4·e^-j3π
  Calculate exponentials:
  e^-j0 = 1
  e^-jπ = -1
  e^-j2π = 1
  e^-j3π = -1
  Substitute:
  X₂ = 1(1) + 2(-1) + 3(1) + 4(-1) = 1 - 2 + 3 - 4 = -2
• k=3:
  X₃ = 1·e^-j0 + 2·e^-j3π/2 + 3·e^-j3π + 4·e^-j9π/2
  Calculate exponentials:
  e^-j0 = 1
  e^-j3π/2 = j
  e^-j3π = -1
  e^-j9π/2 = e^{-j(2π + π/2)} = e^-j2π·e^-jπ/2 = 1 · (-j) = -j
  Substitute:
  X₃ = 1(1) + 2(j) + 3(-1) + 4(-j) = 1 + 2j - 3 - 4j = (1 - 3) + (2j - 4j) = -2 - 2j

Final DFT result:

X = [10, -2 + 2j, -2, -2 - 2j]

Interpretation:

• X0 = 10 is the DC component (average value).
• X1 and X3 are complex conjugates, representing oscillations at specific frequencies.
• X2 = -2 is a real value representing a specific frequency component.

Summary