一類周期為偶數的二元序列的自相關值*

熊 臻,岳 勤

(南京航空航天大學理學院,江蘇 南京 211106)

1 引言

偽隨機序列，特別是以具有良好的自相關性的差集和幾乎差集為特征集的序列,在偽碼測距、導航、定位系統、碼分多址系統、雷達系統、擴頻通信系統和流密碼中均有廣泛的應用。因為當序列的自相關值低且個數少時,序列的穩定性較強,抗干擾能力增強,所以構造差集、幾乎差集和低自相關值的二元序列一直是學者們的研究熱點,具體參見文獻[1-14]。

文獻[2]構造了周期為孿生素數乘積的二階二元序列,且該序列的特征集為差集;文獻[3]推廣了文獻[2]的結果,構造了周期為任意兩個奇素數乘積的二階二元分圓序列,并且得出該序列的特征集為差集;在文獻[5]中,Ding等引進了幾乎差集的概念,并給出了周期為奇數的幾類幾乎差集;文獻[7]第一次給出了周期為pq(p,q均為奇數)的二階二元分圓序列,且該序列具有高線性復雜度和好的自相關性質;文獻[8]利用分圓法構造了幾個周期為2p的幾乎差集;在文獻[9]中,Hu等利用分圓法構造了幾個周期為pq的具有良好自相關性的序列;在文獻[13]中,Tang等利用Gray映射構造了具有最優自相關值的幾乎平衡的二元序列。

目前,構造具有良好自相關性的偶數周期序列仍然是比較困難的。 對于二元偶數周期序列如何使其自相關值少且低,這是本文的研究重點。 序列的構造方法有很多,如用分圓的方法構造分圓序列、基于Gray映射和組合理論構造序列等,而本文是利用ZN上的差集和幾乎差集,這種比分圓集合更廣義的一類集合,設計出具有4值或者6值的、周期為2N或者4N的二元序列,并使其達到最優或幾乎最優,這是與文獻[8,9,13]不同的地方。 在第3節末尾處,本文還給出了一類特殊序列的線性復雜度的算法。

2 相關概念

本文中,|·|表示集合含有的元素個數,?表示空集。

設ZN為模N的剩余類環,定義C0和C1是ZN的子集,滿足C0∪C1=ZN且C0∩C1=?。關于域F2上的序列s={si},i≥0,定義如下:

此時集合C1稱為{si}的特征集合;二元序列{si}被認為是C1的特征序列。

定義1[1]二元序列s=(s0,s1,…,sn,…),(si∈F2)叫做是周期序列,是指存在N≥0和l≥0,使得sn+l=sn(當n≥N時)。

滿足此條件的最小正整數l叫做該序列的周期。

定義2[3]設D是ZN的一個子集,k為集合D中元素的個數,即k=|D|。 若ZN中的任意非零元在差表{r-r′|r≠r′,r∈D,r′∈D}中恰好出現λ次,則稱D為ZN上的(N,k,λ)-差集。

3 自相關值

設N為奇數,s為正整數。 由中國剩余定理知Z2sN?Z2s×ZN,為了方便描述約定Z2sN=Z2s×ZN。

給定一個周期為N的二元序列{si},序列在移動量ω處的自相關值定義為:

其中0≤ω≤N-1。

定義:

dC1(ω)=|(C1+ω)∩C1|,0≤ω≤N-1

其中C1+ω={x+ω:x∈C1}。

引理1[4]設序列{si}是C1的特征序列,那么有:

Cs(ω)=N-4(|C1|-dC1(ω))

其中0≤ω≤N-1。

Cs(ω1,ω2)=

Cs(ω1,ω2)=

這里6個值互不相等。

證明(1) 因為

由于D是差集,故可設：

|(D+ω2)∩D|=λ,ω2≠0

那么

于是：

dC1(ω1,ω2)=

根據引理1,可得到自相關值如下：

Cs(ω1,ω2)=

|D|(|D|-1)=λ(N-1)

則代入有:

(2) 如果D是幾乎差集,那么根據定義有:

同(1),可得到:

根據引理1,可得到自相關值如下:

Cs(ω1,ω2)=

由于N是奇數,故上面6個值互不相等。

證畢。

□

Cs(ω1,ω2)=

輪腿機構設計應滿足以下要求:結構簡單,可以快速靈活地實現單個輪腿的升降，從而穩定挖溝機車體姿態,保證挖溝機工作部件運行平穩、工作可靠.

Cs(ω1,ω2)=

這里6個值互不相等。

證明(1)

于是可以得到以下式子:

dC1(0,ω2)=2|(D+ω2)∩D|+

那么當D為差集時,其差函數為:

dC1(ω1,ω2)=

于是對應的自相關值為:

Cs(ω1,ω2)=

(2) 當D為幾乎差集時,結合定理1可得到差函數:

dD(ω1,ω2)=

于是對應的自相關值為:

Cs(ω1,ω2)=

由于N是奇數,故上面6個值互不相等。

證畢。

□

由于與定理1類似，故不再舉例。

定義序列{si}的線性復雜度Ls為生成序列{si}的最短線性反饋移位寄存器的長度,是二元序列的重要的密碼學特征,對信息具有預測性。 當一個二元序列的Ls達到周期的一半時,那么就認為該序列具有良好的線性復雜度性質。

如果{si}的周期是2kN(k∈N+),那么定義s2kN(x)=s0+s1x+…+s2kN-1x2kN-1。 根據文獻[5]知,{si}的線性復雜度是2kN-deg(gcd(x2kN-1,s2kN(x)))。 下面我們考慮周期為2N的一類序列。

s2N(x)=s0+s1x+…+s2N-1x2N-1=

βN-1+βN-2+…+β+1=0

□

綜上所述,當N是奇素數且N≡±3(mod 8)時,定理3中的二元序列的線性復雜度非常大,達到周期的一半，從而具有好的隨機特性或不可預知性。 例4涉及的二元序列可以用相似的方法求解線性復雜度。

4 應用

為了方便讀者理解,本節將給出具體的例子,供讀者參考。 由于Z2N和Z4N類似,為了計算簡便,只分析Z2N上的情況。

因為5是奇素數,且5≡-3(mod 8),所以該序列的線性復雜度為6,達到周期一半。

5 結束語

具有良好自相關性的周期序列在眾多領域都有著廣泛的應用。 本文研究了兩類周期為2N或4N的二元序列(N為奇數),并且計算了自相關值。 結果表明，這些序列的自相關值是4值或6值,如果去掉某些特定的點,自相關值最優或幾乎最優。 能否考慮周期為2tN(t≥3,t∈Z+)的二元序列的自相關值的情況？這個問題留給讀者思考和研究。