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

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

（1.燕山大學信息科學與工程學院，河北 秦皇島 066004；2.河北省信息傳輸與信號處理重點實驗室，河北 秦皇島 066004；3.燕山大學電氣工程學院，河北 秦皇島 066004)

1 引言

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

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

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

2 基本概念及引理

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

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

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

定義2令u′和v′是2 個周期為N的幾乎二元序列，則序列對u′和v′的周期互相關函數定義為

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

定義4令Ni表示序列u′和v′互相關取值為i時的數量，定義為

定義5設N=4f+1為奇素數，α是有限域GF(N)上的本原元，令

則稱Di為GF(N)上的四階分圓類。令

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

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

當f為奇數時，Z N上的四階分圓數的關系如式(7)所示，ZN四階分圓類的5 個基本分圓數如表1 所示。

表1 f 為奇數時，Z N四階分圓類的5 個基本分圓數

當f為偶數時，Z N上的四階分圓數的關系如式(8)所示，四階分圓類的5 個基本分圓數如表2 所示。

表2 f 為偶數時，ZN四階分圓類的5 個基本分圓數

引理2[22]對于素數N=4f+1，則分圓數和式滿足

3 平衡（幾乎）二元序列的相關界限

引入一個0 元素后，新生成的幾乎二元序列對的相關值會發生變化，所以本節首先對（幾乎）二元序列對的互相關值和幾乎二元序列的自相關值進行證明。

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

證明令和v′的互相關函數值可以計算為

證明當u′=v′時，引理5 是引理3 的特殊情況，根據引理3 可知引理5 結論成立。證畢。

通過引理3 可知，當2 條序列都為平衡幾乎二元序列時，2 條序列的最大互相關值的最小值為θc=1，這時稱平衡幾乎二元序列對為平衡最優互相關的I 型?幾乎二元序列對。為了獲取更多滿足應用需求的幾乎二元序列對，本文對θc=3的平衡幾乎二元序列對的理論界及構造方法進行了研究，這時稱平衡幾乎二元序列對為平衡幾乎最優互相關的I 型?幾乎二元序列對。通過引理4 可知，當一條序列為平衡幾乎二元序列，另一條序列為平衡二元序列時，2 條序列的最大互相關值θc的最小值為θc=2，這時稱平衡幾乎二元序列對為平衡最優互相關的II型?幾乎二元序列對。

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

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

表3 幾乎二元序列對的互相關值分布情況

其他情況可按類似方法分析得到。證畢。

接下來，基于表3 中列出的3 種類型的具有平衡（幾乎）最優互相關的幾乎二元序列對互相關函數值及其分布情況，分別給出3 種類型的幾乎二元序列的自相關函數理論界。

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

證明 定理3 的證明與定理1 證明類似。

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

4 平衡 (幾乎)最優幾乎二元序列對構造

本節將分別給出滿足定義6 的周期為素數N=4f+1的平衡最優幾乎二元序列對和平衡幾乎最優幾乎二元序列對的構造方法。

定理4令為一奇素數，其中，f為整數，y為整數 。當幾乎二元序列對u′和v′、u′和v、u和v′的其他參數滿足表4 所示要求時，得到的序列對為平衡最優幾乎二元序列對或平衡幾乎最優幾乎二元序列對。

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

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

根據分圓數的定義（見式(6)），將上式轉換成分圓數的形式，并根據引理2 進行化簡可得

與計算u′和v′的互相關函數值方法類似，可得u′和v′的自相關函數值分別為

類似地，當x=-1 時，也可得到u′和v′為平衡最優幾乎二元序列對；當x=±3 時,u′和v′為平衡幾乎最優幾乎二元序列對；當取x=1時，u′和v或u和v′為平衡最優幾乎二元序列對。

顯然，當N=37時有θc=1和θa=7滿足引理6的要求和定理1 的下界值，可知得到的序列對u′和v′為平衡最優幾乎二元序列對。而對于相同周期長度，通過文獻[20]的方法得到θc=3和θa=7，可知在相同θ a值情況下本文得到的序列對的θ c更小。

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

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

5 結束語

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

表5 現有的平衡（幾乎）最優幾乎二元序列對的比較