Fast algorithms for optimal two-description scalar quantizer design

Sorina Dumitrescu, Xiaolin Wu, Gaurav Bahl

Research output: Contribution to journalConference articlepeer-review


New efficient algorithms are presented to design globally optimal two-description quantizers of fixed rate. The optimization objective is to minimize the expected distortion at the receiver side. We formulate the problem as one of shortest path in a directed acyclic graph. The fixed rate requirement puts constraints on the number and type of edges of the shortest path, which leads to an O(K 1K 2N 3) time design algorithm, where N is the cardinality of the source alphabet, and K 1, K 2 are the number of codecells, respectively, of the two side quantizers. This complexity is reduced to O(K 1K 2N 2) by exploiting a so-called Monge property of the objective function. Furthermore, if K 1 = K 2 = K and the two descriptions are subject to the same channel statistics, then the optimal description quantizer design problem can be solved in O(K N 2) time.

Original languageEnglish (US)
Pages (from-to)42-51
Number of pages10
JournalData Compression Conference Proceedings
StatePublished - 2004
Externally publishedYes
EventProceedings - DCC 2004 Data Compression Conference - Snowbird, UT., United States
Duration: Mar 23 2004Mar 25 2004

ASJC Scopus subject areas

  • Computer Networks and Communications

Cite this