擬差族的存在性及構(gòu)作

沈 紅 兵

(泰州師范高等?？茖W(xué)校，江蘇 泰州 225300)

1 引言

差族和擬差集是非常有用的設(shè)計(jì)，它們?cè)贐IBD設(shè)計(jì)和編碼密碼理論上都有著廣泛的應(yīng)用[1～4]。Johnson和Weller[5]證明了差族可以構(gòu)作優(yōu)的半循環(huán)低密度奇偶檢驗(yàn)碼(quasi-cyclic lower-density parity-check codes)。擬差族是差族和擬差集概念的直接推廣。

最近，Ding和Yin[6]介紹了擬差族的一些構(gòu)造方法，得到了擬差族的一些無(wú)窮類，同時(shí)指出擬差族同樣可以用來(lái)構(gòu)作LDPC碼。沈[7]用直接構(gòu)作的方法討論了一類擬差族的存在性。本文，我們將借助陪集類和本原元來(lái)構(gòu)作擬差族。

設(shè)G是一v階阿貝爾群，其運(yùn)算記為加法。又設(shè)D=D1,D2,…,Ds是G的一簇k元子集。定義重集

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

其中“∪”表示重集的并。λ為給定的正整數(shù)。若G中的t個(gè)非零元素在ΔD中恰出現(xiàn)λ次，而剩下的v-1-t個(gè)非零元素在ΔD中恰出現(xiàn)λ+1次，則稱D為G的擬差族，簡(jiǎn)記為(v,k,λ,t)-ADF。

當(dāng)t=v-1時(shí)，(v,k,λ,t)-擬差族就是參數(shù)為v,k,λ的差族，即(v,k,λ)-DF；若一個(gè)(v,k,λ,t)-擬差族D中只包含一個(gè)k元子集D，則稱D=D為一個(gè)擬差集，記為(v,k,λ,t)-ADS。

根據(jù)簡(jiǎn)單計(jì)算，若(v,k,λ,t)-ADF存在，則有

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

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

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

2 有限域上的存在性

設(shè)S,T是GF(q)的兩個(gè)子集，為方便表示，記S°T={st:s∈S,t∈T}。若T={t}，則S°T簡(jiǎn)記為St={st:s∈S}。

根據(jù)定理1，我們只要找到符合條件的序偶(x,y)即可得到相應(yīng)的擬差族。為此，我們引用如下結(jié)論。

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

證明：設(shè)欲求的序偶(a,b)滿足下列條件：

應(yīng)用引理1，取參數(shù)n=5。

故對(duì)任意素?cái)?shù)冪q≡1(mod10)且q>276，總存在序偶(a,b)同時(shí)滿足條件(1)和(2)。

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

續(xù)表

qωab1911998632112131824177102251675175271644233

根據(jù)定理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].蘇州大學(xué)學(xué)報(bào):自然科學(xué)版,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.