关于A(n,d,w)的一个注记

A Note on A(n,d,w)

摘要: 编码理论中的一个基本问题是求A(n,d,w)的值，即最小Hamming距离为d的最大n长二元常重码集的大小。而A(n,d,w)又可看作是n维超立方体d-1次幂图中所有重量为w的点导出子图的最大独立集。故为探索的最大独立集，本文首次给出了图的定义，对其一些基本性质进行了研究并得到如下主要结果：是-正则图；是点传递图；对于2≤d≤3，若w≥[n/2]，则；若w<[n/2]，则；当3≤d≤4时，有 或。

Abstract: A basic problem in coding theory is to find the value of A(n,d,w), that is the size of the maximum n-length binary constant weight code with the minimum Hamming distance d. However, it can be regarded as the size of the maximum independent set of which is a subgraph of d-1^th power of n-dimensional hypercube induced by all vertices with constant weight w. To explore the maximum independent set of , this paper gives the definition of for the first time. Furthermore, some basic properties of the graph are studied and the main results are obtained as follows: is -regular. is vertex transitive. For 2≤d≤3, if w≥[n/2], then ; if , then . For 3≤d≤4, or .

1. 引言

在编码理论中，常重码是一种带有检错和纠错能力的重要编码，被广泛地应用于光导纤维中的码分多址系统、雷达和声纳的信号设计、高数据率数字通信等领域。由于其广泛的应用背景，常重码吸引了相当多的学者参与其讨论研究。数学家们尝试用代数、图论以及组合等方法来研究满足一定条件的最大常重码的个数及其结构，并取得了很大的进展。

n维二元向量空间 $Z_2^n=Z_2\times Z_2\times \cdots \times Z_2$，可以将 $Z_2^n$ 中的每个n维二元向量看作是一个n长二元码字，码字构成的集合称为码集。码字x中非零码元的个数为码字x的Hamming重量，简称码重，记为 $wt\left(x\right)$。1950年，Hamming [1] [2] 定义两个码字 $x,y$ 间的Hamming距离为其不同码元的位数，记为 $d_H\left(x,y\right)$，即 $d_H\left(x,y\right)={\displaystyle {\sum }_{i=1}^n\left|x_i-y_i\right|}$， $i\in \left[1,n\right]$。

如文献 [2] 中所述， $A\left(n,d,w\right)$ 为最小Hamming距离为d、码重为w的最大n长二元常重码集的大小，即 $A\left(n,d,w\right)=\max \left\{\left|M\right|:M是n长二元码集,且任取x,y\in M,有wt\left(x\right)=w,d_H\left(x,y\right)\ge d\right\}$。

由于二元常重码广泛的应用背景，许多学者对二元常重码进行了深入的研究，研究的主题主要集中在确定 $A\left(n,d,w\right)$ 的值。二十世纪六十年代，Johnson在 [3] [4] [5] 中给出了关于 $A\left(n,d,w\right)$ 的一些比较经典的性质： $A\left(n,d,w\right)\le \left[\frac{dn}{dn-2w\left(n-w\right)}\right]$ ； $A\left(n,d,w\right)\le \left[\frac{n}{w}A\left(n-1,d,w-1\right)\right]\left(n\ge w\ge 1\right)$ ； $A\left(n,d,w\right)\le \left[\frac{n}{n-w}A\left(n-1,d,w\right)\right]\left(n>w\ge 0\right)$ ； $A\left(n,d,w\right)=1\left(d>2w\right)$ ； $A\left(n,d,w\right)=\left[\frac{n}{w}\right]\left(d=2w\right)$ ；若d为

奇数，则 $A\left(n,d,w\right)=A\left(n,d+1,w\right)$ 等。1977年，MacWilliams和Sloane在 [2] 中系统给出了 $n\le 24$， $d\le 10$ 时 $A\left(n,d,w\right)$ 的上下界。随后，Best等人 [6]、Graham [7] 及Sloane [8] 继续对这些关于 $A\left(n,d,w\right)$ 的上下界进行研究改进。直到1990年，Brouwer等人 [9] 给出了 $n\le 28$， $d\le 18$ 时 $A\left(n,d,w\right)$ 的最优下界。2000年，Vardy等人 [10] 将 $A\left(n,d,w\right)$ 的上下界扩大到了 $n\le 28$， $d\le 14$ 的范围，对已知的 $n\le 24$， $d\le 12$ 时

$A\left(n,d,w\right)$ 的上界做出了极大的改进，并证明了若d为偶数，则 $A\left(n,d,w\right)\le \frac{\left(\begin{array}{c}n\\ w-1\end{array}\right)}{w}$。此后，学者们继续利用半正定规划、Terwilliger代数等方法对 $A\left(n,d,w\right)$ 的上下界进行讨论，但大多都是对d取6，8，10，12时 $A\left(n,d,w\right)$ 的上下界有了一定的改进 [11] [12] [13]。

总的来看，不少研究都致力于求 $A\left(n,d,w\right)$ 确切的值，但是迄今为止还没有统一的方法研究 $A\left(n,d,w\right)$ 的值。本文提出从图论的角度去研究 $A\left(n,d,w\right)$，并非常简洁地给出了 $3\le d\le 4$ 时的一个上界。

本文定义图 $Q_n^{\left(d,w\right)}$ 为n维超立方体d次幂图中所有重量为w的点导出的子图，即 $V\left(Q_n^{\left(d,w\right)}\right)=\left\{u\in Q_n^d:{\displaystyle {\sum }_{i=1}^n{u}_i}=w\right\}$。由上述定义可知 $A\left(n,d,w\right)$ 对应于图 $Q_n^{\left(d-1,w\right)}$ 的最大独立集的大小，即 $A\left(n,d,w\right)=\alpha \left(Q_n^{\left(d-1,w\right)}\right)$。为探索 $Q_n^{\left(d,w\right)}$ 的最大独立集，本文对其基本性质进行了研究并得到如下一些结果： $Q_n^{\left(d,w\right)}$ 是 ${\displaystyle {\sum }_{i=1}^{\lfloor d/2\rfloor }\left(\begin{array}{c}w\\ w-i\end{array}\right)\left(\begin{array}{c}n-w\\ i\end{array}\right)}$ -正则图； $Q_n^{\left(d,w\right)}$ 是点传递图；对于 $2\le d\le 3$，若 $w\ge \lceil n/2\rceil$，则 $\omega \left(Q_n^{\left(d,w\right)}\right)=w+1$ ；若 $w<\lceil n/2\rceil$，则 $\omega \left(Q_n^{\left(d,w\right)}\right)=w+1$ ；对于 $3\le d\le 4$，若 $w\ge \lceil n/2\rceil$，则有 $A\left(n,d,w\right)=\alpha \left(Q_n^{\left(d-1,w\right)}\right)\le \frac{\left(\begin{array}{c}n\\ w\end{array}\right)}{w+1}$，若 $w<\lceil n/2\rceil$，则 $A\left(n,d,w\right)\le \frac{\left(\begin{array}{c}n\\ w\end{array}\right)}{n-w+1}$。与2000年Vardy等人 [10] 得到的 $3\le d\le 4$ 时 $A\left(n,d,w\right)$ 的上界 $\frac{\left(\begin{array}{c}n\\ w-1\end{array}\right)}{w}$ 相比，当 $w<\lceil n/2\rceil$ 时，本文得到的 $A\left(n,d,w\right)$ 的上界 $\frac{\left(\begin{array}{c}n\\ w\end{array}\right)}{n-w+1}=\frac{\left(\begin{array}{c}n\\ w-1\end{array}\right)}{w}$ ；当 $w\ge \lceil n/2\rceil$ 时，本文得到的 $A\left(n,d,w\right)$ 的上界 $\frac{\left(\begin{array}{c}n\\ w\end{array}\right)}{w+1}<\frac{\left(\begin{array}{c}n\\ w-1\end{array}\right)}{w}$。

2. 预备知识

本节给出了本文需要的一些基本概念和符号。

令 $G=\left(V\left(G\right),E\left(G\right)\right)$ 为简单无向图，其中 $V\left(G\right)$ 是图G的顶点集， $E\left(G\right)$ 是图G的边集。任取 $v\in V\left(G\right)$，G中与点v关联的边的数目称为点v的度，记为 $d_G\left(v\right)$。若图G中所有点的度都为k，则称图G是k-正则的。令M是 $V\left(G\right)$ 的一个子集，若M中任意两个顶点在图G中均不相邻，则称M为图G的独立集。若图G中不包含满足 $\left|M^{*}\right|>\left|M\right|$ 的独立集 $M^{*}$，则称M为图G的最大独立集。图G的最大独立集的顶点数称为图G的独立数，记为 $\alpha \left(G\right)$。反之，若M中任意两个顶点在图G中均相邻，则称M为图G的团。若图G中不包含满足 $\left|M^{*}\right|>\left|M\right|$ 的团 $M^{*}$，则称M为图G的最大团，最大团的顶点数称为图G的团数，记为 $\omega \left(G\right)$。

定义2.1：图 $Q_n$ 表示n维超立方体图，其顶点集 $V\left(Q_n\right)=\left\{x|x\in Z_2^n\right\}$，且对于任意的 $x,y\in V\left(Q_n\right)$，有边 $x~y$ 当且仅当 $d_H\left(x,y\right)=1$。

定义2.2：图 $Q_n^d$ 表示n维超立方体 $Q_n$ 的d次幂图，其顶点集 $V\left(Q_n^d\right)=\left\{x|x\in Z_2^n\right\}$，且对于任意的 $x,y\in V\left(Q_n^d\right)$，有边 $x~y$ 当且仅当 $d_H\left(x,y\right)\le d$。

定义2.3： $G=\left(V\left(G\right),E\left(G\right)\right)$ 是一个图， $\phi$ 是从 $V\left(G\right)$ 到其自身的一个双射。任取 $x,y\in V\left(G\right)$，若 $x~y$ 当且仅当 $\phi \left(x\right)~\phi \left(y\right)$，则称 $\phi$ 是图G的一个自同构。图G的所有自同构构成一个群，称为图G的自同构群，记为 $\text{Aut}\left(G\right)$。

定义2.4：给出两个n长二元码字 $x=\left(x_1,x_2,\cdots ,x_n\right)$， $y=\left(y_1,y_2,\cdots ,y_n\right)$，定义 $x\cap y=\left\{i|x_i=y_i=1,1\le i\le n\right\}$。

定义2.5： $G=\left(V\left(G\right),E\left(G\right)\right)$ 为简单无向图，若对于任意的 $x,y\in G$，存在 $\phi \in \text{Aut}\left(G\right)$ 满足 $\phi \left(x\right)=y$，则称图G为点传递图。

定理2.6 ( [14], Lemma 7.2.2)：若图 $G=\left(V\left(G\right),E\left(G\right)\right)$ 为点传递图，则有 $\alpha \left(G\right)\omega \left(G\right)\le \left|V\left(G\right)\right|$。

3. $Q_n^{\left(d,w\right)}$ 的基本性质

由定义可得 $A\left(n,d,w\right)=\alpha \left(Q_n^{\left(d-1,w\right)}\right)$，即n维超立方体 $d-1$ 次幂图中由所有重量为w的点导出子图的独立数等于给定最小Hamming距离为d，重量为w的最大n长二元常重码集的大小。现令 $u_0=\left(0,0,\cdots ,0\right)$， $D_i=\left\{u\in V\left(Q_n^d\right)|d_H\left(u,u_0\right)\le i\right\}\left(0\le i\le n\right)$。为便于观察，给出如下对 $Q_n^d$ 的距离划分(见图1)，则 $Q_n^{\left(d,w\right)}$ 就是由 $D_w$ 导出的子图。在此基础上，本节对 $Q_n^{\left(d,w\right)}$ 进行了研究，并得到了它的一些基本性质。

Figure 1. The distance division graph of $Q_n^d$

图1. $Q_n^d$ 的距离划分图

定理3.1： $Q_n^{\left(d,w\right)}$ 是k-正则图，其中 $k={\displaystyle {\sum }_{i=1}^{\lfloor d/2\rfloor }\left(\begin{array}{c}w\\ w-i\end{array}\right)\left(\begin{array}{c}n-w\\ i\end{array}\right)}$。

证明：对于任意的 $x,y\in V\left(Q_n^{\left(d,w\right)}\right)$，设 $\left|x\cap y\right|=t$，则 $d_H\left(x,y\right)=2\left(w-t\right)$。x与y相邻当且仅当 $d_H\left(x,y\right)=2\left(w-t\right)\le d$，即 $t\ge w-\lfloor d/2\rfloor$。因此，对于 $Q_n^{\left(d,w\right)}$ 中的任意一点x有 $d\left(x\right)=\left(\begin{array}{c}w\\ w-1\end{array}\right)\left(\begin{array}{c}n-w\\ 1\end{array}\right)+\left(\begin{array}{c}w\\ w-2\end{array}\right)\left(\begin{array}{c}n-w\\ 2\end{array}\right)+\cdots +\left(\begin{array}{c}w\\ w-\frac{d}{2}\end{array}\right)\left(\begin{array}{c}n-w\\ \frac{d}{2}\end{array}\right)={\displaystyle {\sum }_{i=1}^{\lfloor d/2\rfloor }\left(\begin{array}{c}w\\ w-i\end{array}\right)\left(\begin{array}{c}n-w\\ i\end{array}\right)}$，即 $Q_n^{\left(d,w\right)}$ 是 $Q_n^{\left(d,w\right)}$ -正则图。

定理3.2： $Q_n^{\left(d,w\right)}$ 是点传递图。

证明：根据定义2.5，要证明 $Q_n^{\left(d,w\right)}$ 是点传递图，我们只需证明对于任意的 $x,y\in V\left(Q_n^{\left(d,w\right)}\right)$，存在 $\phi \in \text{Aut}\left(Q_n^{\left(d,w\right)}\right)$ 满足 $\phi \left(x\right)=y$ 即可。不妨设 $x=\left(x_1,x_2,\cdots ,x_n\right)$， $y=\left(y_1,y_2,\cdots ,y_n\right)$，其中

$x_1=x_2=\cdots =x_k=x_{k+1}=\cdots =x_w=1$， $x_{w+1}=\cdots =x_n=0$，

$y_1=y_2=\cdots =y_k=1$， $y_{k+1}=\cdots =y_w=0$， $y_{w+1}=\cdots =y_{2w-k}=1$， $y_{2w-k+1}=\cdots =y_n=0$。

现假设 $f\in S_n$，即f是集合 $\left\{1,2,\cdots ,n\right\}$ 上的一个置换，且

$f=\left(\begin{array}{ccc}1& 2& \cdots \\ 1& 2& \cdots \end{array}\begin{array}{ccc}k& k+1& k+2\\ k& w+1& w+2\end{array}\begin{array}{ccc}\cdots & w& w+1\\ \cdots & 2w-k& k+1\end{array}\begin{array}{ccc}\cdots & 2w-k& 2w-k+1\\ \cdots & w& 2w-k+1\end{array}\begin{array}{cc}\cdots & n\\ \cdots & n\end{array}\right)$。

对于任意的 $u=\left(u_1,u_2,\cdots ,u_n\right)\in V\left(Q_n^{\left(d,w\right)}\right)$，令 $\phi \left(u_1,u_2,\cdots ,u_n\right)=\left(u_{f\left(1\right)},u_{f\left(2\right)},\cdots ,u_{f\left(n\right)}\right)$。显然， $\phi$ 是点集 $V\left(Q_n^{\left(d,w\right)}\right)$ 到其本身的一个映射，且 $\phi \left(x\right)=y$。下面只需要证明 $\phi \in \text{Aut}\left(Q_n^{\left(d,w\right)}\right)$。

1) $\phi$ 为双射。

$\phi$ 为单射：任取 $u,v\in V\left(Q_n^{\left(d,w\right)}\right)$，若 $u\ne v$，则一定存在 $i\in \left\{1,2,\cdots ,n\right\}$ 有 $u_i\ne v_i$。而对于 $i\in \left\{1,2,\cdots ,n\right\}$ 存在 $j\in \left\{1,2,\cdots ,n\right\}$ 使得 $f\left(j\right)=i$，故 $u_{f\left(j\right)}\ne v_{f\left(j\right)}$，即 $\phi \left(u\right)\ne \phi \left(v\right)$，故 $\phi$ 为单射。

$\phi$ 为满射：对于任意的 $u=\left(u_1,u_2,\cdots ,u_n\right)\in V\left(Q_n^{\left(d,w\right)}\right)$，存在 $v=\left(v_1,v_2,\cdots ,v_n\right)\in V\left(Q_n^{\left(d,w\right)}\right)$，其中

$v_i=u_i$ ( $1\le i\le k$ 或 $2w-k+1\le i\le n$ )，

$v_{k+j}=u_{w+j}\left(1\le j\le w-k\right)$，

$v_{w+j}=u_{k+j}\left(1\le j\le w-k\right)$，

使得 $\phi \left(v\right)=u$，故 $\phi$ 为满射。

2) 对于任意的 $u,v\in V\left(Q_n^{\left(d,w\right)}\right)$， $u~v$ 当且仅当 $\phi \left(u\right)~\phi \left(v\right)$。

由 $\phi$ 和f定义可知， $d_H\left(\phi \left(u\right),\phi \left(v\right)\right)={\displaystyle {\sum }_{i=1}^n\left|u_{f\left(i\right)}-v_{f\left(i\right)}\right|}={\displaystyle {\sum }_{i=1}^n\left|u_i-v_i\right|}=d_H\left(u,v\right)$，故 $u~v$ 当且仅当 $\phi \left(u\right)~\phi \left(v\right)$。

综上， $\phi \in \text{Aut}\left(Q_n^{\left(d,w\right)}\right)$，故 $Q_n^{\left(d,w\right)}$ 是点传递图。

定理3.3：当 $2\le d\le 3$ 时， $Q_n^{\left(d,w\right)}$ 的团数

$\omega \left(Q_n^{\left(d,w\right)}\right)=\{\begin{array}{l}w+1\left(w\ge \lceil n/2\rceil \right)\\ n-w+1\left(w<\lceil n/2\rceil \right)\end{array}$。

证明：令点 $u^0=\left(u_1^0,u_2^0,\cdots ,u_n^0\right)\in V\left(Q_n^{\left(d,w\right)}\right)$，其中 $u_1^0=u_2^0=\cdots =u_w^0=1$， $u_{w+1}^0=\cdots =u_n^0=0$。为了便于观察，我们给出如下对图 $Q_n^{\left(d,w\right)}$ 的距离划分(见图2)，其中 $D_i^w=\left\{u\in V\left(Q_n^{\left(d,w\right)}\right)|d_H\left(u,u^0\right)=i\right\}$，i为偶数，而且若 $w<\frac{n}{2}$，则 $2\le i\le 2w$，否则 $2\le i\le 2\left(n-w\right)$。

Figure 2. The distance division graph of $Q_n^{\left(d,w\right)}$

图2. $Q_n^{\left(d,w\right)}$ 的距离划分图

由 $Q_n^{\left(d,w\right)}$ 的点传递性，我们只需考虑其包含点 $u^0$ 的最大团即可得 $Q_n^{\left(d,w\right)}$ 的团数。求 $Q_n^{\left(2,w\right)}$ 与 $Q_n^{\left(3,w\right)}$ 最大团的方法完全一样，下面我们只给出 $Q_n^{\left(2,w\right)}$ 最大团的构造过程。

当 $d=2$ 时，假设T为 $Q_n^{\left(2,w\right)}$ 中包含点 $u^0$ 的团，则任取 $u\in T$， $d_H\left(u,u^0\right)=2\left(w-\left|u^0\cap u\right|\right)\le 2$，故 $\left(T-\left\{u^0\right\}\right)\subseteq D_2^w$。令 $D_2^{\left(w,i\right)}=\left\{u\in D_2^w|u_i=0\right\}\left(1\le i\le w\right)$， $I=\left\{i:\left(T-\left\{u^0\right\}\right)\cap D_2^{\left(w,i\right)}\ne \varnothing \right\}$。

1) 若 $\left|I\right|\ge 2$，则为满足 $\forall u,v\in T$， $d_H\left(u,v\right)\le 2$，任取 $i\in I$， $\left|\left(T-\left\{u^0\right\}\right)\cap D_2^{\left(w,i\right)}\right|=1$。此时，T最大可取为 $T={\displaystyle {\cup }_{i=1}^w{D}_2^{\left(w,i,j\right)}}\left(j\in \left[w+1,n\right]\right)$，其中 $D_2^{\left(w,i,j\right)}=\left\{u\in D_2^{\left(w,i\right)}|u_j=1\right\}\left(j\in \left[w+1,n\right]\right)$，而且 $\left|T\right|=w+1$。

2) 若 $\left|I\right|\le 1$，由于对于任意的 $u,v\in D_2^{\left(w,i\right)}$， $d_H\left(u,v\right)=2$，故此时T最大可取为 $T=\left\{u^0\right\}\cup D_2^{\left(w,i\right)}\left(i\in \left[1,w\right]\right)$，而且 $\left|T\right|=n-w+1$。

综上， $\omega \left(Q_n^{\left(2,w\right)}\right)=\{\begin{array}{l}w+1\left(w\ge \lceil n/2\rceil \right)\\ n-w+1\left(w<\lceil n/2\rceil \right)\end{array}$。

推论3.4：当 $2\le d\le 3$ 时， $Q_n^{\left(d,w\right)}$ 的独立数 $\alpha \left(Q_n^{\left(d,w\right)}\right)\le \{\begin{array}{l}\frac{\left(\begin{array}{c}n\\ w\end{array}\right)}{w+1}\left(w\ge \lceil n/2\rceil \right)\\ \frac{\left(\begin{array}{c}n\\ w\end{array}\right)}{n-w+1}\left(w<\lceil n/2\rceil \right)\end{array}$，即当 $3\le d\le 4$ 时， $A\left(n,d,w\right)\le \{\begin{array}{l}\frac{\left(\begin{array}{c}n\\ w\end{array}\right)}{w+1}\left(w\ge \lceil n/2\rceil \right)\\ \frac{\left(\begin{array}{c}n\\ w\end{array}\right)}{n-w+1}\left(w<\lceil n/2\rceil \right)\end{array}$。

证明：结合定理2.6，定理3.2及定理3.3很容易得证。

4. 结语

本文将 $A\left(n,d,w\right)$ 看作是n维超立方体 $d-1$ 次幂图中由所有重量为w的点导出子图 $Q_n^{\left(d,w\right)}$ 的最大独立集的大小，通过对 $Q_n^{\left(d,w\right)}$ 结构特点的分析讨论，我们得到了一些 $Q_n^{\left(d,w\right)}$ 的基本性质及 $A\left(n,d,w\right)$ 的一个上界： $Q_n^{\left(d,w\right)}$ 是 ${\displaystyle {\sum }_{i=1}^{\lfloor d/2\rfloor }\left(\begin{array}{c}w\\ w-i\end{array}\right)\left(\begin{array}{c}n-w\\ i\end{array}\right)}$ -正则图； $Q_n^{\left(d,w\right)}$ 是点传递图；对于 $2\le d\le 3$，若 $w\ge \lceil n/2\rceil$，则 $\omega \left(Q_n^{\left(d,w\right)}\right)=w+1$ ；若 $w<\lceil n/2\rceil$，则 $\omega \left(Q_n^{\left(d,w\right)}\right)=w+1$ ；对于 $3\le d\le 4$，有 $A\left(n,d,w\right)=\alpha \left(Q_n^{\left(d-1,w\right)}\right)\le \frac{\left(\begin{array}{c}n\\ w\end{array}\right)}{w+1}$ 或 $\frac{\left(\begin{array}{c}n\\ w\end{array}\right)}{n-w+1}$。

本文我们只是对几个特殊的 $n,d,w$ 的值讨论了 $Q_n^{\left(d,w\right)}$ 的结构特点、性质特征及对应的 $A\left(n,d,w\right)$ 的上界。对于一般的 $A\left(n,d,w\right)$ 的值，后续我们考虑可以从下面几个方面进行研究：

1) 对于一般的 $n,d,w$ 的值 $Q_n^{\left(d,w\right)}$ 的最大团及分布特点是怎么样的？其最大独立集是怎么样的？从而我们可以得到 $A\left(n,d,w\right)$ 的一般的上界，甚至其确切的值。

2) $Q_n^{\left(d,w\right)}$ 的色数 $\chi \left(Q_n^{\left(d,w\right)}\right)$ 等于什么？因为图的独立数大于等于点数与色数的比值，从而我们可以得到 $A\left(n,d,w\right)$ 的一个下界。

基金项目

国家自然科学基金资助项目(11671296)。