強差族及其在相對差族、可分組設計和光正交碼中的應用

楊凱璐,王小苗

（寧波大學 數學與統計學院,浙江 寧波 315211）

組合設計是組合數學的一個重要分支,主要研究各種離散結構的存在性和構造性、分類和計數問題等.近幾十年來,組合設計在通信技術和信息安全領域發揮了重要作用.作為相對差集的自然推廣,相對差族在1998 年由Buratti[1]提出.相對差族是構造組合設計的強有力工具,在研究光正交碼、光正交簽名碼方面具有重要應用.

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

本研究得到了循環群上強差族的新的結果,并構造了相對差族的漸近存在和離散例子,且利用相對差族擴大了可分組設計的存在性,最后給出了組合設計理論在最優光正交碼上的應用.

1 預備知識

在全文中,集合和多重集分別用大括號{}和方括號[]表示,每個并集指保留元素重數的多重集的并.A∪A∪…∪A(h次)用hA表示.

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

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

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

對于正整數r和基區組B,令表示B在基區組的集合中出現r次.

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

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

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

2 強差族和相對差族

3 組型為(k (k- 1))u的k-可分組設計

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

引理6

(1)當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)是素數}時,存在一個組型為30u的6-GDD[10].

(2)當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}時,存在一個組型為42u的7-GDD[13].

(3)當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]時,存在一個組型為56u的8-GDD[13].

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

引理7當素數q≡ 5(mod8)且q﹥ 13時,存在一個組型為30q的6-GDD.

證明由定理2 知,當素數q≡ 5(mod8)且q﹥ 13時,存在一個(Z30× Fq,Z30×{0},6,1)-DF.由Z30×Fq上該DF的基區組可生成組型為30q的6-GDD.

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

定理7當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)是素數}時,存在一個組型為30u的6-GDD.

引理8當素數q≡ 5(mod8)且q﹥ 13時,存在一個組型為42q的7-GDD.

證明由定理3 知,當素數q≡ 5(mod8)且q﹥ 13時,存在一個 (Z42× Fq,Z42×{0},7,1)-DF.由Z42× Fq上該DF 的基區組可生成組型為42q的7-GDD.

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

定理8當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)是素數}時,存在一個組型為42u的7-GDD.

引理9當素數q≡ 1(mod4)且q﹥Q(4,7),或q≡ 7(mod12)且q﹥Q(6,7)時,存在一個組型為56q的8-GDD.

證明由定理5 知,當素數q≡ 1(mod4)且q﹥Q(4,7),或q≡ 7(mod12)且q﹥Q(6,7)時,存在一個(Z56×Fq,Z56×{0},8,1)-DF.由Z56× Fq上該DF的基區組可生成組型為56q的8-GDD.

定理9當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)是素 數} ∪{q:q﹥ 1830677303808,q≡ 7(mod12)是素數}時,存在一個組型為56u的8-GDD.

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

引理10令素數q≡ 5(mod8).當q﹥Q(4,8)或37 ≤q≤9 973時,存在一個組型為72q的9-GDD.

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

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

定理10當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)是素數}時,存在一個組型為72u的9-GDD.

4 最優光正交碼

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

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

定理11(1)當素數q≡ 5(mod8)且q﹥ 13時,存在一個最優(k(k- 1)q,k,1)-OOC,其中k?{ 6,7}.(2)當素數q≡1 (mod4)且q﹥Q(4,7),或q≡7(mod12)且q﹥Q(6,7)時,存在一個最優(56q,8,1)-OOC.(3)令素數q≡ 5(mod8),當q﹥Q(4,8)或37 ≤q≤9973時,存在一個最優(72q,9,1)-OOC.

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