Update

Weight Enumerator and the Covering Radius of Codes

Author: Fuad M. Shareef
Department of Computer Science, Cihan University-Erbil

Author: Peter J. Cameron
School of Mathematics and Statistics, University of St Andrews, UK

DOI:http://dx.doi.org/10.24086/cuesj.v1n2a11

Abstract

The covering radius of a code is a fundamental parameter that is closely related to the quality of the code.  Determining the exact value of the covering radius of a binary linear code is a NP-complete problem (Assmus Jr, 1960). The question arises as to whether extra information on the code parameters can help in determining its covering radius.  In this paper we are concerned with this question and in particular with the potential relationship between the covering radius of a code and its weight enumerator. This is motivated by the observation that knowledge of the weight enumerator sheds a light on the way codewords are distributed.  We shall give an upper bound on the covering radius of arbitrary linear codes in terms of their parameters and show that inequivalent codes with the same weight enumerator do not necessarily have equal covering radius.

Keywords: Linear codes; Weight enumerator; Covering radius

References

Assmus Jr, E.F. & Key, J.D. (1992) Design and Their Codes. Cambridge: University Press.

Assmus Jr, E.F. & Mattson, Jr, F.F. (1969) New 5 –designs. J. Combinatorial Theory (A), 27, 307-423.

Cameron, P. J. & Lint, V. (1991) Graph, Codes, Design and their Links. Cambridge: Cambridge University Press.

Cohen, G., Honkala,I., Litsyn, S. & Lobstein, A. (1997) Covering Codes. North-Holland: Mathematical Library.

Delsarte, P. (1973) Four fundamental parameters of a code and their combinatorial significance. Inform and Control, 23, 407-438.

Greene, C. (1976) Weight enumeration and the geometry of linear codes. Studies Appl. Math., 55, 119-128.

MacWilliams, F.J. & Sloan, N.J. (1977) Theory of error-correcting codes, North Holland: Amsterdam.

Pless, V. & Sloane, N. J. A. (1975) On the classification and enumeration of self-dual codes. J. Comb. Theory, Ser. A, 18, 313-335.

Pless, V. (1972) A classification of self-orthogonal codes over GF(2). Discrete Math., 3, 209-246.

Rutherford, C. G. (2001) Matroids, codes, and their polynomial links. PhD thesis, London: University of London.

SchÖnert, M. et al. (1995) GAP – Groups, Algorithms, and Programming. Lehrstuhl D für Mathematik, Westfälische Technische Hochschule, Aachen, Germany.

Shareef, F. M. (2001) The covering radius of codes and its relation to designs. PhD thesis, London: University of London.

Full Text

About admin

Check Also

Vol. 1, No. 2, ِAugust 2017 Cihan University-Erbil Scientific Journal

  Contents (Articles in English Language) Article Pages Expert Database System for Converting Unfit Query …

Leave a Reply

Your email address will not be published.