A Caltech Library Service

Quantization as histogram segmentation: globally optimal scalar quantizer design in network systems

Muresan, Dan and Effros, Michelle (2002) Quantization as histogram segmentation: globally optimal scalar quantizer design in network systems. In: Data Compression Conference (DCC '02), Snowbird, UT, 2-4 April 2002. IEEE Computer Society , Los Alamitos, CA, pp. 302-311. ISBN 0-7695-1477-4

See Usage Policy.


Use this Persistent URL to link to this item:


We propose a polynomial-time algorithm for optimal scalar quantizer design on discrete-alphabet sources. Special cases of the proposed approach yield optimal design algorithms for fixed-rate and entropy-constrained scalar quantizers, multi-resolution scalar quantizers, multiple description scalar quantizers, and Wyner-Ziv scalar quantizers. The algorithm guarantees globally optimal solutions for fixed-rate and entropy-constrained scalar quantizers and constrained optima for the other coding scenarios. We derive the algorithm by demonstrating the connection between scalar quantization, histogram segmentation, and the shortest path problem in a certain directed acyclic graph.

Item Type:Book Section
Additional Information:© Copyright 2002 IEEE. Reprinted with permission. This work was supported in part by the Lee Center for Advanced Networking at Caltech.
Subject Keywords:computational complexity, directed graphs, entropy codes, optimization, signal quantization, statistical analysis, source code design, source coding theory, network information theory
Record Number:CaltechAUTHORS:MURdcc02
Persistent URL:
Alternative URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7432
Deposited By: Archive Administrator
Deposited On:13 Feb 2007
Last Modified:26 Dec 2012 09:31

Repository Staff Only: item control page