強(qiáng)差族及其在相對(duì)差族、可分組設(shè)計(jì)和光正交碼中的應(yīng)用

楊凱璐,王小苗

（寧波大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,浙江 寧波 315211）

組合設(shè)計(jì)是組合數(shù)學(xué)的一個(gè)重要分支,主要研究各種離散結(jié)構(gòu)的存在性和構(gòu)造性、分類和計(jì)數(shù)問(wèn)題等.近幾十年來(lái),組合設(shè)計(jì)在通信技術(shù)和信息安全領(lǐng)域發(fā)揮了重要作用.作為相對(duì)差集的自然推廣,相對(duì)差族在1998 年由Buratti[1]提出.相對(duì)差族是構(gòu)造組合設(shè)計(jì)的強(qiáng)有力工具,在研究光正交碼、光正交簽名碼方面具有重要應(yīng)用.

由于相對(duì)差族的研究缺乏系統(tǒng)的構(gòu)造方法,1999 年Buratti[2]首次提出了強(qiáng)差族概念.此后近10 年對(duì)強(qiáng)差族的研究進(jìn)展十分緩慢,直到2008 年,Buratti 等[3]討論了任意圖上的強(qiáng)差族,推廣了任意圖上恰頂點(diǎn)可遷的完全多部圖的圖分解.并建立了二面體群上的強(qiáng)差族,從而得到了一類可分組設(shè)計(jì).Momihara[4]構(gòu)造了循環(huán)強(qiáng)差族的無(wú)窮類,同時(shí)給出了特殊參數(shù)強(qiáng)差族的不存在性證明.此外,借助平方和思想,完全解決了二階循環(huán)群上區(qū)組大小任意的強(qiáng)差族.Costa 等[5]借助強(qiáng)差族得到了框架差族,即對(duì)應(yīng)于可分解的循環(huán)相對(duì)差族.Bao等[6]指出,可分解的循環(huán)相對(duì)差族是構(gòu)造嚴(yán)格最優(yōu)跳頻序列的重要工具,跳頻多址系統(tǒng)在現(xiàn)代通信系統(tǒng),如超寬帶、軍事通信等方面有廣泛應(yīng)用.Buratti[7]通過(guò)引入哈達(dá)瑪強(qiáng)差族得到了可劃分差族.Ding等[8]利用可劃分差族構(gòu)造了最優(yōu)常重復(fù)合碼,后者在電力線通信的多進(jìn)制數(shù)字頻率調(diào)制中應(yīng)用廣泛.關(guān)于強(qiáng)差族的相關(guān)成果,還可參見文獻(xiàn)[9-12].

本研究得到了循環(huán)群上強(qiáng)差族的新的結(jié)果,并構(gòu)造了相對(duì)差族的漸近存在和離散例子,且利用相對(duì)差族擴(kuò)大了可分組設(shè)計(jì)的存在性,最后給出了組合設(shè)計(jì)理論在最優(yōu)光正交碼上的應(yīng)用.

1 預(yù)備知識(shí)

在全文中,集合和多重集分別用大括號(hào){}和方括號(hào)[]表示,每個(gè)并集指保留元素重?cái)?shù)的多重集的并.A∪A∪…∪A(h次)用hA表示.

令(G,+)是一個(gè)有限群,其中恒等元記作0.令K= [k1,k2,…,ks]為正整數(shù)的集合,Σ= [F1,F2,…,Fs]是G的多重集構(gòu)成的集族,其中Fi=[f i,1,fi,2,…,fi,ki],1≤i≤s.若滿足條件:

即G中每個(gè)元素(包括0)在多重集ΔΣ 中恰出現(xiàn)μ次,則Σ 稱為一個(gè)(G,K,μ)-強(qiáng)差族(SDF).Σ 中元素稱為基區(qū)組.顯然,.值得注意的是,由于元素0?G在任意多重集中作為差總是出現(xiàn)偶數(shù)次,故μ一定是偶數(shù).若每個(gè)基區(qū)組的大小均為k,則簡(jiǎn)記為(G,k,μ)-SDF.

命題1若存在一個(gè)(G,k,μ)-SDF,則μ為偶數(shù)且μ|G| ≡ 0(modk(k-1)).

對(duì)于正整數(shù)r和基區(qū)組B,令表示B在基區(qū)組的集合中出現(xiàn)r次.

引理 1[12]當(dāng)(v,k,μ) ?{(56,8,4),(56,8,6),(72,9,4)}時(shí),存在一個(gè)(Zv,k,μ)-SDF 為:

一個(gè)(G,N,k,λ)相對(duì)差族(DF),或含有n階子群N的g階群(G,+)上的(g,n,k,λ) -DF 是指G的k-元子集構(gòu)成的集族 B= [B1,B2,…,Br](基區(qū)組),使得:

即,GN中的每個(gè)元素在多重集ΔB 中恰出現(xiàn)λ次,且N中的元素在ΔB中不出現(xiàn).若G是循環(huán)群,稱(g,n,k,λ)-DF 是循環(huán)的.

2 強(qiáng)差族和相對(duì)差族

3 組型為(k (k- 1))u的k-可分組設(shè)計(jì)

相對(duì)差族可以用來(lái)構(gòu)造可分組設(shè)計(jì).令K為正整數(shù)的集合.一個(gè)可分組設(shè)計(jì)(GDD)K-GDD是指一個(gè)三元組(X,G,A),滿足性質(zhì):(1)G 是有限集X的一個(gè)劃分(稱為組);(2)A 是X中大小取自K的子集構(gòu)成的集合(稱為區(qū)組),使得X的每個(gè)2-子集恰包含在一個(gè)區(qū)組中或恰包含在一個(gè)組中,但不能同時(shí)包含在區(qū)組和組中.若G 含有ui個(gè)大小為gi的組,其中1≤i≤r,則稱為GDD 的組型.當(dāng)K={k}時(shí),簡(jiǎn)記為k-GDD.

引理6

(1)當(dāng)u?{6,16,21,25,26,36,41,42,48,49,51,66,71,76,78,81,84,85,86,90,91,96} ∪{q:q≡1(mod6)是素?cái)?shù)}時(shí),存在一個(gè)組型為30u的6-GDD[10].

(2)當(dāng)u?{7,8,9,15,17,28,33,36,41,49,50,56,57,63,64,65,70,71,72,73,77,78,80,81,85,88,91,92,96,97,99}時(shí),存在一個(gè)組型為42u的7-GDD[13].

(3)當(dāng)u?{8,9,10,15,16,17,29,30,33,36,37,41,43,44,49,50,51,53,54,55,57,58,63,64,65,71,72,73,74}∪[79,99]時(shí),存在一個(gè)組型為56u的8-GDD[13].

(4)當(dāng)u?{9,10,17,19,49,54,55,57,58,64,65,66,73,74,80,81,89,90,91}時(shí),存在一個(gè)組型為72u的9-GDD[13].

引理7當(dāng)素?cái)?shù)q≡ 5(mod8)且q﹥ 13時(shí),存在一個(gè)組型為30q的6-GDD.

證明由定理2 知,當(dāng)素?cái)?shù)q≡ 5(mod8)且q﹥ 13時(shí),存在一個(gè)(Z30× Fq,Z30×{0},6,1)-DF.由Z30×Fq上該DF的基區(qū)組可生成組型為30q的6-GDD.

結(jié)合引理6 中(1)和引理7,得到以下定理.

定理7當(dāng)u?{6,16,21,25,26,36,41,42,48,49,51,66,71,76,78,81,84,85,86,90,91,96} ∪{q:q﹥5,q≡ 1,5,7,13,19(mod24)是素?cái)?shù)}時(shí),存在一個(gè)組型為30u的6-GDD.

引理8當(dāng)素?cái)?shù)q≡ 5(mod8)且q﹥ 13時(shí),存在一個(gè)組型為42q的7-GDD.

證明由定理3 知,當(dāng)素?cái)?shù)q≡ 5(mod8)且q﹥ 13時(shí),存在一個(gè) (Z42× Fq,Z42×{0},7,1)-DF.由Z42× Fq上該DF 的基區(qū)組可生成組型為42q的7-GDD.

結(jié)合引理6 中(2)和引理8,得到以下定理.

定理8當(dāng)u?{7,8,9,15,17,28,33,36,41,49,50,56,57,63,64,65,70,71,72,73,77,78,80,81,85,88,91,92,96,97,99}∪{q:q﹥ 13,q≡ 5(mod8)是素?cái)?shù)}時(shí),存在一個(gè)組型為42u的7-GDD.

引理9當(dāng)素?cái)?shù)q≡ 1(mod4)且q﹥Q(4,7),或q≡ 7(mod12)且q﹥Q(6,7)時(shí),存在一個(gè)組型為56q的8-GDD.

證明由定理5 知,當(dāng)素?cái)?shù)q≡ 1(mod4)且q﹥Q(4,7),或q≡ 7(mod12)且q﹥Q(6,7)時(shí),存在一個(gè)(Z56×Fq,Z56×{0},8,1)-DF.由Z56× Fq上該DF的基區(qū)組可生成組型為56q的8-GDD.

定理9當(dāng)u?{8,9,10,15,16,17,29,30,33,36,37,41,43,44,49,50,51,53,54,55,57,58,61,63,64,65,67,71,72,73,74}∪[79,99] ∪{q:q﹥4848812032,q≡ 1(mod4)是素 數(shù)} ∪{q:q﹥ 1830677303808,q≡ 7(mod12)是素?cái)?shù)}時(shí),存在一個(gè)組型為56u的8-GDD.

證明由引理4 知,當(dāng)u? { 61,67}時(shí),存在一個(gè)(Z56×Fu,Z56×{0},8,1)-DF,故由 Z56×Fu上該DF的基區(qū)組可生成組型為56u的 8-GDD.當(dāng)u? { 61,67}時(shí),由引理6 中(3)和引理9 可以得到組型為56u的 8-GDD,其中Q(4,7)=4848812032,Q（6,7）=1830677303808.

引理10令素?cái)?shù)q≡ 5(mod8).當(dāng)q﹥Q(4,8)或37 ≤q≤9 973時(shí),存在一個(gè)組型為72q的9-GDD.

證明由定理 6 知,在 Z72× Fq上由(Z72×Fq,Z72×{0},9,1)-DF 的基區(qū)組可以生成一個(gè)組型為72q的9-GDD.

由于Q（4,8）= 107375099904,故結(jié)合引理6 中(4)和引理10 得到以下定理.

定理10當(dāng)u?{9,10,17,19,49,54,55,57,58,64,65,66,73,74,80,81,89,90,91} ∪{q:q? [ 37,9973]∪[107375099904,+∞),q≡ 5(mod8)是素?cái)?shù)}時(shí),存在一個(gè)組型為72u的9-GDD.

4 最優(yōu)光正交碼

利用定理2、3、5 和6 來(lái)構(gòu)造最優(yōu)光正交碼.一個(gè)碼重為k的(v,k,1)-光正交碼(OOC)是指 Zv的一些k-元子集(稱為碼字)構(gòu)成的集合,要求子集中的任意2 個(gè)元素做差,使得該集合產(chǎn)生的所有的差均不重復(fù),稱 Zv中不出現(xiàn)在這些差中的元素構(gòu)成的集合為差剩余.若差剩余的大小為小于或等于k(k-1),則稱該光正交碼為最優(yōu)的.

一個(gè)循環(huán)(gv,g,k,1)-DF 可被看作是一個(gè)(gv,k,1)-OOC,其中差剩余恰為{0,v,2v,…,(g-1)v}.

定理11(1)當(dāng)素?cái)?shù)q≡ 5(mod8)且q﹥ 13時(shí),存在一個(gè)最優(yōu)(k(k- 1)q,k,1)-OOC,其中k?{ 6,7}.(2)當(dāng)素?cái)?shù)q≡1 (mod4)且q﹥Q(4,7),或q≡7(mod12)且q﹥Q(6,7)時(shí),存在一個(gè)最優(yōu)(56q,8,1)-OOC.(3)令素?cái)?shù)q≡ 5(mod8),當(dāng)q﹥Q(4,8)或37 ≤q≤9973時(shí),存在一個(gè)最優(yōu)(72q,9,1)-OOC.

證明若k(k-1)和q互素,則 Zk（k-1）×Zq同構(gòu)于 Zk（k-1）q.由定理2、3、5 和6 知,存在一個(gè)循環(huán)(k(k- 1)q,k(k- 1),k,1)-DF,其中k?{ 6,7,8,9}.故存在一個(gè)(k(k- 1)q,k,1)-OOC,其中差剩余為{0,q,2q,…,(k(k-1) -1)q}.由于差剩余的大小恰好等于k(k-1),因此得到的光正交碼是最優(yōu)的.