SC · Sampling and discrete time

The DTFT and DFT

The DTFT is the true frequency spectrum of a discrete signal, the z-transform seen on the unit circle. The DFT samples that continuous spectrum at N frequencies so a computer can compute it. Move the signal frequency and watch: land it exactly on a DFT bin and you get one clean spike; fall between bins and the energy leaks across many — spectral leakage.

On a bin one spike, off a bin leakage

Above is a length-N=16 discrete cosine x[n] = cos(ω₀n). Below, the gold curve is its DTFT magnitude, the true spectrum swept continuously over ω, and the blue stems are that curve sampled at the N DFT bins ω = 2πk/N. The dashed line is the signal’s true frequency ω₀. Move the ω₀ slider so that ω₀ lands exactly on one blue bin, making a clean spike where only that bin rises and the rest fall to 0. Fall between bins and the energy leaks into the neighbors.

discrete cosine x[n] = cos(ω₀n), N=16

DTFT magnitude (gold curve) and DFT bins (blue stems)

signal frequency ω₀0.98 rad

Signal frequency and DFT bins

ω₀ = 0.98 · N = 16 · bin Δ = 2π/N = 0.39

nearest bin k = 2 at ω = 0.79

The signal frequency ω₀ has fallen between two DFT bins. No bin sits on the signal’s peak, so the energy leaks broadly across many bins. This is spectral leakage: the DFT is sampling the side lobes of the DTFT curve.

Between bins (leakage)

The spectrum seen on the unit circle

The DTFT of a discrete signal x[n] is X(e^(jω)) = Σₙ x[n] e^(−jωn). This is exactly the z-transform of E3, X(z) = Σ x[n] z⁻ⁿ, with z set to z = e^(jω) on the unit circle. So the DTFT is the spectrum seen around one trip on the z-plane’s unit circle, and it is the system’s frequency response. One feature stands out: periodicity. Since e^(−jωn) repeats with period 2π in ω, the DTFT repeats identically every 2π. This is another face of E1’s fact that sampling copies the spectrum every fs. So one interval from −π to π is all you need for a discrete signal’s spectrum.

ObserveDTFT X(e^jω) = Σₙ x[n] e^−jωn

The DTFT is the spectrum of a discrete signal.

ChooseDTFT = X(z) at z = ?

The DTFT is the z-transform on the unit circle.

Fill inDFT X[k] = X(e^jω) at ω = ?

The DFT samples the DTFT at N points.

On your ownfast algorithm for the DFT = ?

The FFT computes the DFT in N log N.

The DFT a computer can compute

The DTFT is continuous in ω, so it has infinitely many values. A computer cannot compute infinity, so it picks out values only at ω = 2πk/N (k=0..N−1), dividing one period 2π into N. This is the DFT X[k] = Σₙ x[n] e^(−j2πkn/N), taking N finite inputs to N finite outputs — the DTFT curve sampled at N bins. Computing the DFT directly costs N² multiplications, but the 1965 Cooley–Tukey FFT cut it to N log N, making all of digital signal processing practical. Convolution in time becomes multiplication in the DFT domain, so even a long filter runs fast through the FFT.

Leakage from an off-bin frequency

When you take only a finite N samples of a signal, that cut-off window gives the DTFT a peak with width (a main lobe) and a row of smaller peaks beside it (side lobes). If the signal frequency ω₀ lands exactly on a bin 2πk/N, that bin sits on top of the main lobe while the others land exactly on the zeros between side lobes, giving a clean single spike. But if ω₀ falls between bins, every bin samples a side lobe and the energy leaks across many bins — spectral leakage. To reduce it, a window function (Hann, Hamming, and others) that tapers the ends smoothly when you cut lowers the side lobes, so leakage drops but the main lobe widens, weakening the power to tell two close frequencies apart. It is a trade-off between resolution and leakage.

Back to the first screen

With a single length-N discrete cosine, you watched its spectrum. The gold DTFT curve was the true spectrum swept continuously over ω, and the blue DFT stems were that curve sampled at N bins. Landing the signal frequency ω₀ exactly on a bin 2πk/N gave a clean single spike, one bin raised and the rest at 0. Moving it between bins showed the leakage as energy spread across many bins. The DFT is only a sampling of the DTFT, and the DTFT is the z-transform seen on the unit circle. The chain that began at signal basics, through time, convolution, Fourier, Laplace, and sampling, closes its loop here at the discrete spectrum.

The DTFT X(e^jω) = Σₙ x[n] e^−jωn is the spectrum of a discrete signal, the z-transform seen on the unit circle z = e^jω, and is periodic with 2π in ω (a result of discretization). The DFT X[k] = Σ x[n] e^−j2πkn/N is the finite, computable version that samples that DTFT at N points ω = 2πk/N, and the FFT computes it fast in N log N. When the signal frequency lands on a bin you get a clean single spike; between bins comes spectral leakage (the side lobes of the finite window). A window function reduces leakage in trade for resolution.

On to the next chapter

Here the toolkit for analyzing signals and systems is complete. We have learned to view things in time, to transform with Fourier, Laplace, and z, and to sample them for digital handling. Now, in the final chapter, the direction turns from analysis to design. The next unit, stability and the Routh test, makes the first question how to keep a system stable. Without solving for the poles, you build a Routh table from the coefficients of the characteristic equation alone to decide whether all poles lie in the left half-plane. Even for high-order systems whose poles are hard to solve, you judge stability by hand, and then go on to design controllers with the root locus and Bode plots.