A Caltech Library Service

Linear complexity universal decoding with exponential error probability decay

Coleman, Todd P. and Médard, Muriel and Effros, Michelle (2005) Linear complexity universal decoding with exponential error probability decay. In: International Conference on Wireless Networks, Communications and Mobile Computing, Maui, HI, 13-16 June 2005. Vol.2. IEEE , Piscataway, NJ, USA, pp. 1593-1596. ISBN 0 7803 9305 8.

See Usage Policy.


Use this Persistent URL to link to this item:


In this manuscript we consider linear complexity binary linear block encoders and decoders that operate universally with exponential error probability decay. Such scenarios may be relevant in wireless scenarios where probability distributions may not be fully characterized due to the dynamic nature of wireless environments. More specifically, we consider the setting of fixed length-to-fixed length near-lossless data compression of a memoryless binary source of unknown probability distribution as well as the dual setting of communicating on a binary symmetric channel (BSC) with unknown crossover probability. We introduce a new 'min-max distance' metric, analogous to minimum distance, that addresses the universal binary setting and has the same properties as that of minimum distance on BSCs with known crossover probability. The code construction and decoding algorithm are universal extensions of the 'expander codes' framework of Barg and Zemor and have identical complexity and exponential error probability performance.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 2005 IEEE. Reprinted with permission.
Subject Keywords:binary codes, block codes, channel coding, data compression, decoding, error statistics, linear codes, minimax techniques, probability
Record Number:CaltechAUTHORS:COLwir05
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7376
Deposited By: Lindsay Cleary
Deposited On:07 Feb 2007
Last Modified:08 Nov 2021 20:42

Repository Staff Only: item control page