Digital Signal Processing (EC-601) - Unit 3 Short Notes

UNIT 3: Digital Signal Processing

1.0 DISCRETE-TIME SYSTEMS ANALYSIS

1.1 Definitions & Classifications

[!TIP] Exam Focus: Be prepared to classify a given system equation (e.g., y[n] = n·x[n] is time-varying, y[n] = x²[n] is non-linear).

1.2 Linear Time-Invariant (LTI) Systems

• Convolution Sum: The fundamental operation for LTI systems.

$$y[n] = x[n] * h[n] = \sum_{k=-\infty}^{\infty} x[k]\, h[n-k]$$

where `h[n]` is the **impulse response** (output when `x[n] = δ[n]`). Completely characterizes an LTI system.

• Linear Constant-Coefficient Difference Equation (LCCDE):

$$\sum_{k=0}^{N} a_k\, y[n-k] = \sum_{k=0}^{M} b_k\, x[n-k]$$

*   **Solution:** `y[n] = y_zs[n] + y_zi[n]`

    *   **Zero-State Response (y_zs):** Response due to input *only*, with **zero initial conditions**. Found via convolution: `y_zs[n] = x[n] * h[n]`.

    *   **Zero-Input Response (y_zi):** Response due to **initial conditions only**, with input `x[n]=0`. Found by solving homogeneous equation.

1.3 System Properties from Difference Equations

• Causality: If the equation can be written as y[n] = f(y[n-1], y[n-2], ..., x[n], x[n-1], ...), the system is causal.

• Stability: For rational H(z), the system is BIBO stable iff the ROC of H(z) includes the unit circle (|z|=1). For causal LTI systems, this is equivalent to all poles lying strictly inside the unit circle.

[!TIP] Common Pitfall: An unstable system can have a rational H(z) but an ROC that does not include the unit circle (e.g., ROC |z|>0.9 for a pole at z=0.95 is stable; ROC |z|<0.9 for same pole is unstable).

2.0 SYSTEM REPRESENTATIONS & STRUCTURES

2.1 Block Diagram Representations

Example (2nd-order): y[n] - a₁y[n-1] - a₂y[n-2] = b₀x[n] + b₁x[n-1] + b₂x[n-2]

• DF I: Two separate delay lines (one for x, one for y).

• DF II: One shared delay line. x[n] path feeds into the first adder, output feeds back.

[!TIP] Exam Question: "Draw Direct Form I & II for a given 3rd-order equation." Always count delays to highlight the difference.

2.2 Signal Flow Graphs (SFG)

• Nodes: Represent signals (variables).

• Branches: Represent system functions (multipliers) connecting nodes.

• Mason's Gain Formula: T = (Σ P_k Δ_k) / Δ

  • P_k: Gain of k-th forward path.

  • Δ: 1 - (sum of all loop gains) + (sum of gains of all non-touching loop pairs) - ...

  • Δ_k: Δ with loops touching the k-th forward path removed.

• State-Space to SFG: Convert state equations x[n+1]=Ax[n]+Bu[n], y[n]=Cx[n]+Du[n] into a graph with nodes for each state x_i[n], input u[n], output y[n], and branches for A, B, C, D matrices.

2.3 State-Space Representation

$$\mathbf{x}[n+1] = \mathbf{A}\,\mathbf{x}[n] + \mathbf{B}\,u[n]$$

$$y[n] = \mathbf{C}\,\mathbf{x}[n] + D\,u[n]$$

• x[n]: State vector (internal variables).

• A, B, C, D: System, input, output, feedthrough matrices.

• Relationship to H(z): H(z) = C (zI - A)⁻¹ B + D. The poles of H(z) are the eigenvalues of matrix A.

3.0 Z-TRANSFORM ANALYSIS

3.1 Definition & Rationale

• Bilateral Z-Transform: X(z) = Σ_{n=-∞}^{∞} x[n] z^{-n}. ROC is an annular region in z-plane.

• Unilateral Z-Transform: X(z) = Σ_{n=0}^{∞} x[n] z^{-n}. Used for solving difference equations with initial conditions. ROC is always |z| > r (exterior).

• Relationship to DTFT: DTFT X(e^{jω}) is the z-transform evaluated on the unit circle (z = e^{jω}), provided the ROC includes |z|=1.

3.2 Properties (Key for Proofs)

[!TIP] Proof Strategy: For convolution, start from definition: Y(z) = Σ (x₁ * x₂)[n] z^{-n} = Σ Σ x₁[k]x₂[n-k] z^{-n}. Change variables m=n-k and separate sums.

3.3 Region of Convergence (ROC)

• Importance: Determines uniqueness (same X(z) can have different x[n] with different ROC), stability (ROC must include unit circle), and causality (for rational X(z), causal ⇔ ROC is exterior of outermost pole).

• For Rational X(z): X(z) = (polynomial in z⁻¹) / (polynomial in z⁻¹).

  • ROC boundaries are circles determined by pole locations.

  • Right-sided sequence (causal): ROC is |z| > max{|p_i|} (exterior of outermost pole).

  • Left-sided sequence (anti-causal): ROC is |z| < min{|p_i|} (interior of innermost pole).

  • Two-sided: ROC is an annulus min{|p_i|} < |z| < max{|p_i|}.

3.4 Inverse Z-Transform

1. Partial Fraction Expansion (PFE): For rational X(z).

   • Expand X(z)/z into sum of terms A_i / (1 - p_i z⁻¹).

   • Inverse is x[n] = Σ A_i (p_i)ⁿ u[n] (for causal ROC).

2. Power Series Expansion: Long division of X(z) to get coefficients of z⁻ⁿ. Directly gives x[n].

3. Contour Integration (Residue Method): x[n] = (1/(2πj)) ∮ X(z) z^{n-1} dz. Not typically computed by hand.

3.5 Applications & Pole-Zero Analysis

• System Function: H(z) = Y(z)/X(z) for LTI system with zero initial conditions.

• Pole-Zero Plot: Plot poles (×) and zeros (○) on z-plane.

  • Stability: For causal LTI, all poles must be inside unit circle.

  • Causality: For rational H(z), ROC is exterior of outermost pole.

  • Frequency Response: H(e^{jω}) is H(z) evaluated on unit circle. Zeros on unit circle cause nulls (frequencies with zero gain).

  • Impulse Response Nature:

    • Real pole p inside unit circle (|p|<1): Exponential decay pⁿ u[n].

    • Complex pole pair re^{±jθ} inside unit circle (r<1): Damped sinusoid rⁿ cos(θn+φ) u[n].

    • Pole on unit circle (|p|=1): Sustained oscillation.

    • Pole outside unit circle (|p|>1): Exponential growth ⇒ unstable.

[!TIP] Critical Rule: For a causal and stable LTI system, the ROC of H(z) is always |z| > max{|p_i|} (exterior of outermost pole), and max{|p_i|} < 1.

4.0 DISCRETE FOURIER SERIES (DFS) & DISCRETE FOURIER TRANSFORM (DFT)

4.1 Discrete Fourier Series (DFS)

For a periodic sequence x[n] with period N: x[n] = x[n+N].

• DFS Coefficients (Analysis):

$$C[k] = \frac{1}{N} \sum_{n=0}^{N-1} x[n]\, e^{-j(2π/N)kn}, \quad k=0,1,...,N-1$$

• Synthesis:

$$x[n] = \sum_{k=0}^{N-1} C[k]\, e^{j(2π/N)kn}$$

Key Properties (Proof Required):

• Linearity: a x₁[n] + b x₂[n] ↔ a C₁[k] + b C₂[k].

• Time Shifting (Circular Shift): x[(n-n₀) mod N] ↔ C[k] e^{-j(2π/N)kn₀}.

• Frequency Shifting (Modulation): x[n] e^{j(2π/N)m₀ n} ↔ C[(k-m₀) mod N].

• Time Reversal: x[(-n) mod N] ↔ C[(-k) mod N].

• Convolution: Periodic convolution x₁[n] ⊛ x₂[n] ↔ N·C₁[k] C₂[k].

• Parseval's Theorem: Σ_{n=0}^{N-1} |x[n]|² = N Σ_{k=0}^{N-1} |C[k]|².

4.2 Discrete Fourier Transform (DFT)

For a finite-length sequence x[n], 0 ≤ n ≤ N-1.

• DFT (Analysis):

$$X[k] = \sum_{n=0}^{N-1} x[n]\, e^{-j(2π/N)kn}, \quad k=0,1,...,N-1$$

• Inverse DFT (IDFT):

$$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k]\, e^{j(2π/N)kn}$$

Relationship to DFS: The DFT X[k] is exactly N·C[k] from the DFS of the periodic extension x̃[n] = Σ_{m=-∞}^{∞} x[n-mN].

Key Properties (Proof Required):

• Linearity: Same as DFS.

• Circular Time Shifting: x[(n-n₀) mod N] ↔ X[k] e^{-j(2π/N)kn₀}.

• Circular Frequency Shifting: x[n] e^{j(2π/N)m₀ n} ↔ X[(k-m₀) mod N].

• Time Reversal: x[(-n) mod N] ↔ X[(-k) mod N].

• Circular Convolution: x₁[n] ⊛ x₂[n] ↔ X₁[k] X₂[k].

• Linear Convolution via DFT: x₁[n] * x₂[n] (length L₁+L₂-1) can be obtained by zero-padding both to length N ≥ L₁+L₂-1, computing DFTs, multiplying pointwise, then IDFT.

• Symmetry (for real x[n]):

  • X[N-k] = X*[k] (Conjugate symmetry).

  • Re{X[k]} is even, Im{X[k]} is odd.

  • |X[k]| is even, ∠X[k] is odd.

4.3 Circular Convolution

• Definition: (x₁ ⊛ x₂)[n] = Σ_{m=0}^{N-1} x₁[m] x₂[(n-m) mod N].

• Computation Methods:

  1. Concentric Circles (Graphical): Plot sequences on two circles. Rotate one relative to the other, multiply overlapping values, sum for each n.

  2. Matrix (Toeplitz): Construct a circulant matrix from x₂[n] and multiply by vector x₁[n].

• Key Point: Circular convolution is periodic with period N. To compute linear convolution of length-L sequences, zero-pad to N ≥ L₁+L₂-1.

[!TIP] Exam Trap: "Compute circular convolution of two length-4 sequences." Always use N=4 (no zero-padding). If question asks for "linear convolution using DFT," you must first zero-pad to length ≥ 4+4-1 = 7.

5.0 FAST FOURIER TRANSFORM (FFT) ALGORITHMS

5.1 Need for FFT

• Direct DFT Complexity: N outputs, each requiring N multiplications & additions ⇒ O(N²) operations.

• FFT Goal: Exploit symmetry (W_N^{k+N/2} = -W_N^k) and periodicity (W_N^{k+N} = W_N^k) of twiddle factors W_N = e^{-j2π/N} to reduce to O(N log₂ N).

5.2 Decimation-in-Time (DIT) FFT

• Principle: Decompose input x[n] into even-indexed and odd-indexed samples.

$$X[k] = \sum_{n=even} x[n] W_N^{kn} + \sum_{n=odd} x[n] W_N^{kn}$$

Let `n=2m` for even, `n=2m+1` for odd:

$$X[k] = \sum_{m=0}^{N/2-1} x[2m] W_N^{k(2m)} + \sum_{m=0}^{N/2-1} x[2m+1] W_N^{k(2m+1)}$$

$$= \sum_{m=0}^{N/2-1} x[2m] (W_N^2)^{km} + W_N^k \sum_{m=0}^{N/2-1} x[2m+1] (W_N^2)^{km}$$

$$= E[k] + W_N^k O[k]$$

where `E[k]` and `O[k]` are `N/2`-point DFTs of even/odd sequences.

• Butterfly Computation: For k=0,1,...,N/2-1:

  • X[k] = E[k] + W_N^k O[k]

  • X[k+N/2] = E[k] - W_N^k O[k] (since W_N^{k+N/2} = -W_N^k).

• Bit-Reversal Permutation: Input sequence x[n] must be reordered in bit-reversed order before the first butterfly stage (for radix-2).

• Complexity: (N/2)·log₂N complex multiplications, N·log₂N complex additions.

5.3 Decimation-in-Frequency (DIF) FFT

• Principle: Decompose output X[k] into even-frequency bins (k even) and odd-frequency bins (k odd).

$$X[k] = \sum_{n=0}^{N-1} x[n] W_N^{kn}$$

Split sum based on `k`:

*   For `k` even (`k=2m`): `X[2m] = Σ_{n=0}^{N-1} x[n] W_N^{2mn} = Σ_{n=0}^{N-1} x[n] (W_N^2)^{mn}` → `N/2`-point DFT of `x[n]`.

*   For `k` odd (`k=2m+1`): `X[2m+1] = Σ_{n=0}^{N-1} x[n] W_N^{n(2m+1)} = Σ_{n=0}^{N-1} (x[n] W_N^n) (W_N^2)^{mn}` → `N/2`-point DFT of `x[n]·W_N^n`.

• Butterfly Computation: For n=0,1,...,N/2-1:

  • X[k] (even) and X[k+N/2] (odd) computed from two N/2-point DFTs.

  • No bit-reversal at input. May require bit-reversal at output.

• Comparison to DIT:

  • DIT: Decomposes input, bit-reversal at input, twiddle factors applied after smaller DFTs.

  • DIF: Decomposes output, no bit-reversal at input, twiddle factors applied before smaller DFTs.

5.4 Cooley-Tukey Algorithm (Mixed-Radix)

• General framework for composite N = N₁·N₂.

• Radix-2: Special case where N₁=N₂=2 (or powers of 2).

• Mixed-Radix (e.g., N=6=2×3):

  1. Decompose n and k as: n = n₁ + N₁·n₂, k = k₂ + N₂·k₁.

  2. X[k] = Σ_{n₂=0}^{N₂-1} [ Σ_{n₁=0}^{N₁-1} x[n₁ + N₁ n₂] W_N^{n₁ k} ] W_N^{N₁ n₂ k}

  3. Inner sum: N₁-point DFT of subsequences (for each n₂).

  4. Outer sum: N₂-point DFT of results multiplied by twiddle factors.

• Result: N₁·N₂ complex multiplications for twiddle factors, plus N₂·(N₁ log₂ N₁) + N₁·(N₂ log₂ N₂) for smaller DFTs.

5.5 2-D DFT

For M x N matrix x[m,n]:

$$X[k,l] = \sum_{m=0}^{M-1} \sum_{n=0}^{N-1} x[m,n]\, e^{-j2π(km/M + ln/N)}$$

• Separable Property: Compute 1D DFT on rows (length N) to get intermediate X₁[m,l], then compute 1D DFT on columns (length M) of X₁ to get X[k,l]. Order (rows then columns or vice-versa) does not matter.

• Complexity: M·N·(M+N) vs. direct M²N². For 2x2 matrix, compute directly or via separability.

6.0 DIGITAL FILTER DESIGN

6.1 FIR vs. IIR Filter Comparison

6.2 FIR Filter Design (Window Method)

Design Steps:

1. Specifications: Filter type (LP/HP/BP/BS), cutoff ω_c, length M (order N=M-1).

2. Ideal Impulse Response h_d[n]:

   • LP: h_d[n] = (ω_c/π) sinc(ω_c n/π) for n≠0, h_d[0] = ω_c/π.

   • HP, BP, BS: Derived by subtracting appropriate LP responses.

3. Apply Window w[n]: h[n] = h_d[n] · w[n], for n = -(M-1)/2, ..., (M-1)/2 (symmetric about n=0). Window must be symmetric.

4. Shift for Causal Filter: h_causal[n] = h[n + (M-1)/2] for n=0,1,...,M-1.

Common Windows (Main Lobe Width / Side Lobe Attenuation):

Gibbs Phenomenon: Undershoot/overshoot near discontinuities due to truncation. Wider main lobe (better window) reduces side lobes but increases transition width.

Linear Phase Conditions:

• Type I (N even, symmetric): h[n] = h[N-n]. H(ω) = e^{-jωN/2} · A(ω), where A(ω) is real & even.

• Type II (N odd, symmetric): h[n] = h[N-n]. H(ω) = e^{-jω(N-1)/2} · A(ω).

• Type III (N even, anti-symmetric): h[n] = -h[N-n]. H(ω) = j e^{-jωN/2} · B(ω), B(ω) real & odd ⇒ H(0)=H(π)=0 (high-pass/band-stop).

• Type IV (N odd, anti-symmetric): h[n] = -h[N-n]. H(ω) = j e^{-jω(N-1)/2} · B(ω), H(0)=0.

[!TIP] Design Question: "Design LP FIR with ω_c = 0.4π, M=21 using rectangular window." Steps: N=20 (even), ω_c=0.4π. Compute h_d[n] for n=-10,...,10. Multiply by w_R[n]=1 (rectangular). Shift by 10 to get h[n] for n=0,...,20.

6.3 IIR Filter Design (Analog Prototype Transformation)

Impulse Invariant Transformation

• Principle: Sample the continuous-time impulse response h_a(t) of analog filter to get digital h[n] = T·h_a(nT).

• Mapping: z = e^{sT}. Frequency mapping: ω = ΩT (mod 2π).

• Disadvantage: Aliasing in frequency response because analog filter's frequency response is not bandlimited. Only suitable for bandlimited analog filters (e.g., low-pass with very small Ω_c).

• Procedure: Find analog H_a(s), do partial fraction, inverse Laplace to get h_a(t), sample to get h[n], take Z-transform to get H(z).

Bilinear Transformation

• Principle: Use trapezoidal rule for integration to map s to z.

$$s = \frac{2}{T} \cdot \frac{1 - z^{-1}}{1 + z^{-1}} \quad \text{or} \quad z = \frac{1 + (T/2)s}{1 - (T/2)s}$$

• Mapping: One-to-one mapping from entire left-half s-plane (Re{s}<0) to inside of unit circle in z-plane (|z|<1). No aliasing.

• Disadvantage: Frequency Warping: Ω = (2/T) tan(ω/2). Non-linear relationship between analog Ω and digital ω.

• Pre-warping: To meet digital spec at ω_c, design analog filter at warped frequency Ω_c = (2/T) tan(ω_c/2).

• Design Steps:

  1. Pre-warp digital specs (ω_p, ω_s) to analog (Ω_p, Ω_s).

  2. Design analog prototype (Butterworth, Chebyshev) with Ω_c and order N to meet pre-warped specs.

  3. Apply bilinear transform s = (2/T)(1-z⁻¹)/(1+z⁻¹) to H_a(s) to get H(z).

  4. (Optional) Transform to desired filter type (LP→HP/BP/BS) using analog frequency transformations before bilinear transform.

Analog Prototypes:

• Butterworth: Maximally flat passband. Monotonic magnitude. Poles on circle in LHP.

• Chebyshev I: Equiripple passband, monotonic stopband. Sharper transition than Butterworth for same N.

• Chebyshev II (Inverse): Monotonic passband, equiripple stopband. Poles not on circle.

• Elliptic: Equiripple in both bands. Sharpest transition for given N, but most sensitive to quantization.

[!TIP] Comparison Question: "Compare impulse invariant and bilinear transformation." Key points: Impulse invariant preserves impulse response shape, has aliasing, simple mapping z=e^{sT}. Bilinear has no aliasing, warps frequency (needs pre-warping), one-to-one mapping. Bilinear is preferred for most designs.

\boxed{\text{End of Unit 3 Notes}}