Discrete Fourier Transform

Introduction

The Fourier transform decomposes a signal into its constituent frequencies. While the continuous Fourier transform applies to functions on the real line, practical computation requires a discrete version. The Discrete Fourier Transform (DFT) operates on finite sequences, making it central to digital signal processing, numerical analysis, and scientific computing.

Given a sequence of N complex numbers (x_0),(x_1),…,(x_N−1), the DFT produces another sequence (X_0),(X_1),…,(X_N−1) representing frequency content. The transform is linear, invertible, and efficiently computable via the Fast Fourier Transform (FFT).

Definition

For x=((x_0),…,(x_N−1)), the DFT is(X_k)=(∑_n=0^N−1)((x_n))*e(−2*π*i*k*n)/N,k=0,1,…,N−1.

Define the primitive N-th root of unity (ω_N)=e(−2*π*i)/N.

Then (X_k)=(∑_n=0^N−1)((x_n))*(ω_N)(k*n).

The DFT is matrix–vector multiplication.

The DFT Matrix

Let F∈C(N×N) with entries (F_k*n)=(ω_N)(k*n).

Then X=F*x. The rows of F are orthogonal:

F*(F)T=N*I.

Thus F/√(,N) is unitary.

Inverse DFT

The inverse transform is

(x_n)=1/N*(∑_k=0^N−1)((X_k))*e(2*π*i*k*n)/N=1/N*(∑_k=0^N−1)((X_k))*(ω_N)(−k*n).

In matrix form:

x=F(−1)*X=1/N*(F)*X.

Properties

Linearity

F*(α*x+β*y)=α*F*(x)+β*F*(y).

Periodicity

Sequences are treated as periodic with period N.

Shift Property

If (y_n)=(x_n−m) (circular shift), then (Y_k)=(ω_N)(k*m)*(X_k).

Parseval

(∑_n=0^N−1)((x_n))2=1/N*(∑_k=0^N−1)((X_k))2.

Convolution Theorem

Circular convolution (x⋅y)n=(∑_m=0^N−1)((x_m))*(y_n−m) satisfies F*(x⋅y)=F*(x)⋅F*(y).

This reduces convolution cost from O(N2) to O*(N*(log_)(N)) via FFT.

Fast Fourier Transform

Direct computation costs O(N2). FFT reduces this to O*(N*(log_)(N)).

Cooley–Tukey (Radix-2)

Split into even and odd indices:

(X_k)=(E_k)+(ω_N)k*(O_k),(X_k+N/2)=(E_k)−(ω_N)k*(O_k), where (E_k) and (O_k) are N/2-point DFTs.

The recurrence T(N)=2*T*(N/2)+O(N) gives T(N)=O*(N*(log_)(N)).

Frequency Interpretation

If sampling rate is (f_s), (f_k)=(k*(f_s))/N.

For real sequences, (X_N−k)=((X_k)).

Only half the spectrum is unique.

Worked Examples

Constant Sequence

For x=(1,1,1,1),

X=(4,0,0,0).

Alternating Sequence

For x=(1,−1,1,−1),

X=(0,0,4,0).

Energy is at the Nyquist frequency.

Applications

Spectral Analysis

Power spectrum |(X_k)|2 reveals frequency content.

Polynomial Multiplication

DFT enables O*(n*(log_)(n)) multiplication via convolution.

Filtering

Compute X=F*(x), multiply by frequency response H, then inverse transform.

Image Processing

2D DFT enables fast convolution and compression (e.g., DCT in JPEG).

Differential Equations

Differentiation becomes multiplication by i*k in frequency space.

Relation to Other Transforms

The DFT discretizes the Fourier transform and corresponds to Fourier series coefficients for sampled periodic signals. The DCT is a real-valued variant suitable for non-periodic boundaries.

Summary

The DFT maps finite sequences to frequency components. Its algebraic structure (roots of unity, orthogonal matrix) ensures invertibility and energy preservation. The FFT reduces complexity from O(N2) to O*(N*(log_)(N)), making spectral computation practical. It is foundational in signal processing, numerical algorithms, and scientific computing.