Title :
Towards practical minimum-entropy universal decoding
Author :
Coleman, Todd P. ; Médard, Muriel ; Effros, Michelle
Author_Institution :
MIT, MA, USA
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.
Keywords :
computational complexity; decoding; entropy codes; error correction codes; linear codes; linear programming; memoryless systems; minimum entropy methods; relaxation theory; source coding; Slepian-Wolf source coding; block compression; block transmission; discrete memoryless channels; error correcting codes; error exponent; linear codes; linear programming relaxations; method of types; minimum-entropy universal decoding; multiterminal decoding; optimization; performance; polynomial complexity algorithms; polytope projection algorithms; practical approximation algorithms; universal decoding algorithm; vertices; Channel coding; Data compression; Error probability; Information theory; Iterative decoding; Linear code; Linear programming; Maximum likelihood decoding; Memoryless systems; Polynomials;
Conference_Titel :
Data Compression Conference, 2005. Proceedings. DCC 2005
Print_ISBN :
0-7695-2309-9
DOI :
10.1109/DCC.2005.90