Sampling, Z-Transform and DFT

Digital systems work on samples of signals. The sampling theorem says when nothing is lost; the z-transform plays the role of the Laplace transform for sequences.

Sampling theorem

A signal band-limited to f_max can be recovered exactly from samples taken at f_s ≥ 2 f_max (the Nyquist rate).

• Sampling makes the spectrum repeat every f_s. If f_s < 2f_max, the copies overlap: aliasing. An anti-aliasing low-pass filter is used before sampling.
• A frequency f₀ sampled at f_s appears at |f₀ − k f_s| (folded into 0 to f_s/2).
• Reconstruction with an ideal low-pass filter (sinc interpolation); practical systems use a zero-order hold.

Z-transform

X(z) = Σ x[n] z⁻ⁿ

• Shift: x[n − k] → z⁻ᵏ X(z). Convolution → product.
• Causal sequences have ROCs outside the outermost pole.
• A causal LTI system is stable if all poles lie inside the unit circle (the ROC then contains |z| = 1).
• Final value: x[∞] = lim_{z→1} (z − 1) X(z).

Discrete Fourier transform

X[k] = Σ_{n=0}^{N−1} x[n] e^(−j2πkn/N), k = 0 … N − 1.

• X[0] = Σ x[n]. Frequency resolution = f_s/N.
• Direct DFT needs N² complex multiplications; a radix-2 FFT needs (N/2) log₂ N.
• Circular convolution in time ↔ multiplication of DFTs. To get linear convolution of lengths L and M by DFT, use N ≥ L + M − 1.

Digital filters

• FIR: finite impulse response, always stable, can have exactly linear phase.
• IIR: feedback (poles), fewer coefficients, may be unstable; designed from analog prototypes (bilinear transform).

Worked example

A 7 kHz tone is sampled at 10 kHz.

• It appears at |7 − 10| = 3 kHz (aliased).

Practice