长为{4,5,6}的完备删位纠错码的存在性*

2013-04-24 00:58蒲利群柴艳玲
关键词:利群综上码字

蒲利群,柴艳玲

(1. 郑州大学数学与统计学院,河南 郑州450001;2. 郑州城市职业学院,河南 郑州452370)

卫星通讯中,常常会出现信号衰减和数据丢失,删位纠错码为了解决此问题而产生。1992年Levenshtein[1]首次提出完备删位纠错码的概念,现已有大量文献对T(2,k,v)-码做了研究[2-6],这些码中码字长度都是一个固定值。文[7]提出了具有混合长度的删位纠错码T(2,K,v)的概念,其中的码字长度取自一个给定的正整数集K;且对v≥3,v≠8,利用组合设计方法,在Zv上构造了具有混合长度{3,4,5}的T(2,{3,4,5},v)-码,并给出了码字总数的一个上界。本文研究K={4,5,6}时,T(2,{4,5,6},v)-码的存在性。

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

设K是给定的正整数集合,X是v个点的集合,B是k元有序组的集合,其中k∈K。若X的任意一个有序点对都恰好出现在B中的一个k元有序组中,则称(X,B)为一个有向成对平衡设计,简记DB(K,1;v)。其中,B中的任何一个k元有序组称为一个区组。

如果将DB(K,1;v)的所有区组看成码字,所有码字的集合就是一个T(2,K,v)-码。

在Zv上存在一个T(2,K,v)-码,等价于存在一个DB(K,1;v)。若K1⊆K2,T(2,K1,v)-码必为T(2,K2,v)-码。[8]利用组合方法构造,并给出了K={4,5}和K={5,6}时,DB({4,5},1;v)和DB({4,6},1;v)的存在性结论。

引理1[8]当v≥4,且v∉{6,8,9,12,14}时,DB({4,5},1;v)存在。

引理2[8]当v≡0,1 mod 3,v≥4,且v∉{9,15}时,DB({5,6},1;v)存在。

综合引理1和引理2,可以得到,当v≥4和可能的v∉8,9,14,存在一个T(2,{4,5,6},v)-码。于是,我们可以得到以下定理。

定理1 当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)-码的不存在性

设C是定义在Zv上的一个T(2,{4,5,6},v)-码,为叙述方便引入以下记号。

rj(x):字符x在长为j的码字中出现的次数,∀x∈Zv;

bj:C中长度为j的码字个数。其中,j=4,5,6

引理3 设C是一个T(2,{4,5,6},v)-码,则有

(i)3r4(x)+4r5(x)+5r6(x)=2(v-1),∀x∈Zv;

证明Zv中的任意点对都恰好出现在C的一个码字中,任意一点x与其他的(v-1)个点构成2(v-1)个序对。由于x出现在r4(x)个长为4的码字中,且每个码字都有3个含x的序对,因此,所有长为4的码字中共有3r4(x)个含x的序对。同理,所有长为5的码字中共有4r5(x)个含x的序对,所有长为6的码字中共有5r6(x)个含x的序对。从而,(i)式成立。

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

证明假设存在一个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)-码。

证明假设存在一个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 码字总数的上界

4 小 结

本文证明了当v≥4时,v∉8,9和可能v≠14,T(2,{4,5,6},v)-码都存在,且给出了码字个数的一个上界。对v=14,如何构造出一个T(2,{4,5,6},14)-码,或者证明它不存在?

参考文献:

[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}的完备删位纠错码的组合构造[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.

猜你喜欢
利群综上码字
Intravascular lymphoma with hypopituitarism:A case report
具有非齐次泊松到达的队列 模型的稳态分布
集合测试题B卷参考答案
来活力台东,逛升级扩容版利群
全国名校必修五综合测试(B卷)参考答案与提示
放 下
利群:顺势而为,登场华东
走向“利群时代”
数据链系统中软扩频码的优选及应用
放下