CaltechAUTHORS
  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 http://resolver.caltech.edu/CaltechAUTHORS:COLdcc05

[img]
Preview
PDF
See Usage Policy.

184Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:COLdcc05

Abstract

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
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:http://resolver.caltech.edu/CaltechAUTHORS:COLdcc05
Alternative URL:http://dx.doi.org/10.1109/DCC.2005.90
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7373
Collection:CaltechAUTHORS
Deposited By: Lindsay Cleary
Deposited On:08 Feb 2007
Last Modified:26 Dec 2012 09:31

Repository Staff Only: item control page