Fast Non-Uniform Quantization via Two-Level Lookup
Oswaldo Cadenas, Graham M. Megson · 2025
We present a practical and reusable software technique for quantizing real-valued inputs into m non-uniform bins at high speed, specifically optimized for embedded and real-time systems. Traditional approaches rely on binary search to map each input to its quantization bin, incurring O ( log m ) time per value. Our method introduces a two-level binning strategy that uses a lightweight preprocessing step to construct a uniform reference grid, a histogram, and a prefix sum array. Each query then performs a constant-time lookup followed by a short local refinement, achieving effective O (1) average-case performance in practice. Implemented in C and evaluated on both x86 and ARM Cortex-M platforms, the technique delivers up to a 4× speedup over binary search across a variety of input distributions, including real-world µ -law encoded audio streams. The approach requires minimal memory, is easily portable, and integrates well into embedded software stacks for signal processing, audio codecs, and telemetry systems.