Ding-Helleseth-Martinsen序列的交織結(jié)構(gòu)和自相關(guān)分布

柯美儉，楊 波，肖自碧

(武漢科技大學(xué)理學(xué)院，湖北 武漢，430065)

具有最優(yōu)自相關(guān)性質(zhì)的偽隨機(jī)二元序列廣泛應(yīng)用于工程領(lǐng)域，如雷達(dá)測(cè)距、流密碼和通信系統(tǒng)等[1]。對(duì)于周期為N的二元序列a，根據(jù)N模4的剩余，其異相自相關(guān)的最優(yōu)值分為四類(lèi)[2]：(1)N≡0(mod 4)，Ra(τ)∈{0,-4}或{0,4}；(2)N≡1(mod 4)，Ra(τ)∈{1,-3}；(3)N≡2(mod 4)，Ra(τ)∈{2,-2}；(4)N≡3(mod4)，Ra(τ)∈{-1}。滿足條件(4)的二元序列稱為理想二值自相關(guān)序列。此外，若N≡0(mod 4)，Ra(τ)∈{0,±4}，則二元序列a稱為具有最優(yōu)自相關(guān)絕對(duì)值的序列[2-4]。

利用交織技術(shù)構(gòu)造最優(yōu)自相關(guān)序列和低相關(guān)序列組是序列設(shè)計(jì)中的一種重要方法。序列的交織結(jié)構(gòu)由Gong[5]于1995年提出，并用于設(shè)計(jì)低相關(guān)序列[4]和序列集[6]。在密碼和通信系統(tǒng)中廣泛使用的周期為22k-1的m序列、推廣的GMW序列都可以采用交織方法構(gòu)造。2008年，Yu等[4]指出Arasu等構(gòu)造的幾乎差集序列也可以利用交織方法生成。之后，研究者通過(guò)選取適當(dāng)?shù)男蛄凶鳛榱行蛄羞M(jìn)行交織，即重新穿插排列，構(gòu)造出了一些具有最優(yōu)自相關(guān)性質(zhì)的新序列[2-3,7]。利用這些序列的交織結(jié)構(gòu)，研究者又發(fā)現(xiàn)它們還具有較高的線性復(fù)雜度[8-10]以及2-adic復(fù)雜度[11-13]。對(duì)交織序列的研究不僅有助于構(gòu)造更多適用于密碼和通信領(lǐng)域的新序列(集)以及分析序列的隨機(jī)性質(zhì)，而且有助于對(duì)序列結(jié)構(gòu)的深入理解，這是序列設(shè)計(jì)和分析領(lǐng)域的一個(gè)十分有意義的課題。

基于中國(guó)剩余定理和經(jīng)典四階分圓，Ding等[14]構(gòu)造了兩類(lèi)周期為2p的二元序列(稱為Ding-Helleseth-Martinsen序列)，p為素?cái)?shù)且p≡5(mod 8)，其中一類(lèi)是平衡的，另一類(lèi)是幾乎平衡的。當(dāng)參數(shù)滿足一定條件時(shí)，Ding-Helleseth-Martinsen序列的異相自相關(guān)值為{2,-2}。通過(guò)分析該序列的支撐集的特征，本文首先證明其具有p×2交織結(jié)構(gòu)，也就是說(shuō)，如果將序列的項(xiàng)排成一個(gè)p行2列的矩陣，即前兩項(xiàng)作為第一行，接下來(lái)的兩項(xiàng)作為第二行，以此類(lèi)推，那么該矩陣的兩列各自都是經(jīng)典四階分圓序列的移位序列或互補(bǔ)序列。在此基礎(chǔ)上，本文利用交織序列的自相關(guān)公式以及經(jīng)典四階分圓序列的相關(guān)函數(shù)值，計(jì)算得到所有Ding-Helleseth-Martinsen序列的精確自相關(guān)分布。

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

1.1 基本概念和記號(hào)

設(shè)a=(a(0),a(1),…,a(N-1))是周期為N的二元序列，稱集合{t|0≤t

設(shè)a=(a(0),a(1),…,a(N-1))是周期為N的二元序列，令L(a)=(a(1),…,a(N-1),a(0))，稱L是左循環(huán)移位算子。一般地，Lτ(a)=(a(τ),a(τ+1),…,a(τ+N-1))，其中0<τ

1.2 相關(guān)函數(shù)

定義1[2]設(shè)a=(a(0),a(1),…,a(N-1))和b=(b(0),b(1),…,b(N-1))是兩條周期為N的二元序列，a和b的互相關(guān)函數(shù)定義為

(1)

其中t+τ是模N加法。當(dāng)a=b時(shí)，稱Ra(τ)為a的自相關(guān)函數(shù)。

1.3 交織序列及相關(guān)函數(shù)計(jì)算公式

定義2[2]設(shè)ai=(ai(0),ai(1),…,ai(N-1))(0≤i

u=(a0(0),a1(0),…,aT-1(0),a0(1),…,

aT-1(1),…,a0(N-1),…,aT-1(N-1))。

為方便起見(jiàn)，這里用I表示交織運(yùn)算，記u=I(a0,a1,…,aT-1)，稱a0,a1,…,aT-1為序列u的列序列。

引理1[2]設(shè)u=I(a0,a1,…,aT-1)和v=I(b0,b1,…,bT-1)是兩條周期為NT的交織序列，其中ai=(ai(0),ai(1),…,ai(N-1))，bi=(bi(0),bi(1),…,bi(N-1))，0≤i

特別地，當(dāng)u=v時(shí)，有

(2)

1.4 經(jīng)典四階分圓及序列

定義3[15]設(shè)p≡1(mod 4)為素?cái)?shù)，g為模p的本原根，設(shè)

Di={gi+4j(modp)|j=0,1,…,

(3)

稱Di為模p的經(jīng)典四階分圓類(lèi)。將支撐集分別為D0∪D1、D0∪D2、D0∪D3、D1∪D2、D1∪D3和D2∪D3以及周期為p的二元平衡序列稱為經(jīng)典四階分圓序列，分別記作s1、s2、s3、s4、s5和s6，其中s1、s3、s4和s6即為Ding-Helleseth-Lam序列[15]，而s2和s5為L(zhǎng)egendre序列[16]。

1.5 Ding-Helleseth-Martinsen構(gòu)造

文獻(xiàn)[14]中構(gòu)造了兩類(lèi)周期為N=2p的二元序列，即Ding-Helleseth-Martinsen序列。第一類(lèi)是幾乎平衡的二元序列u，定義為

(4)

其中Cu={0}×C0∪{1}×C1。第二類(lèi)是平衡的二元序列v，定義為

(5)

其中Cv={0}×(C0∪{0})∪{1}×C1。

2 Ding-Helleseth-Martinsen序列的交織結(jié)構(gòu)

定理1設(shè)p=4f+1為素?cái)?shù)，則對(duì)任意(i,j,l)，式(4)和式(5)定義的周期為2p的二元序列u和v都具有p×2交織結(jié)構(gòu)，且

u=I(a,L2-1(b)),v=I(c+1,L2-1(b)),

其中a、b和c是周期為p并且支撐集分別為2-1C0、2-1C1和p({0}∪2-1C0)的二元序列。

證明：由于Cu={0}×C0∪{1}×C1，因此序列u的支撐集

{2t+1|2t+1(modp)∈C1}

={2t|t(modp)∈2-1C0}∪

{2t+1|t+2-1(modp)∈2-1C1}。

假設(shè)u=I(u0,u1)，則有

u1(i)=u(2i+1)

令

則有u1(i)=b(i+2-1)，這意味著u1=L2-1(b)。令a=u0，則得到u的交織結(jié)構(gòu)。

且v1(i)=b(i+2-1)。令c(i)=v0(i)+1，即序列c的支撐集為p(2-1C0∪{0})，于是序列v具有交織結(jié)構(gòu)v=I(c+1,L2-1(b))。

注1若2∈De，則2-1∈D-e，因此2-1C0=Di-e∪Dj-e且2-1C1=Dl-e∪Dj-e，也就是說(shuō)，a和b是支撐集分別為Di-e∪Dj-e和Dl-e∪Dj-e的經(jīng)典四階分圓序列。由于i、j和l是{0,1,2,3}中兩兩不同的整數(shù)，因此序列對(duì)(a,b)的所有可能選擇就是a=sh、b=sk，其中h≠k且h+k≠7。由于c的支撐集為p({0}∪2-1C0)=p({0}∪Di-e∪Dj-e)，故c也是六條經(jīng)典四階分圓序列之一。若設(shè)Di-e∪Dj-e的特征序列為sh，容易驗(yàn)證p({0}∪Di-e∪Dj-e)的特征序列為c=s7-h，則序列對(duì)(c,b)的所有可能選擇就是c=sh、b=sk，其中h≠k且h+k≠7，其原因是，如果h取遍集合{1,2,3,4,5,6}，那么7-h也取遍該集合。

推論1由式(4)和式(5)定義的二元序列u和v分別等價(jià)于下面的交織序列:

u=I(sh,L2-1(sk))且v=I(sh+1,L2-1(sk)),

其中sh和sk是兩條不同的經(jīng)典四階分圓序列(見(jiàn)定義3)，且h+k≠7。

3 Ding-Helleseth-Martinsen序列的自相關(guān)分布

在接下來(lái)的討論中，為了方便起見(jiàn)，將序列I(sh,L2-1(sk))和I(sh+1,L2-1(sk))分別記作uh,k和vh,k。根據(jù)引理1，計(jì)算交織序列uh,k和vh,k的自相關(guān)分布可以轉(zhuǎn)化為計(jì)算它們的列序列sh和sk的相關(guān)函數(shù)。

引理2設(shè)sh和sk為兩條不同的經(jīng)典四階分圓序列，其中h+k≠7。令τ=2τ1+τ2，其中0≤τ1

Ruh,k(τ)=

和

證明：由τ=2τ1+τ2，根據(jù)引理1中的式(2)，下面分兩種情況討論。

(i)若τ2=0，0<τ1

Ruh,k(τ)=Rsh,sh(τ1)+Rsk,sk(τ1)

=Rsh(τ1)+Rsk(τ1),

再由自相關(guān)函數(shù)的定義式(1)，得

Rvh,k(τ)=(-1)1+1Rsh(τ1)+Rsk(τ1)=Ruh,k(τ)。

(ii)若τ2=1，0≤τ1

Ruh,k(τ)=Rsh,sk(τ1+2-1)+Rsk,sh(τ1+1-2-1)。

由于τ1+1-2-1≡τ1+2-1(modp)，故

Ruh,k(τ)=Rsh,sk(τ1+2-1)+Rsk,sh(τ1+2-1)。

再由自相關(guān)函數(shù)的定義式(1)，得

Rvh,k(τ)=-Rsh,sk(τ1+2-1)-Rsk,sh(τ1+1-2-1)

=-Ruh,k(τ)。

注2由引理2可得Ruh,k(τ)=Ruk,h(τ)且Rvh,k(τ)=Rvk,h(τ)，事實(shí)上可以驗(yàn)證uk,h=Lp(uh,k)，這表明序列uh,k和uk,h是循環(huán)移位等價(jià)的，因此只需考慮滿足h

為了進(jìn)一步確定u和v的精確自相關(guān)分布，需要借助經(jīng)典四階分圓序列相關(guān)函數(shù)值的結(jié)論。

引理3[17]設(shè)p≡5(mod 8)為素?cái)?shù)且p=x2+4y2，其中x≡1(mod 4)。六條經(jīng)典四階分圓序列的自相關(guān)函數(shù)值以及sh和sk的互相關(guān)函數(shù)值在表1中給出，這里1≤h

表1 六條周期為p=4f+1的二元序列的相關(guān)函數(shù)值(f為奇數(shù))

注3當(dāng)p≡5(mod 8)時(shí)，2是模p的一個(gè)平方非剩余，因此2∈D1或D3。這里取模p的一個(gè)適當(dāng)?shù)谋驹?，使?∈D3，必有y≡1(mod 4)。

下面通過(guò)引理2中的公式計(jì)算u1,3的異相自相關(guān)分布。當(dāng)τ=2τ1且0<τ1≤p-1時(shí)，由表1給出的s1和s3的自相關(guān)函數(shù)值可得

Ru1,3(τ)=Rs1(τ1)+Rs3(τ1)=-2。

當(dāng)τ=2τ1+1且0<τ1≤p-1時(shí)，則有

Ru1,3(τ)=Rs1,s3(τ1+2-1)+Rs3,s1(τ1+2-1)。

令τ1+2-1=τ′，由引理3可知，對(duì)每個(gè)τ′∈Di和ω∈Di+2有

Rs1,s3(τ′)+Rs3,s1(τ′)=Rs1,s3(τ′)+Rs1,s3(ω)

(6)

由于對(duì)每個(gè)τ′∈D0∪D2，有ω∈D2∪D0，對(duì)每個(gè)τ′∈D1∪D3，有ω∈D3∪D1，將表1中給出的互相關(guān)值代入式(6)，即得式(7)：

Ru1,3(τ)=Rs1,s3(τ′)+Rs3,s1(τ′)

=Rs1,s3(τ′)+Rs3,s1(ω)

(7)

于是序列u1,3精確的自相關(guān)分布就得以確定。

注意到由引理3有Rs1(τ)=Rs6(τ)、Rs3(τ)=Rs4(τ)且Rs1,s3(τ)=Rs4,s6(τ)，因此，根據(jù)引理2可得Ru1,3(τ)=Ru4,6(τ)，這意味著序列I(s1,L2-1(s3))和I(s4,L2-1(s6))的自相關(guān)分布相同。通過(guò)類(lèi)似計(jì)算可以確定相應(yīng)于(h,k)不同取值的其他序列的自相關(guān)分布，結(jié)果由下面的定理給出。

定理2設(shè)p≡5(mod 8)為素?cái)?shù)且p=x2+4y2，其中x≡1(mod 4)，則周期為2p的交織序列uh,k=I(sh,L2-1(sk))，1≤h

再由引理2知，若τ=2τ1，Rvh,k(τ)=Ruh,k(τ)，若τ=2τ1+1，Rvh,k(τ)=-Ruh,k(τ)，因此，序列vh,k=I(sh+1,L2-1(sk))的自相關(guān)分布可以由定理2的結(jié)果得到。

4 結(jié)語(yǔ)

本文證明了Ding-Helleseth-Martinsen序列具有p×2交織結(jié)構(gòu)，進(jìn)而利用交織序列的自相關(guān)公式和經(jīng)典四階分圓序列的相關(guān)函數(shù)值，計(jì)算得到了所有Ding-Helleseth-Martinsen序列的精確的自相關(guān)分布。計(jì)算結(jié)果顯示，所有Ding-Helleseth-Martinsen序列的異相自相關(guān)絕對(duì)值相對(duì)于其周期都較小，即都具有低自相關(guān)性。