Fast algorithms for optimal two-description scalar quantizer design
Sorina Dumitrescu, Xiaolin Wu, Gaurav Bahl · 2004
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/sub 1/K/sub 2/N/sup 3/) time design algorithm, where N is the cardinality of the source alphabet, and K/sub 1/, K/sub 2/ are the number of codecells, respectively, of the two side quantizers. This complexity is reduced to O(K/sub 1/K/sub 2/N/sup 2/) by exploiting a so-called Monge property of the objective function. Furthermore, if K/sub 1/=K/sub 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(KN/sup 2/) time.