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: $$ h[k] = \sum_{j} d_j \cdot 2^{-p_j}, \quad 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:#2196f3,color:#fff style B fill:#4caf50,color:#fff style C fill:#ff9800,color:#fff style D fill:#f44336,color:#fff </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:#ff9800,color:#fff style B fill:#9c27b0,color:#fff style C fill:#4caf50,color:#fff style D fill:#4caf50,color:#fff style E fill:#2196f3,color:#fff </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:#f44336,color:#fff style B5 fill:#4caf50,color:#fff style A1 fill:#2196f3,color:#fff style B1 fill:#ff9800,color:#fff </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_{r \in \mathbb{R}^N} \max_{\omega} R(\omega) \quad \text{s.t.} \quad L^2 \le R(\omega) \le U^2 $$ Then post-process: $h_{csd}[k] = \operatorname{csd}(h[k], nnz)$ ### Discrete Optimization (CSD-aware) $$ \min_{r \in \mathcal{Q}^N} \max_{\omega} R_{csd}(\omega) \quad \text{s.t.} \quad L^2 \le R_{csd}(\omega) \le U^2 $$ Where $\mathcal{Q}$ is the set of CSD-representable autocorrelations: $$ \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:#f44336,color:#fff style B_P fill:#4caf50,color:#fff </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 $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:#4caf50,color:#fff style C2 fill:#ff9800,color:#fff style C3 fill:#f44336,color:#fff </pre> ] $$ r^* \xrightarrow{\text{spectral\_fact}} h \xrightarrow{\text{csd\_quantize}} h_{csd} \xrightarrow{\text{inv\_spect\_fact}} r_{csd} \neq 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:#4caf50,color:#fff style D fill:#2196f3,color:#fff style F fill:#ff9800,color:#fff style G fill:#f44336,color:#fff </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:#4caf50,color:#fff style FG fill:#ff9800,color:#fff </pre> ] The oracle guarantees feasibility at $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:#ff9800,color:#fff style B fill:#4caf50,color:#fff style D fill:#2196f3,color:#fff style E fill:#4caf50,color:#fff </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:#f44336,color:#fff style DB3 fill:#4caf50,color:#fff </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! ## Questions? @luk036 👨‍💻 · 2026 📅