A Caltech Library Service

Towards practical minimum-entropy universal decoding

Coleman, Todd P. and Médard, Muriel and Effros, Michelle (2005) Towards practical minimum-entropy universal decoding. In: Data Compression Conference (DCC '05), Snowbird, UT, 29-31 March 2005. IEEE Computer Society , Los Alamitos, CA, pp. 33-42. ISBN 0 7695 2309 9.

See Usage Policy.


Use this Persistent URL to link to this item:


Minimum-entropy decoding is a universal decoding algorithm used in decoding block compression of discrete memoryless sources as well as block transmission of information across discrete memoryless channels. Extensions can also be applied for multiterminal decoding problems, such as the Slepian-Wolf source coding problem. The 'method of types' has been used to show that there exist linear codes for which minimum-entropy decoders achieve the same error exponent as maximum-likelihood decoders. Since minimum-entropy decoding is NP-hard in general, minimum-entropy decoders have existed primarily in the theory literature. We introduce practical approximation algorithms for minimum-entropy decoding. Our approach, which relies on ideas from linear programming, exploits two key observations. First, the 'method of types' shows that that the number of distinct types grows polynomially in n. Second, recent results in the optimization literature have illustrated polytope projection algorithms with complexity that is a function of the number of vertices of the projected polytope. Combining these two ideas, we leverage recent results on linear programming relaxations for error correcting codes to construct polynomial complexity algorithms for this setting. In the binary case, we explicitly demonstrate linear code constructions that admit provably good performance.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 2005 IEEE. Reprinted with permission. The authors thank Jon Feldman and Ralf Koetter for their helpful discussions and comments on LP decoding.
Subject Keywords:computational complexity, decoding, entropy codes, error correction codes, linear codes, linear programming, memoryless systems, minimum entropy methods, relaxation theory, source coding
Record Number:CaltechAUTHORS:COLdcc05
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7373
Deposited By: Lindsay Cleary
Deposited On:08 Feb 2007
Last Modified:02 Oct 2019 23:41

Repository Staff Only: item control page