UNIT 4: MULTIRATE SIGNAL PROCESSING & FILTER DESIGN
I. DISCRETE FOURIER TRANSFORM (DFT) ADVANCED PROPERTIES
1. Circular Convolution Property
- Statement: For two length-\(N\) sequences \(x_1(n)\) and \(x_2(n)\) with DFTs \(X_1(k)\) and \(X_2(k)\), the DFT of their circular convolution is the product of their DFTs.
$$x_1(n) \circledast x_2(n) \xrightarrow{\text{DFT}} X_1(k) \cdot X_2(k)$$
where \(\circledast\) denotes N-point circular convolution.
-
Proof: By definition,
\[ \text{DFT}\{x_1(n) \circledast x_2(n)\} = \sum_{n=0}^{N-1} \left( \sum_{m=0}^{N-1} x_1(m)x_2((n-m)\mod N) \right) W_N^{nk} \]
Interchanging sums and using \(W_N^{mk} \cdot W_N^{(n-m)k} = W_N^{nk}\) yields \(X_1(k)X_2(k)\).
-
Relationship with Linear Convolution:
-
Linear convolution of length-\(M\) and length-\(L\) sequences produces length-\((M+L-1)\) output.
-
To compute linear convolution via DFT, zero-pad both sequences to length \(N \ge M+L-1\) to avoid time-domain aliasing (circular convolution artifact).
-
Then, \(x_1(n) * x_2(n) = \text{IDFT}\{ \text{DFT}\{x_1(n)\} \cdot \text{DFT}\{x_2(n)\} \}\) for \(N \ge M+L-1\).
-
[!TIP] Exam Focus: You may be asked to compute an 8-point circular convolution directly (e.g., for \(x_1(n) = \sin(3\pi n/8)\)). Use the formula \(y(n) = \sum_{m=0}^{7} x_1(m)x_2((n-m)\mod 8)\) or DFT-IDFT method.
2. DFT of Real and Even Sequences
-
Statement: If \(x(n)\) is real and even (\(x(n) = x(-n)\) and \(x(n) \in \mathbb{R}\)), then:
-
\(X(k)\) is real and even.
-
\(X(k) = \sum_{n=0}^{N-1} x(n)\cos\left(\frac{2\pi kn}{N}\right)\) (sine terms vanish).
-
-
Proof: For real \(x(n)\), \(X^*(k) = X(N-k) \mod N\) (conjugate symmetry). For even \(x(n)\), \(X(k)\) is even because cosine is even. Combining gives \(X(k) = X^*(k)\), so \(X(k)\) is real and even.
-
Implication: Reduces computation by half (only \(N/2+1\) unique real values for even \(N\)).
3. DFT Modulation (Frequency Shift) Property
-
Statement: If \(g(n) = W_N^{-k_0 n} x(n)\), then \(G(k) = X((k + k_0) \mod N)\).
\[ G(k) = \sum_{n=0}^{N-1} x(n) W_N^{-k_0 n} W_N^{-kn} = \sum_{n=0}^{N-1} x(n) W_N^{-(k+k_0)n} = X((k+k_0)\mod N) \]
-
Application: Given \(X(k)\) for \(x(n)\), find \(G(k)\) for \(g(n) = W_5^{-2n}x(n)\).
-
Here \(N=5\), \(k_0=2\).
-
\(G(k) = X((k+2)\mod 5)\).
-
If \(X(k) = [5,6,1,2,9]\) for \(k=0,\dots,4\):
\[ G(0)=X(2)=1,\; G(1)=X(3)=2,\; G(2)=X(4)=9,\; G(3)=X(0)=5,\; G(4)=X(1)=6 \]
\boxed{G(k) = [1,2,9,5,6]}
-
II. MULTIRATE SIGNAL PROCESSING FUNDAMENTALS
1. Quadrature Mirror Filter Banks (QMF)
-
Definition: A two-channel filter bank where analysis filters \(H_0(z)\) (lowpass) and \(H_1(z)\) (highpass) are mir-image responses about \(\omega = \pi/2\). Typically \(H_1(z) = H_0(-z)\).
-
Purpose: Split input signal into subbands (analysis) and reconstruct (synthesis) with aliasing cancellation.
-
Types & Conditions:
| Type | Property | Perfect Reconstruction (PR) Condition | |------|----------|--------------------------------------| | Orthogonal | \(H_0(z)H_1(-z) + H_0(-z)H_1(z) = 0\) | \(F_0(z)=H_1(-z), F_1(z)=-H_0(-z)\) (aliasing cancels, \(T(z)=2H_0(z)H_1(-z)\)) | | Non-orthogonal | No orthogonality constraint | Design \(F_0(z), F_1(z)\) to cancel aliasing and achieve desired \(T(z)\) |
-
Aliasing Cancellation: Achieved by choosing synthesis filters \(F_0(z), F_1(z)\) such that overall transfer function \(T(z)\) is distortion-free and alias terms sum to zero.
2. Computationally Efficient Sampling Rate Converters
-
Basic Operations:
-
Decimation (Downsampling by \(M\)): Keep every \(M\)-th sample, discard others. Requires anti-aliasing LPF before decimation.
-
Interpolation (Upsampling by \(L\)): Insert \(L-1\) zeros between samples. Requires anti-imaging LPF after upsampling.
-
-
Polyphase Implementation:
-
Polyphase Decomposition: Any filter \(H(z) = \sum_{n=0}^{N-1} h(n)z^{-n}\) can be written as:
\[ H(z) = \sum_{m=0}^{M-1} z^{-m} E_m(z^M), \quad \text{where } E_m(z) = \sum_{n} h(m+nM)z^{-n} \]
\(E_m(z)\) are polyphase components.
-
Efficient Architecture for Rational Rate Conversion \(L/M\):
-
Use polyphase filters after upsampler and before downsampler.
-
Reduces computation by factor \(\approx \max(L,M)\).
-
-
Commutator Model: For decimation, a polyphase network with commutator switch cycles through polyphase filters, outputting one sample per input block.
-
[!TIP] Key Benefit: Polyphase structures avoid processing zero samples (from upsampling) and reduce filter switching rate.
3. Spline Interpolation
-
Definition: Piecewise polynomial interpolation where pieces connect with continuous derivatives up to order \(p-1\) for p-th order spline.
-
Cubic Spline (\(p=3\)):
-
On each interval \([n, n+1]\), \(s(x) = a_n + b_n(x-n) + c_n(x-n)^2 + d_n(x-n)^3\).
-
Conditions: \(s(x)\) and first/second derivatives continuous at interior knots.
-
System of equations solved for coefficients (tridiagonal for second derivatives).
-
-
Comparison with Polynomial Interpolation:
| Method | Stability | Smoothness | Local Support | |--------|-----------|------------|--------------| | Zero-order (nearest) | Very stable | Discontinuous | Yes | | Linear | Stable | \(C^0\) continuous | Yes | | Cubic Spline | Stable | \(C^2\) continuous | Yes (local) | | High-degree Poly | Runge phenomenon | \(C^{p-1}\) | No (global) |
-
Application: Signal resampling and reconstruction in multirate systems (e.g., sample rate conversion).
III. DIGITAL FILTER DESIGN & STRUCTURES
1. Basic FIR Filter Structures
-
Direct Form:
-
Transversal structure: \(y(n) = \sum_{k=0}^{M} b_k x(n-k)\).
-
Simple, but coefficient sensitivity moderate.
-
-
Cascade Form: Series connection of second-order sections (biquads). Improves numerical stability vs. high-order direct form.
-
Linear Phase Structures:
-
Exploit symmetry: \(h(n) = h(M-1-n)\) (Type I/II) or antisymmetry (Type III/IV).
-
Reduce multiplications by ~50% (only \(\lceil (M+1)/2 \rceil\) unique coefficients).
-
Advantages: Exactly linear phase, always stable (no poles except at \(z=0\)).
-
Limitation: Higher order for sharp transitions vs. IIR.
-
2. Basic IIR Filter Structures
-
Direct Form I: Separate polynomials for numerator/denominator. Requires more delays; prone to coefficient quantization noise.
-
Direct Form II (Canonical): Shared delay elements. Minimal number of delays (\(=\max(M,N)\)). Sensitive to coefficient quantization (possible instability).
-
Cascade Form: Series connection of first- and second-order sections. Better numerical stability and coefficient sensitivity than direct forms.
-
Parallel Form: Parallel connection of sections (often all-pass + gain). Useful for adaptive and all-pass decompositions.
-
Comparison with FIR:
-
IIR: Lower order for sharp specs, nonlinear phase, potential instability.
-
FIR: Always stable, linear phase possible, higher order.
-
3. Parallel All-Pass Realization of IIR Transfer Functions
-
Theory: Any stable, rational IIR transfer function \(H(z)\) can be decomposed as:
\[ H(z) = \sum_{i=1}^{K} c_i A_i(z) + d \]
where each \(A_i(z)\) is an all-pass filter (\(|A_i(e^{j\omega})|=1\)) of form:
\[ A_i(z) = \frac{\tilde{p}_i + z^{-1}}{1 + \tilde{p}_i z^{-1}} \quad \text{(first-order)} \quad \text{or} \quad \frac{\tilde{p}_i + \tilde{q}_i z^{-1} + z^{-2}}{1 + \tilde{p}_i z^{-1} + \tilde{q}_i z^{-2}} \quad \text{(second-order)} \]
with poles/zeros reciprocals.
-
Implementation Benefits:
-
Improved Stability: Each all-pass section is inherently stable (poles inside unit circle).
-
Reduced Sensitivity: Coefficient quantization effects minimized; amplitude response less sensitive than phase.
-
Modular Design: Easy to adjust sections independently.
-
-
Design Methodology:
-
Factor \(H(z)\) into partial fractions or use spectral factorization.
-
Express each section as all-pass plus gain.
-
Cascade (series) or parallel combine sections.
-
-
Example Application: Design of half-band filters and wavelet filters where linear phase or stability is critical.
[!TIP] Exam Question Pattern: You may be asked to explain parallel all-pass realization, its benefits over direct form, and possibly a simple example (e.g., decompose a second-order IIR into all-pass sections).
Final Summary for Revision:
-
DFT Properties: Circular convolution ↔ multiplication; zero-padding for linear convolution; real/even → real/even DFT; modulation → circular shift.
-
Multirate: QMF for subband coding; polyphase for efficient rate change; splines for smooth interpolation.
-
Filter Structures: FIR: direct/cascade/linear phase (stable, linear phase). IIR: direct forms (sensitive), cascade/parallel (robust). Parallel all-pass: stability + low sensitivity.