柯美儉，楊 波，肖自碧

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

具有最優(yōu)自相關性質的偽隨機二元序列廣泛應用于工程領域，如雷達測距、流密碼和通信系統等[1]。對于周期為N的二元序列a，根據N模4的剩余，其異相自相關的最優(yōu)值分為四類[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)的二元序列稱為理想二值自相關序列。此外，若N≡0(mod 4)，Ra(τ)∈{0,±4}，則二元序列a稱為具有最優(yōu)自相關絕對值的序列[2-4]。

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

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

1 預備知識

1.1 基本概念和記號

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

設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 相關函數

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

(1)

其中t+τ是模N加法。當a=b時，稱Ra(τ)為a的自相關函數。

1.3 交織序列及相關函數計算公式

定義2[2]設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))。

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

引理1[2]設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

特別地，當u=v時，有

(2)

1.4 經典四階分圓及序列

定義3[15]設p≡1(mod 4)為素數，g為模p的本原根，設

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

(3)

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

1.5 Ding-Helleseth-Martinsen構造

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

(4)

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

(5)

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

2 Ding-Helleseth-Martinsen序列的交織結構

定理1設p=4f+1為素數，則對任意(i,j,l)，式(4)和式(5)定義的周期為2p的二元序列u和v都具有p×2交織結構，且

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}。

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

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

令

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

且v1(i)=b(i+2-1)。令c(i)=v0(i)+1，即序列c的支撐集為p(2-1C0∪{0})，于是序列v具有交織結構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，也就是說，a和b是支撐集分別為Di-e∪Dj-e和Dl-e∪Dj-e的經典四階分圓序列。由于i、j和l是{0,1,2,3}中兩兩不同的整數，因此序列對(a,b)的所有可能選擇就是a=sh、b=sk，其中h≠k且h+k≠7。由于c的支撐集為p({0}∪2-1C0)=p({0}∪Di-e∪Dj-e)，故c也是六條經典四階分圓序列之一。若設Di-e∪Dj-e的特征序列為sh，容易驗證p({0}∪Di-e∪Dj-e)的特征序列為c=s7-h，則序列對(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分別等價于下面的交織序列:

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

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

3 Ding-Helleseth-Martinsen序列的自相關分布

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

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

Ruh,k(τ)=

和

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

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

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

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

再由自相關函數的定義式(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)。

再由自相關函數的定義式(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(τ)，事實上可以驗證uk,h=Lp(uh,k)，這表明序列uh,k和uk,h是循環(huán)移位等價的，因此只需考慮滿足h

為了進一步確定u和v的精確自相關分布，需要借助經典四階分圓序列相關函數值的結論。

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

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

注3當p≡5(mod 8)時，2是模p的一個平方非剩余，因此2∈D1或D3。這里取模p的一個適當的本原根，使得2∈D3，必有y≡1(mod 4)。

下面通過引理2中的公式計算u1,3的異相自相關分布。當τ=2τ1且0<τ1≤p-1時，由表1給出的s1和s3的自相關函數值可得

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

當τ=2τ1+1且0<τ1≤p-1時，則有

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

令τ1+2-1=τ′，由引理3可知，對每個τ′∈Di和ω∈Di+2有

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

(6)

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

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

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

(7)

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

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

定理2設p≡5(mod 8)為素數且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))的自相關分布可以由定理2的結果得到。

4 結語

本文證明了Ding-Helleseth-Martinsen序列具有p×2交織結構，進而利用交織序列的自相關公式和經典四階分圓序列的相關函數值，計算得到了所有Ding-Helleseth-Martinsen序列的精確的自相關分布。計算結果顯示，所有Ding-Helleseth-Martinsen序列的異相自相關絕對值相對于其周期都較小，即都具有低自相關性。