一類周期為偶數(shù)的二元序列的自相關(guān)值*

熊 臻,岳 勤

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

1 引言

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

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

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

2 相關(guān)概念

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

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

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

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

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

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

3 自相關(guān)值

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

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

其中0≤ω≤N-1。

定義:

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

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

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

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

其中0≤ω≤N-1。

Cs(ω1,ω2)=

Cs(ω1,ω2)=

這里6個值互不相等。

證明(1) 因為

由于D是差集,故可設(shè)：

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

那么

于是：

dC1(ω1,ω2)=

根據(jù)引理1,可得到自相關(guān)值如下：

Cs(ω1,ω2)=

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

則代入有:

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

同(1),可得到:

根據(jù)引理1,可得到自相關(guān)值如下:

Cs(ω1,ω2)=

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

證畢。

□

Cs(ω1,ω2)=

輪腿機構(gòu)設(shè)計應(yīng)滿足以下要求:結(jié)構(gòu)簡單,可以快速靈活地實現(xiàn)單個輪腿的升降，從而穩(wěn)定挖溝機車體姿態(tài),保證挖溝機工作部件運行平穩(wěn)、工作可靠.

Cs(ω1,ω2)=

這里6個值互不相等。

證明(1)

于是可以得到以下式子:

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

那么當(dāng)D為差集時,其差函數(shù)為:

dC1(ω1,ω2)=

于是對應(yīng)的自相關(guān)值為:

Cs(ω1,ω2)=

(2) 當(dāng)D為幾乎差集時,結(jié)合定理1可得到差函數(shù):

dD(ω1,ω2)=

于是對應(yīng)的自相關(guān)值為:

Cs(ω1,ω2)=

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

證畢。

□

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

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

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

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

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

□

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

4 應(yīng)用

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

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

5 結(jié)束語

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