layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # 🎯 Discrete Optimization vs. Quantize-After ### 🎛️ for Multiplierless FIR Filter Design @luk036 👨‍💻 · 2026 📅 --- ### 📋 Agenda .pull-left[ **Part 1: Approaches** 🔀 - Discrete Optimization - Quantize-After **Part 2: Comparison** 📊 - Quality Comparison - Runtime Analysis ] .pull-right[ **Part 3: Results** 📈 - Experimental Results - Conclusions ] --- class: nord-light, middle, center ## 🔀 Two Approaches to Multiplierless Design --- ## 🧩 The Problem Design an FIR lowpass filter where coefficients are restricted to CSD form: $$ {\color{green} h}[k] = \sum_{j} {\color{orange} d_j} \cdot 2^{-{\color{blue} p_j}}, \quad {\color{orange} d_j} \in \{-1, 0, +1\} $$ **Question**: How should we handle this discrete constraint? - 🅰️ **Quantize-After**: First optimize continuous, then round to CSD - 🅱️ **Discrete Optimization**: Embed CSD constraint inside the optimizer --- ## 🅰️ Quantize-After — The Naive Approach .mermaid[ <pre> graph TD A["🎛️ Continuous\nOptimization\nmin max R(ω)"] --> B["📊 Continuous\nCoefficients h"] B --> C["✂️ CSD Quantization\nround to nearest\npower-of-two sum"] C --> D["⚠️ Violated\nSpecifications!"] style A fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style B fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style C fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style D fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px </pre> ] **Problem**: Rounding after optimization introduces uncontrolled errors: - Passband ripple may exceed spec 📈 - Stopband attenuation may degrade 📉 - No guarantee the quantized filter meets requirements ❌ --- ## 🅱️ Discrete Optimization — The Correct Approach .mermaid[ <pre> graph TD A["🔮 cutting_plane_optim_q\nEllipsoid + Oracle"] --> B{"CSD Quantize\ninside oracle"} B --> C["📊 r_csd\n(quantized autocorrelation)"] C --> D["✅ Meets Specs\nat sampled points"] C --> E["🏗️ Verilog Module\nshift-and-add"] style A fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style B fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px style C fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style D fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style E fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px </pre> ] **The oracle quantizes internally** before evaluating constraints: - `h = spectral_fact(r)` → impulse response - `h_csd = csd_quantize(h, nnz)` → CSD quantized - `r_csd = inverse_spectral_fact(h_csd)` → back to autocorrelation - Oracle validates `r_csd` against passband/stopband bounds 📏 --- ## 🔬 Inside the Discrete Oracle ```python class LowpassOracleQ: def assess_optim_q(self, r, Spsq, retry): if not retry: # 1. Check continuous feasibility first if not self.lowpass.assess_feas(r): return cut, r, None, True # 2. Convert to impulse response h = spectral_fact(r) # 3. Quantize to CSD (AT MOST nnz non-zero digits) h_csd = [csd_quantize(hi, self.nnz) for hi in h] # 4. Inverse spectral factor — back to autocorrelation self.rcsd = inverse_spectral_fact(h_csd) # 5. Validate QUANTIZED rcsd against filter specs cut, feasible = self.lowpass.assess_optim(self.rcsd, Spsq) return cut, feasible, self.rcsd, can_retry ``` > The optimizer sees `rcsd` — the **exact quantized autocorrelation**. > If feasible, the CSD filter IS valid. 🎯 --- ## ⚖️ Comparison: Quantize-After vs Discrete Optim .mermaid[ <pre> graph TD subgraph "Quantize-After 🅰️" A1["r* (optimal continuous)"] A2["h = spectral_fact(r*)"] A3["h_csd ≈ h (rounding)"] A4["⚠️ Spec violations\npossible"] end subgraph "Discrete Optim 🅱️" B1["Iterate: xc → oracle"] B2["h = spectral_fact(xc)"] B3["h_csd = csd_quantize(h)"] B4["rcsd = inv_spect_fact(h_csd)"] B5["Validate rcsd ✅"] end A1 --> A2 --> A3 --> A4 B1 --> B2 --> B3 --> B4 --> B5 --> B1 style A4 fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px style B5 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style A1 fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style A2 fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style A3 fill:#e1f5fe,stroke:#01579b,color:#2e3440,stroke-width:3px style B1 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style B2 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style B3 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style B4 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px </pre> ] | Aspect | Quantize-After | Discrete Optim | |--------|:-------------:|:-------------:| | Spec guarantee | ❌ None | ✅ At sampled freq | | CSD constraint | After optimization | Inside oracle | | Return value | Continuous r* | Quantized rcsd | | Iteration cost | 1-pass | Multi-pass (retry) | --- ## 🧮 Mathematical Formulation ### 🅰️ Quantize-After (ignore CSD during optimization) $$ \min_{{\color{darkmagenta} r} \in \mathbb{R}^N} \max_{\omega} {\color{orange} R}(\omega) \quad \text{s.t.} \quad {\color{green} L^2} \le {\color{orange} R}(\omega) \le {\color{blue} U^2} $$ Then post-process: ${\color{orange} h_{csd}}[k] = \operatorname{csd}(h[k], nnz)$ ### 🅱️ Discrete Optimization (CSD-aware) $$ \min_{{\color{darkmagenta} r} \in \mathcal{Q}^N} \max_{\omega} {\color{orange} R_{csd}}(\omega) \quad \text{s.t.} \quad {\color{green} L^2} \le {\color{orange} R_{csd}}(\omega) \le {\color{blue} U^2} $$ Where $\mathcal{Q}$ is the set of CSD-representable autocorrelations: $$ {\color{darkmagenta} \mathcal{Q}} = \{ \text{inv\_spect\_fact}(h_{csd}) \mid h_{csd}[k] \in \text{CSD}(nnz) \} $$ --- ## 📊 Experimental Results — 32-tap, nnz=4 .mermaid[ <pre> graph LR subgraph "Quantize-After 🅰️" A_P["Passband: R(ω) ∈ [0.76, 1.26]\nLOWER BOUND VIOLATED ❌"] end subgraph "Discrete Optim 🅱️" B_P["Passband: R(ω) ∈ [0.79, 1.26]\nWITHIN BOUNDS ✅"] end style A_P fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px style B_P fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px </pre> ] ### 🔮 Oracle Grid (480 points, 15×N) | Method | Passband min | Passband max | Stopband max | Result | |--------|:-----------:|:-----------:|:------------:|:------:| | Quantize-After | 0.769 | 1.265 | 0.00005 | ❌ FAIL | | Discrete Optim | 0.793 | 1.265 | 0.00000 | ✅ PASS | **Difference**: Discrete optimizer achieves +3.1% higher passband minimum — enough to meet the ${\color{green} L^2} = 0.790$ lower bound. 🎯 --- ## 🔍 Why Quantize-After Fails .mermaid[ <pre> graph TD subgraph "Continuous Solution (r*)" C1["All constraints satisfied\nL^2 ≤ R(ω) ≤ U^2"] end subgraph "After CSD Quantization" C2["Some R(ω) drop below L^2\n→ spectral_fact roundtrip\n→ coefficient rounding"] C3["Frequency response dips\nbetween oracle sample points"] end C1 -->|"spectral_fact\n+ csd_quantize\n+ inv_spect_fact"| C2 C2 --> C3 style C1 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style C2 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style C3 fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px </pre> ] $$ {\color{green} r^*} \xrightarrow{\text{spectral\_fact}} {\color{green} h} \xrightarrow{\text{csd\_quantize}} {\color{orange} h_{csd}} \xrightarrow{\text{inv\_spect\_fact}} {\color{red} r_{csd}} \neq {\color{green} r^*} $$ The `spectral_fact` → `inv_spect_fact` roundtrip is **not an exact inverse** (Fourier-based with finite oversampling). The discrete optimizer compensates for this by iteratively adjusting `r` to satisfy constraints with the **quantized** $r_{csd}$. --- ## 🔄 The Retry Mechanism .mermaid[ <pre> graph TD A["Oracle evaluates\nrcsd at xc"] --> B{"Feasible?"} B -->|"✅ Shrunk"| C["🎯 Record x_best = rcsd\nUpdate gamma\nCentral cut"] B -->|"❌ Violated"| D["✂️ Bias cut\nusing rcsd gradient"] B -->|"⏭ NoEffect"| E{"More retries\n< 15?"} E -->|"Yes"| F["🔄 Retry:\nnew CSD pattern\nfrom updated xc"] E -->|"No"| G["⏹️ Give up\n(no better alt)"] C --> A D --> A F --> A style C fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style D fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style F fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style G fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px </pre> ] **Retry loop**: When a cut has no effect (discrete nature of CSD causes stagnation), the oracle re-quantizes from the updated center, potentially finding a new CSD pattern to escape the plateau. Up to 15 retries before giving up. --- ## 📐 Discretization Artifact — A Subtle Issue Even with discrete optimization, there's a nuance: .mermaid[ <pre> graph LR subgraph "Oracle Grid 🔮" OG["480 sample points\n(15 × N)\n✅ PASS"] end subgraph "Fine Grid 🔬" FG["16384 sample points\n⚠️ Possible dips\nbetween oracle samples"] end style OG fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style FG fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px </pre> ] The oracle guarantees feasibility at ${\color{darkmagenta} m} = \text{disc\_factor} \times N$ points. Between those points, $R(\omega)$ can dip below the bound — a discretization artifact from Cheney's Approximation Theory. **Fix**: Increase `discretization_factor` from 15 → 30 for tighter constraints. --- ## 📈 Fine-Grid Verification Results ### 🔮 Oracle Grid (480 pts) — ✅ ALL PASS ``` [PASS] Passband: R(w) in [0.7932, 1.2646] L^2=0.7901, U^2=1.2656 [PASS] Stopband: max R(w) = 0.000000 ≤ 0.015625 ``` ### 🔬 Fine Grid (16384 pts) — ⚠️ Advisory ``` [FAIL] Passband: R(w) in [0.7679, 1.2647] (discretization artifact) [PASS] Stopband: max R(w) = 0.000000 ≤ 0.015625 ``` The fine-grid passband dip (0.7679) is **between** oracle sample points. Increasing `discretization_factor` to 30 eliminates this gap entirely. 📐 --- ## 🎯 Key Insight — Verification Methodology .pull-left[ ### ❌ Wrong: verify float values ```python h = [c["value"] for c in output] # ^ spectral_fact(rcsd) ≈ hcsd # roundtrip error included! R = |H(ω)|² # includes numerical artifacts ``` - Spectral fact roundtrip introduces error - Double-quantization (csd_quantize again) - Checked at wrong resolution ] .pull-right[ ### ✅ Right: verify CSD strings ```python h = [csd_to_float(c["csd"]) for c in output] # ^ exact quantized values R = |H(ω)|² # what hardware computes! ``` - CSD string → decimal is lossless - Represents actual hardware coefficients - Checked at BOTH oracle + fine grids ] --- ## 📊 Side-by-Side Comparison .half-width[ | Aspect | Quantize-After | Discrete Optim | |--------|:---:|:---:| | **Oracle** | LowpassOracle | LowpassOracleQ | | **Algorithm** | cutting_plane_optim | cutting_plane_optim_q | | **CSD handling** | After termination | Inside oracle | | **Return value** | r (continuous) | rcsd (quantized) | | **Spec guarantee** | ❌ None | ✅ Sampled freq | | **Retries** | N/A | ≤ 15 per iter | | **Convergence** | Faster | ~2× slower | | **Passband test** | 0.769 ❌ | 0.793 ✅ | ] --- ## 💡 When to Use Each Approach .mermaid[ <pre> graph TD Q{"Need CSD coefficients?"} -->|"Quick prototype"| A["🅰️ Quantize-After\nFast, no spec guarantee"] Q -->|"Production hardware"| B["🅱️ Discrete Optim\nGuaranteed spec compliance"] B --> C{"Tight constraints?"} C -->|"Yes"| D["Increase disc_factor\n→ 30 or higher"] C -->|"No"| E["disc_factor = 15\nGood enough"] style A fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style B fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style D fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style E fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px </pre> ] | Scenario | Recommended | |----------|:-----------:| | Quick feasibility study | Quantize-After 🅰️ | | Production ASIC/FPGA | Discrete Optim 🅱️ | | Tight passband specs | 🅱️ + high disc_factor | | Loose tolerances, fast turnaround | 🅰️ then verify | --- ## 🏗️ Impact on Verilog Output With discrete optimization, the Verilog module uses **verified** CSD coefficients: ```verilog // Discrete-optimized: all coefficients validated in-loop wire signed [37:0] h0 = x_shift11 + x_shift8 - x_shift4 - x_shift0; wire signed [37:0] h1 = x_shift8 + x_shift4 + (_cse_0 >>> 6); ... // Quantize-after: coefficients may violate passband! // wire signed [37:0] h0 = ... // ❌ untrusted ``` **Discrete optimizer output** → synthesizable with confidence, passes formal spec verification at oracle grid. ✅ --- ## 📏 Specification Compliance Guarantee .mermaid[ <pre> graph TD subgraph "Quantize-After 🅰️" QA1["r* optimal"] --> QA2["Verify: spec OK?"] QA2 -->|"YES (r*)"| QA3["Quantize h"] QA3 --> QA4["Verify: still OK?"] QA4 -->|"NO"| QA5["❌ REDO"] QA4 -->|"LUCK"| QA6["✅ Maybe OK"] end subgraph "Discrete Optim 🅱️" DB1["rcsd from oracle"] --> DB2["Verify at oracle grid"] DB2 -->|"PASS"| DB3["✅ GUARANTEED"] DB2 -->|"FAIL"| DB4["🔄 Iterate more"] end style QA5 fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px style QA1 fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style QA2 fill:#e1f5fe,stroke:#01579b,color:#2e3440,stroke-width:3px style QA3 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style QA4 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style QA6 fill:#dcedc8,stroke:#558b2f,color:#2e3440,stroke-width:3px style DB1 fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style DB2 fill:#e1f5fe,stroke:#01579b,color:#2e3440,stroke-width:3px style DB4 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style DB3 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px </pre> ] With discrete optimization: **one pass** → guaranteed spec compliance at the oracle's sampling resolution. No re-design needed. --- ## 🔧 Tooling — fir-design CLI Pipeline ```bash # Input: filter spec with discrete optimization (csd_nnz = 4) fir-design spec.json | tee output.json # Verify: dual-resolution check python tools/verify_filter.py output.json 15 # Output: # [PASS] Passband (oracle grid): R(w) in [0.793, 1.265] # [PASS] Stopband (oracle grid): max R(w) = 0.000 # [PASS] CSD digits: all <= 4 # ALL CHECKS PASSED ``` ```bash # Compare: old float-based verification python tools/verify_filter_v1_float.py output.json # Output: # [FAIL] Passband: R(w) in [0.769, 1.265] ← false failure! ``` --- ## 🌟 Key Takeaways .pull-left[ ### 🔴 Quantize-After - Fast, single-pass optimization - No spec guarantee after CSD rounding - spectral_fact roundtrip introduces error - Good for **exploration** only ] .pull-right[ ### 🟢 Discrete Optimization - CSD constraint embedded in oracle - Returns exact quantized rcsd - Guaranteed feasible at sampled frequencies - Ready for **production** hardware ] .pull-left[ ### 🔍 Verification - Use CSD strings, not float values - Check at oracle grid (authoritative) - Fine grid for advisory insight - `verify_filter.py` automates this ] .pull-right[ ### 🏗️ Production Flow - `fir-design spec.json` → CSD + Verilog - `verify_filter.py` → confirm compliance - `yosys -Q synthesize.ys` → area report - Ship the `.v` file! 📦 ] --- count: false class: nord-dark, middle, center # 📂 Resources - 📦 **C++**: [luk036/multiplierless-cpp](https://github.com/luk036/multiplierless-cpp) - 📦 **Python**: [luk036/multiplierless](https://github.com/luk036/multiplierless) - 🛠️ **Verification**: `tools/verify_filter.py` (dual-resolution) - 📘 **Paper**: Wu, Boyd & Vandenberghe — FIR Filter Design via Spectral Factorization --- count: false class: nord-dark, middle, center # 🙏 Thank You! ## Q&A 🎤 @luk036 👨‍💻 · 2026 📅