## Abstract

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 _{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(K N ^{2}) time.

Original language | English (US) |
---|---|

Pages (from-to) | 42-51 |

Number of pages | 10 |

Journal | Data Compression Conference Proceedings |

State | Published - 2004 |

Externally published | Yes |

Event | Proceedings - DCC 2004 Data Compression Conference - Snowbird, UT., United States Duration: Mar 23 2004 → Mar 25 2004 |

## ASJC Scopus subject areas

- Computer Networks and Communications