Gold序列互相關(guān)性的新證明及非最大Gold序列性質(zhì)研究*

王玉東，劉春雷

(上海交通大學(xué) 數(shù)學(xué)系，上海200240)

0 引言

偽隨機(jī)序列，簡(jiǎn)稱(chēng)PN(Pseudo－Noise)序列，在現(xiàn)代擴(kuò)頻編碼理論中扮演著重要角色。常見(jiàn)的偽隨機(jī)序列有m序列，Gold序列，M序列，以及序列偶［1］等。其中Gold序列作為m序列的延伸，以其碼字?jǐn)?shù)量多、互相關(guān)性好等特點(diǎn)得到了廣泛的應(yīng)用，例如我國(guó)的北斗衛(wèi)星通信系統(tǒng)［2］。Gold序列以美國(guó)Magnavox實(shí)驗(yàn)室的工程師Robert Gold命名，他研究了一種特殊m序列優(yōu)選對(duì)的互相關(guān)性［3］，優(yōu)選對(duì)的采樣因子取為d=2k+1，滿(mǎn)足gcd(k，n)=1，其中n是對(duì)應(yīng)m序列的寄存器級(jí)數(shù)，且n為奇數(shù)，并且證明了這種優(yōu)選對(duì)的互相關(guān)系數(shù)為三值的，最大取值為+1。這是Gold序列得以應(yīng)用的理論基礎(chǔ)。1966年，Kasami將采樣因子的條件放寬至n/gcd(k，n)為奇數(shù)［4］，并證明了這時(shí)序列的自相關(guān)系數(shù)和互相關(guān)系數(shù)也都為三值的。此后，Niho，Welch以及 Dobbertin等人研究了采樣因子d取為其他值的情形［5－7］。

Kasami的證明將擴(kuò)頻碼視為循環(huán)碼，應(yīng)用了循環(huán)碼的理論。文中提供了一種從Gold序列和互相關(guān)系數(shù)的定義出發(fā)，利用有限域上跡函數(shù)(trace)性質(zhì)的直接證明方法，并去掉了采樣因子d=2k+1中k的任何限制條件。不過(guò)，當(dāng)k不滿(mǎn)足n/gcd(k，n)為奇數(shù)時(shí)，采樣得到的序列不是m序列，而是非最大的移位寄存器序列，因此這種情況下我們稱(chēng)之為非最大Gold序列。以下是文中的詳細(xì)證明。

1 基礎(chǔ)知識(shí)

一般通信中的序列，是指具有固定周期的0、1序列，即序列 a0a1a2a3…，滿(mǎn)足 ai∈{0，1}，以及對(duì)任意i，有ai=ai+N，其中N為序列的周期。實(shí)際應(yīng)用中要求這種序列必須滿(mǎn)足0、1平衡(即一個(gè)周期中0和1的數(shù)量幾乎一樣多)，以及具有良好的偽正交性等。評(píng)價(jià)序列的偽正交性常用序列的自相關(guān)函數(shù)和互相關(guān)函數(shù)。序列ai的自相關(guān)函數(shù)Pa(τ)以及相同周期的兩個(gè)序列ai和bi的互相關(guān)函數(shù)Pa，b(τ)分別定義如下:。除此之外，如果其他 Pa(τ)和(τ)的取值遠(yuǎn)小于 N，我們就稱(chēng)序列有好的自相關(guān)性和互相關(guān)性。這與數(shù)學(xué)上一組正交族的正交性的概念十分相似，因此也稱(chēng)為偽正交性。

以偽隨機(jī)序列中最常用的m序列為例。m序列，即最大線(xiàn)性移位寄存器序列，由線(xiàn)性反饋移位寄存器生成，具有生成方便、自相關(guān)性好等優(yōu)點(diǎn)。常見(jiàn)的m序列的定義是指滿(mǎn)足某種線(xiàn)性反饋條件的序列，不過(guò)在理論研究時(shí)，我們常用的是m序列的另一個(gè)定義，即用有限域上的跡函數(shù)得到的m序列的通項(xiàng)公式，定義如下:

由有限域的理論可知，α的特征多項(xiàng)式即為移位寄存器的特征多項(xiàng)式。利用以上定義可以很方便的計(jì)算出m序列的自相關(guān)函數(shù)滿(mǎn)足:

這是周期為奇數(shù)的序列所能達(dá)到的最好自相關(guān)性，稱(chēng)為理想的自相關(guān)性(ideal autocorrelation)。m序列具有理想的自相關(guān)性，然而不同m序列之間的互相關(guān)性十分不規(guī)律，這限制了m序列的應(yīng)用。Gold、Kasami等人研究了m序列和其特定的采樣序列之間的互相關(guān)性(序列ai的采樣序列bi定義為bi=ad*i，其中d為正整數(shù)，稱(chēng)為采樣因子。可以證明，m序列的互素采樣序列仍為m序列)，發(fā)現(xiàn)這時(shí)它們的互相關(guān)函數(shù)取值為三值的，具有較好的互相關(guān)性。具體來(lái)說(shuō)，他們證明了以下定理:

定理1 ai=tr(αi)為某個(gè)周期為N=2n－1的m序列，將采樣因子取為d=2k+1，滿(mǎn)足n/e為奇數(shù)，其中e=gcd(n，k)為它們的最大公因數(shù)，這時(shí)的采樣序列記為bi=ad*i=tr(αdi+u)，這兩個(gè)序列的互相關(guān)函數(shù) Pa，b(τ)為:

選用適合定理1條件且e=1的兩個(gè)m序列稱(chēng)為一對(duì)優(yōu)選對(duì)。現(xiàn)在，將Gold序列定義為m序列優(yōu)選對(duì)的和序列，由于兩個(gè)序列采用不同的平移相加得到的序列是不同的，即=+，其中v=0，1，…，N－1是不同的平移，因此一對(duì)優(yōu)選對(duì)共可產(chǎn)生N個(gè)不同的Gold序列，其中只有半數(shù)－1個(gè)是0、1平衡的，這就是實(shí)際應(yīng)用中選用的Gold序列。考察Gold序列的自相關(guān)性和互相關(guān)性:

由于m序列具有性質(zhì)“m序列與其平移序列的和是該序列的另一個(gè)平移”，上面兩個(gè)和式在一個(gè)周期上求和后，仍然變?yōu)槭?1)中的某個(gè)值，因此Gold序列的自相關(guān)函數(shù)和互相關(guān)函數(shù)都為三值的，且取值同于定理1中的取值。這是Gold序列相對(duì)于m序列的優(yōu)點(diǎn)之一，即擁有較好的互相關(guān)性。

Kasami在證明定理1時(shí)是將序列視為循環(huán)碼，用到了循環(huán)碼的理論，證明過(guò)程比較繁瑣。下一節(jié)中將提供一種直接從定義出發(fā)，利用有限域上跡函數(shù)性質(zhì)的巧妙證法，且該證法可以很方便的推廣至非極大Gold序列的情形。

2 定理1的證明

首先需要一個(gè)引理，以看清楚定理1中的條件。

引理 1 n，k為正整數(shù)，e=gcd(n，k)，則gcd(2n－1，2k+1)=1的充要條件是n/e為奇數(shù)。

證明 2k+1和2k－1是相鄰的兩個(gè)奇數(shù)，一定互素，因此

現(xiàn)在，要使 gcd(2n－1，2k+1)=1，需要上式右邊分子分母相同，即 gcd(n，2k)=gcd(n，k)，這就要求k含的2因子數(shù)大于或等于n含的2因子數(shù)，也就是n/e為奇數(shù)，引理證畢。

于是，定理1中n/e為奇數(shù)的條件，保證了采樣為互素采樣，否則得到的bi將不是m序列，不再具有平移相加的性質(zhì)，這種情況我們將得到非最大Gold序列，后面會(huì)看到，這種序列的自相關(guān)函數(shù)和互相關(guān)函數(shù)會(huì)是五值的。

將上面的和式視為有限域上的求和，i取遍0，1，…，2n－2 時(shí)，αi取遍域 F2n中的所有非零元，再令ατ=a，因此只需求出下面的和:

求s(a)的方法是令a取遍F2n，計(jì)算:

其中j是任意正整數(shù)。交換求和號(hào)，并利用有限域上跡函數(shù)求和的性質(zhì):

于是前式變?yōu)?

引理2 j≥3為正整數(shù)，Tj的定義如上，則:

證明 注 意d=2k+1，于是在域F2n上:

上式代入Tj的定義，利用性質(zhì)tr(x)=tr(x2)以及交換求和號(hào)，Tj變?yōu)?

利用性質(zhì)(2)，可知需要一組滿(mǎn)足方程

的x1到的解，只有這樣后半部分求和號(hào)才不為0。將方程(4)中 x1到視為常數(shù)視為變量，這是關(guān)于的一個(gè)非齊次線(xiàn)性方程，且有一個(gè)顯然的解=x1+… +，對(duì)應(yīng)常數(shù)項(xiàng)為 0 的齊次線(xiàn)性方程為:

不考慮零解時(shí)，整理變?yōu)?

因此得

引理證畢。

可以很簡(jiǎn)單的算出T1=2n，于是j=2m－1取奇數(shù)時(shí)，=，也就是

現(xiàn)在，對(duì)于域F2n一共2n個(gè)s(a)的值，分別設(shè)為 y1，y2，…，y2n，那么上式就是:

上式左端是非負(fù)zi的任意m次冪的和，右端是固定值，那么zi只可能取值0或1，且取1的次數(shù)恰為2n－e。一步步還原回去，即可知s(a)只可能取值0或±2(n+e)/2，且取 ±2(n+e)/2的共有 2n－e個(gè)，取 0 的有 2n－2n－e個(gè)。前者分別取正負(fù)的個(gè)數(shù)可由下式算出:設(shè)取正值的有t個(gè)，取負(fù)值的有2n－e－t個(gè)，則:

3 非最大Gold序列

本節(jié)討論定理1沒(méi)有解決的情形。引理1告訴我們，n/e不為奇數(shù)時(shí)，令 f=gcd(n，2k)，則有 f=2e，此時(shí) gcd(2n－1，2k+1)=2e+1，不是互素采樣，經(jīng)采樣后得到的序列bi不是m序列，但由采樣的定義可知bi仍具有bi=tr(αdi+u)的形式，此時(shí)的和序列我們稱(chēng)為非最大Gold序列。本節(jié)將討論非最大Gold序列的自相關(guān)性和互相關(guān)性。

沿用定理1中的記號(hào)。仍然從式(1)中 Pa，b(τ)的定義出發(fā)，這次不同的是由于d不再與N互素，我們不能像第3節(jié)開(kāi)始那樣將u處理掉，必須帶著運(yùn)算。令 a=αu+τ，b= αu，仍將 Pa，b(τ)轉(zhuǎn)化為有限域上的指數(shù)和，需要求下列指數(shù)和:

與之前不同的是和式中多了一個(gè)參數(shù)b。我們有如下定理:

定理2 sb(a)定義如上。則當(dāng)b是域F2n中的d階元時(shí)，sb(a)的取值和次數(shù)分別為:當(dāng)b不是域F2n中的d階元時(shí)，sb(a)的取值和次數(shù)分別為:

證明 使用與定理1的證明相同的方法，類(lèi)似的步驟省略，重點(diǎn)看b的引入引起的不同之處。

仍令

繼續(xù)使用分離變量的方法:

注意由于b的引入，對(duì)tr內(nèi)部的冪次進(jìn)行處理時(shí)，連帶引起了b冪次的變化，產(chǎn)生了b2－k的項(xiàng)，這是與之前不同的地方。現(xiàn)在，需要處理的方程是:

這仍是 xj－1的線(xiàn)性方程，xj－1=x1+ … +xj－2為一顯然解，對(duì)應(yīng)的齊次線(xiàn)性方程是

將之變形為:

由于d=2k+1與2n－1不互素，因此分情況討論:當(dāng)b是域中的d階元時(shí)，上述方程有g(shù)cd(2n－1，22k－1)=2f－1 個(gè)解，對(duì)應(yīng)方程(7)有 2f個(gè)解，也即方程(6)有2f個(gè)解;當(dāng)b不是域F2n中的d階元時(shí)，上述方程無(wú)解，對(duì)應(yīng)方程(7)只有零解，也即方程(6)只有一個(gè)解。

后續(xù)的處理跟定理1中的證明完全相同，此時(shí)引理2的結(jié)論變?yōu)?繼續(xù)按相同的方法處理，于是當(dāng)b是域F2n中的d階元時(shí)，sb(a)可能的取值為0或 ±，當(dāng) b不是域F2n中的d階元時(shí)，可能的取值為±2n/2。具體取值次數(shù)的計(jì)算方法也相同，最終結(jié)果即為定理2的結(jié)論。定理2證畢。

確定了sb(a)后，減1 即得對(duì)應(yīng)Pa，b(τ)的取值，注意sb(a)的取值里多出一種a=0的情形，不過(guò)sb(0)的取值與b有關(guān)，即我們無(wú)法確定Pa，b(τ)的取值要在定理2中的哪一類(lèi)里少一次，唯一可以確定的是sb(0)不會(huì)取0。因此Pa，b(τ)取值的結(jié)論要復(fù)雜一點(diǎn)。我們總結(jié)為如下定理:

定理3 ai=tr(αi)為某個(gè)周期為N=2n－1的m序列，采樣因子取為d=2k+1，滿(mǎn)足n/e為偶數(shù)，其中e=gcd(n，k)為它們的最大公因數(shù)，f=(n，2k)=2e。采樣序列 bi==tr()，令 b=αu，則當(dāng)b是域 F2n中的 d階元時(shí)，Pa，b(τ)的取值和次數(shù)分別為:

以上第一種或第三種情形取值少取一次。b不是域F2n中的 d階元時(shí)，Pa，b(τ)的取值和次數(shù)分別為:以上兩種情形的某一種取值少取一次。

來(lái)看此時(shí)構(gòu)造出的非最大Gold序列的自相關(guān)性和互相關(guān)性。令，選取得到的序列中0、1平衡的那些，自相關(guān)函數(shù)和互相關(guān)函數(shù)仍如第一節(jié)中的形式。ai是m序列，平移相加后是本序列的另一個(gè)位移;但是bi不是m序列，沒(méi)有平移相加的性質(zhì)因此對(duì)應(yīng)到定理 3 中無(wú)法確定這個(gè)是否為域F2n中的d階元，因此這時(shí)自相關(guān)函數(shù)和互相關(guān)函數(shù)可能取到定理3中所有的五個(gè)值，即非最大Gold序列的自相關(guān)函數(shù)和互相關(guān)函數(shù)，除了自相關(guān)函數(shù)τ=0時(shí)的一個(gè)平凡取值2n－1外，為五值的，可能的取值為－1，－1±2n/2和－1±。這五個(gè)值的取值次數(shù)沒(méi)有簡(jiǎn)單的確定方法。

下面用一個(gè)非最大Gold序列的例子來(lái)闡述我們的結(jié)論。取n=6，本原多項(xiàng)式f(x)=1+x+x6產(chǎn)生的周期為63的m序列為:

采樣因子取為 d =3，于是 k =1，e=1，f=2，采樣得到的序列為:

分別取平移量v=0和v=1，將上面兩序列相加，得到兩個(gè)0、1平衡的非最大Gold序列和分別為:

經(jīng)計(jì)算，ci(0)的自相關(guān)函數(shù)取值分別為:63(取1次)，－17(取2次)，15(取2次)，－9(取18次)，7(取18次)，－1(取22次)和的互相關(guān)函數(shù)取值分別為:－17(取3次)，15(取4次)，－9(取15次)，7(取21次)，－1(取20次)，與我們得到的五值性結(jié)論相符。

4 結(jié)語(yǔ)

Gold序列是通信技術(shù)中有重要應(yīng)用價(jià)值的一種偽隨機(jī)序列。Gold、Kasami等人完成了Gold序列理論的證明。文中提供了一種更直接和巧妙的證明方法，并自然推廣到了前人未提及的情形——非最大Gold序列。從上節(jié)討論可以看出，非最大Gold序列具有和Gold序列相似的自相關(guān)性和互相關(guān)性，相關(guān)函數(shù)的取值較為平滑，具有一定的應(yīng)用價(jià)值。目前，對(duì)于m序列互素采樣序列的相關(guān)性研究較多，但當(dāng)采樣為非互素采樣時(shí)，得到的非m序列及相關(guān)衍生序列等，因?yàn)樾再|(zhì)比較復(fù)雜，目前研究較少。希望本文中用到的有限域上指數(shù)和的理論，以及證明思路等，對(duì)這個(gè)方向的研究能有所啟發(fā)。

［1］ 霍曉磊，康霞.序列偶擴(kuò)頻通信系統(tǒng)性能分析［J］.通信技術(shù)，2011，44(08):1 －3.HUO Xiao － lei，KANG Xia.Analysis on Sequence －Pairs Spread Spectrum Communication System［J］.Communications Technology，2011，44(08):1 －3.

［2］ GAO Xing－xin，CHEN Alan，LO Sherman，etal.Compass－M1 Broadcast Codes in E2，E5b，and E6 Frequency Bands［J］.IEEE Journal of Selected Topics in Signal Proceeding，2009，3(04):599 －612.

［3］ GOLD R.Maximal Recursive Sequences with 3－Valued Recursive Cross－ Correlation Functions［J］.IEEE Transactions on Information Theory，1968(14):154－156.

［4］ KASAMI T.Weight Distribution Formula for Some Class of Cyclic Codes［R］.Urbana:Coordinated Science Lab.Tech.Rep.R －285，Univ.Illinois，1966.

［5］ NIHO Y.Multivalued Cross－ correlation Functions between Two Maximal Linear Recursive Sequences［D］.Los Angeles:Univ.Southern Calif.，1972.

［6］ WELCH L R.Trace Mappings in Finite Fields and Shift Register Cross－correlation Properties［R］.Los Angeles:Electrical Engineering Department Report，Univ.Southern Calif.，1969.

［7］ CUSICK TW，DOBBERTIN H.Some New Three－Valued Crosscorrelation Functions for Binarym － Sequences［J］.IEEE Transactions on Information Theory，1996，42(04):1238－1240.