Discrete Fourier Transform (DFT)

April 10, 2026 · Luciano Muratore

Having established the concept of infinite-dimensional Hilbert spaces, we now look at a fundamental tool for processing finite-length signals: the Discrete Fourier Transform (DFT). The DFT allows us to transition from a temporal view of a signal to a spectral one, identifying the underlying periodicities that compose our data.

1. The DFT Function Mapping

The Discrete Fourier Transform (DFT) maps an $N$-point discrete-time signal from the time domain to a set of $N$ discrete components in the frequency domain[cite: 103]. This relationship is defined by the following transform pair:

• Forward Transform (DFT): $X[k] = \sum_{n=0}^{N-1} x[n] e^{-j\frac{2\pi}{N}kn}, \quad k=0, \dots, N-1$.
• Inverse Transform (IDFT): $x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j\frac{2\pi}{N}kn}, \quad n=0, \dots, N-1$.

Each coefficient $X[k]$ represents the contribution of a complex exponential with a frequency of $k/N$ cycles per sample.

2. Fourier Representation and Orthogonality

A finite-length signal $x[n]$ for $n=0, \dots, N-1$ is expressed as a linear combination of $N$ orthogonal complex exponentials. These basis functions, $e^{j\frac{2\pi}{N}kn}$, form a complete basis for $\mathbb{C}^N$. This means any $N$-point signal can be uniquely represented using them.

The orthogonality of these basis functions is a critical property:

$\sum_{n=0}^{N-1} e^{j\frac{2\pi}{N}kn} e^{-j\frac{2\pi}{N}mn} = \begin{cases} N, & k=m \\ 0, & k \neq m \end{cases}$

This orthogonality ensures a unique decomposition, simplifies coefficient computation via inner products, and leads to Parseval’s relation, which guarantees that energy is preserved between domains:

$\sum_{n=0}^{N-1} |x[n]|^2 = \frac{1}{N} \sum_{k=0}^{N-1} |X[k]|^2$

3. Matrix Representation

The DFT can be written compactly using matrix notation. If we define the $N$-th root of unity as $W_N = e^{-j\frac{2\pi}{N}}$ , the transform is expressed as:

$X = Wx$

Where $W$ is the DFT matrix:

The inverse transform is calculated using the conjugate transpose (Hermitian) of $W$:

$x = \frac{1}{N} W^H X$

4. Example: Unit Step Signal ($N=4$)

Consider a unit step signal for $n=0, \dots, 3$: $x = \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix}^T$

For $N=4$, $W_4 = e^{-j\pi/2} = -j$. The matrices $W$ and $W^H$ are defined as:

$W = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{bmatrix}, \quad W^H = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & j & -1 & -j \\ 1 & -1 & 1 & -1 \\ 1 & -j & -1 & j \end{bmatrix}$

Matrix Computation ($X = Wx$)

Computing row by row for the unit step signal:

• $X[0]$: $1(1) + 1(1) + 1(1) + 1(1) = \mathbf{4}$
• $X[1]$: $1(1) + 1(-j) + 1(-1) + 1(j) = 1 - j - 1 + j = \mathbf{0}$
• $X[2]$: $1(1) + 1(-1) + 1(1) + 1(-1) = 1 - 1 + 1 - 1 = \mathbf{0}$
• $X[3]$: $1(1) + 1(j) + 1(-1) + 1(-j) = 1 + j - 1 - j = \mathbf{0}$

The resulting frequency-domain vector is $X = \begin{bmatrix} 4 & 0 & 0 & 0 \end{bmatrix}^T$.

5. Physical Meaning

Each DFT coefficient $X[k]$ provides specific information about the signal’s composition:

• Magnitude $|X[k]|$: Represents the amplitude of that frequency component (magnitude spectrum).
• Phase $\arg(X[k])$: Represents the phase shift of that component (phase spectrum).

In essence, the DFT decomposes a complex signal into its fundamental sinusoidal building blocks, allowing for reconstruction by summing these individual components.