A complete reference covering continuous and discrete signals, the Nyquist-Shannon sampling theorem, DFT, FFT, Z-transform, Laplace transform, convolution, FIR/IIR filters, windowing, power spectral density, and wavelet transforms.
A continuous-time signal x(t) is defined for every real value of time t. It is the natural description of physical quantities — voltage across a capacitor, acoustic pressure, temperature — that vary smoothly over time. A discrete-time signal x[n] is defined only at integer sample indices n. It arises whenever a continuous signal is measured at regular intervals: x[n] = x(nT), where T is the sampling period and fs = 1/T is the sampling rate in hertz.
Energy and power give two useful signal categories. An energy signal has finite total energy:
E = integral from -inf to +inf of |x(t)|^2 dt < infinity For discrete-time: E = sum from n=-inf to +inf of |x[n]|^2 < infinity
A power signal has finite average power but infinite energy (e.g., a sinusoid that lasts forever). Most periodic signals are power signals. Noise processes are commonly analyzed as power signals characterized by their power spectral density.
Completely specified by a mathematical formula. Examples: sinusoids, step functions, exponentials. Every sample value is known exactly.
Described statistically by probability distributions, mean, variance, and autocorrelation. Examples: thermal noise, speech signals, stock prices.
Satisfy x(t + T0) = x(t) for all t, where T0 is the fundamental period. Fundamental frequency f0 = 1/T0 Hz, angular frequency omega0 = 2*pi*f0 rad/s.
Fourier transform X(f) = 0 for |f| greater than fmax. This condition is necessary for perfect reconstruction from samples and is fundamental to the sampling theorem.
The central theorem of digital signal processing: a bandlimited continuous-time signal with maximum frequency component fmax can be perfectly reconstructed from uniformly spaced samples taken at rate fs, provided:
fs > 2 * fmax Nyquist rate fN = 2 * fmax Nyquist frequency fN/2 = fmax = fs / 2
The reconstruction formula uses sinc interpolation:
x(t) = sum from n=-inf to +inf of x[n] * sinc( (t - n*T) / T ) where sinc(u) = sin(pi*u) / (pi*u) and T = 1/fs is the sampling period
In the frequency domain, sampling creates a periodic replication of X(f) with period fs. When fs is large enough, the replicas do not overlap and a lowpass reconstruction filter with cutoff at fs/2 recovers the original spectrum exactly.
Problem: Human hearing extends to approximately 20 kHz. What is the minimum sampling rate required for CD-quality audio?
Solution: Applying the Nyquist criterion:
fmax = 20,000 Hz Minimum fs = 2 * 20,000 = 40,000 Hz = 40 kHz CD standard uses fs = 44,100 Hz This provides a safety margin above 40 kHz and accommodates the transition band of the anti-aliasing lowpass filter.
Before sampling any real-world signal, an anti-aliasing lowpass filter must be applied to remove all frequency content above fs/2. Without this filter, high-frequency components above the Nyquist frequency fold back into the baseband and corrupt the sampled signal irreversibly. The anti-aliasing filter is the analog lowpass filter whose cutoff is set at or below fs/2 — it is a necessary hardware component in every ADC front end.
Aliasing occurs when a signal is sampled below its Nyquist rate. The spectral replicas created by sampling overlap, and frequency components above fs/2 appear to the sampled system as lower frequencies. The alias frequency of a tone at frequency f when sampled at rate fs is:
f_alias = | f - round(f/fs) * fs | Equivalently, frequencies fold around fs/2: f_alias = | f mod fs - fs/2 | is not quite right — use: For f in range (fs/2, fs): f_alias = fs - f (folds down from fs) For f in range (fs, 3*fs/2): f_alias = f - fs (same as baseband)
Sampling rate: fs = 1000 Hz Signal tone: f = 1200 Hz (above Nyquist frequency 500 Hz) Alias: f_alias = 1200 - 1000 = 200 Hz The 1200 Hz tone is indistinguishable from a 200 Hz tone after sampling at 1000 Hz. Once aliased, the original frequency cannot be recovered.
Temporal aliasing is visible in video: a spinning propeller or wagon wheel filmed at 24 fps can appear to spin backward when its rotation rate places a blade in a position that matches a lower apparent rotation rate. The same phenomenon in audio causes heterodyne interference in undersampled audio ADCs.
Any periodic function x(t) with period T0 satisfying the Dirichlet conditions can be expressed as a Fourier series. The trigonometric form is:
x(t) = a0/2 + sum from n=1 to inf of
[ an * cos(n * omega0 * t) + bn * sin(n * omega0 * t) ]
omega0 = 2*pi / T0 (fundamental angular frequency)
Coefficients:
a0 = (2/T0) * integral over one period of x(t) dt
an = (2/T0) * integral over one period of x(t)*cos(n*omega0*t) dt
bn = (2/T0) * integral over one period of x(t)*sin(n*omega0*t) dtUsing Euler's formula, the compact complex exponential form is:
x(t) = sum from n=-inf to +inf of cn * exp(j*n*omega0*t) cn = (1/T0) * integral from 0 to T0 of x(t)*exp(-j*n*omega0*t) dt Relationship to real coefficients: c0 = a0/2 cn = (an - j*bn) / 2 for n > 0 c-n = cn* (complex conjugate)
When the Fourier series of a function with a jump discontinuity is truncated to N terms, the partial sum overshoots the function value near the discontinuity. The overshoot converges to approximately 8.9% of the jump height — the Gibbs constant of roughly 9% — regardless of how many terms are included. The width of the overshoot narrows as N increases but the peak amplitude does not decrease. In signal processing this manifests as ringing artifacts when a rectangular filter (brick-wall bandpass) is applied. Windowing functions and smooth filter roll-offs reduce the Gibbs effect at the cost of slightly reduced frequency resolution.
(1/T0) * integral over one period of |x(t)|^2 dt = sum from n=-inf to +inf of |cn|^2 = (a0/2)^2 + (1/2)*sum from n=1 to inf of (an^2 + bn^2) Interpretation: total average power = sum of power in each harmonic
Parseval's theorem is frequently used to evaluate the sums of infinite series. For example, the Fourier series of the square wave provides the identity: 1 + 1/9 + 1/25 + ... = pi^2/8 (sum of 1/(2k-1)^2 for k=1 to infinity).
The DFT converts a finite sequence of N time-domain samples x[0], x[1], ..., x[N-1] into N complex frequency-domain values X[0], X[1], ..., X[N-1]:
DFT:
X[k] = sum from n=0 to N-1 of x[n] * exp(-j * 2*pi * k * n / N)
= sum from n=0 to N-1 of x[n] * W_N^(k*n)
where W_N = exp(-j * 2*pi / N) is the twiddle factor base
Inverse DFT (IDFT):
x[n] = (1/N) * sum from k=0 to N-1 of X[k] * exp(j * 2*pi * k * n / N)The DFT bin index k corresponds to physical frequency f_k = k * fs / N. The frequency resolution (bin spacing) is Delta_f = fs / N. To achieve 1 Hz resolution with a 44,100 Hz sample rate, one needs N = 44,100 samples. The first N/2 bins correspond to positive frequencies 0 to fs/2 - Delta_f; bins N/2 through N-1 correspond to negative frequencies.
| Property | Time Domain | Frequency Domain |
|---|---|---|
| Linearity | a*x[n] + b*y[n] | a*X[k] + b*Y[k] |
| Circular shift | x[(n-m) mod N] | W_N^(k*m) * X[k] |
| Frequency shift | W_N^(-l*n) * x[n] | X[(k-l) mod N] |
| Circular convolution | x[n] circularly convolved with h[n] | X[k] * H[k] |
| Conjugate symmetry (real x[n]) | x[n] real | X[N-k] = X[k]* |
| Parseval | sum |x[n]|^2 | (1/N) * sum |X[k]|^2 |
Sequence: x[n] = [1, 1, 1, 1], N = 4
W_4 = exp(-j*pi/2) = -j
X[0] = x[0]*W4^0 + x[1]*W4^0 + x[2]*W4^0 + x[3]*W4^0
= 1 + 1 + 1 + 1 = 4
X[1] = x[0]*1 + x[1]*(-j) + x[2]*(-1) + x[3]*(j)
= 1 - j - 1 + j = 0
X[2] = 1 + (-1) + 1 + (-1) = 0
X[3] = 1 + j + (-1) + (-j) = 0
Result: X[k] = [4, 0, 0, 0]
Interpretation: DC component only (as expected for a constant signal).The Cooley-Tukey radix-2 decimation-in-time (DIT) FFT splits an N-point DFT (N = 2^m) recursively into two N/2-point DFTs of the even-indexed and odd-indexed samples:
X[k] = X_even[k] + W_N^k * X_odd[k] for k = 0, ..., N/2 - 1 X[k + N/2] = X_even[k] - W_N^k * X_odd[k] (butterfly structure) where: X_even[k] = DFT of x[0], x[2], x[4], ..., x[N-2] X_odd[k] = DFT of x[1], x[3], x[5], ..., x[N-1] W_N^k = exp(-j*2*pi*k/N) (twiddle factor)
An 8-point FFT requires 3 stages (log2(8) = 3). Each stage performs N/2 = 4 butterfly operations. The input samples are bit-reversed before the first stage.
Bit-reversal permutation for N=8:
Index: 0 1 2 3 4 5 6 7
Binary: 000 001 010 011 100 101 110 111
Reversed:000 100 010 110 001 101 011 111
New idx: 0 4 2 6 1 5 3 7
Stage 1 (W_8^0 = 1, W_8^2, W_8^4 = -1, ...):
Butterfly pairs: (x[0],x[1]), (x[2],x[3]), (x[4],x[5]), (x[6],x[7])
Each butterfly:
a' = a + W * b
b' = a - W * b
Stage 2: span-2 butterflies
Stage 3: span-4 butterflies → final X[k]
Complexity: (N/2)*log2(N) complex multiplications
N=1024: 512 * 10 = 5,120 vs 1,048,576 for direct DFT| N | Direct DFT (N^2) | FFT (N/2 * log2(N)) | Speedup |
|---|---|---|---|
| 64 | 4,096 | 192 | 21x |
| 1,024 | 1,048,576 | 5,120 | 205x |
| 65,536 | 4,294,967,296 | 524,288 | 8,192x |
The Z-transform is the discrete-time counterpart of the Laplace transform. For a sequence x[n], the bilateral Z-transform is:
X(z) = sum from n=-infinity to +infinity of x[n] * z^(-n) z is a complex variable: z = r * exp(j*omega) One-sided (unilateral) Z-transform: X(z) = sum from n=0 to +infinity of x[n] * z^(-n) (used when x[n] = 0 for n < 0, i.e., causal sequences)
The ROC is the set of z values for which the sum converges absolutely. The ROC is always a connected annular region r1 < |z| < r2 in the complex plane.
Right-sided (causal) sequence: ROC: |z| > r_max (exterior of circle) Includes z = infinity Left-sided (anticausal) sequence: ROC: |z| < r_min (interior of circle) Includes z = 0 Two-sided sequence: ROC: r1 < |z| < r2 (annular ring, if non-empty) BIBO stability condition: System is stable iff ROC includes the unit circle |z| = 1
| x[n] | X(z) | ROC |
|---|---|---|
| delta[n] | 1 | All z |
| u[n] (unit step) | z / (z-1) = 1/(1-z^-1) | |z| > 1 |
| a^n * u[n] | z / (z-a) = 1/(1-a*z^-1) | |z| > |a| |
| n * a^n * u[n] | a*z^-1 / (1-a*z^-1)^2 | |z| > |a| |
| cos(omega0*n) * u[n] | (1 - cos(omega0)*z^-1)/(1 - 2*cos(omega0)*z^-1 + z^-2) | |z| > 1 |
Three main methods for the inverse Z-transform:
Factor the denominator, expand into known pairs from the table, then use linearity. This is the most common method for rational X(z).
Divide the numerator polynomial by the denominator polynomial to obtain the series coefficients directly: X(z) = x[0] + x[1]*z^(-1) + x[2]*z^(-2) + ...
x[n] = (1/(2*pi*j)) * contour integral of X(z) * z^(n-1) dz (closed contour inside ROC — evaluated by residues)
For a linear time-invariant (LTI) discrete system described by the difference equation:
sum from k=0 to N of a[k]*y[n-k] = sum from k=0 to M of b[k]*x[n-k]
Taking Z-transform and solving for H(z) = Y(z)/X(z):
H(z) = (b[0] + b[1]*z^-1 + ... + b[M]*z^-M)
/ (a[0] + a[1]*z^-1 + ... + a[N]*z^-N)
H(z) = B(z) / A(z) (ratio of polynomials in z^-1)
Poles: roots of A(z) = 0
Zeros: roots of B(z) = 0
Stable system: all poles inside unit circle |z| < 1The Laplace transform is the continuous-time analog of the Z-transform. For a signal x(t), the bilateral Laplace transform is:
X(s) = integral from -inf to +inf of x(t) * exp(-s*t) dt s = sigma + j*omega (complex frequency) One-sided (unilateral): X(s) = integral from 0 to +inf of x(t) * exp(-s*t) dt
The Fourier transform is the special case s = j*omega (sigma = 0). The Laplace transform extends this to complex s, allowing the analysis of growing or decaying exponential signals.
| x(t) | X(s) | ROC |
|---|---|---|
| delta(t) | 1 | All s |
| u(t) | 1/s | Re(s) > 0 |
| t*u(t) | 1/s^2 | Re(s) > 0 |
| exp(-a*t)*u(t) | 1/(s+a) | Re(s) > -a |
| sin(omega0*t)*u(t) | omega0 / (s^2 + omega0^2) | Re(s) > 0 |
| cos(omega0*t)*u(t) | s / (s^2 + omega0^2) | Re(s) > 0 |
| t^n * exp(-a*t) * u(t) | n! / (s+a)^(n+1) | Re(s) > -a |
For a continuous LTI system with input X(s) and output Y(s), the transfer function is H(s) = Y(s) / X(s). For a system described by a linear ODE with constant coefficients, H(s) is always a rational function of s:
H(s) = (b_M * s^M + b_(M-1)*s^(M-1) + ... + b_0)
/ (a_N * s^N + a_(N-1)*s^(N-1) + ... + a_0)
Poles: values of s where H(s) -> infinity (denominator = 0)
Zeros: values of s where H(s) = 0 (numerator = 0)
BIBO stability: all poles must have Re(s) < 0
(all poles in left half of complex s-plane)
Frequency response: H(j*omega) = H(s)|_(s = j*omega)
(evaluate on imaginary axis)RC circuit differential equation:
RC * dy/dt + y(t) = x(t)
Laplace transform (zero initial conditions):
s*RC*Y(s) + Y(s) = X(s)
Transfer function:
H(s) = Y(s)/X(s) = 1 / (1 + s*RC)
= (1/RC) / (s + 1/RC)
Pole at s = -1/RC (left half plane -> stable)
Cutoff frequency: omega_c = 1/RC rad/s, f_c = 1/(2*pi*RC) Hz
|H(j*omega)| = 1 / sqrt(1 + (omega*RC)^2)
At omega = 1/RC: |H| = 1/sqrt(2) ≈ -3 dB (3 dB point)The output y(t) of any LTI system is the convolution of the input x(t) with the system's impulse response h(t):
y(t) = x(t) * h(t) = integral from -inf to +inf of x(tau)*h(t-tau) dtau Discrete-time: y[n] = x[n] * h[n] = sum from k=-inf to +inf of x[k]*h[n-k] Convolution theorem: Y(omega) = X(omega) * H(omega) (pointwise multiplication) The output spectrum equals the input spectrum multiplied by the frequency response H(omega).
Direct convolution of an N-sample signal with an M-sample filter requires O(N*M) operations. Using the FFT convolution theorem, the same result is computed as:
1. Zero-pad both sequences to length L >= N + M - 1 2. Compute X[k] = FFT(x, L) O(L log L) 3. Compute H[k] = FFT(h, L) O(L log L) 4. Multiply Y[k] = X[k] * H[k] O(L) 5. Recover y[n] = IFFT(Y, L) O(L log L) Total: O(L log L) vs O(N*M) Note: zero-padding to L >= N+M-1 converts circular convolution (DFT property) into linear convolution.
Cross-correlation measures the similarity between two signals as a function of time lag:
Cross-correlation:
R_xy(tau) = integral of x*(t) * y(t + tau) dt
= x*(-t) convolved with y(t)
Autocorrelation:
R_xx(tau) = integral of x*(t) * x(t + tau) dt
Key difference from convolution: no time-reversal of x.
Correlation detects signal presence in noise (matched filter);
convolution implements filtering.A Finite Impulse Response (FIR) filter of order M is described by the difference equation:
y[n] = sum from k=0 to M of b[k] * x[n-k]
Transfer function:
H(z) = sum from k=0 to M of b[k] * z^(-k)
= B(z) (numerator polynomial only, no denominator)
All poles at z = 0 -> always stable
Impulse response: h[n] = b[n] (the coefficients themselves)FIR filters with symmetric coefficients (b[k] = b[M-k]) have exactly linear phase, meaning all frequencies are delayed by the same constant M/2 samples. This preserves waveform shape and is essential in applications like ECG processing and audio effects.
An Infinite Impulse Response (IIR) filter uses feedback. The general difference equation is:
y[n] = sum from k=0 to M of b[k]*x[n-k]
- sum from k=1 to N of a[k]*y[n-k]
Transfer function:
H(z) = B(z) / A(z)
= (b0 + b1*z^-1 + ... + bM*z^-M)
/ (1 + a1*z^-1 + ... + aN*z^-N)
Stable iff all poles are inside unit circle.Maximally flat magnitude in passband. |H(j*omega)|^2 = 1/(1 + (omega/omega_c)^(2N)). No ripple in either band. Moderate roll-off.
Type I: equiripple in passband, monotone in stopband. Type II: monotone in passband, equiripple in stopband. Steeper roll-off than Butterworth for same order.
Equiripple in both passband and stopband. Steepest roll-off for given order and ripple specs. Most computationally efficient for sharp transitions.
| Property | FIR | IIR |
|---|---|---|
| Stability | Always stable | Requires pole check |
| Phase | Exactly linear (if symmetric) | Generally nonlinear |
| Coefficient count | High (sharp filters need many taps) | Low (very efficient) |
| Feedback | None | Yes (recursive) |
| Analog prototype | No direct analog equivalent | Yes (bilinear transform) |
| Round-off noise | Not amplified by feedback | Can accumulate |
Windowing multiplies a finite data record by a smoothly tapered function before computing the DFT to reduce spectral leakage. The main trade-off is between main lobe width (frequency resolution) and sidelobe level (dynamic range / leakage rejection).
Rectangular: w[n] = 1 (no windowing) Sidelobe level: -13 dB Main lobe width: 4*pi/N Hann (von Hann): w[n] = 0.5 * (1 - cos(2*pi*n / (N-1))) Sidelobe level: -31 dB Main lobe width: 8*pi/N Hamming: w[n] = 0.54 - 0.46 * cos(2*pi*n / (N-1)) Sidelobe level: -42 dB Main lobe width: 8*pi/N Blackman: w[n] = 0.42 - 0.5*cos(2*pi*n/(N-1)) + 0.08*cos(4*pi*n/(N-1)) Sidelobe level: -74 dB Main lobe width: 12*pi/N Blackman-Harris: 4-term cosine window Sidelobe level: -92 dB Main lobe width: 16*pi/N Flat-top: Near-unity gain across main lobe; best for amplitude accuracy Sidelobe level: -93 dB Very wide main lobe
You need good frequency resolution with moderate leakage rejection. Good general-purpose choice for audio analysis, vibration, and machine monitoring.
Strong leakage rejection is more important than frequency resolution — detecting a weak tone near a strong one. Common in radio frequency analysis.
Amplitude accuracy matters more than frequency resolution. Used in calibration and precise power measurements where bin interpolation is not applied.
The signal exactly fits in the window (integer number of cycles), or when processing transient signals that naturally taper to zero at the edges.
The frequency response H(e^(j*omega)) of a discrete system is obtained by evaluating the Z-transform transfer function H(z) on the unit circle z = e^(j*omega):
H(e^(j*omega)) = H(z)|_(z = e^(j*omega)) Magnitude response: |H(e^(j*omega))| Phase response: angle(H(e^(j*omega))) = theta(omega) Phase delay: tau_p(omega) = -theta(omega) / omega Time delay experienced by a sinusoid at frequency omega. Group delay: tau_g(omega) = -d(theta(omega)) / d(omega) Delay experienced by the envelope of a narrowband signal. Constant group delay = linear phase = all frequencies delayed equally.
Linear phase (constant group delay) is essential in applications where waveform shape must be preserved: audio, ECG, radar pulse compression. FIR filters with symmetric coefficients achieve exactly linear phase. IIR filters can approximate constant group delay using all-pass equalizer cascades.
The Bode plot displays |H(j*omega)| in decibels (20*log10|H|) and the phase angle in degrees versus log frequency. Key asymptotic rules for a pole at s = -p (or zero at s = -z):
Simple pole at s = -p (p > 0):
Magnitude: 0 dB for omega << p, slopes at -20 dB/decade for omega >> p
Phase: 0 degrees for omega << p/10, -90 degrees for omega >> 10*p
crosses -45 degrees at omega = p
Simple zero at s = -z (z > 0):
Magnitude: +20 dB/decade after omega = z
Phase: +90 degrees contribution
Double pole: -40 dB/decade slope, -180 degrees phase
n poles at origin: -20n dB/decade, -90n degrees at all frequenciesPower spectral density (PSD) characterizes how power is distributed across frequencies in a random or stationary signal. For a wide-sense stationary (WSS) process:
Autocorrelation:
R_xx(tau) = E[ x(t) * x*(t + tau) ]
Wiener-Khinchin theorem:
S_xx(f) = F( R_xx(tau) )
= integral from -inf to +inf of R_xx(tau) * exp(-j*2*pi*f*tau) dtau
Total power:
P = R_xx(0) = integral from -inf to +inf of S_xx(f) df
Units: S_xx(f) in units of [signal^2 / Hz] (e.g., V^2/Hz)S_xx(f) = (1/(N*fs)) * |X(f)|^2 where X(f) is the DFT of the windowed data segment. Simple but high variance (does not converge as N increases without averaging).
Divide the signal into overlapping windowed segments (typically 50% overlap). Compute periodogram of each segment, then average. Reduces variance at the cost of frequency resolution. The standard PSD estimator in MATLAB, Python scipy, and NumPy.
Like Welch but without overlap — segments are non-overlapping, each rectangularly windowed. Simpler but slightly higher variance than Welch for the same data length.
White noise: S_xx(f) = N0 / 2 = constant (flat spectrum) Pink (1/f) noise: S_xx(f) = C / f (electronics, music, finance) Brownian noise: S_xx(f) = C / f^2 (random walk / integration of white noise) For a system H(s) driven by white noise with PSD N0/2: Output PSD: S_yy(f) = |H(j*2*pi*f)|^2 * N0/2
The Wiener filter is the optimal linear filter for signal estimation in the presence of additive noise, in the minimum mean-square error (MMSE) sense. Given an observed signal y[n] = s[n] + v[n] (desired signal s plus noise v), the Wiener filter estimates s[n] from y[n].
Wiener-Hopf equation (in frequency domain): H_opt(f) = S_sy(f) / S_yy(f) For uncorrelated signal and noise: S_yy(f) = S_ss(f) + S_vv(f) S_sy(f) = S_ss(f) (cross-PSD of desired signal with observation) Therefore: H_opt(f) = S_ss(f) / (S_ss(f) + S_vv(f)) When SNR(f) = S_ss(f) / S_vv(f): H_opt(f) = SNR(f) / (1 + SNR(f)) At high SNR: H_opt(f) -> 1 (pass everything) At low SNR: H_opt(f) -> 0 (attenuate noise-dominated frequencies)
The Wiener filter requires knowledge of the signal and noise PSDs (S_ss and S_vv). When these are unknown, they must be estimated from data. The Kalman filter is the time-domain, recursive, non-stationary generalization of the Wiener filter.
Unlike the Fourier transform, which uses infinitely long sinusoids with no time localization, the wavelet transform uses short, oscillatory functions (wavelets) that are scaled and shifted to provide simultaneous time-frequency localization. This is especially valuable for non-stationary signals whose frequency content changes over time.
CWT: W(a, b) = (1/sqrt(|a|)) * integral from -inf to +inf of
x(t) * psi*( (t-b)/a ) dt
a = scale parameter (a > 0; large a -> low frequency / stretched)
b = translation parameter (time localization)
psi(t) = mother wavelet
psi* = complex conjugate of psi
Admissibility condition (required for reconstruction):
C_psi = integral of |PSI(f)|^2 / |f| df < infinity
Requires PSI(0) = 0 (zero mean: wavelet has no DC component)The DWT samples the CWT on a dyadic grid: a = 2^j, b = k * 2^j for integers j and k. This is implemented efficiently using a two-channel filter bank (Mallat's algorithm):
At each decomposition level j:
Approximation coefficients:
cA_j[k] = sum_n x[n] * h[n - 2k] (lowpass filter + downsample by 2)
Detail coefficients:
cD_j[k] = sum_n x[n] * g[n - 2k] (highpass filter + downsample by 2)
h[n] = scaling filter (lowpass) — derived from scaling function phi
g[n] = wavelet filter (highpass) — derived from mother wavelet psi
For orthogonal wavelets: g[n] = (-1)^n * h[L-1-n] (quadrature mirror filters)
Reconstruction (synthesis):
x[n] = sum_k cA_j[k]*h[n-2k] + sum_k cD_j[k]*g[n-2k] (upsample + filter)Mallat's multiresolution analysis framework provides the mathematical foundation for the DWT. An MRA is a sequence of nested closed subspaces V_j of L^2(R) satisfying:
... subset V_2 subset V_1 subset V_0 subset V_-1 subset V_-2 subset ... Closure under scaling: f(t) in V_j <=> f(2t) in V_(j-1) Union dense in L^2(R), Intersection = (0) V_(j-1) = V_j (+) W_j (direct sum: W_j are detail spaces) DWT decomposes signal at each level: Level 0: original signal Level 1: cA1 (approx 0-fs/4) + cD1 (detail fs/4-fs/2) Level 2: cA2 (0-fs/8) + cD2 (fs/8-fs/4) + cD1 (fs/4-fs/2) ...continuing until desired resolution
The Haar wavelet is the simplest orthogonal wavelet. Its mother wavelet and scaling function are:
Scaling function (father wavelet): phi(t) = 1 for 0 <= t < 1 phi(t) = 0 otherwise Mother wavelet: psi(t) = +1 for 0 <= t < 0.5 psi(t) = -1 for 0.5 <= t < 1 psi(t) = 0 otherwise Haar filter coefficients: h = [1/sqrt(2), 1/sqrt(2)] (lowpass / scaling) g = [1/sqrt(2), -1/sqrt(2)] (highpass / wavelet) Haar DWT of [4, 6, 8, 2]: Level 1 lowpass (avg pairs): [5*sqrt(2), 5*sqrt(2)] -> approx: [5, 5] Level 1 highpass (diff pairs): [-sqrt(2), 3*sqrt(2)] -> detail: [-1, 3]
N vanishing moments. db1 = Haar. Compactly supported, orthogonal. Used in image compression (JPEG 2000 uses biorthogonal cousins), denoising, ECG processing.
Gaussian-modulated sinusoid. Provides excellent time-frequency localization. Complex-valued, used for CWT analysis of oscillatory signals (EEG, seismology).
Second derivative of Gaussian. Symmetric, real-valued. Commonly used in seismic analysis and edge detection. psi(t) = (1 - t^2)*exp(-t^2/2).
Separate analysis and synthesis filters. Can achieve symmetric (linear phase) filters even for compactly supported wavelets. CDF 9/7 used in JPEG 2000 lossy compression.
A bandlimited signal with maximum frequency fmax can be perfectly reconstructed from samples taken at any rate fs greater than 2*fmax (the Nyquist rate). Reconstruction uses sinc interpolation. Sampling below the Nyquist rate causes aliasing — irreversible corruption where high frequencies appear as lower frequencies.
The DFT is the mathematical definition converting N time-domain samples to N frequency-domain values, requiring O(N^2) operations. The FFT is an efficient algorithm computing the exact same DFT using O(N log N) operations by exploiting symmetry of the twiddle factors. For N = 1024 the FFT is about 200 times faster than the direct DFT.
The ROC is the set of complex z values where the Z-transform sum converges absolutely. It is always an annular region r1 < |z| < r2. Causal sequences have ROC exterior to a circle; anticausal sequences interior. A discrete-time system is BIBO stable if and only if the ROC includes the unit circle |z| = 1.
FIR filters have no feedback and are always stable; symmetric FIR filters achieve exactly linear phase. IIR filters use feedback and achieve sharp roll-off with far fewer coefficients but can be unstable and have nonlinear phase. Choose FIR for linear-phase requirements (audio, ECG); IIR for efficient sharp filtering (audio EQ, communications).
Truncating a signal to a finite record implicitly applies a rectangular window, whose frequency-domain sidelobes cause spectral leakage: energy from one frequency bin spills into neighboring bins. Smooth window functions (Hann, Hamming, Blackman) reduce sidelobe levels at the cost of a slightly wider main lobe, trading resolution for dynamic range.
The wavelet transform provides simultaneous time and frequency localization using short, oscillatory basis functions (wavelets) scaled and shifted across the signal. The Fourier transform uses infinite sinusoids with no time localization. Wavelets are ideal for non-stationary signals where frequency content changes over time — EEG, seismic, financial time series. The DWT is implemented by a cascaded filter bank and is the basis for JPEG 2000 image compression.
Convolution in the time domain equals pointwise multiplication in the frequency domain: Y(f) = X(f)*H(f). This theorem is why LTI system analysis is easy in the frequency domain: the output spectrum is just the input spectrum times the frequency response. It also enables fast O(N log N) convolution via FFT rather than the naive O(N^2) direct method.
PSD describes how signal power is distributed across frequencies. For a stationary random process, the PSD is the Fourier transform of the autocorrelation function (Wiener-Khinchin theorem). Integrating the PSD over all frequencies gives the total signal power. White noise has a flat PSD; pink (1/f) noise has PSD proportional to 1/f. Welch's method — averaging periodograms of overlapping windowed segments — is the standard PSD estimator.
Test your understanding with step-by-step worked problems on DFT, Z-transforms, filter design, and wavelet decomposition — guided by private tutoring.
Start Practicing Free