The threshold probability of a code
Gilles Zémor, Gérard Cohen · IEEE Transactions on Information Theory · 1995
We define and estimate the threshold probability /spl theta/ of a linear code, using a theorem of Margulis (1974) 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 lesspl theta/, where p is the probability of erasure. In effect, /spl theta/ can be thought of as a capacity notion designed for codes rather than for channels. Binomial codes haven the 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.>