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

張希會

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

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

張希會*

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

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

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

1 引 言

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

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

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

2 m序列與Gold碼相關(guān)性質(zhì)

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

(1)

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

m序列有著非常優(yōu)異的隨機(jī)性，是很好的偽隨機(jī)碼，但數(shù)量有限。1967年，R.Gold在m序列基礎(chǔ)上提出了Gold碼，隨機(jī)性性能逼近m序列，但數(shù)目遠(yuǎn)大于同一階數(shù)的m序列。Gold碼由屬于同一優(yōu)選對的兩個m序列移位模2相加得到。m序列優(yōu)選定義為兩個m序列，若其互相關(guān)函數(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碼具有三值自相關(guān)特性，非常相似于m序列自相關(guān)函數(shù)。兩個m序列優(yōu)選對不同移位相加產(chǎn)生的新序列都是Gold碼。因?yàn)榭偣灿?n-1個不同的相對位移，加上原來的兩個m序列本身，所以，兩個m級移位寄存器可以產(chǎn)生2n+1個Gold碼。因此，Gold碼的序列數(shù)遠(yuǎn)大于m序列數(shù)。Gold碼互相關(guān)特性滿足優(yōu)選對條件，且互相關(guān)峰值和主瓣與旁瓣之比都比m序列小得多。這一特性使得Gold碼廣泛應(yīng)用于實(shí)現(xiàn)碼分多址和測控數(shù)傳等領(lǐng)域。

本文提出了一種基于Gold碼分類搜索的算法來找到對應(yīng)的標(biāo)準(zhǔn)Gold碼，并修正誤碼。

3 Gold碼分類

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

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

(3)

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

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

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

為嚴(yán)格區(qū)分不同Gold碼類互相關(guān)函數(shù)特征，先對優(yōu)選對的特征進(jìn)行更嚴(yán)格分類。以m=10為例，300個優(yōu)選對，可分為單元集和三元集兩大類。如果序列號為i、j、k的3個m序列兩兩都能形成優(yōu)選對，則(i，j，k)可構(gòu)造屬于三元集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)選對，但其互相關(guān)函數(shù)依然滿足三值性，從互相關(guān)角度來分類，它們屬于嚴(yán)格的一類。因此，將一個三元集或多元集生成的所有Gold碼化為一類，對于m=10階，則300個優(yōu)選對生成的20多萬個Gold碼只分為120類，可表示為SG-i,j,k=Gi,j∪Gi,k∪Gj,k或SG-m,n=Gm,n。

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

4 誤碼修正算法

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

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

Step 2 選取所有分類的第一個Gold碼，組成一個標(biāo)準(zhǔn)樣本庫。

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

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

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

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

5 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

[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ì)[J].電訊技術(shù),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].電訊技術(shù)，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年于電子科技大學(xué)獲博士學(xué)位，現(xiàn)為工程師，主要研究方向?yàn)樾盘柗治?、陣列理論和陣列信號處理?/p>

Email:seaharm_yeah@163.com

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