SC · Sampling and discrete time

The DTFT and DFT

The DTFT is the true frequency spectrum of a discrete signal, the z-transform viewed on the unit circle. The DFT samples that continuous spectrum at N frequencies so a computer can calculate it. In this lesson you move the signal frequency and see that when it lands exactly on a DFT bin you get one clean spike, and when it falls between bins you get leakage spreading into several bins.

On a bin one spike, off a bin leakage

The upper plot is a discrete cosine of length N = 16, x[n] = cos(ω₀n). In the lower plot, the gold curve is its DTFT magnitude, the true spectrum swept continuously over ω from 0 to π, and the blue bars are that curve sampled at the DFT bins placed at ω = 2πk/N. The bin spacing is 2π/16 ≈ 0.39 rad, and the gray dashed line is the signal's true frequency ω₀. The starting ω₀ = 0.98 sits almost exactly midway between bins k = 2 and 3, so the energy leaks into several bins. Set ω₀ exactly on one blue bin and only that bin rises while the rest drop to 0: one clean spike.

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 spacing Δ = 2π/N = 0.39

nearest bin k = 2 · ω = 0.79

The signal frequency ω₀ is caught between two DFT bins (more than 1/4 of the bin spacing from the nearest bin). No bin lands on the top of the DTFT peak, and the other bins are not at the zeros either but sample the slopes of the peak and the side peaks, so the energy leaks widely into several bins. This is spectral leakage.

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 the E3 unit, X(z) = Σ x[n] z⁻ⁿ, with z placed on the unit circle, z = e^(jω), so the DTFT is the spectrum seen by going once around the unit circle of the z-plane, and for a system it is the frequency response. Its standout feature is periodicity. Because e^(−jωn) has period 2π in ω, the DTFT repeats identically every 2π, which is another face of what the E1 unit showed: 'sampling copies the spectrum at every fs'. So the spectrum of a discrete signal is fully seen over one interval from −π to π, and for a real signal half of it, from 0 to π, is enough; the plot on the first screen draws that half.

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

The DTFT is the spectrum of a discrete signal.

ChooseDTFT = X(z), z = ?

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

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

The DFT samples the DTFT at N points.

On your ownfast algorithm for the DFT = ?

The FFT calculates the DFT on the order of N log N.

The DFT a computer can compute

Because ω is continuous, the DTFT has infinitely many values. A computer cannot calculate infinitely many, so it picks values only at ω = 2πk/N (k = 0, …, N−1), which divide one period 2π into N equal parts; this is the DFT, X[k] = Σₙ x[n] e^(−j2πkn/N). It turns N finite inputs into N finite outputs and is the same as sampling the DTFT curve at N bins. Calculating the DFT directly takes N² multiplications, but the FFT that Cooley and Tukey published in 1965 cut this to the order of N log N and brought digital signal processing into practical use. Since convolution in the time domain becomes multiplication in the DFT domain (with 0s padded on so the result does not wrap around onto itself), even long filters can run fast with the FFT.

Leakage from an off-bin frequency

When you cut a signal down to a finite N samples, that cutting window gives the DTFT a peak with some width (the main lobe) and small peaks lined up beside it (the side lobes). If the signal frequency ω₀ lands exactly on a bin 2πk/N, that bin sits on the top of the main lobe and every other bin lands exactly on a zero between side lobes, giving one clean spike. But if ω₀ falls between bins, every bin samples the slope of the main lobe or a side lobe, and spectral leakage spreads the energy into several bins. Using a window function (Hann, Hamming, and so on) that tapers the two ends smoothly when cutting lowers the side lobes and reduces leakage, but widens the main lobe and weakens the ability to tell two nearby frequencies apart. Resolution is traded for leakage.

Back to the first screen

On the first screen you took a single discrete cosine of length N = 16 and looked at its spectrum. The gold DTFT curve was the true spectrum swept continuously over ω, and the blue DFT bars were that curve sampled at N bins. Setting the signal frequency ω₀ exactly on a bin 2πk/N produced one clean spike, with only one bin raised and the rest at 0; moving it between bins showed leakage spreading the energy into several bins. The DFT is just samples of the DTFT, and the DTFT is the z-transform seen on the unit circle. The chain of analysis tools that started from signal basics and passed through 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; it is the z-transform seen on the unit circle z = e^jω and has period 2π in ω (a result of discretization). The DFT X[k] = Σ x[n] e^−j2πkn/N is the finite, computable version that samples the DTFT at N points, ω = 2πk/N, and the FFT calculates it quickly, on the order of N log N. When the signal frequency is on a bin you get one clean spike, and between bins you get spectral leakage (side lobes made by the finite window). Reducing leakage with a window function costs resolution in return.

On to the next chapter

With this, every tool for analyzing signals and systems is in place. You have learned to look at signals in time, transform them with Fourier, Laplace, and z, and sample them to handle them digitally. In the last chapter the direction turns from analysis to design. The first question of the next unit, Stability and the Routh Test, is how to make a system stable, and it builds the Routh table, which tells whether every pole is in the left half-plane from the coefficients of the characteristic equation alone, without finding the poles. You will be able to judge stability by hand even for high-order systems whose poles are hard to solve for, and then go on to design controllers with the root locus and the Bode plot.