A Novel Algorithm for Comparison-limited Vector Quantization

Joseph Chataignon, Stefano Rini

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

In [1] we have introduced the comparison-limited vector quantization (CLVQ) problem as a variation of the classic vector quantization problem in which the analog-To-digital (A2D) conversion is not constrained by the cardinality of the output but rather by the number of comparators available for quantization. More precisely, we consider the problem of producing a bit-restricted representation of a random vector of dimension d so as to minimize a given distortion between the quantizer input and output. This bit-restricted representation is obtained through k comparators, each receiving a linear combination of the inputs and producing zero/one when this signal is above/below a threshold. This vector quantizer architecture naturally arises in many analog-To-digital conversion scenarios in which the A2D performance is not limited by the number of bits used to represent the quantizer output, but rather on the limited availability of comparators in the quantizer. In this paper, we focus on the design of quantizer for the CLVQ problem through a polynomial-Time algorithm. The quantizer design problem has a super-exponential complexity and thus determining the optimal solution, even for moderate values of d, is computationally very challenging. For this reason, we develop a genetic algorithm for the optimization of the quantizer structure. This algorithm is aimed at producing a large number of quantizer designs to be used for initialization. For each candidate, the quantizer configuration is partially optimized using particle filters. After this optimization, quantizer configurations are again selected for fitness and recombined. Simulations are provided to numerically validate the proposed algorithm and compare the CLVQ performance to the classic Linde-Buzo-Gray algorithm.

Original languageEnglish
Title of host publicationIWCIT 2020 - Iran Workshop on Communication and Information Theory
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728182575
DOIs
StatePublished - May 2020
Event2020 Iran Workshop on Communication and Information Theory, IWCIT 2020 - Tehran, Iran, Islamic Republic of
Duration: 26 May 202028 May 2020

Publication series

NameIWCIT 2020 - Iran Workshop on Communication and Information Theory

Conference

Conference2020 Iran Workshop on Communication and Information Theory, IWCIT 2020
CountryIran, Islamic Republic of
CityTehran
Period26/05/2028/05/20

Keywords

  • Analog-To-digital conversion
  • Comparison-limited vector quantization
  • Genetic algorithm
  • Gray algorithm
  • Linde-Buzo

Fingerprint Dive into the research topics of 'A Novel Algorithm for Comparison-limited Vector Quantization'. Together they form a unique fingerprint.

Cite this