拟差族的存在性及构作

沈 红 兵

(泰州师范高等专科学校，江苏 泰州 225300)

1 引言

差族和拟差集是非常有用的设计，它们在BIBD设计和编码密码理论上都有着广泛的应用[1～4]。Johnson和Weller[5]证明了差族可以构作优的半循环低密度奇偶检验码(quasi-cyclic lower-density parity-check codes)。拟差族是差族和拟差集概念的直接推广。

最近，Ding和Yin[6]介绍了拟差族的一些构造方法，得到了拟差族的一些无穷类，同时指出拟差族同样可以用来构作LDPC码。沈[7]用直接构作的方法讨论了一类拟差族的存在性。本文，我们将借助陪集类和本原元来构作拟差族。

设G是一v阶阿贝尔群，其运算记为加法。又设D=D1,D2,…,Ds是G的一簇k元子集。定义重集

ΔDi={a-b|a≠b且a,b∈Di}，

其中“∪”表示重集的并。λ为给定的正整数。若G中的t个非零元素在ΔD中恰出现λ次，而剩下的v-1-t个非零元素在ΔD中恰出现λ+1次，则称D为G的拟差族，简记为(v,k,λ,t)-ADF。

当t=v-1时，(v,k,λ,t)-拟差族就是参数为v,k,λ的差族，即(v,k,λ)-DF；若一个(v,k,λ,t)-拟差族D中只包含一个k元子集D，则称D=D为一个拟差集，记为(v,k,λ,t)-ADS。

根据简单计算，若(v,k,λ,t)-ADF存在，则有

sk(k-1)=tλ+(v-1-t)(λ+1)

即(v,k,λ,t)-ADF存在的必要条件为

(λ+1)(v-1)≡t(modk(k-1))。

2 有限域上的存在性

设S,T是GF(q)的两个子集，为方便表示，记S∘T={st:s∈S,t∈T}。若T={t}，则S∘T简记为St={st:s∈S}。

根据定理1，我们只要找到符合条件的序偶(x,y)即可得到相应的拟差族。为此，我们引用如下结论。

利用引理1，我们得到下面的定理。

证明：设欲求的序偶(a,b)满足下列条件：

应用引理1，取参数n=5。

故对任意素数幂q≡1(mod10)且q>276，总存在序偶(a,b)同时满足条件(1)和(2)。

qωab1129731332441661761258871775981x4+2x+2x3+2x2x2+x+21012648121x2-8x-3x+79x+713128313151665418126447

续表

qωab1911998632112131824177102251675175271644233

根据定理1和定理2即得以下定理：

[1]Greig M,Some balanced incompete block design constructions[J].Congr.Numer，1990，(77)：121～134.

[2]Storer T,Cyclotomy and differencr sets[M].Chicago:Markhan,1967.

[3]Whiteman A.L.,A family of difference sets[J].Illinois J.Math，1962,(6)：107～121.

[4]Wilson R.M.,Cyclotomy and difference families in elementary abelian groups[J].J.Number Theory，1972，(4)：17～47.

[5]Johnson S.J.,Weller S.R.,Quasi-cyclic LDPC codes from difference families,in:Proceeding of the 3rd Australian Communications Theory Workshop,pp.18～22,Canberra,February,4-5，2002.

[6]Ding C.S.,Yin J.X.,Constructions of Almost Difference Families[J].Discrete Mathematics,2008,(308):4914～4954.

[7]沈红兵.一类拟差族的存在性[J].苏州大学学报:自然科学版,2007,23(4):26～28.

[8]Chang Y.X. and Ji L.J.,Optimal(4up,5,1) Optical Orthogonal Codes,J.Combin. Des，2004,(12)：346～361.