長(zhǎng)為{4,5,6}的完備刪位糾錯(cuò)碼的存在性*

蒲利群，柴艷玲

(1. 鄭州大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，河南 鄭州450001；2. 鄭州城市職業(yè)學(xué)院，河南 鄭州452370)

衛(wèi)星通訊中，常常會(huì)出現(xiàn)信號(hào)衰減和數(shù)據(jù)丟失，刪位糾錯(cuò)碼為了解決此問(wèn)題而產(chǎn)生。1992年Levenshtein[1]首次提出完備刪位糾錯(cuò)碼的概念，現(xiàn)已有大量文獻(xiàn)對(duì)T(2,k,v)-碼做了研究[2-6]，這些碼中碼字長(zhǎng)度都是一個(gè)固定值。文[7]提出了具有混合長(zhǎng)度的刪位糾錯(cuò)碼T(2,K,v)的概念，其中的碼字長(zhǎng)度取自一個(gè)給定的正整數(shù)集K；且對(duì)v≥3,v≠8，利用組合設(shè)計(jì)方法，在Zv上構(gòu)造了具有混合長(zhǎng)度{3,4,5}的T(2,{3,4,5},v)-碼，并給出了碼字總數(shù)的一個(gè)上界。本文研究K={4,5,6}時(shí)，T(2,{4,5,6},v)-碼的存在性。

1 T(2,{4,5,6},v)-碼的存在性

設(shè)K是給定的正整數(shù)集合，X是v個(gè)點(diǎn)的集合，B是k元有序組的集合,其中k∈K。若X的任意一個(gè)有序點(diǎn)對(duì)都恰好出現(xiàn)在B中的一個(gè)k元有序組中，則稱(X,B)為一個(gè)有向成對(duì)平衡設(shè)計(jì)，簡(jiǎn)記DB(K,1;v)。其中，B中的任何一個(gè)k元有序組稱為一個(gè)區(qū)組。

如果將DB(K,1;v)的所有區(qū)組看成碼字，所有碼字的集合就是一個(gè)T(2,K,v)-碼。

在Zv上存在一個(gè)T(2,K,v)-碼，等價(jià)于存在一個(gè)DB(K,1;v)。若K1?K2，T(2,K1,v)-碼必為T(mén)(2,K2,v)-碼。[8]利用組合方法構(gòu)造，并給出了K={4,5}和K={5,6}時(shí)，DB({4,5},1;v)和DB({4,6},1;v)的存在性結(jié)論。

引理1[8]當(dāng)v≥4,且v?{6,8,9,12,14}時(shí)，DB({4,5},1;v)存在。

引理2[8]當(dāng)v≡0,1 mod 3，v≥4，且v?{9,15}時(shí)，DB({5,6},1;v)存在。

綜合引理1和引理2，可以得到，當(dāng)v≥4和可能的v?8,9,14，存在一個(gè)T(2,{4,5,6},v)-碼。于是，我們可以得到以下定理。

定理1 當(dāng)v≥4，且v?{8,9}和可能的v≠14時(shí)，存在一個(gè)T(2,{4,5,6},v)-碼。

下面我們將在定理2和定理3中證明v∈{8,9}時(shí)，T(2,{4,5,6},v)-碼不存在。

2 v∈{8,9}時(shí)，T(2,{4,5,6},v)-碼的不存在性

設(shè)C是定義在Zv上的一個(gè)T(2,{4,5,6},v)-碼，為敘述方便引入以下記號(hào)。

rj(x)：字符x在長(zhǎng)為j的碼字中出現(xiàn)的次數(shù)，?x∈Zv；

bj：C中長(zhǎng)度為j的碼字個(gè)數(shù)。其中，j=4,5,6

引理3 設(shè)C是一個(gè)T(2,{4,5,6},v)-碼，則有

(i)3r4(x)+4r5(x)+5r6(x)=2(v-1)，?x∈Zv；

證明Zv中的任意點(diǎn)對(duì)都恰好出現(xiàn)在C的一個(gè)碼字中，任意一點(diǎn)x與其他的(v-1)個(gè)點(diǎn)構(gòu)成2(v-1)個(gè)序?qū)?。由于x出現(xiàn)在r4(x)個(gè)長(zhǎng)為4的碼字中，且每個(gè)碼字都有3個(gè)含x的序?qū)?，因此，所有長(zhǎng)為4的碼字中共有3r4(x)個(gè)含x的序?qū)?。同理，所有長(zhǎng)為5的碼字中共有4r5(x)個(gè)含x的序?qū)?，所有長(zhǎng)為6的碼字中共有5r6(x)個(gè)含x的序?qū)?。從而?i)式成立。

定理2 不存在T(2,{4,5,6},8)-碼。

證明假設(shè)存在一個(gè)T(2,{4,5,6},8)-碼C，由引理3得，

3r4(x)+4r5(x)+5r6(x)=14

于是，(r4(x),r5(x),r6(x))=(0,1,2)，(3,0,1)，或(2,2,0)。將Z8中的點(diǎn)劃分成三類：

V1={x∈Z8|(r4(x),r5(x),r6(x))=(0,1,2)}，

V2={x∈Z8|(r4(x),r5(x),r6(x))=(3,0,1)}，

V3={x∈Z8|(r4(x),r5(x),r6(x))=(2,2,0)}

其中，|Vi|=vi，i=1,2,3。

綜上，不存在T(2,{4,5,6},8)-碼。

定理3 不存在T(2,{4,5,6},9)-碼。

證明假設(shè)存在一個(gè)T(2,{4,5,6},9)-碼，由引理3得，

3r4(x)+4r5(x)+5r6(x)=16

于是，(r4(x),r5(x),r6(x))=(2,0,2)，(1,2,1)，(0,4,0)或(4,1,0)。將Z9中的點(diǎn)劃分成四類：

V1={x∈Z9|(r4(x),r5(x),r6(x))=(2,0,2)}，

V2={x∈Z9|(r4(x),r5(x),r6(x))=(1,2,1)}，

V3={x∈Z9|(r4(x),r5(x),r6(x))=(0,4,0)}，

V4={x∈Z9|(r4(x),r5(x),r6(x))=(4,1,0)}

其中，|Vi|=vi，i=1,2,3,4。

綜上，不存在T(2,{4,5,6},9)-碼。

3 碼字總數(shù)的上界

4 小 結(jié)

本文證明了當(dāng)v≥4時(shí)，v?8,9和可能v≠14，T(2,{4,5,6},v)-碼都存在，且給出了碼字個(gè)數(shù)的一個(gè)上界。對(duì)v=14，如何構(gòu)造出一個(gè)T(2,{4,5,6},14)-碼，或者證明它不存在？

參考文獻(xiàn)：

[1] LEVENSHTEIN V I. On perfect codes in deletion and insertion metric [J]. Discrete Math Appl, 1992, 2(3): 241-258.

[2] BOURS P A H. On the construction of perfect deletion-correcting codes using design theory [J]. Designs, Codes and Cryptography, 1995, 6(2): 5-20.

[3] MAHMOODI A. Existence of perfect 3-deletion-correcting codes [J]. Designs, Codes and Cryptography, 1998,14(1): 81-87.

[4] YIN J X. A combinatorial construction for perfect deletion-correcting codes[J]. Designs, Codes and Cryptography, 2001, 23(2): 99-110.

[5] SHALABY N, WANG J M, YIN J X. Existence of 4-deletion-correcting codes with length six [J]. Designs, Codes and Cryptography, 2002, 27(3): 145-156.

[6] WANG J M, YIN J X. Constructions for perfect 5-deletion-correcting codes of length 7 [J]. IEEE Transaction on Information Theory, 2006, 52(8): 3676-3685.

[7] 蒲利群, 柴艷玲. 長(zhǎng)為{3,4,5}的完備刪位糾錯(cuò)碼的組合構(gòu)造[J]. Journal of Mathematics, 2013, 33(1): 163-166.

[8] FUJI-HARA R, MIAO Y, WANG J M, et al. DirectedB(K,1;v) withK={4,5} and {5,6} related to deletion/insertion-correcting codes [J].Combinatorial Designs, 2001,9(12): 147-156.