Abstract
In [1] K. A. S. Abdel-Ghaffar derives a lower bound on the probability of undetected error for unrestricted codes. The proof relies implicitly on the binomial moments of the distance distribution of the code. We use the fact that these moments count the size of subcodes of the code to give a very simple proof of the bound in Abdel by showing that it is essentially equivalent to the Singleton bound. This proof reveals connections of the probability of undetected error to the rank generating function of the code and to related polynomials (Whitney function, Tutte polynomial, and higher weight enumerators). We also discuss some improvements of this bound.
Finally, we analyze asymptotics. We show that an upper bound on the undetected error exponent that corresponds to the bound of Abdel improves known bounds on this function.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
K. A. S. Abdel-Ghaffar, A lower bound on the undetected error probability and strictly optimal codes, IEEE Trans. Inform. Theory, Vol. 43,No. 5 (1997) pp. 1489-1502.
A. Barg, The matroid of supports of a linear code, Applicable Algebra in Engineering, Communication and Computing, Vol. 8 (1997) pp. 165-172.
T. Brylawski and J. G. Oxley, The Tutte polynomial and its applications, in Matroid Applications (N. White, ed.), Encyclopedia of Mathematics and Its Applications, Vol. 40, Cambridge Univ. Press (1992).
N. J. Fine, Hypergeometric Series and Applications, AMS (1988).
C. Greene, Weight enumeration and the geometry of linear codes, Stud. Appl. Math., Vol. 55 (1976) pp. 119-128.
T. Helleseth, T. Kløve, and V. I. Levenshtein, On the information function of an error-correcting code, IEEE Trans. Inform. Theory, Vol. 43,No. 2 (1997) pp. 549-557.
T. Helleseth, T. Kløve, and J. Mykkeltveit, The weight distribution of irreducible cyclic codes with block lengths n1((ql − 1)/N), Discrete Math., Vol. 18 (1977) pp. 179-211.
G. L. Katsman and M. A. Tsfasman, Spectra of algebraic geometric codes, Problemy Peredachi Informatsii, Vol. 23,No. 4 (1988) pp. 19-34.
G. L. Katsman, M. A. Tsfasman, and S. G. VlĂduţ, Spectra of linear codes and error probability of decoding, in Coding Theory and Algebraic Geometry (H. Stichtenoth and M. A. Tsfasman, eds.), Lect. Notes Math., Vol. 1518, Springer, Berlin (1992) pp. 82-98.
T. Kløve and V. I. Korzhik, Error Detecting Codes, Kluwer (1995).
T. Kløve, Bounds on the weight distribution of cosets, IEEE Trans. Inform. Theory, Vol. 42,No. 6 (1996) pp. 2257-2260.
V. I. Korzhik, Bounds on the probability of undetected error and optimum group codes in a channel with feedback, Radiotechnika, Vol. 20,No. 1 (1965) pp. 27-33. English translation in Telecommun. Radio Eng., Vol. 20, No. 1, pt. 2 (1965) pp. 87–92.
V. K. Leontiev, Error-detecting encoding, Problemy Peredachi Informatsii, Vol. 8,No. 3 (1972) pp. 6-14.
V. I. Levenshtein, Bounds on the probability of undetected error, Problemy Peredachi Informatsii, Vol. 13,No. 1 (1977) pp. 3-18.
V. I. Levenshtein, Straight-line bound for the undetected error exponent, Problemy Peredachi Informatsii, Vol. 25,No. 1 (1989) pp. 33-37.
F. J. MacWilliams, A theorem on the distribution of weights in a systematic codes, Bell Syst. Techn. Journal, Vol. 42 (1963) pp. 79-94.
J. Simonis, The effective length of subcodes, Applicable Algebra in Engineering, Communication and Computing, Vol. 5 (1994) pp. 371-377.
D. J. A. Welsh, Complexity: Knots, Colourings and Counting, London Math. Society Lecture Note Series, Vol. 186, Cambridge Univ. Press, Cambridge (1993).
J. K. Wolf, A. M. Michelson, and A. H. Levesque, On the probability of undetected error for linear block codes, IEEE Trans. Commun, Vol. 30 (1982) pp. 317-324.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Barg, A., Ashikhmin, A. Binomial Moments of the Distance Distribution and the Probability of Undetected Error. Designs, Codes and Cryptography 16, 103–116 (1999). https://doi.org/10.1023/A:1008382528138
Issue Date:
DOI: https://doi.org/10.1023/A:1008382528138