林麗英，鄭鷺亮，張勝元

(1.福建信息職業(yè)技術(shù)學(xué)院基礎(chǔ)部，福建福州350007;2.福建醫(yī)科大學(xué)基礎(chǔ)醫(yī)學(xué)院，福建福州350001;3.福建師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建福州350007)

0 引言

在雷達(dá)、聲納、碼分多址等系統(tǒng)的信號(hào)設(shè)計(jì)中，往往要求信號(hào)具有良好的自相關(guān)性，這樣的信號(hào)稱為最佳信號(hào).傳統(tǒng)的信號(hào)設(shè)計(jì)使用單條序列，即發(fā)送端發(fā)送的信號(hào)序列與接收端中計(jì)算自相關(guān)函數(shù)所使用的本地序列是同一個(gè)信號(hào)序列.基于具有優(yōu)的自相關(guān)性的的理想序列在雷達(dá)、聲納、碼分多址等系統(tǒng)的信號(hào)設(shè)計(jì)中有著重要的應(yīng)用，因此序列設(shè)計(jì)一直也是應(yīng)用數(shù)學(xué)、編碼理論領(lǐng)域?qū)W者所研究的熱點(diǎn).最佳二元序列是最理想的信號(hào)，但是最佳信號(hào)的存在空間非常有限.Wolfman于1992年在文獻(xiàn)［1］中提出了幾乎最佳二元序列的概念，在這種定義下序列數(shù)量大大增加，但是對(duì)于序列長(zhǎng)度n還有比較多的限制，如要求n是4的倍數(shù).之后，人們對(duì)此進(jìn)行了大量的探討:Pott等于1995年在文獻(xiàn)［2］中建立了幾乎最佳二元序列與一類特殊可分差集的等價(jià)關(guān)系，大大增加序列的存在空間;鄭鷺亮等在文獻(xiàn)［3］中改進(jìn)了幾乎差集的定義，并利用4階分圓類構(gòu)造廣義幾乎差集;趙曉群等在文獻(xiàn) ［4］中提出一類新的最佳信號(hào)——最佳二元序列偶，利用這種序列偶，可以在系統(tǒng)發(fā)送端選取序列偶中的一條序列作為傳送信號(hào)，而用序列偶中的另一條序列作為接收端的本地序列，通過計(jì)算序列偶的自相關(guān)函數(shù)來達(dá)到提取信息的目的;最佳二元序列偶對(duì)應(yīng)的組合結(jié)構(gòu)為差集偶［5］，李建周等在文獻(xiàn) ［6］中提出新的區(qū)組設(shè)計(jì)——幾乎差集偶，并證明了幾乎差集偶與幾乎最佳自相關(guān)二元序列偶的等價(jià)關(guān)系.但從現(xiàn)有的研究成果看，具有好的相關(guān)性的序列偶的存在性結(jié)果還不是很豐富.本文首先在廣義幾乎差集和差集偶基礎(chǔ)上，提出廣義幾乎差集偶概念.其對(duì)應(yīng)的序列偶是最佳二元序列偶的推廣，然后利用2階和4階分圓類構(gòu)造了一些廣義幾乎差集偶的類，這將為實(shí)際工程應(yīng)用提供更大的信號(hào)序列選擇范圍.

1 廣義幾乎差集偶的概念

定義2［3］設(shè)ZN={0，1，…，N-1}為模N剩余類環(huán)，D為ZN的一個(gè)k元子集.設(shè)N為奇數(shù)，如果對(duì)(N-1)/2個(gè)非零元a∈ZN，同余方程x-y≡a∈(mod N)，x，y∈D×D恰有個(gè)λ1解，而對(duì)其余(N-1)/2個(gè)非零元該同余方程恰有λ2個(gè)解，則稱D為一個(gè)(N，k，λ1，λ2)廣義幾乎差集.

結(jié)合定義1和定義2，給出定義3.

以下把 (N，k1，k2，l，λ1，λ2)廣義幾乎差集偶記為 (N，k1，k2，l，λ1，λ2)-GADSP.

例1 在 Z5中，U={1，2}，V={4}構(gòu)成 (5，2，1，0，1，0)-GADSP.

當(dāng)U=V時(shí)，廣義幾乎差集偶退化為廣義幾乎差集;當(dāng)λ1=λ2時(shí)，廣義幾乎差集偶就退化為通常的差集偶.由于廣義差集和差集偶都是廣義差集偶的特殊情形，因此本文只對(duì)U≠V、λ1≠λ2的情況進(jìn)行研究.

2 用分圓方法構(gòu)造廣義幾乎差集偶

以下介紹有關(guān)分圓的一些基本概念［7］.

設(shè)N=ef+1是一個(gè)奇素?cái)?shù)，此時(shí)ZN構(gòu)成域.設(shè)θ是域ZN的一個(gè)本原元，D0=＜θe＞為由θe生成的的f階乘法子群，則有以下陪集分解:其中Di= θiD0，0≤i≤e-1，稱陪集Di為分圓類.

下面先考慮2階分圓類能否構(gòu)成廣義幾乎差集偶，先給出2階分圓數(shù).

1)當(dāng)f為偶數(shù)時(shí)，這些分圓數(shù)關(guān)系由表1給出.其中A=f/2，B=(f-2)/2.

表12 階分圓數(shù)關(guān)系表 (f為偶數(shù))Tab.1 The relations of the cyclotomic numbers of order 2(f even)

表2 2階分圓數(shù)關(guān)系表 (f為奇數(shù))Tab.2 Relations of the cyclotomic numbers of order 2(f odd)

定理1 設(shè)奇素?cái)?shù)N=2f+1，U=D0，V=D1，則:1)當(dāng)f為偶數(shù)時(shí)，(U，V)(U，V)不構(gòu)成任何形式下的廣義幾乎差集偶;2)當(dāng) f為奇數(shù)時(shí)，(U，V)構(gòu)成 ZN上 (2f+1，f，f，0，(f+1)/2，(f-1)/2)-GADSP.

1)當(dāng)f為偶數(shù)時(shí)，由表1可得Δ0=A=f/2，Δ1=A=f/2.由于Δ0=Δ1，(U，V)構(gòu)成ZN上的一個(gè)差集偶.

2)當(dāng)f為奇數(shù)時(shí)，由表2可得Δ0=B= ( f +1)/2，Δ1=A= ( f -1)/2.由于Δ0≠Δ1，根據(jù)定義3，取λ1=Δ0，λ2=Δ1，又因?yàn)棣?-λ2=Δ0-Δ1=B-A=1，從而(U，V)可構(gòu)成ZN上的一個(gè)廣義幾乎差集偶，經(jīng)過計(jì)算參數(shù)可知，(U，V)構(gòu)成ZN上的(2f+1，f，f，0，(f+1)/2，(f-1)/2)-GADSP.

例2 令 f=3 ，U=D0={2，4，1}，V=D1={6，5，3}構(gòu)成 (7，3，3，0，2，1)-GADSP.

用同樣方法可以證明定理2.

定理2 設(shè)奇素?cái)?shù) N=2f+1 ，U=D0∪ D1，V=D0，則 (U，V)構(gòu)成 ZN上的 (2f+1，2f，f，f，f，f-1)-GADSP.

例3 令 f=3 ，U=D0∪D1={2，4，1，6，5，3}，V=D0={2，4，1}構(gòu)成 (7，6，3，3，3，2)-GADSP.

以下考慮利用4階分圓類構(gòu)造廣義幾乎差集偶，先給出4階分圓數(shù)，這些分圓數(shù)由奇素?cái)?shù)N=4f+1的分解式x2+4y2，x ≡1(mod 4)唯一決定［8］.

1)當(dāng)f是偶數(shù)時(shí)，這些分圓數(shù)關(guān)系由表3給出，其中:A=(N-11-6x)/16;B=(N-3+2x+8y)/16;C=(N-3+2x)/16;D=(N-3+2x-8y)/16;E=(N+1-2x)/16.

2)當(dāng)f是奇數(shù)時(shí)，這些分圓數(shù)關(guān)系由表4給出，其中:A=(N-7+2x)/16;B=(N+1+2x-8y)/16;C=(N+1-6x)/16;D=(N+1+2x+8y)/16;E=(N-3-2x)/16.

當(dāng)e=4時(shí)，可以得出定理3.

表3 4階分圓數(shù)關(guān)系表 (f為偶數(shù))Tab.3 The relations of the cyclotomic numbers of order 4(f even)

表4 4階分圓數(shù)關(guān)系表 (f為奇數(shù))Tab.4 The relations of the cyclotomic numbers of order 4(f odd)

定理3 設(shè)奇素?cái)?shù)N=4f+1=x2+4y2，x≡1(mod 4)，U=D0，V=D2，則:1)當(dāng)f為偶數(shù)時(shí)，(U，V)構(gòu)成 ZN上的 (4f+1，f，f，0，(f+2h)/4，(f-2h)/4)-GADSP ，當(dāng)且僅當(dāng) h=( x -1)/4且x≠1;2)當(dāng)f為奇數(shù)時(shí)，(U，V)不構(gòu)成任何形式下的廣義幾乎差集偶.

1)當(dāng)f為偶數(shù)時(shí)，由表3可得:Δ0=C=(N-3+2x)/16;Δ1=E=(N+1-2x)/16;Δ2=C=(N-3+2x)/16;Δ3=E=(N+1-2x)/16.

顯然Δ0=Δ2，Δ1=Δ3.當(dāng)x=1時(shí)，Δ0=Δ3，(U，V)就可構(gòu)成ZN上的一個(gè)差集偶.當(dāng)x≠1時(shí)，Δ0≠Δ3，(U，V)就可構(gòu)成ZN上的一個(gè)廣義幾乎差集偶.根據(jù)定義3，取λ1=Δ0，λ2=Δ1，由于λ1-λ2=Δ0-Δ1=C-E=(x-1)/4，令h=(x-1)/4.經(jīng)過計(jì)算參數(shù)可知，(U，V)構(gòu)成ZN上的一個(gè) (4f+1，f，f，0，(f+2h)/4，(f-2h)/4)-GADSP.

綜上所得，當(dāng) f為偶數(shù)時(shí)，(U，V)構(gòu)成 ZN上的 (4f+1，f，f，0，(f+2h)/4，(f-2h)/4)-GADSP 當(dāng)且僅當(dāng)h=(x-1)/4且x≠1.

2)當(dāng)f為奇數(shù)時(shí)，由表4可得:Δ0=C=(N+1-6x)/16;Δ1=D=(N+1+2x+8y)/16;Δ2=A=(N-7+2x)/16;Δ3=B=(N+1+2x-8y)/16.下面分3種情形討論.

情形1.當(dāng)Δ0=Δ1，Δ2=Δ3時(shí)，可得x=-1，y=1，與x≡1(mod 4)矛盾.

情形2.當(dāng)Δ0=Δ2，Δ1=Δ3時(shí)，可得y=0，與N=4f+1=x2+4y2是奇素?cái)?shù)矛盾.

情形3.當(dāng)Δ0=Δ3，Δ1=Δ2時(shí)，可得x=-1，y=-1，與x≡1(mod 4)矛盾.

綜上所述，當(dāng)f為奇數(shù)時(shí)，(U，V)不構(gòu)成ZN上任何形式的廣義幾乎差集偶.

例4 令f=10，x=5，y=2時(shí)，U=D0={±18，±4，±10，±16，±1}，V=D2={±20，±9，± 2，± 5，± 8}構(gòu)成 (41，10，10，0，3，2)-GADSP.

利用4階分圓類還可以構(gòu)造更多的廣義幾乎差集偶，以下列出這些廣義幾乎差集偶，并略去計(jì)算過程.

定理4 設(shè)奇素?cái)?shù)N=4f+1=x2+4y2，x≡1(mod 4)，U=D0∪D2，V=D1，則:1)當(dāng)f為偶數(shù)時(shí)，(U，V)構(gòu)成 ZN上的 (4f+1，2f，f，0，(f+h)/2，(f-h)/2)-GADSP 當(dāng)且僅當(dāng) y=(x-1)/2，h=y或 y=(1-x)/2，h=y;2)當(dāng) f為奇數(shù)時(shí)，(U，V)構(gòu)成 ZN上的 (4f+1，2f，f，0，(f+h)/2，(f-h)/2)-GADSP當(dāng)且僅當(dāng)y=(1+x)/2，h=-y或 y=(-1-x)/2，h=-y.

例5 令f=10，x=5，y=2時(shí)，U=D0∪D2={±18，±4，±10，±16，±1，±20，±9，±2，± 5，± 8}，V=D1={± 3，± 13，± 12，± 11，± 7}構(gòu)成 (41，20，10，0，6，4)-GADSP.

例6 令 f=3 ，x=-3，y=1 時(shí)，U=D0∪D2={3，9，1，12，10，4}，V=D1={6，5，2}構(gòu)成 (13，6，3，0，2，1)-GADSP

定理5 設(shè)奇素?cái)?shù)N=4f+1=x2+4y2，x≡1(mod 4)，U=D0∪D2，V=D3，則:1)當(dāng)f為偶數(shù)時(shí)，(U，V)構(gòu)成 ZN上的 (4f+1，2f，f，0，(f+h)/2，(f-h)/2)-GADSP 當(dāng)且僅當(dāng) y=(x-1)/2，h=-y 或 y=(1-x)/2，h=-y;2)當(dāng) f為奇數(shù)時(shí)，(U，V)構(gòu)成 ZN上的 (4f+1，2f，f，0，(f+h)/2，(f-h)/2)-GADSP當(dāng)且僅當(dāng)y=(1+x)/2，h=y或 y=(-1-x)/2，h=y.

定理6 設(shè)奇素?cái)?shù)N=4f+1=x2+4y2，x≡1(mod 4)，U=D0∪D3，V=D1∪D2，則:1)當(dāng) f為偶數(shù)時(shí)，(U，V)構(gòu)成 ZN上的 (4f+1，2f，2f，0，(2f+h)/2，(2f-h)/2)-GADSP 當(dāng)且僅當(dāng) h=y;2)當(dāng)f為奇數(shù)時(shí)，(U，V)不構(gòu)成任何形式的廣義幾乎差集偶.

例7 令f=4，x=1，y=2時(shí)，U=D0∪D3={±1，±4，±6，±7}，V=D1∪D2={±3，± 5，± 2，± 8}構(gòu)成 (17，8，8，0，5，3)-GADSP

定理7 設(shè)奇素?cái)?shù)N=4f+1=x2+4y2，x≡1(mod 4)，U=D0∪D1∪D2，V=D0∪D2∪D3，則:1)當(dāng) f為偶數(shù)時(shí)，(U，V)構(gòu)成 ZN上的 (4f+1，3f，3f，2f，(9f-2+2h)/4，(9f-2-2h)/4)-GADSP當(dāng)且僅當(dāng)h=(-3-x)/4，x≠-3;2)當(dāng)f為奇數(shù)時(shí)，(U，V)不構(gòu)成任何形式的廣義幾乎差集偶.

例8 令f=4，且x=1，y=2時(shí)，U=D0∪D1∪D2={±1，±4，±3，±5，±2，±8}，V=D0∪ D1∪ D3={± 1，± 4，± 3，± 5，± 6，±7}構(gòu)成 (17，12，12，8，8，9)-GADSP.

3 小結(jié)

本文首先在廣義幾乎差集和幾乎差集偶基礎(chǔ)上，提出廣義幾乎差集偶概念.其對(duì)應(yīng)的序列偶是最佳二元序列偶的推廣.然后利用2階和4階分圓類構(gòu)造了一些廣義幾乎差集偶的類，這將為實(shí)際工程應(yīng)用提供更大的信號(hào)序列選擇范圍.進(jìn)一步考慮6階分圓情形還可能得到一些廣義幾乎差集偶的類，然而其計(jì)算將變得更加復(fù)雜.

［1］ WOLFMANN J.Almost perfect autocorrelation sequence ［J］.IEEE Trans on Information Theory，1992，38(4):1412-1418.

［2］ BRADLEY S P，POTT A.Existence and nonexistence of almost-perfect autocorrelation sequences［J］.IEEE Trans on Information Theory，1995，41(1):301-304.

［3］鄭鷺亮，林麗英，張勝元.廣義幾乎差集［J］.福建師范大學(xué)學(xué)報(bào):自然科學(xué)版，2011，27(1):26-29.

［4］趙曉群，王仲文，賈世樓.最佳二進(jìn)陣列偶理論研究 ［J］.電子學(xué)報(bào)，1999，27(1):34-37.

［5］許成謙.差集偶與最佳二進(jìn)陣列偶的組合研究方法 ［J］.電子學(xué)報(bào)，2001，29(1):87-89.

［6］李建周，柯品惠.幾乎差集偶與幾乎最佳自相關(guān)二元序列偶的研究 ［J］.武夷學(xué)院學(xué)報(bào)，2008，27(2):10-14.

［7］沈?yàn)?組合設(shè)計(jì)理論［M］.上海:上海交通大學(xué)出版社，2008:108-110.

［8］ DING C.Binary cyclotomic generators［J］.Lecture Notes in Computer Science，1995，1008:29-60.