Visual
Key formulas
| Name | Formula | Variables / Notes |
|---|---|---|
| Discrete Fourier Transform (DFT) | X[k] = Σ_{n=0}^{N-1} x[n] * e^(-j2πkn/N) | X[k]: DFT output at frequency index k; x[n]: input sequence of length N; n: time index; k: frequency index (0 to N-1) |
| Inverse DFT (IDFT) | x[n] = (1/N) * Σ_{k=0}^{N-1} X[k] * e^(j2πkn/N) | x[n]: reconstructed time-domain sequence; X[k]: DFT coefficients; N: total number of samples |
| Z-Transform | X(z) = Σ_{n=-∞}^{∞} x[n] * z^(-n) | X(z): z-domain representation; x[n]: discrete-time sequence; z: complex variable z = r * e^(jω) |
| Linear Convolution | y[n] = x[n] * h[n] = Σ_{k=-∞}^{∞} x[k] * h[n-k] | y[n]: output sequence; x[n]: input signal; h[n]: impulse response of the system; k: dummy summation index |
| DTFT | X(e^jω) = Σ_{n=-∞}^{∞} x[n] * e^(-jωn) | X(e^jω): frequency spectrum; x[n]: discrete-time signal; ω: normalized angular frequency (rad/sample), ranges -π to π |
Key concepts
Sampling Theorem
A continuous signal must be sampled at a rate f_s >= 2 * f_max to avoid aliasing. f_max is the highest frequency component. The minimum rate 2 * f_max is called the Nyquist rate.
Region of Convergence (ROC)
The ROC of X(z) is the set of z values for which the z-transform sum converges. For causal sequences, the ROC is the exterior of a circle. For anti-causal sequences, the interior. ROC determines system stability and causality.
FIR vs IIR Filters
FIR filters have a finite impulse response and no feedback; they are always stable and can achieve linear phase. IIR filters use feedback, are more computationally efficient, but can be unstable and have nonlinear phase.
FFT Algorithm
The FFT computes the N-point DFT in O(N log N) operations instead of O(N²). The Cooley-Tukey radix-2 algorithm splits the DFT into successive 2-point transforms using the butterfly operation.
Stability Condition (IIR)
A causal LTI system is stable if all poles of H(z) lie strictly inside the unit circle |z| = 1. Poles on or outside the unit circle indicate an unstable or marginally stable system.
Tables
Common Z-Transform Pairs
| x[n] | X(z) | ROC |
|---|---|---|
| δ[n] | 1 | All z |
| u[n] | z / (z - 1) | |z| > 1 |
| a^n * u[n] | z / (z - a) | |z| > |a| |
| n * u[n] | z / (z - 1)^2 | |z| > 1 |
| cos(ω0*n) * u[n] | (z² - z*cosω0) / (z² - 2z*cosω0 + 1) | |z| > 1 |
FIR vs IIR Filter Summary
| Property | FIR | IIR |
|---|---|---|
| Feedback | None | Yes |
| Stability | Always stable | Conditional |
| Phase | Linear phase possible | Nonlinear phase |
| Order needed | Higher | Lower |
| Design method | Windowing, Parks-McClellan | Butterworth, Chebyshev |
Quick facts
- N-point DFT requires N² complex multiplications; FFT reduces this to (N/2) * log2(N).
- For N = 1024, FFT uses 5120 multiplications vs 1,048,576 for direct DFT.
- Frequency resolution of DFT: Δf = f_s / N, where f_s is sampling frequency.
- Circular convolution of two N-point sequences produces an N-point result; linear convolution produces a (2N-1)-point result.
- The unit circle in the z-plane corresponds to the DTFT (i.e., z = e^jω).
- A Butterworth filter has maximally flat passband response with no ripple.
- Gibbs phenomenon causes 9% overshoot near discontinuities when using a rectangular window for FIR design.
Exam shortcuts
- To check stability from H(z), factor the denominator and locate poles. If all pole magnitudes < 1, the system is stable. For H(z) = 1/(1 - 0.5z^(-1)), the pole is at z = 0.5, so |0.5| < 1: stable.
- Linear convolution length rule: if x[n] has length L and h[n] has length M, then y[n] has length L + M - 1. Use this to set N for circular convolution to avoid aliasing.
- DFT symmetry shortcut: for real x[n], X[N-k] = X*[k]. This means you only need to compute X[0] to X[N/2]; the rest follow by conjugate symmetry, halving computation in exams.