Discrete Fourier Transform

The Discrete Fourier Transform (DFT) converts a finite sequence of N samples $x[0], x[1], \ldots, x[N-1]$ into a sequence of complex frequency components $X[0], X[1], \ldots, X[N-1]$:

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

The DFT reveals which frequencies are present in the signal.

Power Spectrum

The power spectrum measures the energy at each frequency:

$P[k] = \frac{|X[k]|^2}{N^2}$

For a pure cosine $x[n] = \cos(2\pi k_0 n / N)$, the power spectrum has peaks at $k = k_0$ and $k = N - k_0$ (the aliased component), each with value $0.25$.

Inverse DFT

The inverse DFT reconstructs the original signal from frequency components:

$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k]\, e^{2\pi i k n / N}$

The round-trip $\text{IDFT}(\text{DFT}(x)) = x$ is exact (up to floating-point precision).

Frequency Resolution

If the signal has a sampling interval $\Delta t$, the frequency resolution is:

$\Delta f = \frac{1}{N \Delta t}$

Frequencies range from $0$ to $(N-1)/(N \Delta t)$, and the Nyquist frequency is $1/(2\Delta t)$.

Complexity

The direct DFT requires $O(N^2)$ operations. The Fast Fourier Transform (FFT) reduces this to $O(N \log N)$ by exploiting symmetry, but here we implement the straightforward $O(N^2)$ version to understand the definition.

Your Task

Implement the DFT, power spectrum, and inverse DFT. Represent complex numbers as (real, imag) tuples. Use only Python's built-in math and cmath modules.