The threshold probability of a code |
| |
Authors: | Zemor G Cohen GD |
| |
Affiliation: | Ecole Nat. Superieure des Telecommun., Paris; |
| |
Abstract: | We define and estimate the threshold probability &thetas; 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 &thetas; is particularly relevant to the erasure channel since linear codes achieve a vanishing error probability as long as p⩽&thetas;, where p is the probability of erasure. In effect, &thetas; can be thought of as a capacity notion designed for codes rather than for channels. Binomial codes haven the highest possible &thetas; (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 |
| |
Keywords: | |
|
|