周期為N≡1(mod4)的平衡最優(yōu)幾乎二元序列對(duì)

彭秀平，李紅曉，王仕德，林洪彬

（1.燕山大學(xué)信息科學(xué)與工程學(xué)院，河北 秦皇島 066004；2.河北省信息傳輸與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004；3.燕山大學(xué)電氣工程學(xué)院，河北 秦皇島 066004)

1 引言

具有優(yōu)良自相關(guān)特性的序列在線性系統(tǒng)參數(shù)識(shí)別、實(shí)時(shí)信道估計(jì)、均衡和同步等領(lǐng)域都有廣泛應(yīng)用[1]，另外一些應(yīng)用領(lǐng)域如對(duì)抗多徑干擾[2]、多載波碼分多址（CDMA,code-division multiple access）、正交頻分復(fù)用多址（OFDMA,orthogonal frequency division multiple access）、雷達(dá)和測(cè)距系統(tǒng)等不僅要求序列具備優(yōu)良的自相關(guān)特性，也需具備優(yōu)良的互相關(guān)特性[3]。為了給序列設(shè)計(jì)提供一個(gè)理論評(píng)判標(biāo)準(zhǔn)，國(guó)內(nèi)外學(xué)者對(duì)序列設(shè)計(jì)相關(guān)性的理論界限進(jìn)行了研究[4-6]，其中，Shedd 等[6]推導(dǎo)了周期自相關(guān)和互相關(guān)的理論界，并在周期自相關(guān)值和互相關(guān)值之間進(jìn)行了折中。Sarwate 界表明，不存在一組序列同時(shí)具有優(yōu)良自相關(guān)性和優(yōu)良互相關(guān)性以滿足不同的應(yīng)用需求。為此，國(guó)內(nèi)外學(xué)者主要致力于先設(shè)計(jì)自相關(guān)旁瓣值盡可能小的各類(lèi)序列，再研究它們的互相關(guān)性。當(dāng)序列的自相關(guān)函數(shù)旁瓣值全為0 時(shí)，稱(chēng)這樣的序列為最佳序列，然而現(xiàn)有的最佳二元序列僅存在長(zhǎng)度為4 的情況，最佳四元序列僅存在長(zhǎng)度為2、4、8 和16 的情況[7]。基于此，備受關(guān)注的是具有理想或優(yōu)良自相關(guān)特性的（幾乎）二元[8-9]和（幾乎）四元序列[10-11]及最佳多相序列[12-14]的構(gòu)造方法研究。由于最佳多相序列大量存在，目前研究得到了一些滿足Sarwate 界最優(yōu)的最佳多相序列集[13]。同時(shí)，由于二元和四元序列在實(shí)際應(yīng)用中實(shí)現(xiàn)簡(jiǎn)單，學(xué)者們對(duì)這些具有優(yōu)良自相關(guān)特性的二元[15-16]和四元序列[17]的互相關(guān)特性也進(jìn)行了大量研究，然而這些序列的互相關(guān)值并不能達(dá)到Sarwate 界的下界值。

為解決上述問(wèn)題，文獻(xiàn)[18]對(duì)平衡二元序列對(duì)的互相關(guān)值的理論界做了進(jìn)一步研究，以序列自相關(guān)值最優(yōu)為前提研究序列對(duì)互相關(guān)值的理論界，與Sarwate 界相比，提高了互相關(guān)理論下界值，并提出了周期為N≡1(mod4)的自相關(guān)值為{1,-3 }且滿足理論界的下界值為的平衡最優(yōu)二元序列對(duì)的構(gòu)造方法。在此思想的啟發(fā)下，文獻(xiàn)[19]對(duì)自相關(guān)模值為且周期為N≡1(mod4)的平衡四元序列對(duì)的互相關(guān)理論界進(jìn)行了研究，并得到了滿足理論界要求的理想四元序列對(duì)；文獻(xiàn)[20]從另一角度進(jìn)行了研究，當(dāng)二元序列對(duì)的互相關(guān)值滿足最優(yōu)值情況時(shí)，對(duì)周期為N≡1(mod4)且以互相關(guān)值{1,-3}為前提，對(duì)這類(lèi)序列對(duì)的自相關(guān)理論界進(jìn)行了研究，并得到了滿足自相關(guān)理論下界值的最優(yōu)二元序列對(duì)的構(gòu)造方法，但是得到的最優(yōu)二元序列對(duì)相當(dāng)有限，在周期N≤300內(nèi)，僅存在N=5,37,101,197這4 種情況。

為了獲得更多的最優(yōu)二元序列對(duì)，本文在文獻(xiàn)[20]的基礎(chǔ)上，通過(guò)在二元序列中引入一個(gè)0 元素，首先對(duì)（幾乎）二元序列對(duì)的互相關(guān)值和自相關(guān)值的取值情況進(jìn)行了討論，得出最大互相關(guān)值θ c分別為1、2、3 這3 種情況；其次以互相關(guān)值最優(yōu)（即θc=1,2）或幾乎最優(yōu)（即θc=3）的分布值情況為前提，推導(dǎo)出周期為N≡1(mod4)的平衡幾乎二元序列對(duì)的自相關(guān)函數(shù)值所滿足的理論界；最后基于四階分圓類(lèi)的方法，提出了滿足（幾乎）最優(yōu)互相關(guān)值和自相關(guān)理論界下界值的平衡（幾乎）最優(yōu)幾乎二元序列對(duì)的構(gòu)造方法。

2 基本概念及引理

定義1若周期為N的序列滿足式(1)。

為了便于描述，本文約定只考慮u(0)=-1 的情況，那么集合稱(chēng)為二元序列u的特征集，集合稱(chēng)為幾乎二元序列u'的特征集。序列u和u'分別稱(chēng)為集合U和U'的特征序列。

對(duì)于二元序列，如果N是奇數(shù)，則u是平衡的；對(duì)于幾乎二元序列，如果N是奇數(shù),則u'是平衡的。

定義2令u′和v′是2 個(gè)周期為N的幾乎二元序列，則序列對(duì)u′和v′的周期互相關(guān)函數(shù)定義為

定義 3令θc為序列u′和v′的最大互相關(guān)幅度值，θ a為序列u′和v′的最大異相自相關(guān)幅度值，分別定義為

定義4令Ni表示序列u′和v′互相關(guān)取值為i時(shí)的數(shù)量，定義為

定義5設(shè)N=4f+1為奇素?cái)?shù)，α是有限域GF(N)上的本原元，令

則稱(chēng)Di為GF(N)上的四階分圓類(lèi)。令

其中，Di+1代表集合代表和模N，則稱(chēng)（i,j）為基于GF(N)的四階分圓數(shù)。

引理1[21]設(shè)N=4f+1為奇素?cái)?shù)，其中f為正整數(shù)。N又可表示為N=4y2+x2，根據(jù)f的奇偶性和x≡1(mod4)或x≡3(mod4)的不同取值將四階分圓數(shù)進(jìn)行如下分類(lèi)。

當(dāng)f為奇數(shù)時(shí)，Z N上的四階分圓數(shù)的關(guān)系如式(7)所示，ZN四階分圓類(lèi)的5 個(gè)基本分圓數(shù)如表1 所示。

表1 f 為奇數(shù)時(shí)，Z N四階分圓類(lèi)的5 個(gè)基本分圓數(shù)

當(dāng)f為偶數(shù)時(shí)，Z N上的四階分圓數(shù)的關(guān)系如式(8)所示，四階分圓類(lèi)的5 個(gè)基本分圓數(shù)如表2 所示。

表2 f 為偶數(shù)時(shí)，ZN四階分圓類(lèi)的5 個(gè)基本分圓數(shù)

引理2[22]對(duì)于素?cái)?shù)N=4f+1，則分圓數(shù)和式滿足

3 平衡（幾乎）二元序列的相關(guān)界限

引入一個(gè)0 元素后，新生成的幾乎二元序列對(duì)的相關(guān)值會(huì)發(fā)生變化，所以本節(jié)首先對(duì)（幾乎）二元序列對(duì)的互相關(guān)值和幾乎二元序列的自相關(guān)值進(jìn)行證明。

引理3 令N≡1(mod4)，當(dāng)u′和v′為周期為N的平衡幾乎二元序列時(shí)，互相關(guān)值有以下3 種情況：3(mod4)。

證明令和v′的互相關(guān)函數(shù)值可以計(jì)算為

證明當(dāng)u′=v′時(shí)，引理5 是引理3 的特殊情況，根據(jù)引理3 可知引理5 結(jié)論成立。證畢。

通過(guò)引理3 可知，當(dāng)2 條序列都為平衡幾乎二元序列時(shí)，2 條序列的最大互相關(guān)值的最小值為θc=1，這時(shí)稱(chēng)平衡幾乎二元序列對(duì)為平衡最優(yōu)互相關(guān)的I 型?幾乎二元序列對(duì)。為了獲取更多滿足應(yīng)用需求的幾乎二元序列對(duì)，本文對(duì)θc=3的平衡幾乎二元序列對(duì)的理論界及構(gòu)造方法進(jìn)行了研究，這時(shí)稱(chēng)平衡幾乎二元序列對(duì)為平衡幾乎最優(yōu)互相關(guān)的I 型?幾乎二元序列對(duì)。通過(guò)引理4 可知，當(dāng)一條序列為平衡幾乎二元序列，另一條序列為平衡二元序列時(shí)，2 條序列的最大互相關(guān)值θc的最小值為θc=2，這時(shí)稱(chēng)平衡幾乎二元序列對(duì)為平衡最優(yōu)互相關(guān)的II型?幾乎二元序列對(duì)。

本文將采用式(10)和式(11)[23]證明θa的下界值。

引理6設(shè)u'和v'是幾乎二元序列，u是二元序列，且u'、v'和u均為周期為N≡（1 mod4)的平衡序列，則具有平衡最優(yōu)或平衡幾乎最優(yōu)互相關(guān)的I 型?幾乎二元序列對(duì)和具有平衡最優(yōu)互相關(guān)的II型?幾乎二元序列對(duì)的互相關(guān)值的分布情況如表3所示。

表3 幾乎二元序列對(duì)的互相關(guān)值分布情況

其他情況可按類(lèi)似方法分析得到。證畢。

接下來(lái)，基于表3 中列出的3 種類(lèi)型的具有平衡（幾乎）最優(yōu)互相關(guān)的幾乎二元序列對(duì)互相關(guān)函數(shù)值及其分布情況，分別給出3 種類(lèi)型的幾乎二元序列的自相關(guān)函數(shù)理論界。

定理1設(shè)u′和v′是周期為N≡1(mod4)且具有最優(yōu)互相關(guān)的平衡I 型?幾乎二元序列對(duì)，即θc=1，則序列u′和v′的最大異相自相關(guān)幅值滿足

證明 定理3 的證明與定理1 證明類(lèi)似。

定義6 設(shè)u′和v′是幾乎二元序列，u是二元序列，且u′、v′和u均為周期為N≡（1 mod4)的平衡序列，當(dāng)u′和v′為具有最優(yōu)互相關(guān)的平衡I 型?幾乎二元序列對(duì)且θa滿足式(12)下界值時(shí)，稱(chēng)u′和v′為平衡最優(yōu)幾乎二元序列對(duì)。當(dāng)u和v′為具有最優(yōu)互相關(guān)的平衡II 型?幾乎二元序列對(duì)且θ a滿足式(16)下界時(shí)，稱(chēng)u和v′為平衡最優(yōu)幾乎二元序列對(duì)。當(dāng)u′和v′為具有幾乎最優(yōu)互相關(guān)平衡I 型?幾乎二元序列對(duì)且θ a滿足式(17)下界值時(shí)，稱(chēng)u′和v'為平衡幾乎最優(yōu)幾乎二元序列對(duì)。

4 平衡 (幾乎)最優(yōu)幾乎二元序列對(duì)構(gòu)造

本節(jié)將分別給出滿足定義6 的周期為素?cái)?shù)N=4f+1的平衡最優(yōu)幾乎二元序列對(duì)和平衡幾乎最優(yōu)幾乎二元序列對(duì)的構(gòu)造方法。

定理4令為一奇素?cái)?shù)，其中，f為整數(shù)，y為整數(shù) 。當(dāng)幾乎二元序列對(duì)u′和v′、u′和v、u和v′的其他參數(shù)滿足表4 所示要求時(shí)，得到的序列對(duì)為平衡最優(yōu)幾乎二元序列對(duì)或平衡幾乎最優(yōu)幾乎二元序列對(duì)。

表4 滿足條件的平衡(幾乎)最優(yōu)幾乎二元序列對(duì)

證明以f為奇數(shù)，x=1，特征集合的平衡幾乎二元序列對(duì)為例進(jìn)行證明。首先考慮u′和v′的互相關(guān)，當(dāng)τ=0時(shí)，容易得到Ru′,v′(0)=0。當(dāng)τ≠ 0時(shí)，存在一個(gè)整數(shù)k(0≤k＜4)，使τ∈Dk，由于u′(0)v′(τ)+v′(0)u(N-τ)=0，則

根據(jù)分圓數(shù)的定義（見(jiàn)式(6)），將上式轉(zhuǎn)換成分圓數(shù)的形式，并根據(jù)引理2 進(jìn)行化簡(jiǎn)可得

與計(jì)算u′和v′的互相關(guān)函數(shù)值方法類(lèi)似，可得u′和v′的自相關(guān)函數(shù)值分別為

類(lèi)似地，當(dāng)x=-1 時(shí)，也可得到u′和v′為平衡最優(yōu)幾乎二元序列對(duì)；當(dāng)x=±3 時(shí),u′和v′為平衡幾乎最優(yōu)幾乎二元序列對(duì)；當(dāng)取x=1時(shí)，u′和v或u和v′為平衡最優(yōu)幾乎二元序列對(duì)。

顯然，當(dāng)N=37時(shí)有θc=1和θa=7滿足引理6的要求和定理1 的下界值，可知得到的序列對(duì)u′和v′為平衡最優(yōu)幾乎二元序列對(duì)。而對(duì)于相同周期長(zhǎng)度，通過(guò)文獻(xiàn)[20]的方法得到θc=3和θa=7，可知在相同θ a值情況下本文得到的序列對(duì)的θ c更小。

當(dāng)N=37，u′ 和v的特征 集合分別為U′=D0∪D1，V=D0∪D3時(shí)，可得θc=2，θa=7滿足引理6 的要求和定理2 的下界值，所以序列對(duì)u′和v為平衡最優(yōu)幾乎二元序列對(duì)。同樣與文獻(xiàn)[20]中方法得到的最優(yōu)二元序列對(duì)相比，在相同θ a值情況下本文得到的序列對(duì)的θ c更小。

當(dāng)N=13，u′和v′的特征集合為U′=D0∪D1，V'=D0∪D3時(shí)，可得θc=3，θa=3，滿足引理6 的要求和定理3 的下界值，所以u(píng)′和v′為平衡幾乎最優(yōu)幾乎二元序列對(duì)。其互相關(guān)最大值雖然與文獻(xiàn)[20]提出的界限相同，但是不再限定f為奇數(shù)，拓寬了最優(yōu)序列對(duì)的存在空間。

5 結(jié)束語(yǔ)

本文通過(guò)在二元序列基礎(chǔ)上引入一個(gè)0 元素的方式，首先對(duì)周期為N≡1(mod4)的兩類(lèi)（幾乎）二元序列對(duì)的互相關(guān)函數(shù)值的最小值進(jìn)行了研究，然后在此互相關(guān)值基礎(chǔ)上，對(duì)序列對(duì)中序列的自相關(guān)值的理論界進(jìn)行了研究，最后基于四階分圓類(lèi)，構(gòu)造了4 對(duì)滿足定理1～定理3 中理論界下界值的周期為N≡1(mod4)的平衡（幾乎）最優(yōu)相關(guān)特性的幾乎二元序列對(duì)。表5 列出了本文與目前已有的平衡最優(yōu)二元序列對(duì)在性能參數(shù)方面的對(duì)比情況。由表5可知，與文獻(xiàn)[18]相比，文獻(xiàn)[18]是在序列具有最優(yōu)自相關(guān)的前提下得到了序列對(duì)互相關(guān)滿足的理論界。與文獻(xiàn)[20]相比，雖然文獻(xiàn)[20]滿足最優(yōu)二元序列對(duì)的理論界，但是限定f為奇數(shù)，導(dǎo)致存在空間相當(dāng)有限，在N≤300內(nèi)僅存在周期為N=5,37,101,197這4 種情況，而本文將f的取值擴(kuò)展到任意整數(shù)可得到更多滿足理論界的序列對(duì)，同樣在N≤300的范圍內(nèi)，本文可得到的平衡（幾乎）最優(yōu)序列對(duì)周期為N=5,13,17,37,73,101,109,197,257這9 種情況，拓寬了序列存在空間。在文獻(xiàn)[20]中，只構(gòu)造了滿足θc=3的序列對(duì)，而在本文中，構(gòu)造了θc=1、θc=2和θc=3的3 種幾乎二元序列對(duì)，進(jìn)一步改善了序列相關(guān)性的同時(shí)也為實(shí)際工程應(yīng)用和通信系統(tǒng)提供了更多的可供選擇的序列對(duì)。

表5 現(xiàn)有的平衡（幾乎）最優(yōu)幾乎二元序列對(duì)的比較