Optimal search in random quantizers

Signal sample quantization represents the basic operation of any system for digital signal processing and can be mathematically formalized as a least-distance application from the domain of input samples to a finite and fixed set of reproduction values generally called quantization levels, in case of scalar quantization, or reconstruction codewords in case of vector quantization. As the size of the reproduction set increases, the computational overhead introduced by the least-distance search procedure leads to a drastic reduction of the system performances. A fast and efficient implementation of the search algorithm represents a problem of key relevance, especially as far as high dimensional vector quantization is concerned. The algorithm presented in the paper employs a binary tree structure to address the reconstruction set according to the least-distance rule, providing a logarithmic reduction of the search complexity