Fast algorithms for optimal two-description scalar quantizer design

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 ₁K ₂N ³) time design algorithm, where N is the cardinality of the source alphabet, and K ₁, K ₂ are the number of codecells, respectively, of the two side quantizers. This complexity is reduced to O(K ₁K ₂N ²) by exploiting a so-called Monge property of the objective function. Furthermore, if K ₁ = K ₂ = 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 ²) time.