糾單個(gè)有序刪除和擦除錯(cuò)誤碼的構(gòu)造方法*

何雅萍，賀玉成，周 林

(華僑大學(xué)廈門(mén)市移動(dòng)多媒體通信重點(diǎn)實(shí)驗(yàn)室，福建 廈門(mén) 361021)

0 引 言

在通信和存儲(chǔ)系統(tǒng)的傳輸過(guò)程中，由于數(shù)據(jù)同步錯(cuò)誤或信道中存在噪聲、時(shí)序等干擾引發(fā)傳輸差錯(cuò)，所接收到的信息可能存在元素插入、刪除、擦除和替換等錯(cuò)誤[1］。為了糾正接收信息中存在的錯(cuò)誤，以得到正確的傳輸信息，Varshamov和Tenengolt首先提出以他們名字命名的Varshamov-Tenengolt（VT）碼，可以糾正信道傳輸過(guò)程中發(fā)生的非對(duì)稱錯(cuò)誤[2］。隨后，Levenshtein提出了一種可以糾正單個(gè)插入或者刪除錯(cuò)誤的二進(jìn)制碼[3］，并且在此基礎(chǔ)上提出了一種新的構(gòu)造方法，可以糾正兩個(gè)相鄰插入或刪除錯(cuò)誤[4］。多年來(lái)，學(xué)者們一直致力于構(gòu)造具有更高糾錯(cuò)能力的二進(jìn)制碼[5-6］和非二進(jìn)制碼[7-9］，并根據(jù)構(gòu)造方法設(shè)計(jì)相應(yīng)的簡(jiǎn)單高效譯碼方法。

最近，Gabrys等人針對(duì)元素刪除和擦除錯(cuò)誤提出了四種錯(cuò)誤模型，并構(gòu)造出可糾正多個(gè)刪除錯(cuò)誤的方法[10］。本文研究了傳輸信息發(fā)生刪除的位置始終在擦除前的有序刪除和擦除錯(cuò)誤，結(jié)合現(xiàn)有的糾錯(cuò)碼構(gòu)造方法，提出了一種可以糾正單個(gè)有序刪除和擦除錯(cuò)誤的二進(jìn)制碼的構(gòu)造方法及其譯碼方法。

1 基本理論

1.1 有序刪除和擦除錯(cuò)誤

對(duì)于整數(shù)n≥ 2，α=(α1,α2,…,αn)∈GF(2)n為一個(gè)碼長(zhǎng)為n的二進(jìn)制傳輸碼字，β表示接收碼字。

定義1：對(duì)于整數(shù)1≤d≤e≤n，α中第d位αd被刪除，第e+1位αe+1被擦除，且刪除位置始終在擦除位置前，稱為“單個(gè)有序刪除和擦除錯(cuò)誤”，記為Fd,e(α):=β=(β1,…,βn-1)，其中

當(dāng)e≤n-1時(shí)，擦除值βe=?；當(dāng)e=n時(shí)，β僅發(fā)生刪除錯(cuò)誤，無(wú)擦除錯(cuò)誤。

例 1：設(shè)α=(0,0,1,0,1,1,0,1)，d=3，e=6，由定義1可得β=(0,0,0,1,1,?,1)。

1.2 Varshamov-Tenengolts碼

為了糾正信道傳輸過(guò)程中發(fā)生的非對(duì)稱錯(cuò)誤，文獻(xiàn)[2］中提出了VT碼的構(gòu)造方法。

定義2：對(duì)于給定正整數(shù)a∈?n，VT碼VTa(n)的定義如下：

可以糾正單個(gè)刪除錯(cuò)誤。

2 構(gòu)造與譯碼方法

本節(jié)針對(duì)傳輸過(guò)程中發(fā)生的單個(gè)有序刪除和擦除錯(cuò)誤，利用定義2的VT碼，提出一種新的構(gòu)造方法，并在證明過(guò)程中給出了相應(yīng)的譯碼方法。

構(gòu)造：給定整數(shù)n≥2，0≤a1≤2和0≤a2≤n，二進(jìn)制碼

首先，分析刪除錯(cuò)誤和擦除錯(cuò)誤都發(fā)生的情況，隨后再分析僅發(fā)生刪除錯(cuò)誤的情況。假定k∈[e］表示刪除位置d的可能值，為刪除和擦除值，其校驗(yàn)和

當(dāng)且僅當(dāng)如下兩個(gè)條件同時(shí)滿足：

（2）αk位于刪除值αd所處的游程中，即存在d1≤k，d≤d2，對(duì)任意j∈ [d1,d2］，有αk=αd=αj，αd1-1=αd2+1=1-αd1。

此時(shí)，和fk(β)之間的關(guān)系為：

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

下面，對(duì)fk(·)分情況討論。

（1）1≤k≤d

由式（1）可知，式（4）第一項(xiàng)求和式可表示為：

第二項(xiàng)求和式可表示為：

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

其中：

當(dāng)a＜b時(shí)，

綜上，當(dāng)1≤k≤d時(shí)：

（2）d+1≤k≤e

由式（1）可知，式（4）第一項(xiàng)求和式可表示為：

第二項(xiàng)求和式可表示為：

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

綜上，當(dāng)d+1≤k≤e時(shí)，

為了恢復(fù)刪除值αd和擦除值αe+1，根據(jù)構(gòu)造式（3）可得差值表達(dá)式為：

下面分別考慮D(β)存在的3種可能結(jié)果：

（1）D(β)=0

在這種情況下，刪除值αd和擦除值αe+1均為0，設(shè)定此時(shí)，式（8）中Δ=0。存在任意j(d1≤d,j≤d2)，有αj=0，αd1-1=αd2+1=1。也就是說(shuō)(αd1,…,αd2)為一個(gè)0的游程，刪除位αd位于該游程中。

當(dāng)1≤k≤d1-1時(shí)，在位置k和d-1之間至少存在一位值為1，使得1≤r(k,d-1)≤n，代入式（11）可得fk(β)-a20 mod (n+1)。

當(dāng)d1≤k≤d時(shí)，有r(k,d-1)=0；當(dāng)d+1≤k≤d2時(shí)，有r(d+1,k)=0。分別代入式（11）和式（15）均得fk(β)-a2≡ 0 mod (n+1)，其中d1≤k≤d2。

當(dāng)d2+1≤k≤e時(shí)，在位置d+1和k之間至少存在一位值為1，使得-n≤-r(d+1,k)≤-1，代入式（15）可得fk(β)-a20 mod (n+1)。

（2）D(β)=2

在這種情況下，刪除值αd和擦除值αe+1均為1，設(shè)定，此時(shí)，Δ=k-d。存在任意j(d1≤d,j≤d2)，有αj=1，αd1-1=αd2+1=0。也就是說(shuō) (αd1,…,αd2)為一個(gè)1的游程，刪除位αd位于該游程中。

當(dāng)1≤k≤d1-1時(shí)，在位置k和d-1之間至少存在一位值為0，使得：

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

當(dāng)d1≤k≤d時(shí)， 有k-d+r(k,d-1)=0； 當(dāng)d+1≤k≤d2時(shí)，分別代入式（11）和式（15）均得fk(β)-a2≡0 mod(n+1)，其中d1≤k≤d2。

當(dāng)d2+1≤k≤e時(shí)，在位置d+1和k之間至少存在一位值為0，使得：

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

（3）D(β)=1

首先，假定刪除值αd=1，擦除值αe+1=0，在這種情況下：

當(dāng)1≤k≤d時(shí)，由式（10）可得：

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

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

當(dāng)d+1≤k≤e時(shí)，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，在這種情況下：

當(dāng)1≤k≤d時(shí)，-e≤k-e-1+r(k,d-1)≤k-e-1+(dk)=d-e-1≤-1，

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

當(dāng)d+1≤k≤e時(shí)，-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(α)僅發(fā)生單個(gè)刪除錯(cuò)誤，而未發(fā)生擦除錯(cuò)誤。此時(shí)，設(shè)定則類 似地，當(dāng)αd=0時(shí)，Δ=0，分析與情況①一致；當(dāng)αd=1時(shí)，Δ=k-d，分析與情況②一致。這兩種情況都可得出，當(dāng)且僅當(dāng)d1≤k≤d2時(shí)，滿足fk(β)-a2≡ 0 mod (n+1)。

綜上，譯碼方法的完整步驟如算法1所示：

算法1：糾正單個(gè)有序刪除和擦除錯(cuò)誤。

輸入：接收碼字β，擦除位置e（若未發(fā)生擦除錯(cuò)誤，則e=n）。

輸出：恢復(fù)傳輸碼字?α。

譯碼過(guò)程：

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

#尋找刪除位置d和擦除位置e+1

4.判斷F(k)-a20 mod (n+1)且k≤e是否成立，若成立則進(jìn)入循環(huán)，重復(fù)執(zhí)行k=k+1，直到不滿足條件，跳出循環(huán)，進(jìn)行下一步。

5.如果F(k)-a2≡0 mod (n+1)且k≤e，則輸出譯碼結(jié)束，不再執(zhí)行下述步驟。

6.如果fl ag=1，則輸出“譯碼錯(cuò)誤”，不再執(zhí)行下述步驟。

7.如果步驟5和6均不滿足判斷條件，則重新進(jìn)行初始化k=0，F(xiàn)(0)=a2+1 mod (n+1)，且設(shè)定標(biāo)記fl ag=1，跳到步驟4重新開(kāi)始尋找位置。

例2：令正整數(shù)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，現(xiàn)根據(jù)算法1對(duì)其進(jìn)行譯碼。初始化可得k=0，F(xiàn)(0)=2，由于發(fā)生擦除錯(cuò)誤，且D=1，先假定標(biāo)記fl ag=0。執(zhí)行步驟4，直到k=7＞6，跳出循環(huán)。由于步驟5和6均不滿足判斷條件，重新初始化k=0，F(xiàn)(0)=2，并設(shè)定標(biāo)記fl ag=1，跳至步 驟 4重 新 尋 找。 當(dāng)k=4＜6時(shí)，F(xiàn)(4)=21，F(xiàn)(4)-1≡0 mod 10，跳出循環(huán)。執(zhí)行步驟5，滿足判斷條件，輸出?=(0,1,1,0,0,0,1,0,1)，與原傳輸碼字α比對(duì)，譯碼正確。

3 結(jié) 語(yǔ)

本文結(jié)合可糾正一位刪除錯(cuò)誤的VT碼，提出了一種可糾正有序刪除和擦除錯(cuò)誤的二進(jìn)制碼構(gòu)造方法，同時(shí)給出了相應(yīng)的譯碼方法。本文所提出的構(gòu)造方法簡(jiǎn)單直觀，譯碼方法具有較低的譯碼復(fù)雜度，編譯碼過(guò)程簡(jiǎn)單，并通過(guò)實(shí)例驗(yàn)證了所提出的譯碼方法的正確性。