Bounds for unrestricted codes, by linear programming
Bounds for unrestricted codes, by linear programming
复制标题
DOI：
--
复制
发表时间：
1972
期刊：
影响因子：
--
通讯作者：
P. Delsarte
中科院分区：
文献类型：
--
作者：
P. Delsarte
The paper describes a problem of linear programming associated with distance properties of unrestricted codes. As a solution to the problem, one obtains an .upper bound for the number of words in codes having a prescribed set of distances. 1. Introduetion Important information about a code is contained in its Hamming distance distribution, defined as follows: for a q-ary code C of length n, it is the (n + 1)tuple (Ao(C), A1(C), ... , AII(C)), where A1(C) denotes the mean number of codewords being at Hamming distance i from a fixed codeword. For linear codes over the field GF(q), the distance distribution reduces to the classical weight distribution. In that case the distributions of a code C and of its dual C' are related by the MacWilliams identities 11), i.e., by linear equations of the form IJ ICI Ak(C/) = ~ A1(C)Pk(i), 0 ~ k ~ n, 1=0 (1) where the Pk(i) are constant integers, only depending on nand q. It turns out that Pk(X) can be identified with a Krawtchouk polynomial of degree k, for a suitable normalization (cf. Szegö 16)). The present paper starts from the observation that the distance distribution of an unrestricted code (over an unrestricted alphabet) yields nonnegative numbers when substituted to the right-hand member of (1). This theorem leads in a natural way to a problem of linear programming, the solution of which gives an upper bound for the number of words in codes having a designed set of distances. Some characteristic properties of codes meeting that bound are also derived from the well-known theory of duality in linear programming; for this we refer to Simonnard 14). When only the minimum distance is specified, these results imply, as particular cases, some classical theorems such as the Plotkin, Singleton and Hamming bounds (cf. Berlekamp 1)). In the latter case, the codes meeting the bound are the perfect codes and the characterization one obtains for them is the Lloyd theorem (cf. Van Lint 9)) which is shown to hold for any alphabet. BOUNDS FOR UNRESTRICTED CODES. BY LINEAR PROGRAMMING 273 The same result has been recently discovered by Lenstra B), in a very different way. For group codes over an Abelian group, called additive codes in this paper, one defines a duality relation that reduces to the classical concept for linear codes over a prime field. If Cl is the dual of any additive code C, it is shown that the MacWilliams identities on the weight distributions are still satisfied. A basic tool in this paper is the theory of group characters of an Abelian group, used in a similar way as in Van Lint 9). Mapping the q-ary alphabet onto an Abelian group of order q, one defines the characteristic matrices of a code by means of the characters of that group. These matrices appearto be very useful in the study of distance properties of a code. 2. Definitions and preliminaries Let V = F" be the set of n-tuples over a finite alphabet F of order q, with q ~ 2, n ;;:,1. Then V is made a metric space by definition of the Hamming distance d over it: for any two points a, b of V, we set dCa,b) = I {i 11 ~ i ~ n, al =]i: bl}l, where al denotes the ith component of a. An (n, M) code over F is a subspace of cardinality M of the metric space (V, d). The elements of a code are called the codewords. In order to be able to calculate with codes, we now map the alphabet F onto a given "additive" Abelian group of order q, in an arbitrary way. Then the points of V are considered as elements of the group (F, +)", and V is made a normed space by means of the Hamming weight w, where w(a) is defined to be the number of nonzero components of a. Comparing this with the definition of d, we have dia, b) = w(ab), Va, b F V. (2) Let 'V be the period of the group (F, +), i.e., the smallest integer 'V such that '1'/= 0, V/ E F. We shall now introduce a symmetric inner product (,) of V over the cyclotomic field Qv of complex vth roots of unity. The notations are the same as in the author's paper on Abelian codes 2). Let /0 = 0'/1'/2' ... ,/;., with À = q1, be the elements of F and let CPo, CP1' ••• , CP;. be the group characters of (F, +), i.e., the homomorphic mappings of (F, +) into the multiplicative group of Qv. It is always possible to choose the numbering in such a way that CPI(fj) = cPift)· In particular, CPo is the principal character: CPo(fj) = 1V j. Then, for a, b E V, we define " (a, b) = IT c?t,(al), with Ir, = bi' 1=1 (3)
