一种基于分类搜索的Gold误码修正算法*

张希会

(中国西南电子技术研究所，成都 610036)

一种基于分类搜索的Gold误码修正算法*

张希会*

(中国西南电子技术研究所，成都 610036)

扩频系统侦察对抗时，在低信噪比下估计得到的扩频码存在严重误码，会影响信号解扩解调质量。通过Gold码与其对应m序列优选对的基本特性结合互相关函数特征，提出了一种严格的Gold码分类，并得出一种基于分类搜索的误码修正算法，通过比较待测Gold码与各类样本Gold码互相关函数的三值分布特性，可以快速搜索准确定位到正确的Gold码，实现误码完全修正。当Gold码的误码率不高于11%时，算法可实现对误码的完全修正，能有效降低扩频信号盲处理的信噪比门限。

扩频信号；盲处理；低信噪比；Gold误码修正；三值分布性；分类搜索

1 引 言

伪随机序列广泛应用于扩频信号中，除传统的安全通信领域[1]和新兴的码分多址(Code Division Multiple Access,CDMA)系统[2]外，军用的测控、雷达等也常引入伪随机序列，以提供抗截获性能。扩频通信的抗干扰性能、抗噪声性能、数据保密性能、多址通信能力、捕获跟踪性能等都与伪随机扩频码的设计密切相关，最适合作为伪随机扩频码的序列为m序列，它有着几乎完美的相关特性，但可用的地址数较少，容易被窃获，使用受到限制。为了扩充伪随机码的数量，最广泛使用的是由m序列优选对复合生成的Gold码，其中平衡Gold码的相关特性也很良好，且两两互相关函数小的序列数量很多，非常适合各种扩频系统中，是一种理想的周期性伪随机序列。Gold码已广泛应用于纠错码[3]、扩频通信[4]、系统识别和参数测量[5]以及3D场景建模等领域[6]。通用Gold码序列发生器的设计已经成熟，并实现了全面的商业化[7-8]。

由于Gold码或m序列等伪随机扩频码的频谱被展得很宽，可以在负信噪比环境下完成信息传输，具有很强的抗截获性能，对于侦察方增加了扩频信号检测和处理的难度，对扩频码的估计也往往伴随着误码。针对低信噪比环境下扩频信号侦察，文献[13-15]对Gold扩频码盲估计进行了大量的研究，但对估计得到误码进行修正的算法则没有相关的文献讨论。

Gold码由两个平衡m序列对生成，即两个m序列优选对的互相关函数性质决定了所生成Gold码的所有特性。本文通过m序列平衡优选对的构成样式对Gold进行严格分类，并得到基于分类搜索的误码修正算法，通过计算待测Gold码与各类样本码的互相关函数，可实现待测Gold误码的快速修正。

2 m序列与Gold码相关性质

Gold码由两个m序列优选对生成，m序列是最长线性移位寄存器序列的简称。由于m序列容易产生,规律性强,有许多优良的性能，在扩频通信中早期获得广泛的应用，而Gold码(包括m序列)在保持m序列的优良性质的情况下扩展了m序列的数量。m序列由本原多项式生成，在二进制移位寄存器发生器中，若n为级数，则所能产生的最大长度的码序列为2n-1位,可用g(x)=gmxm+gm-1xm-1+…+g1x+g0(gi=0或1)表示。m序列最重要的性质就是自相关函数满足二值性:

(1)

式中：p=2n-1为序列长度。

m序列有着非常优异的随机性，是很好的伪随机码，但数量有限。1967年，R.Gold在m序列基础上提出了Gold码，随机性性能逼近m序列，但数目远大于同一阶数的m序列。Gold码由属于同一优选对的两个m序列移位模2相加得到。m序列优选定义为两个m序列，若其互相关函数的绝对值有界，且满足以下条件：

(2)

Gold码由优选对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序列自相关函数。两个m序列优选对不同移位相加产生的新序列都是Gold码。因为总共有2n-1个不同的相对位移，加上原来的两个m序列本身，所以，两个m级移位寄存器可以产生2n+1个Gold码。因此，Gold码的序列数远大于m序列数。Gold码互相关特性满足优选对条件，且互相关峰值和主瓣与旁瓣之比都比m序列小得多。这一特性使得Gold码广泛应用于实现码分多址和测控数传等领域。

本文提出了一种基于Gold码分类搜索的算法来找到对应的标准Gold码，并修正误码。

3 Gold码分类

随着阶数增加，Gold码数量变得很大，根据互相关特征对Gold码进行有效分类能简化Gold码盲分析复杂度，同时修复一定程度的误码。最直接的分类就是将同一组m序列优选对生成的两个Gold码看成一类，它们有着相似的互相关特征。但来自不同优选对生成的Gold码互相关特征也可能有非常大的差异，也可能有相似的特征，与同组优选对得到Gold码无法区分，因此仅根据是否属于同一组优选对的分类是不完整的。

以m=10阶为例，总共60个m序列，分别对应60个本原多项式，根据多项式升幂排序，并依此编号为p1,p2,p3,…,p60,对应的m序列表示为m1,m2,m3,…,m60：

(3)

60个m序列一共可构成300对优选对，共生成超过20万个Gold码(不同的优选对可能产生同样的Gold码)。对300个优选对也进行编号，如pi和pj构成优选对编号为pi,j，而由pi和pj生成的Gold码集合标记为Gi,j，如p1,6表示m1和m6构成的优选对，G1,6表示p1和p6生成的所有平衡Gold码的集合。G1,6中任意两个不同Gold码的互相关函数呈现三值(-65,-1,63)特征。

一般而言，Gi,j中Gold码和另一个优选对生成Gold码Gm,n互相关函数呈现无序特征，如G1,6和G2,13中Gold码互相关函数就呈现乱序的形态。但Gi,j和Gm,n下标出现相同时，即i、j、m、n4个数出现两个相同时，其互相关也可能呈现三值特征，如G1,6和G1,8中Gold码互相关函数就呈现三值特征，如图1所示。

图1 G1,6与G1,8Gold码互相关函数

为严格区分不同Gold码类互相关函数特征，先对优选对的特征进行更严格分类。以m=10为例，300个优选对，可分为单元集和三元集两大类。如果序列号为i、j、k的3个m序列两两都能形成优选对，则(i，j，k)可构造属于三元集Gold码类，如(p1,6，p1,8，p6,8)、(P2,28，p2,48，p28,48)这样的优选对组合属于三元集。另一方面，不能组合成三元集的则为单元集，如(p1,16)、(p2,22)这样的单优选对。m=10阶只可能出现单元集和三元集，其中单元集共120个，三元集60个，由于三元集中两两可形成优选对，因此，三元集里共形成180对优选对，总共形成300个优选对。对于更高阶的情况，则可形成更多元的分类集。

来源于三元集或更多元集的Gold码尽管可能来自不同的优选对，但其互相关函数依然满足三值性，从互相关角度来分类，它们属于严格的一类。因此，将一个三元集或多元集生成的所有Gold码化为一类，对于m=10阶，则300个优选对生成的20多万个Gold码只分为120类，可表示为SG-i,j,k=Gi,j∪Gi,k∪Gj,k或SG-m,n=Gm,n。

这种分类是严格的分类，即同一类Gold码互相关呈现严格的三值特性，而不同类Gold码互相关呈现乱序性。

4 误码修正算法

由于不同类别的Gold码互相关函数存在巨大差异，可从上节讨论的每个分类中选取任意一个Gold码，形成标准样本库；然后有误码的待测Gold码与标准库每个样本分别做互相关，最接近三值性质的样本则与待测码来自同一类，再对同类里面Gold码样本继续做互相关，则出现最大值的为对应Gold码。整个修正算法可分解为以下步骤：

Step 1 根据优选对构成方式(单元集、三元集……)对所有Gold码严格分类。

Step 2 选取所有分类的第一个Gold码，组成一个标准样本库。

Step 3 计算待测Gold码和每一个样本序列的互相关函数，寻找与标准三值分布差异最小的序列。差异可进行量化计算，即将互相关函数分成三区，如m=10阶对应的三区间可分为：大于31的判决为63，小于-32的判决为-65，-32～31之间的值判决为-1，然后统计三值各自的个数，并与标准无误码互相关函数的三值个数分别作差，对差值的绝对值求和，和值最小那一类判决为待测Gold码所属的类。

Step 4 计算待测序列与对应Gold类里面所有Gold码的互相关函数，相关函数最大值最大的一个，即为对应正确的Gold码。

综上可知，由于利用Gold码严格的分类特征，从携带误码的待测序列中搜索到正确的Gold码只需进行两次搜索，第一次是与样本库搜索比较，寻找同类，第二步在同类里搜索。

以m=10为例，样本序列仅有300个，即每一类最多Gold码数量为不超过2 301个(每类可包含3组优选对形成的所有Gold码，每组优选对最多产生767个Gold码)。因此，最多只需2 301次相关运算即可修正误码Gold码，相比全样本搜索超过20万次相关运算，计算量减少2个数量级。

5 仿真实验

采用搜索法寻找正确Gold码，只要能成功寻找对正确的序列，就可完全修复所有误码。而搜到待测Gold码对应所属类是成功修复误码最关键的步骤，即在与样本码互相关差异统计判断出差异最小的类。仿真实验考虑两种情况，即随机位置分布误码和连续分布误码情况。

(1)考虑m=10阶，误码高斯随机分布，误码数分别为10个、50个以及100个。不同误码数目下待测Gold码与同类Gold码互相关函数如图2所示。

从图2可以明显看出:当误码数为1%(第二排，对应10个误码)时，互相关函数基本保持三值函数原样特征;随着误码数增至5%(第三排，对应50个误码)，三值性已经变得模糊，但基本轮廓还能辨认;当误码数增至10%(对应最后一排，100个误码)时，已经很难分辨出三值特征来。

(2)考虑m=10阶，误码连续分布，误码数也为10个、50个以及100个。不同误码数目下待测Gold码与同类Gold码互相关函数如图3所示。

图3 连续误码与同类Gold码互相关函数

图2与图3几乎没有统计差异，即误码修正算法对连续误码还是随机误码都同样实用。

图4所示为不同误码数目下待测Gold码与300个Gold样本码互相关函数三值统计与标准三值分布差异(数字越小表示统计差异越小)。

从图中可看出，当误码数较低时，同类三值统计差异相比异类明显偏小，当误码数到100个时，虽然同类差异也很小，但不一定对应最小值，这时如果仅采用差异最小的判定为类型归属，会发生错误，无法修复误码。但可以采用放宽同类搜索标准，如采用差异最小的10%多作为待测Gold码同类进行进一步判定，这样虽然增加了计算量，但可相应增加可修正误码的数量。

在对三值差异统计判定待测Gold所属类时，仅采用最小差异值判定，即根据待测Gold码与300个样本码的互相关函数(结果如图2所示)；根据算法步骤3，对300个互关函数进行统计分析(结果如图4所示)。当误码较少时，从图4(a)～(c)都可以明显看出差异值最小对应的样本码和待测码正好是属于同一类型。随着误码个数进一步增加，则差异值最小对应的样本码不一定与待测码属于同一类，如图4(d)中差异性最小的是第65类样本码，而待测码本身属于第1类。图5给出了不同误码个数下，依靠差异性最小值判决待测码属于对应类的成功率。对每一类都随机选出10个待测码，误码添加位置为随机方式，每一个待测码加误码后运行100次计算正确率，统计判定正确率。运行结果与所属类型无关，当误码数超过50个，就开始出现判决错误情况，即完全判定正确对应的误码数为5%。

图5 采用最小差异值作为判决时不同误码数与误码修复成功率

图5显示，当误码率超过5%时，仅采用最小差异值判决所属类型不一定正确，从图4(d)中可以看出，最小差异值对应的是第65类，但正确的所属类第1类对应的差异值虽然不是最小，但依然很小，仅比第65类和70类稍大一点。因此，可以将互相关三值统计差异排序，选择最小的几个作为备选正确类，后面对每备选类利用算法Step 4判决出正确的Gold码，并不影响最后Gold码修正，只是算法Step 4的计算量会增加。

当采用差异值最小的10%对应的样本类(即18个类)都判定为可能的所属类，再对类型里面全样本求互相关进行搜索修正，则修复误码的个数提高至110个(对应m=10时占总码数目1 023的11%)，如图6所示(误码添加和运行次数与图5一致)。但随之而来的计算量也增加一个数量级，相比20万个全样本搜索计算依然可减少一个数量级。

图6 采用最小10%范围差异作为判决时不同误码数与误码修复成功率

6 结束语

对于非合作军用扩频信号的处理通常是盲处理，而扩频信号的低截获性使得其信噪比很低，扩频码的估计也不可避免地伴随着误码，影响着后续码元解调和信息解析的正确性。有关扩频伪码的估计文献很多，而对扩频误码修正的研究则相对缺失。本文通过m序列优选对的组合方式对Gold码按照互相关函数严格分类，并通过快速的分类搜索算法，寻找对应的正确码，为Gold误码修正提供了一种基本的方法。仿真显示本文算法对Gold型扩频码误码具备很强的修复能力，能在负信噪比环境下提高对扩频系统的侦测能力，对于军事测控信号侦测具有重要意义。下一步准备在计算互相关三值统计差异性上进一步优化算法，降低搜索计算量。

[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] 阳锐,张天骐,石穗,等. 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年于电子科技大学获博士学位，现为工程师，主要研究方向为信号分析、阵列理论和阵列信号处理。

Email:seaharm_yeah@163.com

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