蒲利群，柴艷玲

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

證明假設(shè)存在一個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中的點劃分成三類：

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è)存在一個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中的點劃分成四類：

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時，v?8,9和可能v≠14，T(2,{4,5,6},v)-碼都存在，且給出了碼字個數(shù)的一個上界。對v=14，如何構(gòu)造出一個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] 蒲利群, 柴艷玲. 長為{3,4,5}的完備刪位糾錯碼的組合構(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.