Cihan University-Erbil Scientific Journal a periodic multidisciplinary scientific journal issued by Cihan University- Erbil after auditing and revising by a specialized staff headed by the President of the university. The journal publishes original creative researches related to all fields of pure and applied sciences and humanities in Kurdish, Arabic and English.
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
