Fast algorithms for optimal two-description scalar quantizer design

New efficient algorithms are presented to design globally optimal two-description quan-tizers 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_{1}K_{2}N^{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_{1}K_{2}N^{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(KN^{2})$ time.