F_p上一类MDS符号对码的构造

The Construction of a Class of MDS Symbol-Pair Codes over F_p

摘要: 符号对码是一类可以很好地处理在数据读取过程中出现对错误的情况的编码方法。符号对距离是衡量符号对码在符号对读取信道中的纠错能力的一个重要参数指标。在符号对码的长度和维数一定的情况下，MDS符号对码是符号对距离最大的一类最佳符号对码。符号对码的研究的主要内容之一是构造MDS符号对码，特别是构造出符号对距离较大的MDS符号对码。本文分析了重根循环码的符号对距离的刻画方法，并且利用重根循环码构造出参数不同于已知构造且符号对距离较大的一类MDS符号对码。

Abstract: Symbol-pair codes are designed to protect against pair error in data reading. The pair-distance is an important parameter to measure the error correction ability of the symbol pair in the symbol pair reading channel. MDS symbol pair codes are the best symbol pair codes with the largest symbol pair distance when the length and dimension of the symbol pair codes are constant. One of the important problems of symbol-pair codes is to construct MDS symbol-pair codes with a large code length and a large minimum pair-distance. In this paper, we analyze the method of characterizing pair-distance by repeated-root cyclic codes and construct a new class of MDS symbol-pair codes with different parameters and larger symbol pair-distance.

1. 研究背景

随着高密度数据存储技术的发展，人们能够使用高分辨率的存储技术对数据进行快速的存储和读取。然而通常由于物理条件的限制，在数据的读取过程中并不总能使用高分辨率的读取设备来读取由高分辨率的写入设备所存储的数据。这种用较低的分辨率的读取头来读取通过高分辨率写入储存介质的信息的过程中，信息读取结果可能不会如一般情形一样得到单个符号，而是得到一个符号对，我们把这种信道称为符号对读取信道。具体而言，设 $\Sigma$ 表示一个字符串的集合， $\left(x_0,x_1,\cdots ,x_{n-1}\right)$ 为待传输的码字，在符号对读取信道中该信息被读取为 $\left(\left(x_0,x_1\right),\left(x_1,x_2\right),\cdots ,\left(x_{n-1},x_1\right)\right)$。然而，由于外界干扰等因素的影响，码字在传输的过程中可能会发生错误，使得读取出的码字的符号对中有一个和多个符号对出现错误。一个符号对错误是指在一个符号对中存在一个或两个符号的读取错误。针对这种情况，Cassuta和Blaum [1] [2] 提出了符号对码来刻画在符号对读取信道中出现符号对错误的情况下如何设计好的码。

设C是 $F_q^n$ 上长度为n、含有M个向量、符号对距离是 $d_P$ 的符号对码，记为 ${\left(n,M,d_P\right)}_q$ 符号对码。与经典纠错码类似，符号对距离可以反映符号对码的对错误的纠错能力，当符号对距离为 $d_P$ 时，这个符号对码至多可以纠正 $\lfloor \left(d_P-1\right)/2\rfloor$ 个符号对错误 [2]。为了得到具有较强纠错能力的符号对码，研究人员期望构造出符号对距离较大的符号对码。另外，如何构造出码字较多的码也是编码理论的一个重要问题。如果 $2\le d_P\left(C\right)\le n$，那么 $M\le q^{n-d_P+2}$，该上界被称为Singleton-type界 [3]。如果 $M=q^{n-d_P+2}$，那么称C为最大距离可分(MDS)符号对码，记为 ${\left(n,d_P\right)}_q$ MDS符号对码。

针对如何构造符号对距离较大的MDS符号对码的问题，2015年，Kai [4] 等人利用常循环码性质构造了一系列符号对距离为5和6的MDS符号对码。2016年，Chen [5] 等人通过重根循环码构造了符号对距离为7和8的MDS符号对码。2018年，文献 [6] 进一步利用重根循环码给出了3类新的符号对距离为6和7的MDS符号对码。

本文首先分析了符号对码的相关性质，刻画了重根循环码的符号对距离，并构造出符号对距离为7的新参数的MDS符号对码。利用Magma软件，给出了若干MDS符号对码的实例并给出了具体参数，列举出决定符号对距离的码字。这些实例显示了符号对距离的码字的一些特征，将为进一步研究重根循环码的符号对距离提供参考。

2. 预备知识

设 $x=\left(x_0,x_1,\cdots ,x_{n-1}\right)\in {\Sigma }^n$，那么x对应的符号对向量为

$\pi \left(x\right)=\left[\left(x_0,x_1\right),\left(x_1,x_2\right),\cdots ,\left(x_{n-1},x_0\right)\right]$, (1.1)

$\pi \left(x\right)$ 的每一个分量 $\left(x_i,x_{i+1}\right)$ 被称为一个符号对，显然 $\pi \left(x\right)$ 由x唯一确定。对 $\forall \left(a,b\right),\left(c,d\right)\in \Sigma \times \Sigma$，有 $\left(a,b\right)=\left(c,d\right)$ 当且仅当 $a=b$， $c=d$。设 $x=\left(x_0,x_1,\cdots ,x_{n-1}\right)$， $y=\left(y_0,y_1,\cdots ,y_{n-1}\right)\in {\Sigma }^n$，定义

$d_P\left(x,y\right)=d_H\left(\pi \left(x\right),\pi \left(y\right)\right)$ (1.2)

作为x，y的符号对距离，这里 $d_H\left(\pi \left(x\right),\pi \left(y\right)\right)$ 表示 $\pi \left(x\right)$ 和 $\pi \left(y\right)$ 的Hamming距离。关于向量 $x=\left(x_0,x_1,\cdots ,x_{n-1}\right)$，定义x的符号对重量为

$d_P\left(x\right)=\left|\left\{x_i\ne 0|x_i\in x\right\}\right|$, (1.3)

如果定义

$gap\left(x\right)=\left|\left\{0\le i\le n-1|x_i\in F_q^{*},x_{i+1}=0\right\}\right|$, (1.4)

那么可以得到x的Hamming距离和符号对距离具有关系式：

$d_P\left(x\right)=w{t}_H\left(x\right)+gap\left(x\right)$. (1.5)

关于 $C\in {\Sigma }^n$ 的符号对距离，定义如下，

$d_P\left(C\right)=\min \left\{d_P\left(x,y\right):\forall x,y\in C,x\ne y\right\}$.(1.6)

定理1 [7] ：对任意 $C\in {\Sigma }^n$，如果 $1\le d_H\left(C\right)\le n-1$，那么 $d_H+1\le d_P\left(C\right)\le 2d_H$。

线性码 $C\in F_q^n$ 是一个 $\lambda$ -循环码，当且仅当C是环 $F_q\left[x\right]/\left(x^n-\lambda \right)\left(\lambda \in F_q\right)$ 的一个理想。如果 $ord\left(\lambda \right)=r$， $or{d}_{rn}\left(q\right)=t$，那么 $\exists \delta \in F_{q^t}$ s.t. ${\delta }^n=\lambda$。根据 $x^n-\lambda$ 的根组成集合 $\left\{{\delta }^{1+rj}|0\le j\le n-1\right\}$，定

义集合

$\Omega =\left\{1+rj|0\le j\le n-1\right\}$,(1.7)

如果对于 $\forall s\in \Omega$，定义

$C_S=\left\{s,sq,s{q}^2,\cdots \right\}\left(\mathrm{mod}nr\right)$,(1.8)

那么所有的集合 $C_s$ 组成 $\Omega$ 的一个分割。取 ${\Omega }^{*}$ 为所有分割的代表元素组成的集合，则C的生成多项式 $g\left(x\right)$ 可以表示为

$g\left(x\right)={\displaystyle \underset{s\in A}{\prod }{\displaystyle \underset{i\in C_s}{\prod }\left(x-{\delta }^i\right)}}$, (1.9)

其中， $A\subset {\Omega }^{*}$。

如果 $\left(n,p\right)\ne 1$，那么C为重根循环码。设 $F_q^n$ 上的重根 $\lambda$ -循环码C，其中 $\lambda \in F_q$， $n=l{p}^s\left(s\ge 1\right)$， $l\ge 1$ 且 $\left(p,l\right)=1$， $\exists g\left(x\right)$ s.t. $C=\langle g\left(x\right)\rangle$。设 $g\left(x\right)$ 在 $F_q$ 的完全因式分解为

$g\left(x\right)={\displaystyle \underset{i=1}{\overset{k}{\prod }}{m}_i{\left(x\right)}^{e_i}}$,(1.10)

其中， $\left(m_i\left(x\right),m_j\left(x\right)\right)=1\left(i\ne j\right)$ 且 $e_i\le p^s\left(i=1,2,\cdots ,k\right)$。定义

$D_t=\langle g_t\left(x\right)\rangle$,(1.11)

其中， $g_t\left(x\right)={\displaystyle \underset{e_i>t}{\prod }{m}_i\left(x\right)}$，那么 $\exists {\lambda }_0\in F_q$ s.t. ${\lambda }_0^{p^s}=\lambda$，从而 $D_t$ 是 $F_q^n$ 上的单根 ${\lambda }_0$ -循环码。规定

$d_H\left(D_t\right)=\{\begin{array}{l}\infty ,g_t\left(x\right)=x^l-{\lambda }_0\\ 1,g_t(x)=1\end{array}$, (1.12)

那么我们可以利用如下定理确定重根循环码的Hamming距离。

定理2 [2] ：设 $n=l{p}^s\left(s\ge 1\right)$ 且 $\left(l,p\right)=1$，q是素数p幂次，C是 $F_q^n$ 上的重根循环码，那么有

$d_H\left(C\right)=\min \left\{P_t\cdot d_H\left(D_t\right)|0\le t\le p^s-1\right\}$ (1.13)

其中 $P_t={\displaystyle {\prod }_{i=0}^{m-1}\left(t_i+1\right)}$， $\left[t_{m-1},\cdots ,t_1,t_0\right]$ 是t的p进制表示。

如果C满足一定的条件我们可以得到关于C的Hamming距离和符号对距离的相关性质，具体如下：

定理3 [5] ：设C是 $F_q$ 上的 $\left(n,k,d_H\right)\left(2\le d_H<n\right)$ 常循环码。如果C中存在一个长度为 $d_H+s$ 的码字，且该码字是连续的，那么有 $n-d_H\le k+s-1$。

定理4 [5] ：设C是 $F_q^n$ 上的 $\left(n,k,d_H\right)$ 常循环码且 $2\le d_H\le n$。那么 $d_P\left(C\right)\ge d_H+2$ 当且仅当C不是MDS码。

3. F_p上长为2p的MDS符号对码

定理5：设p是素数且 $p\ge 5$，那么存在 ${\left(\text{2}p,7\right)}_p$ MDS符号对码。

证明：设 $C=\langle g\left(x\right)\rangle$， $g\left(x\right)={\left(x-1\right)}^3{\left(x+1\right)}^{\text{2}}\in F_5\left[x\right]$，那么C形成 $GR=\frac{F_p\left[x\right]}{\langle x^{2p}-1\rangle }$ 的理想。由定理2可得： $d_H=4$，此时C不是MDS码，因此 $d_P\left(C\right)\ge d_H+2$，下面分析 $d_P\left(C\right)=d_H+2$ 是否成立。如果 $d_P=d_H+2$，意味着 $\exists c\in C$ s.t. $d_P\left(c\right)=d_H+2$，具体而言存在两种情况：

Case1: $w{t}_H\left(c\right)=\text{5}$， $gap\left(c\right)=1$

由于 $lp-d_H>k$，由定理3可知不存在这样的码字c；

Case2: $w{t}_H\left(c\right)=\text{4}$， $gap\left(c\right)=2$

(i) $c\left(x\right)=c_0+c_{1}x+c_i{x}^i+c_{i+1}{x}^{i+1},\left(3\le i\le 2p-2\right)$，其中 $c_0,c_1,c_i,c_{i+1}\in F_q^{*}$，由于 $g\left(x\right)|c\left(x\right)$，那么

$\{\begin{array}{l}{c}_0+c_1+c_i+c_{i+1}=0\\ c_1+i{c}_i+\left(i+1\right)c_{i+1}=0\\ i\left(i-1\right)c_i+\left(i+1\right)i{c}_{i+1}=0\\ c_0-c_1+{\left(-1\right)}^i{c}_i+{\left(-1\right)}^{i+1}{c}_{i+1}=0\\ c_1+i{\left(-1\right)}^{i-1}{c}_i+\left(i+1\right){\left(-1\right)}^i{c}_{i+1}=0\end{array}$ (2.1)

由方程组(2.1)中第二、五个方程可得：

$i\left[1-{\left(-1\right)}^{i-1}\right]c_i+\left(i+1\right)\left[1-{\left(-1\right)}^i\right]c_{i+1}=0$, (2.2)

当i是奇数时，由(2.2)可得：

$\left(i+1\right)c_{i+1}=0$, (2.3)

若 $i+1\ne 0$，那么 $c_{i+1}=0$，推出矛盾；

若 $i+1=0$，由(2.1)中第三个方程可得： $2c_i=0$，即 $c_i=0$，推出矛盾；

当i是偶数时，由(2.2)可得： $i{c}_i=0$，由于 $3\le i\le 2p-1$，则 $i\ne 0$，从而 $c_i=0$，推出矛盾。

(ii) $c\left(x\right)=c_0+c_{1}x+c_2{x}^2+c_i{x}^i,\left(4\le i\le 2p-1\right)$，其中 $c_0,c_1,c_2,c_i\in F_q$，由于 $g\left(x\right)|c\left(x\right)$，那么

$\{\begin{array}{l}{c}_0+c_1+c_2+c_i=0\hfill \\ c_1+2c_2+i{c}_i=0\hfill \\ 2c_2+i\left(i-1\right)c_i=0\hfill \\ c_0-c_1+c_2+{\left(-1\right)}^i{c}_i=0\hfill \\ c_1-2c_2+i{\left(-1\right)}^{i-1}{c}_i=0\hfill \end{array}$ (2.4)

如果 $i\left(i-1\right)=0$，由(2.4)中第三个方程可得： $c_2=0$，推出矛盾，下面分析 $i\left(i-1\right)\ne 0$ 的情况。

由方程组(2.4)中第一、四个方程可得：

$2c_1+\left[1-{\left(-1\right)}^i\right]c_i=0$, (2.5)

当i是偶数时，由(2.5)可得： $c_1=0$，推出矛盾；

当i是奇数时，由(2.5)可得：

$c_1+c_i=0$,(2.6)

联立(2.4)中第二个方程和(2.6)可得：

$2c_2+\left(i-1\right)c_i=0$, (2.7)

由(2.4)第三个方程和(2.7)可得： ${\left(i-1\right)}^2{c}_i=0$，即 $c_i=0$ 推出矛盾；

从而 $d_P\ge d_H+3=7$，又C满足Singleton-type界，因此 $d_P=7$，从而C是 ${\left(2p,7\right)}_p$ MDS符号对码，证毕。

下述实例根据定理5条件给出实例，并且通过C中码字的Hamming距离不同情况来确定C的符号对距离，为简化分析，我们把可以由同一个码字循环移位得到的所有码字简记为一个码字。

例1：设 $C=\langle g\left(x\right)\rangle$， $g\left(x\right)={\left(x-1\right)}^3{\left(x+1\right)}^2\in F_5\left[x\right]$，由MAGMA运行结果可知：C是 $\left(10,5,4\right)$ 纠错码。记

$C_i=\left\{c\in C:w{t}_H=i\right\}$, (2.8)

$4\le i\le 10$，C中码字按照Hamming距离分类处理如下：

1) $\left|C_4\right|=40$， $C_4$ 中的码字具有4中的形式： $\left(\text{0102030400}\right)$ 、 $\left(\text{0204010300}\right)$ 、 $\left(\text{0301040200}\right)$ 、 $\left(0\text{4}0\text{3}0\text{2}0\text{1}00\right)$，可知 $\forall c\in C_4$， $gap\left(c\right)=4$，从而 $d_P\left(c\right)=8$ ；

2) $\left|C_5\right|=8$， $C_5$ 中的码字具有4中的形式： $\left(\text{0101010101}\right)$ 、 $\left(\text{0202020202}\right)$ 、 $\left(\text{0303030303}\right)$ 、 $\left(\text{0404040404}\right)$，可知 $\forall c\in C_5$， $gap\left(c\right)=5$，从而 $d_P\left(c\right)=10$ ；

3) $\left|C_6\right|=400$， $\exists c^{\prime }=\left(2,3,1,4,2,3,0,0,0,0\right)\in C_6$ s.t. $gap\left(c^{\prime }\right)=1$，那么 $d_P\left(c^{\prime }\right)=7$，从而 $\forall c\in C_6$， $d_P\left(c\right)\ge 7$，此处的“=”能够成立；

4) 如果 $w{t}_H\left(c\right)\ge 7$，那么 $d_P\left(c\right)\ge w{t}_H\left(c\right)+gap\left(c\right)\ge 7$ ；

综上可得： $d_P\left(C\right)=7$，此时C是 ${\left(10,7\right)}_5$ MDS符号对码。

例2：设 $C=\langle g\left(x\right)\rangle$，其中 $g\left(x\right)={\left(x-1\right)}^3{\left(x+1\right)}^2\in F_7\left[x\right]$，分析 MAGMA结果可得：C是 $\left(14,9,4\right)$ 纠错码，按照Hamming距离大小对C中码字分类如下，记

$C_i=\left\{c\in C:w{t}_H=i\right\}$,(2.9)

$4\le i\le 10$，C中码字按照Hamming距离分类处理如下：

1) $\left|C_4\right|=420$，对 $\forall c\in C_{\text{4}}$， $gap\left(c\right)=4$，此时 $d_P\left(c\right)=8$ ；

2) $\left|C_5\right|=756$，对 $\forall c\in C_{\text{5}}$， $gap\left(c\right)=5$，此时 $d_P\left(c\right)=10$ ；

3) $\exists c^{″}=\left(1,6,5,2,1,6,0,0,0,0,0,0,0,0\right)\in C_6$，s.t. $gap\left(c^{″}\right)=1$，那么 $d_P\left(c^{″}\right)=7$，从而 $\forall c\in C_6$， $d_P\left(c\right)\ge 7$，此处的“=”能够成立；

4) 如果 $w{t}_H\left(c\right)\ge 7$，那么 $d_P\left(c\right)\ge w{t}_H\left(c\right)+gap\left(c\right)\ge 7$ ；

综上可得： $d_P\left(C\right)=7$，此时是 ${\left(14,7\right)}_7$ MDS符号对码。

4. 结论

本文利用给出了重根循环码的性质结合符号对码的符号对距离特征构造了符号对距离为7 MDS符号对码，构造出参数不同于已知构造且符号对距离较大的新的MDS符号对码，扩充了MDS符号对码类型。