Abstract
A theorem of Margulis states the existence of a threshold phenomenon in the probability of disconnecting a graph, given that each of its edges is independently severed with some probability p. We show how this theorem can be reinterpreted in the coding context: in particular we study the probability f c(p) of residual error after maximum likelihood decoding, when we submit a linear code C to a binary symmetric channel with error probability p. We show that the function f c(p) displays a threshold behaviour i.e. jumps suddenly from almost zero to almost one, and how the acuteness of the threshold effect grows with the minimal distance of C. Similar results for the erasure channel are also discussed.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
G. Margulis, Probabilistic characteristics of graphs with large connectivity, Problemy Peredachi Informatsii, 10 (1974), pp. 101–108.
M. Talagrand, Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem, Geometric and Functional Analysis, 3 (1993), pp. 295–314.
G. Zémor and G. Cohen, The threshold probability of a code. Submitted to IEEE Trans on Inf Theory.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zémor, G. (1994). Threshold effects in codes. In: Cohen, G., Litsyn, S., Lobstein, A., Zémor, G. (eds) Algebraic Coding. Algebraic Coding 1993. Lecture Notes in Computer Science, vol 781. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57843-9_29
Download citation
DOI: https://doi.org/10.1007/3-540-57843-9_29
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57843-7
Online ISBN: 978-3-540-48357-1
eBook Packages: Springer Book Archive