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. IEEE , Piscataway, NJ, USA, pp. 1593-1596. ISBN 0 7803 9305 8 http://resolver.caltech.edu/CaltechAUTHORS:COLwir05
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:COLwir05
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|
|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|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Lindsay Cleary|
|Deposited On:||07 Feb 2007|
|Last Modified:||26 Dec 2012 09:31|
Repository Staff Only: item control page