--- title: "Remez exchange algorithm with flow chart" subject: "Digital Signal Analysis and Processing" chapter: 5 key: "semester_7/digital_signal_analysis_and_processing:remez-flowchart-explain" source: https://www.bctengineer.com/q/semester_7/digital_signal_analysis_and_processing/remez-flowchart-explain site: BCT Engineering --- # Remez exchange algorithm with flow chart Digital Signal Analysis and Processing · Chapter 5: FIR Filter Design - Asked in: 2073 Shrawan, 9 marks; 2071 Shrawan, 9 marks; 2073 Chaitra, 7 marks; 2072 Kartik, 6 marks (asked 4 times) - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/digital_signal_analysis_and_processing/remez-flowchart-explain - Whole chapter: https://www.bctengineer.com/md/semester_7/digital_signal_analysis_and_processing/chapter-5 ## Question Explain the Remez exchange algorithm with suitable derivation and flow chart. ## Short answer The Remez exchange algorithm minimizes the maximum weighted error. It selects L+2 alternating extremal frequencies where E(ω_i)=(−1)^i δ, solves for δ and H_r(ω) by Lagrange interpolation, then finds new local maxima of |E(ω)| on a dense grid and updates the set. The process repeats until convergence, then h(n) is computed via IDFT. ## Answer The **Remez exchange algorithm** (Parks–McClellan) designs an optimal equiripple linear-phase FIR filter. It iteratively adjusts a set of "extremal" frequencies until the weighted approximation error has equal-height ripples. It is the usual way to implement the Chebyshev (minimax) criterion. #### Problem set-up For a symmetric, odd-length filter (Type I), H(e^jω) = e^{−jωL} H_r(ω) with H_r(ω) = Σ (k = 0 to L) a(k) cos kω, L = (M−1)/2 and the weighted error over the pass and stop bands (the set S): E(ω) = W(ω) [H_d(ω) − H_r(ω)], ω ∈ S The goal is to choose a(k) to minimise δ = max over S of |E(ω)|. #### Derivation By the **alternation theorem**, the best H_r(ω) is the one for which |E(ω)| reaches its maximum δ at at least L + 2 points ω₀ < ω₁ < … < ω_{L+1} in S, with alternating signs: E(ω_i) = (−1)^i δ ⇒ H_r(ω_i) = H_d(ω_i) − (−1)^i δ / W(ω_i) These are L + 2 linear equations in the L + 1 coefficients a(k) and δ. Using x_i = cos ω_i, they are solved without matrix inversion: - δ = [Σ_{k=0}^{L+1} b_k H_d(ω_k)] / [Σ_{k=0}^{L+1} (−1)^k b_k / W(ω_k)], b_k = Π_{i≠k} 1/(x_k − x_i) - For the first L + 1 points, C_k = H_d(ω_k) − (−1)^k δ/W(ω_k), the amplitude response at any x = cos ω is the Lagrange interpolation H_r(ω) = [Σ d_k C_k/(x − x_k)] / [Σ d_k/(x − x_k)], d_k = Π_{i≠k, i≤L} 1/(x_k − x_i) #### Algorithm steps 1. Choose M and band edges; guess L + 2 extremal frequencies (equally spaced in the bands, including the band edges). 2. Compute δ from the formula above. 3. Compute H_r(ω) by interpolation and evaluate E(ω) on a dense grid (about 16 × M points). 4. Find the local maxima of |E(ω)| on the grid. If at some frequencies |E| > |δ|, take the L + 2 largest alternating extrema as the new set (this is the "exchange"). 5. Repeat steps 2–4 until max |E| ≈ |δ| (the set no longer changes). Convergence is guaranteed. 6. Compute the impulse response by inverse DFT of the sampled H_r(ω): h(n) = (1/M)[H_r(0) + 2 Σ (k=1..L) H_r(2πk/M) cos(2πk(n−L)/M)]. #### Flow chart ```text ┌───────────────────────────┐ │ Inputs: M, edges, W(ω) │ └─────────────┬─────────────┘ ▼ ┌───────────────────────────┐ │ Initial guess of L+2 │ │ extremal frequencies │ └─────────────┬─────────────┘ ▼ ┌───────────────────────────┐ ◄─────────┐ │ Compute δ │ │ └─────────────┬─────────────┘ │ ▼ │ ┌───────────────────────────┐ │ │ Interpolate H_r(ω); find │ │ │ error E(ω) on dense grid │ │ └─────────────┬─────────────┘ │ ▼ │ ┌───────────────────────────┐ no │ │ max|E(ω)| ≤ |δ| (+ tol)? ├───────────┤ └─────────────┬─────────────┘ new set │ │ yes of L+2 │ ▼ extrema ─┘ ┌───────────────────────────┐ │ Compute h(n) (IDFT); stop │ └───────────────────────────┘ ``` The result is an equiripple filter with the smallest possible maximum error for that M. For a fixed δ the required M can be estimated from M ≈ [−10 log₁₀(δ₁δ₂) − 13] / (14.6 Δf) + 1, where Δf = (ωs − ωp)/2π. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does the Remez exchange algorithm produce? A. A linear-phase FIR filter with equiripple error satisfying the minimax criterion B. A filter with maximally flat response C. An IIR filter by bilinear transform D. A window with minimum side lobes Answer: A. It iterates on the extremal frequencies until the weighted error is equiripple. (Key point: Purpose) 2. What gives the L + 2 linear equations in the derivation? A. E(w_i) = (-1)^i delta at L + 2 extremal frequencies B. E(w) = 0 at all frequencies C. H_r(w_i) = 1 at L + 2 points D. Window orthogonality Answer: A. Alternation requires E(w_i) = (-1)^i delta, so H_r(w_i) = H_d(w_i) - (-1)^i delta/W(w_i). (Key point: Alternation theorem) 3. What is done in the exchange step? A. Swap pass-band and stop-band edges B. Pick the L + 2 largest alternating local extrema of |E| as the new set when |E| exceeds |delta| C. Double the length M D. Replace delta by zero Answer: B. The error is evaluated on a dense grid and the new extremal set replaces the old one. (Key point: Exchange step) 4. How is h(n) obtained at the end? A. By inverse DFT of sampled H_r(w) B. By differentiating H_r C. By multiplying with a window D. By solving a matrix inversion of M x M Answer: A. After convergence, h(n) is computed by IDFT of the sampled amplitude response. (Key point: Final step) ## Related in Digital Signal Analysis and Processing - [Optimum filter; Remez exchange expression](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Aoptimum-filter-remez-expression) — Digital Signal Analysis and Processing, chapter 5, asked 5× ## Related in other subjects - [Algorithm for an exchange sort](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aexchange-sort-algorithm) — Data Structure and Algorithm, chapter 7, asked 2× - [Bilateral/unilateral gains and design flow chart](https://www.bctengineer.com/question.md?key=semester_7%2Frf_and_microwave_engineering%3Aamplifier-gains-flowchart-0-55) — RF and Microwave Engineering, chapter 6 - [Unilateral max gain with design flow chart](https://www.bctengineer.com/question.md?key=semester_7%2Frf_and_microwave_engineering%3Aunilateral-gain-flowchart) — RF and Microwave Engineering, chapter 6 - [Decoupled load flow assumptions and algorithm](https://www.bctengineer.com/question.md?key=semester_5%2Fpower_system_analysis_ii%3Adecoupled-assumptions-algorithm) — Power System Analysis II, chapter 2, asked 2×