纠单个有序删除和擦除错误码的构造方法*

何雅萍，贺玉成，周 林

(华侨大学厦门市移动多媒体通信重点实验室，福建 厦门 361021)

0 引 言

在通信和存储系统的传输过程中，由于数据同步错误或信道中存在噪声、时序等干扰引发传输差错，所接收到的信息可能存在元素插入、删除、擦除和替换等错误[1］。为了纠正接收信息中存在的错误，以得到正确的传输信息，Varshamov和Tenengolt首先提出以他们名字命名的Varshamov-Tenengolt（VT）码，可以纠正信道传输过程中发生的非对称错误[2］。随后，Levenshtein提出了一种可以纠正单个插入或者删除错误的二进制码[3］，并且在此基础上提出了一种新的构造方法，可以纠正两个相邻插入或删除错误[4］。多年来，学者们一直致力于构造具有更高纠错能力的二进制码[5-6］和非二进制码[7-9］，并根据构造方法设计相应的简单高效译码方法。

最近，Gabrys等人针对元素删除和擦除错误提出了四种错误模型，并构造出可纠正多个删除错误的方法[10］。本文研究了传输信息发生删除的位置始终在擦除前的有序删除和擦除错误，结合现有的纠错码构造方法，提出了一种可以纠正单个有序删除和擦除错误的二进制码的构造方法及其译码方法。

1 基本理论

1.1 有序删除和擦除错误

对于整数n≥ 2，α=(α1,α2,…,αn)∈GF(2)n为一个码长为n的二进制传输码字，β表示接收码字。

定义1：对于整数1≤d≤e≤n，α中第d位αd被删除，第e+1位αe+1被擦除，且删除位置始终在擦除位置前，称为“单个有序删除和擦除错误”，记为Fd,e(α):=β=(β1,…,βn-1)，其中

当e≤n-1时，擦除值βe=?；当e=n时，β仅发生删除错误，无擦除错误。

例 1：设α=(0,0,1,0,1,1,0,1)，d=3，e=6，由定义1可得β=(0,0,0,1,1,?,1)。

1.2 Varshamov-Tenengolts码

为了纠正信道传输过程中发生的非对称错误，文献[2］中提出了VT码的构造方法。

定义2：对于给定正整数a∈ℤn，VT码VTa(n)的定义如下：

可以纠正单个删除错误。

2 构造与译码方法

本节针对传输过程中发生的单个有序删除和擦除错误，利用定义2的VT码，提出一种新的构造方法，并在证明过程中给出了相应的译码方法。

构造：给定整数n≥2，0≤a1≤2和0≤a2≤n，二进制码

首先，分析删除错误和擦除错误都发生的情况，随后再分析仅发生删除错误的情况。假定k∈[e］表示删除位置d的可能值，为删除和擦除值，其校验和

当且仅当如下两个条件同时满足：

（2）αk位于删除值αd所处的游程中，即存在d1≤k，d≤d2，对任意j∈ [d1,d2］，有αk=αd=αj，αd1-1=αd2+1=1-αd1。

此时，和fk(β)之间的关系为：

fk(β)-a2≡ 0 mod (n+1)

下面，对fk(·)分情况讨论。

（1）1≤k≤d

由式（1）可知，式（4）第一项求和式可表示为：

第二项求和式可表示为：

将式（5）和式（6）代入式（4）可得：

其中：

当a＜b时，

综上，当1≤k≤d时：

（2）d+1≤k≤e

由式（1）可知，式（4）第一项求和式可表示为：

第二项求和式可表示为：

将式（12）和式（13）代入式（4）可得：

综上，当d+1≤k≤e时，

为了恢复删除值αd和擦除值αe+1，根据构造式（3）可得差值表达式为：

下面分别考虑D(β)存在的3种可能结果：

（1）D(β)=0

在这种情况下，删除值αd和擦除值αe+1均为0，设定此时，式（8）中Δ=0。存在任意j(d1≤d,j≤d2)，有αj=0，αd1-1=αd2+1=1。也就是说(αd1,…,αd2)为一个0的游程，删除位αd位于该游程中。

当1≤k≤d1-1时，在位置k和d-1之间至少存在一位值为1，使得1≤r(k,d-1)≤n，代入式（11）可得fk(β)-a20 mod (n+1)。

当d1≤k≤d时，有r(k,d-1)=0；当d+1≤k≤d2时，有r(d+1,k)=0。分别代入式（11）和式（15）均得fk(β)-a2≡ 0 mod (n+1)，其中d1≤k≤d2。

当d2+1≤k≤e时，在位置d+1和k之间至少存在一位值为1，使得-n≤-r(d+1,k)≤-1，代入式（15）可得fk(β)-a20 mod (n+1)。

（2）D(β)=2

在这种情况下，删除值αd和擦除值αe+1均为1，设定，此时，Δ=k-d。存在任意j(d1≤d,j≤d2)，有αj=1，αd1-1=αd2+1=0。也就是说 (αd1,…,αd2)为一个1的游程，删除位αd位于该游程中。

当1≤k≤d1-1时，在位置k和d-1之间至少存在一位值为0，使得：

由式（11）可得fk(y)-a20 mod (n+1)。

当d1≤k≤d时， 有k-d+r(k,d-1)=0； 当d+1≤k≤d2时，分别代入式（11）和式（15）均得fk(β)-a2≡0 mod(n+1)，其中d1≤k≤d2。

当d2+1≤k≤e时，在位置d+1和k之间至少存在一位值为0，使得：

代入式（15）可得fk(β)-a20 mod (n+1)。

（3）D(β)=1

首先，假定删除值αd=1，擦除值αe+1=0，在这种情况下：

当1≤k≤d时，由式（10）可得：

1≤-d+e+1≤-d+e+1+r(k,d-1)≤-k+e+1

代入式（11）得fk(β)-a20 mod (n+1)。

当d+1≤k≤e时，e≥-d+e+1-r(d+1,k)≥-d+e+1-(k-d)=e+1-k≥1，

代入式（15）得fk(β)-a20 mod (n+1)。

其次，假定删除值αd=0，擦除值αe+1=1，在这种情况下：

当1≤k≤d时，-e≤k-e-1+r(k,d-1)≤k-e-1+(dk)=d-e-1≤-1，

代入式（11）得fk(β)-a20 mod (n+1)。

当d+1≤k≤e时，-1≥k-e-1-r(d+1,k)≥k-e-1-(k-d)=d-e-1≥ -e，

代入式（15）得fk(β)-a20 mod (n+1)。

最后，假定β=Fd,e(α)仅发生单个删除错误，而未发生擦除错误。此时，设定则类 似地，当αd=0时，Δ=0，分析与情况①一致；当αd=1时，Δ=k-d，分析与情况②一致。这两种情况都可得出，当且仅当d1≤k≤d2时，满足fk(β)-a2≡ 0 mod (n+1)。

综上，译码方法的完整步骤如算法1所示：

算法1：纠正单个有序删除和擦除错误。

输入：接收码字β，擦除位置e（若未发生擦除错误，则e=n）。

输出：恢复传输码字ˆα。

译码过程：

1.初始化：k=0，F(0)=a2+1 mod (n+1)。

#寻找删除位置d和擦除位置e+1

4.判断F(k)-a20 mod (n+1)且k≤e是否成立，若成立则进入循环，重复执行k=k+1，直到不满足条件，跳出循环，进行下一步。

5.如果F(k)-a2≡0 mod (n+1)且k≤e，则输出译码结束，不再执行下述步骤。

6.如果fl ag=1，则输出“译码错误”，不再执行下述步骤。

7.如果步骤5和6均不满足判断条件，则重新进行初始化k=0，F(0)=a2+1 mod (n+1)，且设定标记fl ag=1，跳到步骤4重新开始寻找位置。

例2：令正整数n=9，d=5，e=6，假定传输码字α=(0,1,1,0,0,0,1,0,1)，a1=1，a2=1，接收码字β=(0,1,1,0,0,?,0,1)。

已知接收码字β和擦除位置e=6，现根据算法1对其进行译码。初始化可得k=0，F(0)=2，由于发生擦除错误，且D=1，先假定标记fl ag=0。执行步骤4，直到k=7＞6，跳出循环。由于步骤5和6均不满足判断条件，重新初始化k=0，F(0)=2，并设定标记fl ag=1，跳至步 骤 4重 新 寻 找。 当k=4＜6时，F(4)=21，F(4)-1≡0 mod 10，跳出循环。执行步骤5，满足判断条件，输出ˆ=(0,1,1,0,0,0,1,0,1)，与原传输码字α比对，译码正确。

3 结 语

本文结合可纠正一位删除错误的VT码，提出了一种可纠正有序删除和擦除错误的二进制码构造方法，同时给出了相应的译码方法。本文所提出的构造方法简单直观，译码方法具有较低的译码复杂度，编译码过程简单，并通过实例验证了所提出的译码方法的正确性。