9.3 Discrete Fourier transforms

Source: Ideas from Computational Physics (Landau, Páez, Bordeianu), §9.3. Rewritten in original wording — no textbook listings. Continues 9.2b. Next: 9.3b.

Finite samples force a DFT

In practice $y(t)$ is known at $N$ independent times with spacing $h=\Delta t$:

$$y_k=y(t_k),\quad t_k=kh,\quad T=Nh,\quad s=\frac{1}{h}=\frac{N}{T}.$$

Choosing a window $T$ makes the mathematics treat $y$ as period-$T$ ($y_0=y_N$). Only $N$ independent $y_k$ can determine $N$ independent $Y_n$. The fundamental bin is

$$\omega_1=\frac{2\pi}{T},\qquad \omega_n=n\omega_1=n\frac{2\pi}{Nh},\quad n=0,1,\ldots,N-1,$$

with $n=0$ the DC (non-oscillating) piece.

Trapezoid → DFT sum and Nyquist

Restrict the FT integral to $[0,T]$ and apply the trapezoid rule (endpoint $h/2$ weights merge because $y_0=y_N$). Sparse sampling also forces a Nyquist ceiling. Pick the DFT sum and the Nyquist frequency among lookalikes.

(Book indexing $k=1..N$ is the same cycle.) Inverting with $d\omega\to 2\pi/(Nh)$ reconstitutes $y(t)$ for any $t$; evaluating at the sample grid recovers a period-$N$ sequence. Both $y_{k+N}$ and $Y_{n+N}$ repeat — $N$ in, $N$ independent out.

Longer $T$ (smaller $\omega_1$) smooths the frequency axis. Padding trailing zeros lengthens $T$ artificially and assumes “signal gone afterward.”

Complex $Z=e^{-2\pi i/N}$ turns the DFT into powers of $Z$ (or separate cos/sin real-imag forms). A real $y_k$ need not produce a purely real $Y_n$; leftover Im parts measure windowing / symmetry error, not necessarily a bug.

Naive DFT is an $N\times N$ multiply — $\mathcal{O}(N^2)$. The FFT (§9.5) reaches $\mathcal{O}(N\log N)$; for $N\sim10^{2\text{–}3}$ that is minutes vs weeks territory.

Aliasing in words

Unresolved high frequencies can impersonate low ones (aliasing — also the Moiré story in images). If a tone at frequency $f$ is sampled at rate $s$ with the Nyquist rule violated, $f$ and $f-2s$ can yield the same samples. Filter high-$f$ first, or raise $s$ by shrinking $h$ at fixed $T$.

Raising $N$ at fixed $T$ improves high-frequency fidelity and moves former “edge” bins inward. Raising $T$ at fixed $h$ densifies low-frequency bins (padding is the after-the-fact version).

Assessment menu (do these)

1. Even: $y=3\cos\omega t+2\cos 3\omega t+\cos 5\omega t$ — nearly real $Y_n$, amplitudes $3:2:1$ (power $9:4:1$), reconstruct.
2. Odd: $y=\sin\omega t+2\sin 3\omega t+3\sin 5\omega t$ — nearly imaginary, ratios $1:2:3$ (power $1:4:9$).
3. Mixed: $5\sin\omega t+2\cos 3\omega t+\sin 5\omega t$ — amplitudes $5:2:1$.
4. Offset / phase: $5+10\sin(t+2)$ — peel DC and phase separately.
5. Aliasing: $y=\sin(\pi t/2)+\sin(2\pi t)$ under coarse vs fine $s$; check Nyquist.
6. Chapter 8 orbits: $p=12$ and soft-$\alpha$ trajectories — how many harmonics exceed $10\%$ of $|b_1|$? Use the true period, not $\omega_0$.

Nonperiodic packet (preview)

A localized electron model $\psi(x,0)=e^{-\frac12((x-5)/\sigma_0)^2}e^{ik_0 x}$ is not a $p$-eigenstate. Its momentum content is the FT $\psi(p)$ — same DFT machinery on a long spatial window.

Quiz

DFT and aliasing

1 / 4

With N samples spaced by h, the sampling rate is…

Pick an answer to see if you are right.

Next: 9.3b DFT labs.