A threshold property of Iinear codes
Gilles Zémor, G.D. Cohen · 2005
We define and estimate the threshold probability /spl theta/ of a linear code, using a theorem of Margulis originally conceived for the study of the probability of disconnecting a graph. We then apply this concept to the study of the erasure and Z-channels, for which we propose linear coding schemes that admit simple decoding. We show that /spl theta/ is particularly relevant to the erasure channel since linear codes achieve a vanishing error probability as long as p /spl les/ /spl theta/, where p is the probability of erasure. Binomial codes have highest possible /spl theta/ (and achieve capacity). As for the Z-channel, a subcapacity is derived with respect to the linear coding scheme. For a transition probability in the range ] log(3/2); 1 [, we show how to achieve this subcapacity. As a by-product we obtain improved constructions and existential results for intersecting codes (linear Sperner families) which are used in our coding schemes.