Discrete Fourier Transform

Discrete Fourier Transform

The Discrete Fourier Transform (DFT) transforms a finite sequence of $N$ samples from the time domain into the frequency domain. It is the cornerstone of all digital signal processing.

Definition

$X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-2\pi j k n / N}, \quad k = 0, 1, \ldots, N-1$

Each output $X[k]$ is a complex number representing the amplitude and phase of the frequency component at:

$f_k = k \cdot \frac{f_s}{N}$

where $f_s$ is the sampling rate.

Magnitude Spectrum

The magnitude spectrum $|X[k]|$ shows how much energy is at each frequency. The phase spectrum $\angle X[k]$ shows the phase offset.

Example

DFT of $[1, 0, 0, 0]$ (a single impulse):

$X[k] = \sum_{n=0}^{3} \delta[n] \cdot e^{-2\pi j k n/4} = e^0 = 1 \quad \text{for all } k$

All frequency bins have equal magnitude $= 1.0$ — an impulse contains all frequencies equally.

DFT of $[1, 1, 1, 1]$:

$X[0] = 4, \quad X[1] = X[2] = X[3] = 0$

A DC signal (constant) has energy only at frequency $0$.

Your Task

Implement:

• dft(x) — returns a list of $N$ complex numbers $X[k]$
• dft_magnitude(x) — returns $[|X[0]|, |X[1]|, \ldots, |X[N-1]|]$

import math

def dft(x):
    N = len(x)
    X = []
    for k in range(N):
        val = 0 + 0j
        for n in range(N):
            val += x[n] * math.e ** (-2j * math.pi * k * n / N)
        X.append(val)
    return X

def dft_magnitude(x):
    return [abs(v) for v in dft(x)]