THREE-WEIGHT CODES AND ASSOCIATION SCHEMES-猫眼课题宝

DOI：

发表时间：

2014

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

A. Calderbank;J.-M. Goethals

考虑三权重投影码C，其中汉明关联方案Hn(q)对C的限制是具有三类的关联方案。建立充分条件，得到C的三个权重的限制。在二进制情况下，缩短的二阶 Reed-Muller 码的三权重子码提供了大量示例。先前已知的例子是完美的 3 纠错码或统一打包的 2 纠错码的对偶。数学。 Rev.: 94B25, 05B30 1. Delsarte 研究了具有少距离码 C 的性质，即汉明关联方案对 C 的限制本身就是一个关联方案 1)，他对于线性码获得了一个充分必要条件：如果 C 是一个具有 s 权重的代码，那么汉明方案对 C 的限制是一个具有 s 类的关联方案当且仅当，在其对偶码的陪集之中CL，正好发生 s + 1 个不同的权重分布。先前已知的例子是从Delsarte的观察中得到的1）如果CL的最小距离d满足d~2s 1，则any的权重分布。 CL 的陪集由其最小权重唯一确定。 Goethals 和 van Tilborg 2) 表明，当且仅当 CL 是均匀打包的准完美码时，才会发生这种情况。在本文中，我们进一步研究了 Delsarte 条件在三权码情况下的含义。特别是，我们获得了一个新的充分条件，该条件也适用于 d < 5 的情况。在此过程中，我们还通过类似于 Calderbank 和 Goethals 3) 在 d ~ 2s 1 时使用的方法获得了对 C 权重的限制。我们还发现了一大类在二元情况下满足新条件的示例。本文的结构如下。秒后。 2，我们检查三权重投影码产生三级关联方案的条件并获得 Philips Journalof Research Vol. 2。 39 Nos 4/5 1984 143 144 飞利浦研究期刊 Vol.39 Nos 4/5 1984 A. R. Calderbank 和 J.-M. Goethals在定理2.2中提出了新的充分条件。秒后。如图3所示，我们通过证明缩短的二阶Reed-Muller码的所有三权重循环子码满足我们的新条件，获得了大量的例子。最后，在几秒钟内。参照图4，我们更详细地分析由此获得的关联方案的参数。我们对三权重循环码的研究源于这样一个事实，即这些码提供了具有良好互相关特性的周期序列，正如 Sarwate 和 Pursley 所表明的那样。 2. 三权重投影码和关联方案令 C 为有限域 GF(q) 上长度为 n、维度为 k 的三权重投影码。因此，我们假设：(i) C 的码字之间仅出现三个不同的非零距离；(ii) 对偶码 C.L 的最小距离为至少等于 3。C.L 的分布矩阵将 C.L Delsarte ' 的所有陪集的权重分布作为其行集（参见定理 6.10，第 91 页）证明，当且仅当对偶代码 C.L 的分布矩阵包含 s + 1 个不同行时，s 权重线性码 C 中的距离关系定义了与 C 上的 s 类的关联方案 A。 C.L 可以分为 s + 1 个不相交的子集，每个子集都由给定的权重分布来表征，我们用 So = (c.LJ, SI, S2, ... , Ss 表示。s + 1 关系 Ro,RI, ... ,Rs，由 (C.L + x, C.L +Y) E R 定义，当且仅当 C.L + (x + Y) E Si 时，然后产生与 A 对偶的 s 类关联方案 B（参见Delsarte '), Goethals 5), 以及 Calderbank 和 Goethals 3» 我们的目的是研究产生上述一对对偶关联方案的三权重投影码的类，足以检查这些码中的哪些具有在其对偶的陪集中仅出现四个不同的权重分布的属性，因为 C 中仅出现三个权重，因此 C.L 的覆盖半径最多等于 3。（参见 Delsarte+j），因此 C.L 的任何陪集的最小权重只能是以下值之一：0、1、2 或 3。如果我们假设所有四个值，并且只有四个不同的权重分布出现在 C.L 的陪集中，我们必须得出结论，任何陪集的权重分布都是由其最小权重唯一确定的，尽管原则上可以考虑其他可能性，但我们将把注意力限制在这种情况上。从 Delsarte 6）（参见 MacWilliams 和 Sloane 7），定理 20，第 169 页的结果可知，（1）三权码和关联方案任何陪集 C.L+ x 的权重分布 Ao(x)、AI(x)、...、An(x) 由前三个值 Ao(x)、AI(x) 和 A2(x) 唯一确定，其中 A;(x)表示距 x 距离 i 处的 C.L 的码字数量。更准确地说，我们以适合我们的情况的引理形式重申 Delsarte 的结果 (Delsarte) 让多项式的 Krawtchouk 展开 *) 由 3 F(z) = I (l;K;(z), ;=0 给出，其中 W1、W2、W3 是 C 中出现的三个权重。 k = 1,2, ... , n 3，令 Zk F(z) 的 Krawtchouk 展开式为 _ k+3 z" F(z) = I IJ;K;(z). ;=0 那么，对于任何陪集 C.L+ x，其权重枚举器的系数 A;(x) 之间的关系为 3 L (l;A;(x) = 1, ;=0 (2) k+3 LIJ; A;(x) = 0. ;=0 (3) 关系式 (2) 和 (3) 清楚地表明如何从前三个系数获得权重枚举器的所有系数。现在让我们检查 Ao(x)、AI(x) 和 A2(x) 的可能性。我们首先观察到： (i) 对于 C.Litself，我们有 Ao = 1，Al = A2 = 0，因为最小距离至少为 3。最小权重等于 3 的陪集，我们有 Ao = Al = A2 = 0。请注意，在这种情况下，我们必须从 (2) 得到 (l3A3 = 1。在这两种情况下，权重分布都是唯一确定的。对于每个剩余陪集 C.L+x，让我们假设存在整数 À. 1, À.2，使得来自 C.L 的距离 x 为 2 处的码字数量由 À 给出。 1，分别 À.2，如果 C.L+x 的最小权重分别为 2。 *) 对于 Krawtchouk 展开式的定义，例如，我们参考 MacWilliams 和 Sloane，第 168 页。 Philips Journalof Research Vol. 39 Nos 4/5 1984 145 A. R. Calderbank 和 J.-M. C.L+ x，我们有

Three-weight projective codes C are considered for which the restrietion to C of the Hamming association scheme Hn(q) is an association scheme with three classes. Sufficient conditions are established and restrictions on the three weights of C are obtained. It is shown in the binary case that the three-weight subcodes of the shortened second-order Reed-Muller codes provide a large class of examples. Previously known examples were the duals of perfect 3-error-correcting or uniformly packed 2-error-correcting codes. Math. Rev.: 94B25, 05B30 1. Introduetion Codes C with few distances having the property that the restrietion to C of the Hamming association scheme is itself an association scheme were studied by Delsarte 1), who for linear codes obtained a necessary and sufficient condition: if C is a code with s weights, then the restrietion to C of the Hamming scheme is an association scheme with s classes if and only if, among the cosets of its dual code CL, exactly s + 1 distinct weight distributions occur. Previously known examples were obtained from the observation made by Delsarte 1) that if the minimum distance d of CL satisfies d ~ 2s 1, then the weight distribution of any. coset of CL is uniquely determined by its minimum weight. It was shown by Goethals and van Tilborg 2) that this situation occurs if and only if CL is a uniformly packed quasi perfect code. In this paper, we investigate further the implications of Delsarte' s condition in the case of three-weight codes. We obtain, in particular, a new sufficient condition which applies also when d < 5. Along the way we also obtain restrictions on the weights of C by a method similar to the one used by Calderbank and Goethals 3) for the case when d ~ 2s 1. We also find a large class of examples satisfying our new condition in the binary case. The paper is organized as follows. In sec. 2, we examine the conditions for a three-weight projective code to yield a 3-class association scheme and obtain Philips Journalof Research Vol. 39 Nos 4/5 1984 143 144 Philips Journalof Research Vol.39 Nos 4/5 1984 A. R. Calderbank and J.-M. Goethals in theorem 2.2 a new sufficient condition. In sec. 3, we obtain a large class of examples by showing that all three-weight cyclic subcodes of the shortened second-order Reed-Muller codes satisfy our new condition. Finally, in sec. 4, we analyze in more detail the parameters of the association schemes thus obtained. Our study of three-weight cyclic codes was motivated by the fact that these codes provide periodic sequences with good crosscorrelation properties, as it was shown by Sarwate and Pursley "). 2. Three-weight projective codes and association schemes Let C be a three-weight projective code of length n and dimension k over the finite field GF(q). Thus we assume: (i) only three distinct nonzero distances occur among codewordsof C; (ii) the dual code C.L has minimum distance at least equal to 3. The distribution matrix of C.L has as its set of rows the weight distributions of all of the cosets of C.L. Delsarte ') (cf. theorem 6.10, p. 91) proved that the distance relations in an s-weight linear code C define an association scheme A with s classes on C if and only if the distribution matrix of the dual code C.L contains s + 1 distinct rows. In this case the set of cosets of C.L can be partitioned into s + 1 disjoint subsets, each characterized by a given weight distribution, which we denote by So = (c.LJ, SI, S2, ... , Ss. The s + 1 relations Ro,RI, ... ,Rs, defined by (C.L + x, C.L +Y) E R, iff C.L + (x + Y) E Si, then yield an s-class association scheme B which is dual to A (cf. Delsarte '), Goethals 5), and Calderbank and Goethals 3». It is our purpose to study the classes of three-weight projective codes which yield a pair of dual association schemes as above. From the abovementioned result of Delsarte, it is sufficient to examine which of these codes have the property that among the cosets of their duals only four distinct weight distributions occur. Since only three weights occur in C, the covering radius of C.L is at most equal to 3 (cf. Delsarte+j), Thus the minimum weight of any coset of C.L can only be one of the following values: 0, 1, 2 or 3. If we assume that all four values, and only four distinct weight distributions, occur among the cosets of C.L, we have to conclude that the weight distribution of any coset is uniquely deterrnined by its minimum weight. Although it is in principle possible to think of other possibilities, we shall restrict our attention to this case. We knowalready from a result of Delsarte 6) (cf. MacWilliams and Sloane 7), theorem 20, p. 169) that the weight distribution Ao(x), AI(x), ... , An(x) of (1) Three-weight codes and association schemes any coset C.L+ x is uniquely determined by the first three values Ao(x), AI(x) and A2(x), where A;(x) denotes the number of codewords of C.L at distance i from x. To be more precise we restate here Delsarte's result in the form of a lemma adapted to our case. Lemma 2.1 (Delsarte) Let the Krawtchouk expansion *) of the polynomial be given by 3 F(z) = I (l;K;(z), ;=0 where W1, W2, W3 are the three weights occurring in C. Moreover, for k = 1,2, ... , n 3, let the Krawtchouk expansion of Zk F(z) be given by _ k+3 z" F(z) = I IJ;K;(z). ;=0 Then, for any coset C.L+ x, the coefficientsA;(x) of its weight enumerator are related by 3 L (l;A;(x) = 1, ;=0 (2) k+3 LIJ; A;(x) = 0. ;=0 (3) The relations (2) and (3), clearly show how all coefficients of the weight enumerator can be obtained from the first three. Let us now examine what the possibilities are for Ao(x), AI(x) and A2(x). We first observe that: (i) for C.Litself, we have Ao = 1, Al = A2 = 0, since the minimum distance is at least 3. (ii) for any coset of minimum weight equal to 3, we have Ao = Al = A2 = 0. Note that, in this case, we must have, from (2), (l3A3 = 1. In both cases the weight distribution is uniquely determined. For each of the remaining cosets C.L+x, let us assume that there exist integers À. 1, À.2 such that the number of codewords from C.L at distance 2 from x is given by À. 1, respectively À.2, if the minimum weight of C.L+x is 1, respectively 2. This *) For a definition of the Krawtchouk expansion, we refer, for example, to MacWilliams and Sloane 7), p. 168. Philips Journalof Research Vol. 39 Nos 4/5 1984 145 A. R. Calderbank and J.-M. Goethals means that for the weight distribution of C.L+ x, we have either

THREE-WEIGHT CODES AND ASSOCIATION SCHEMES

文献摘要

被引文献

相似文献