張希會

(中國西南電子技術研究所，成都 610036)

一種基于分類搜索的Gold誤碼修正算法*

張希會*

(中國西南電子技術研究所，成都 610036)

擴頻系統(tǒng)偵察對抗時，在低信噪比下估計得到的擴頻碼存在嚴重誤碼，會影響信號解擴解調質量。通過Gold碼與其對應m序列優(yōu)選對的基本特性結合互相關函數(shù)特征，提出了一種嚴格的Gold碼分類，并得出一種基于分類搜索的誤碼修正算法，通過比較待測Gold碼與各類樣本Gold碼互相關函數(shù)的三值分布特性，可以快速搜索準確定位到正確的Gold碼，實現(xiàn)誤碼完全修正。當Gold碼的誤碼率不高于11%時，算法可實現(xiàn)對誤碼的完全修正，能有效降低擴頻信號盲處理的信噪比門限。

擴頻信號；盲處理；低信噪比；Gold誤碼修正；三值分布性；分類搜索

1 引 言

偽隨機序列廣泛應用于擴頻信號中，除傳統(tǒng)的安全通信領域[1]和新興的碼分多址(Code Division Multiple Access,CDMA)系統(tǒng)[2]外，軍用的測控、雷達等也常引入偽隨機序列，以提供抗截獲性能。擴頻通信的抗干擾性能、抗噪聲性能、數(shù)據(jù)保密性能、多址通信能力、捕獲跟蹤性能等都與偽隨機擴頻碼的設計密切相關，最適合作為偽隨機擴頻碼的序列為m序列，它有著幾乎完美的相關特性，但可用的地址數(shù)較少，容易被竊獲，使用受到限制。為了擴充偽隨機碼的數(shù)量，最廣泛使用的是由m序列優(yōu)選對復合生成的Gold碼，其中平衡Gold碼的相關特性也很良好，且兩兩互相關函數(shù)小的序列數(shù)量很多，非常適合各種擴頻系統(tǒng)中，是一種理想的周期性偽隨機序列。Gold碼已廣泛應用于糾錯碼[3]、擴頻通信[4]、系統(tǒng)識別和參數(shù)測量[5]以及3D場景建模等領域[6]。通用Gold碼序列發(fā)生器的設計已經成熟，并實現(xiàn)了全面的商業(yè)化[7-8]。

由于Gold碼或m序列等偽隨機擴頻碼的頻譜被展得很寬，可以在負信噪比環(huán)境下完成信息傳輸，具有很強的抗截獲性能，對于偵察方增加了擴頻信號檢測和處理的難度，對擴頻碼的估計也往往伴隨著誤碼。針對低信噪比環(huán)境下擴頻信號偵察，文獻[13-15]對Gold擴頻碼盲估計進行了大量的研究，但對估計得到誤碼進行修正的算法則沒有相關的文獻討論。

Gold碼由兩個平衡m序列對生成，即兩個m序列優(yōu)選對的互相關函數(shù)性質決定了所生成Gold碼的所有特性。本文通過m序列平衡優(yōu)選對的構成樣式對Gold進行嚴格分類，并得到基于分類搜索的誤碼修正算法，通過計算待測Gold碼與各類樣本碼的互相關函數(shù)，可實現(xiàn)待測Gold誤碼的快速修正。

2 m序列與Gold碼相關性質

Gold碼由兩個m序列優(yōu)選對生成，m序列是最長線性移位寄存器序列的簡稱。由于m序列容易產生,規(guī)律性強,有許多優(yōu)良的性能，在擴頻通信中早期獲得廣泛的應用，而Gold碼(包括m序列)在保持m序列的優(yōu)良性質的情況下擴展了m序列的數(shù)量。m序列由本原多項式生成，在二進制移位寄存器發(fā)生器中，若n為級數(shù)，則所能產生的最大長度的碼序列為2n-1位,可用g(x)=gmxm+gm-1xm-1+…+g1x+g0(gi=0或1)表示。m序列最重要的性質就是自相關函數(shù)滿足二值性:

(1)

式中：p=2n-1為序列長度。

m序列有著非常優(yōu)異的隨機性，是很好的偽隨機碼，但數(shù)量有限。1967年，R.Gold在m序列基礎上提出了Gold碼，隨機性性能逼近m序列，但數(shù)目遠大于同一階數(shù)的m序列。Gold碼由屬于同一優(yōu)選對的兩個m序列移位模2相加得到。m序列優(yōu)選定義為兩個m序列，若其互相關函數(shù)的絕對值有界，且滿足以下條件：

(2)

Gold碼由優(yōu)選對m序列(x,y)表示為SGold={x,y,x⊕y,x⊕T-1y,x⊕T-2y,…,x⊕T-(N-1)y}，其中T-1y={y1,y2,…,yN-1,y0}表示序列y左移一位。

Gold碼具有三值自相關特性，非常相似于m序列自相關函數(shù)。兩個m序列優(yōu)選對不同移位相加產生的新序列都是Gold碼。因為總共有2n-1個不同的相對位移，加上原來的兩個m序列本身，所以，兩個m級移位寄存器可以產生2n+1個Gold碼。因此，Gold碼的序列數(shù)遠大于m序列數(shù)。Gold碼互相關特性滿足優(yōu)選對條件，且互相關峰值和主瓣與旁瓣之比都比m序列小得多。這一特性使得Gold碼廣泛應用于實現(xiàn)碼分多址和測控數(shù)傳等領域。

本文提出了一種基于Gold碼分類搜索的算法來找到對應的標準Gold碼，并修正誤碼。

3 Gold碼分類

隨著階數(shù)增加，Gold碼數(shù)量變得很大，根據(jù)互相關特征對Gold碼進行有效分類能簡化Gold碼盲分析復雜度，同時修復一定程度的誤碼。最直接的分類就是將同一組m序列優(yōu)選對生成的兩個Gold碼看成一類，它們有著相似的互相關特征。但來自不同優(yōu)選對生成的Gold碼互相關特征也可能有非常大的差異，也可能有相似的特征，與同組優(yōu)選對得到Gold碼無法區(qū)分，因此僅根據(jù)是否屬于同一組優(yōu)選對的分類是不完整的。

以m=10階為例，總共60個m序列，分別對應60個本原多項式，根據(jù)多項式升冪排序，并依此編號為p1,p2,p3,…,p60,對應的m序列表示為m1,m2,m3,…,m60：

(3)

60個m序列一共可構成300對優(yōu)選對，共生成超過20萬個Gold碼(不同的優(yōu)選對可能產生同樣的Gold碼)。對300個優(yōu)選對也進行編號，如pi和pj構成優(yōu)選對編號為pi,j，而由pi和pj生成的Gold碼集合標記為Gi,j，如p1,6表示m1和m6構成的優(yōu)選對，G1,6表示p1和p6生成的所有平衡Gold碼的集合。G1,6中任意兩個不同Gold碼的互相關函數(shù)呈現(xiàn)三值(-65,-1,63)特征。

一般而言，Gi,j中Gold碼和另一個優(yōu)選對生成Gold碼Gm,n互相關函數(shù)呈現(xiàn)無序特征，如G1,6和G2,13中Gold碼互相關函數(shù)就呈現(xiàn)亂序的形態(tài)。但Gi,j和Gm,n下標出現(xiàn)相同時，即i、j、m、n4個數(shù)出現(xiàn)兩個相同時，其互相關也可能呈現(xiàn)三值特征，如G1,6和G1,8中Gold碼互相關函數(shù)就呈現(xiàn)三值特征，如圖1所示。

圖1 G1,6與G1,8Gold碼互相關函數(shù)

為嚴格區(qū)分不同Gold碼類互相關函數(shù)特征，先對優(yōu)選對的特征進行更嚴格分類。以m=10為例，300個優(yōu)選對，可分為單元集和三元集兩大類。如果序列號為i、j、k的3個m序列兩兩都能形成優(yōu)選對，則(i，j，k)可構造屬于三元集Gold碼類，如(p1,6，p1,8，p6,8)、(P2,28，p2,48，p28,48)這樣的優(yōu)選對組合屬于三元集。另一方面，不能組合成三元集的則為單元集，如(p1,16)、(p2,22)這樣的單優(yōu)選對。m=10階只可能出現(xiàn)單元集和三元集，其中單元集共120個，三元集60個，由于三元集中兩兩可形成優(yōu)選對，因此，三元集里共形成180對優(yōu)選對，總共形成300個優(yōu)選對。對于更高階的情況，則可形成更多元的分類集。

來源于三元集或更多元集的Gold碼盡管可能來自不同的優(yōu)選對，但其互相關函數(shù)依然滿足三值性，從互相關角度來分類，它們屬于嚴格的一類。因此，將一個三元集或多元集生成的所有Gold碼化為一類，對于m=10階，則300個優(yōu)選對生成的20多萬個Gold碼只分為120類，可表示為SG-i,j,k=Gi,j∪Gi,k∪Gj,k或SG-m,n=Gm,n。

這種分類是嚴格的分類，即同一類Gold碼互相關呈現(xiàn)嚴格的三值特性，而不同類Gold碼互相關呈現(xiàn)亂序性。

4 誤碼修正算法

由于不同類別的Gold碼互相關函數(shù)存在巨大差異，可從上節(jié)討論的每個分類中選取任意一個Gold碼，形成標準樣本庫；然后有誤碼的待測Gold碼與標準庫每個樣本分別做互相關，最接近三值性質的樣本則與待測碼來自同一類，再對同類里面Gold碼樣本繼續(xù)做互相關，則出現(xiàn)最大值的為對應Gold碼。整個修正算法可分解為以下步驟：

Step 1 根據(jù)優(yōu)選對構成方式(單元集、三元集……)對所有Gold碼嚴格分類。

Step 2 選取所有分類的第一個Gold碼，組成一個標準樣本庫。

Step 3 計算待測Gold碼和每一個樣本序列的互相關函數(shù)，尋找與標準三值分布差異最小的序列。差異可進行量化計算，即將互相關函數(shù)分成三區(qū)，如m=10階對應的三區(qū)間可分為：大于31的判決為63，小于-32的判決為-65，-32～31之間的值判決為-1，然后統(tǒng)計三值各自的個數(shù)，并與標準無誤碼互相關函數(shù)的三值個數(shù)分別作差，對差值的絕對值求和，和值最小那一類判決為待測Gold碼所屬的類。

Step 4 計算待測序列與對應Gold類里面所有Gold碼的互相關函數(shù)，相關函數(shù)最大值最大的一個，即為對應正確的Gold碼。

綜上可知，由于利用Gold碼嚴格的分類特征，從攜帶誤碼的待測序列中搜索到正確的Gold碼只需進行兩次搜索，第一次是與樣本庫搜索比較，尋找同類，第二步在同類里搜索。

以m=10為例，樣本序列僅有300個，即每一類最多Gold碼數(shù)量為不超過2 301個(每類可包含3組優(yōu)選對形成的所有Gold碼，每組優(yōu)選對最多產生767個Gold碼)。因此，最多只需2 301次相關運算即可修正誤碼Gold碼，相比全樣本搜索超過20萬次相關運算，計算量減少2個數(shù)量級。

5 仿真實驗

采用搜索法尋找正確Gold碼，只要能成功尋找對正確的序列，就可完全修復所有誤碼。而搜到待測Gold碼對應所屬類是成功修復誤碼最關鍵的步驟，即在與樣本碼互相關差異統(tǒng)計判斷出差異最小的類。仿真實驗考慮兩種情況，即隨機位置分布誤碼和連續(xù)分布誤碼情況。

(1)考慮m=10階，誤碼高斯隨機分布，誤碼數(shù)分別為10個、50個以及100個。不同誤碼數(shù)目下待測Gold碼與同類Gold碼互相關函數(shù)如圖2所示。

從圖2可以明顯看出:當誤碼數(shù)為1%(第二排，對應10個誤碼)時，互相關函數(shù)基本保持三值函數(shù)原樣特征;隨著誤碼數(shù)增至5%(第三排，對應50個誤碼)，三值性已經變得模糊，但基本輪廓還能辨認;當誤碼數(shù)增至10%(對應最后一排，100個誤碼)時，已經很難分辨出三值特征來。

(2)考慮m=10階，誤碼連續(xù)分布，誤碼數(shù)也為10個、50個以及100個。不同誤碼數(shù)目下待測Gold碼與同類Gold碼互相關函數(shù)如圖3所示。

圖3 連續(xù)誤碼與同類Gold碼互相關函數(shù)

圖2與圖3幾乎沒有統(tǒng)計差異，即誤碼修正算法對連續(xù)誤碼還是隨機誤碼都同樣實用。

圖4所示為不同誤碼數(shù)目下待測Gold碼與300個Gold樣本碼互相關函數(shù)三值統(tǒng)計與標準三值分布差異(數(shù)字越小表示統(tǒng)計差異越小)。

從圖中可看出，當誤碼數(shù)較低時，同類三值統(tǒng)計差異相比異類明顯偏小，當誤碼數(shù)到100個時，雖然同類差異也很小，但不一定對應最小值，這時如果僅采用差異最小的判定為類型歸屬，會發(fā)生錯誤，無法修復誤碼。但可以采用放寬同類搜索標準，如采用差異最小的10%多作為待測Gold碼同類進行進一步判定，這樣雖然增加了計算量，但可相應增加可修正誤碼的數(shù)量。

在對三值差異統(tǒng)計判定待測Gold所屬類時，僅采用最小差異值判定，即根據(jù)待測Gold碼與300個樣本碼的互相關函數(shù)(結果如圖2所示)；根據(jù)算法步驟3，對300個互關函數(shù)進行統(tǒng)計分析(結果如圖4所示)。當誤碼較少時，從圖4(a)～(c)都可以明顯看出差異值最小對應的樣本碼和待測碼正好是屬于同一類型。隨著誤碼個數(shù)進一步增加，則差異值最小對應的樣本碼不一定與待測碼屬于同一類，如圖4(d)中差異性最小的是第65類樣本碼，而待測碼本身屬于第1類。圖5給出了不同誤碼個數(shù)下，依靠差異性最小值判決待測碼屬于對應類的成功率。對每一類都隨機選出10個待測碼，誤碼添加位置為隨機方式，每一個待測碼加誤碼后運行100次計算正確率，統(tǒng)計判定正確率。運行結果與所屬類型無關，當誤碼數(shù)超過50個，就開始出現(xiàn)判決錯誤情況，即完全判定正確對應的誤碼數(shù)為5%。

圖5 采用最小差異值作為判決時不同誤碼數(shù)與誤碼修復成功率

圖5顯示，當誤碼率超過5%時，僅采用最小差異值判決所屬類型不一定正確，從圖4(d)中可以看出，最小差異值對應的是第65類，但正確的所屬類第1類對應的差異值雖然不是最小，但依然很小，僅比第65類和70類稍大一點。因此，可以將互相關三值統(tǒng)計差異排序，選擇最小的幾個作為備選正確類，后面對每備選類利用算法Step 4判決出正確的Gold碼，并不影響最后Gold碼修正，只是算法Step 4的計算量會增加。

當采用差異值最小的10%對應的樣本類(即18個類)都判定為可能的所屬類，再對類型里面全樣本求互相關進行搜索修正，則修復誤碼的個數(shù)提高至110個(對應m=10時占總碼數(shù)目1 023的11%)，如圖6所示(誤碼添加和運行次數(shù)與圖5一致)。但隨之而來的計算量也增加一個數(shù)量級，相比20萬個全樣本搜索計算依然可減少一個數(shù)量級。

圖6 采用最小10%范圍差異作為判決時不同誤碼數(shù)與誤碼修復成功率

6 結束語

對于非合作軍用擴頻信號的處理通常是盲處理，而擴頻信號的低截獲性使得其信噪比很低，擴頻碼的估計也不可避免地伴隨著誤碼，影響著后續(xù)碼元解調和信息解析的正確性。有關擴頻偽碼的估計文獻很多，而對擴頻誤碼修正的研究則相對缺失。本文通過m序列優(yōu)選對的組合方式對Gold碼按照互相關函數(shù)嚴格分類，并通過快速的分類搜索算法，尋找對應的正確碼，為Gold誤碼修正提供了一種基本的方法。仿真顯示本文算法對Gold型擴頻碼誤碼具備很強的修復能力，能在負信噪比環(huán)境下提高對擴頻系統(tǒng)的偵測能力，對于軍事測控信號偵測具有重要意義。下一步準備在計算互相關三值統(tǒng)計差異性上進一步優(yōu)化算法，降低搜索計算量。

[1] BUREL G. Detection of spread spectrum transmissions using fluctuations of correlation estimators[C]//Proceedings of 2000 International Symposium on Intelligent Signal Processing and Communication Systems(ISPACS 2000). Honolulu,Hawaii:IEEE,2000:593-619.

[2] BUREL G,BOUDER C. Blind estimation of the pseudo-random sequence of a direct sequence spread spectrum signal[C]//Proceedings of 2000 IEEE 21st Century Military Communication Conference.Los- Angeles:IEEE,2000:201-204.

[3] YEN C H,WU B F. An error-correcting stream cipher design with state-hopping architecture[J].Journal of the Chinese Institute of Engineers,2005,28(1):9-16.

[4] KIM H J,LEE I，KIM W M. PN sequence generation from 2-D array of shift registers[J].Etri Journal,2005,27(3):273-279.

[5] ROLLINS D K,PACHECO L,BHANDARI N，et al.A quantitative measure to evaluate competing designs for non-linear dynamic process identification[J].The Canadian Journal of Chemical Engineering,2006,84(4):459-468.

[6] SPOELDER H J W. Some aspects of pseudo random binary array-based surface characterization[J].IEEE Transactions on Instrumentation and Measurement,2000,49(6):1331-1336.

[7] TAN A H,GODFREY K R. The generation of binary and near-binary pseudorandom signals:an overview[J].IEEE Transactions on Instrumentation and Measurement,2002,51(4):583-588.

[8] SZCZEPANSKIETAL J.Biometric random number generators[J].Computer Security,2004,23(1):77-84.

[9] 陽銳,張?zhí)祢U,石穗,等. BOC信號的偽碼周期和組合碼盲估計[J].電訊技術,2014,54(6):79-764. YANG Rui,ZHANG Tianqi,SHI Sui,et al.Blind estimation of pseudo code period and combination code for BOC signal[J].Telecommunication Engineering,2014,54(6):79-764.(in Chinese)

[10] QIU P Y,HUANG Z T,JIANG W L,et al.Blind multiuser spreading sequences estimation algorithm for the direct-sequence code division multiple access signals[J].IET Signal Processing,2010,4(5):465-478.

An Error Correction Algorithm for Gold Codes Based on Classification Search

ZHANG Xihui

(Southwest China Institute of Electronic Technology,Chengdu 610036,China)

In the countermeasuring of blind processing spread spectrum system with a very low signal-to-noise ratio(SNR),the estimated spreading codes always contain error codes，which can affect the quality of despreading and demodulating the spreading codes. A strict classification scheme is presented according to cross-correlation function and the basic characteristics of the preferred pair of m sequence. And an error correction algorithm based on classification search is proposed，which can quickly search and locate the corresponding code by comparing the three-valued distribution of the cross-correlation function between the test code and the sample Gold codes of each category. Simulations illustrate that the proposed algorithm can completely correct the error codes when the bit error rate(BER) is lower than 11% and also effectively reduce the SNR threshold for the blind processing of spread spectrum signals.

spread spectrum signal;blind processing;low signal-to-noise ratio;error Gold codes correction;three-valued distribution;classification search

10.3969/j.issn.1001-893x.2017.04.006

張希會.一種基于分類搜索的Gold誤碼修正算法[J].電訊技術，2017,57(4):402-406.[ZHANG Xihui.An error correction algorithm for Gold codes based on classification search[J].Telecommunication Engineering,2017,57(4):402-406.]

2016-10-19；

2017-01-17 Received date:2016-10-19；Revised date：2017-01-17

TN914.42

A

1001-893X(2017)04-0402-05

張希會(1979—)，男，四川榮縣人，2012年于電子科技大學獲博士學位，現(xiàn)為工程師，主要研究方向為信號分析、陣列理論和陣列信號處理。

Email:seaharm_yeah@163.com

*通信作者：seaharm_yeah@163.com Corresponding author：seaharm_yeah@163.com