基于码重分布距离的自同步扰码识别方法

吕全通，张旻，李歆昊，朱宇轩

（1.解放军电子工程学院，安徽合肥230037；2.安徽省电子制约技术重点实验室，安徽合肥230037；3.清华大学电子工程系，北京100084）

基于码重分布距离的自同步扰码识别方法

吕全通1，2，张旻1，2，李歆昊1，2，朱宇轩3

（1.解放军电子工程学院，安徽合肥230037；2.安徽省电子制约技术重点实验室，安徽合肥230037；3.清华大学电子工程系，北京100084）

针对线性分组码的自同步扰码识别问题，提出了一种基于码重分布距离的自同步扰码识别方法。该方法首先证明了线性分组码的自同步扰码序列构造不同维数的矩阵时，矩阵周期性的存在线性相关列，且该周期为线性分组码的码长；然后分析了线性分组码的码重分布的独特特性；在获取线性分组码码长的基础上，通过遍历计算抽取序列与随机序列的码重分布距离并寻找最大值的方式实现了对自同步扰码多项式的识别。仿真实验表明，该方法在序列不均衡度ε=0时也能有效识别，且不需要已知线性分组码的编码参数。

自同步扰码；盲识别；线性分组码；码重分布距离

0 引言

在数字通信中，扰码技术的应用不仅保证了数据同步传输的准确性，而且也扩展了信号频谱，提高了其抗干扰能力。扰码盲识别是信道编码盲识别的重要内容，在信息截获、信息对抗和智能通信等领域都具有十分重要的作用。因此，扰码的盲识别研究越来越引起国内外相关领域学者和专家的重视［1-7］。

自同步扰码的保密性较同步扰码更强，是扰码的一种主要形式。目前公开发表的自同步扰码的盲识别算法都是基于加扰前信息序列是0、1分布不均衡的，如文献［8—9］的扰码多项式的判决准则都是基于0、1比特不平衡性提出的；文献［10］重点研究了信源不平衡条件下的自同步扰码序列的重码统计特性，实现了对自同步扰码多项式的识别；文献［11］讨论了信源不平衡条件下的自同步扰码序列的游程数与扰码多项式阶数的关系，实现了对自同步扰码阶数的判断。但在实际通信系统中还存在着信道编码后加扰的情况，由于信道编码后序列的不均衡度非常小甚至趋近于0［4］，使得现有的基于加扰前序列0、1分布不均衡的算法大都失效。目前国内外鲜有文献涉及此类问题，文献［4］针对线性分组码的同步扰码识别展开研究，将扰码生成多项式的识别转化为二元假设检验问题，利用扰码序列构造一个服从正态分布的随机变量，根据给出的判决阈值实现扰码多项式的识别，但该方法需要已知加扰前线性分组码的校验矩阵的先验知识，离全盲识别的要求还有一定差距。本文针对此问题，提出了一种基于码重分布距离的自同步扰码识别方法。

1 自同步扰码原理

通信系统中，加扰器一般位于信源编码之后，但是实际中也存在加扰器在分组编码之后的情况，其结构如图1所示，其中，输入xk为加扰前的线性分组编码序列，输出zk为加扰后的自同步扰码序列。

图1 线性分组码的自同步扰码结构Fig.1 The structure of self-synchronous scrambler placed after the linear block code

自同步扰码器主要是由LFSR（线性反馈移位寄存器）构成，其结构如图2所示。

自同步扰码的加扰过程可表示为：

其中，ciϵ｛0，1｝，0＜i≤L且cL=1是LFSR的反馈系数，式中⊕表示模二加，∑表示模二累加。

自同步解扰器由线性前馈移位寄存器组成，其结构如图3所示。可从输入的扰码序列zk中得到原始序列xk，解扰输出序列：

图2 自同步扰码器结构图Fig.2 The structure of self-synchronized scrambler

图3 自同步解扰器结构Fig.3 The structure of self-synchronized descrambler

2 线性分组码的自同步扰码盲识别

2.1 线性分组码自同步扰码的线性相关性分析

性质1［13］：任何一个（n，k）线性分组码都可以由其生成矩阵G的基线性表示，如果将收到的一组码字排成p行n列（p＞n）的矩阵形式，即每行是一个完整的码字，对该矩阵进行初等行变换，则矩阵的前k行可以化成［IkH ］的形式，其余p～k行化简为0。

引理1［14］：对于m×n的矩阵A和m×q的矩阵B，rank［ A，B］≤rank（A）+rank（B）。

引理2［14］：如果矩阵A经有限次初等变换变成矩阵B，就称矩阵A与B等价，记作A～B。

定理1［14］：若矩阵A～B，则rank（A）=rank（B）。

推论1：由（n，k）线性分组码序列构造的p×p矩阵M有如下性质：

1）当p=mn（m≥2）时，即矩阵列值p为线性分组码码长n的整数倍数时，矩阵M各行至少包含m—1个完整对齐的码字，如式（3）所示，根据性质1可知，此时矩阵M存在线性相关列。

2）当p≠mn（m≥2）时，即矩阵列值p不等于线性分组码码长n的整数倍数时，矩阵M各行没有完整对齐的码字，此时矩阵M不存在线性相关列。性质2：（n，k）线性分组码序列C=c1，c2，…，cN，…，经过一个s位长的延迟器形成序列C1（结构如图4所示），序列C2由序列C和序列C1的逻辑异或得到，由序列C2构造的p×p矩阵（p=mn），仅在矩阵列值p为线性分组码码长n的整数倍数时，矩阵存在线性相关列。证明：根据题设条件，序列C2=C⊕C1，其中，序列C可表示为C=（c1，c2，…，cN，… ），序列C1可表示为C1=（c1，…，cs，c1，c2，…，cN，…），（c1，…，cs）为延迟器的初始状态。

由序列C构造的p×p矩阵C，当p=mn，m= 1，2，…时，矩阵各行码字起点对齐，矩阵排列如式（4）所示。

图4 序列的延迟异或结构Fig.4 The XOR structure of delayed sequence

由序列C1构造的p×p矩阵C1，矩阵排列如式（5）所示。

矩阵C进行有限次的初等变换得到如式（6）的结果。

由于矩阵C1与矩阵C的实线框中的数据是完全一致的，因此，矩阵C1与矩阵C进行相同的步骤的初等变换可得到如（7）式的结果。

由序列C2=C⊕C1可知，矩阵C2=C⊕C1，而矩阵C～B，C1～B1。由此可得，C⊕C1=C2～B⊕B1，即：

由式（8）可知，初等变换后的矩阵B和矩阵B1实线框中的全0行的位置是对齐的，此时矩阵Umn，（m—1）n存在线性相关列且rank（Umn，（m—1）n）=（m—1）k。而由推论1可知，矩阵D'mn，s和矩阵F'mn，n—s的各行不存在完整对齐的码字，矩阵为列满秩矩阵，因此，rank（D'mn，s）=s，rank（F'mn，n—s）=n—s。

由引理1和定理1可得：

因此，由序列C2构造的p×p矩阵C2，当矩阵列值p=mn，m=1，2，…时，矩阵存在线性相关列。

当矩阵列值p不为线性分组码码长n的整数倍数时，即p≠mn，m=1，2，…，矩阵C1、矩阵C都为满秩矩阵，此时矩阵C2也为满秩矩阵，不存在线性相关列。

综上所述，由序列C2构造的p×p矩阵C2，仅在矩阵列值p取得线性分组码码长n的整数倍数时，矩阵存在线性相关列。

性质2得证。

自同步扰码由于误码扩散率与生成多项式的项数成正比，一般都使用2项式或3项式［8］，现以3项式自同步扰码器为例（其结构如图5所示），其扰码器输出可由线性分组码及其延迟序列异或而得到，即zk=xk⊕yk—1⊕yk—L=xk⊕yk，其中yk—1、yk—L是线性分组码序列xk的延迟序列。因为序列yk= yk—1⊕yk—L，由推论1及性质2可知，由序列yk构造的p×p矩阵，在矩阵列值P取得线性分组码码长n的整数倍数时，矩阵存在线性相关列。同理，对于自同步扰码输出序列zk=xk⊕yk，扰码序列也有如性质2的特性。

图5 自同步扰码器结构Fig.5 The structure of self-synchronized scrambler

综合上述分析可得，对于线性分组码的自同步扰码序列，由该序列构造的p×p的矩阵，在矩阵列值P取得线性分组码码长n的整数倍数时，矩阵存在线性相关列。

2.2 线性分组码码重特性分析

一个码字（或任何向量）的Hamming重量等于该码字中的非零元素的个数。对（n，k）线性分组码，定义码字C的码重分布W（C）为集合W（C）=｛Ni=i，0≤i≤n｝，W（C）表示C中Hamming重量为i的所有码组的数目。重量为i的码组在C中出现的概率pi就是该重量码组的码重分布概率［13］。

定理1（n，k）线性分组码的k位信息生成的n位码字集v（2k）是n维空间V（2n）的子集，且v在V中的分布是非等概的［13］。

对于（n，k）线性分组码，生成的码字集大小为2k且2k≪2n，k位信息生成的n位码字的集合必定隶属于n位码字组成的码字集合，前者在后者中的分布是非等概率的，其重量为i的码组的概率分布为Pi。

其中，n为估计码长。

2.3 序列抽取

自同步扰码器的生成多项式可以表示为：

其中，L是LFSR的反馈逻辑输出级数，rv是生成多项式f（x）的项数。

自同步扰码的输入序列为xk，扰码器的输出序列为zk。定义GF（2）上的多项式

按照多项式g（x）对扰码序列抽取并进行模二求和得

当g（x）=f（x）时，该抽取并模二求和的过程实际上等价于自同步扰码的解扰的过程。

因此，抽取并模二求和后的序列mk1即为加扰前的线性分组编码序列。

当g（x）≠f（x）时，式（14）所示的处理过程不再是解扰过程，由于扰码序列zk中的0、1等概率出现，因此，在错误抽取时抽头位0、1比特出现的概率是相等的，即

其中，rw是多项式g（x）的项数。

在错误抽取时抽头位0、1比特出现的概率是相等的，因此模二求和的输出序列mk2中的0、1也是等概率出现的，近似为随机序列。

2.4 识别步骤

综合上述分析提出以下识别步骤：

步骤1：对于待识别的扰码序列，遍历码长构造P×P矩阵，其中P=1，2，…，160，统计矩阵的秩差，矩阵的秩差R-Dj=j—Rj（其中j=1，2，…，P为矩阵列值，Rj为矩阵的秩），矩阵的秩差在矩阵列数取码长整数倍时周期性取得峰值，其峰值对应的列值的最大公约数即为加扰前线性分组码的码长n。

步骤2：遍历N个多项式对扰码序列抽取并模二求和，其输出序列为：mtk，其中，t=1，2，…，N，t为多项式集合G中的多项式序号。

步骤3：根据判断得出的码长n，遍历抽取的输出序列mtk的码字起点f=1，2，…n，计算与随机序列的码重分布距离，统计遍历码字起点时的最大码重分布距离：

步骤4：最大码重分布距离对应的多项式即为所待识别扰码多项式：g（x）= G｛ s｝，s= argmaxd（ t）。

3 仿真实验及性能对比

为了验证识别方法的效性，使用软件matlab 7.10进行仿真实验。

3.1 仿真实验

实验1：自同步扰码与线性分组码的秩差统计

随机产生长度为N=30 000 bit的（15，5）线性分组码作扰码器的输入信息数据，仿真长度为30 000 bit、生成多项式为f（x）=1+x18+x23的自同步扰码序列，统计（15，5）线性分组码、自同步扰码序列的秩差，其统计结果如图6、图7所示。

由图6、图7所示的统计结果可以看出，（15，5）线性分组码及其自同步扰码的秩差统计都在矩阵列值取码长整数倍时周期性取得峰值，其峰值统计结果如表1所示，（15，5）线性分组码及其自同步扰码的秩差统计的峰值对应的矩阵列值的最大公约数都为15。因此，通过对线性分组码的自同步扰码的秩差统计，可以预先识别出加扰前线性分组码的码长。

图6 （15，5）线性分组码Fig.6 （15，5）linear block code

图7 自同步扰码Fig.7 Self-synchronized scrambler

表1 峰值统计结果Tab.1 The result of peak value statistics_

实验2：自同步扰码多项式的识别

实际通信中LFSR的级数绝大多数分布在3～60之间，自同步扰码由于误码扩散率与生成多项式的项数成正比，一般都使用2项式或3项式，比如ITU V.34中使用的就是3项式1+x18+x23［8］。因此，有限的多项式项数和LFSR的阶数是扰码盲识别方法可行的重要前提条件。

为给出较为实际有效的正确识别率，在仿真遍历多项式时，采用三组多项式作为自同步扰码的生成多项式：第一组，由3～60阶的全部58个2项式f（x）=1+xL（L=3，4，…，60）组成；第二组，由3～60阶的全部1 769个3项式f（x）=1+xk+xL，L= 3，…，60，k=1，…，L—1组成；第三组，由3～60阶的5项式组成，由于3～60阶的5项式的总数过于庞大，因此在各个阶数对应的5项式中分别随机抽取10个或11个多项式，若相应阶数的5项式不足10个（比如3～6阶）则该阶数对应的5项式全部抽取，共555个5项式。多项式集合中多项式共2 382个。

实验中采用ITUV.34中常用的生成多项式为f（x）=1+x18+x23的自同步加扰方式，随机产生长度为N=45 000 bit的（15，5）线性分组码作扰码器的输入信息数据，线性分组码序列的不均衡为0，仿真长度为45 000 bit的自同步扰码序列进行盲识别实验，统计结果如图8和表2所示（表2是码重分布距离按从大到小排序的前5个值，以及其码重分布距离对应的多项式）。

表2 码重分布距离统计Tab.2 Weight distribution distance statistics

由图8及表2的实验结果可以知，在多项式序号为306（多项式取g（x）=1+x18+x23）时，码重分布距离取得最大值0.0273，且与其他多项式对应的码重分布距离有明显差异，可以判断自同步扰码的生成多项式为g（x）=1+x18+x23，与待识别自同步扰码的多项式一致。因此，通过计算并寻找扰码抽取序列与随机序列的码重分布距离最大值的方法可以有效地实现此类自同步扰码多项式的识别。

3.2 性能比较

为了更好地说明本文所提方法的识别性能，将本文所提的方法与文献［10］的方法进行比较。仿真对比实验中使用ITU V.34（其自同步扰码多项式为1+x18+x23）和ITU G.709（其自同步扰码多项式为1+x43）这2个实际系统所使用的生成多项式，分别仿真长度从0～9 000 bit以900 bit步长变化的线性分组码序列作为扰码器的输入信息序列且线性分组码序列的不均衡为0，分别使用本文方法和文献［10］的方法对相应的自同步扰码序列进行蒙特卡洛仿真实验，蒙特卡洛仿真次数为500次，仿真结果如图9、图10所示。

由图9、图10的仿真结果可知，本文方法的识别率与不均衡度ε无关，在ε=0时也可以实现正确识别，但本文方法识别率与扰码序列长度有关，在数据量为8 000 bit时，正确识别率能达到90%以上，在数据量大于9 000 bit时，正确识别率能达到100%。文献［10］所提方法的识别率均为0，对加扰前序列为线性分组码的自同步扰码无法识别。综上所述，本文方法针对加扰前序列为线性分组码的自同步扰码序列具有很好的识别性能，且本文方法不需要已知线性分组码的具体参数也能有效地识别。

图8 码重分布距离Fig.8 Weight distribution distance

图9 ITU V.34的扰码识别率对比曲线Fig.9 Comparison of recognition ratio of the ITU V.34 scrambler performance

图10 ITU G.709的扰码识别率对比曲线Fig.10 Comparison of recognition ratio of the ITU G.709 scrambler performance

4 结论

本文提出了基于码重分布距离的自同步扰码识别方法。该方法证明了线性分组码的自同步扰码序列码组间的线性相关性，利用线性分组码序列与随机序列的码重分布特性的差异，实现了对线性分组码的自同步扰码多项式的识别。仿真实验表明，本文方法在序列不均衡度ε=0时也能有效识别，且不需要已知线性分组码的编码参数。但是，本文方法仍然需要遍历大量的多项式，计算复杂度较大，在下一步的研究中还需要对算法进一步的优化。

［1］袁叶.线性扰码的盲识别研究［D］.成都：电子科技大学，2013.

［2］Cluzeau M.Reconstruction of a Linear Scrambler［J］. IEEE Transaction on Computers，2007，56（9）：1283-1291.

［3］Liu X B，Soo N K，Wu X W，et al.Reconstructing a linear scrambler with improved detection capability and in the presence of noise［J］.IEEE Transaction on Information Forensics and Security，2012，7（1）：208-218.

［4］Liu X B，Soo N K，Wu X W.A study on reconstruction of linear scrambler using dual words of channel encoder［J］.IEEE Transactions on Information Forensics and Security，2013，8（3）：542-552.

［5］郝士琦，戚林，王勇.一种新的伪随机扰码盲识别方法［J］.电路与系统学报，2011，16（4）：6-12.

［6］廖斌，张玉，杨晓静.含错扰码序列生成多项式的快速恢复方法［J］.电子信息对抗技术，2014，29（1）：13-16.

［7］伍文君，黄芝平，唐贵林，等.含错扰码序列的快速恢复［J］.兵工学报，2009，30（8）：1134-1138.

［8］廖红舒，袁叶，甘露.自同步扰码的盲识别方法［J］.通信学报，2013，34（1）：136-143.

［9］张永光，王挺，楼才义.一种自同步扰码生成多项式的盲识别方法［P］.中国：CN102201912A，2011.

［10］吕喜在，苏绍璟，黄芝平.一种新的自同步扰码多项式盲恢复方法［J］.兵工学报，2011，32（6）：680-685.

［11］黄芝平，周靖，苏绍璟，等.基于游程统计的自同步扰码多项式阶数估计［J］.电子科技大学学报，2013，42（4）：541-545.

［12］姜丹.信息论与编码［M］.合肥：中国科学技术大学出版社，2011.

［13］张永光，楼才义.信道编码及其识别分析［M］.北京：电子工业出版社，2010.

［14］张贤达.矩阵分析与应用［M］.北京：清华大学出版社，2014.

Self-synchronized Scrambler Recognition Based on Code Weight Distributing Distance

LU Quantong1，2，ZHANG Min1，2，LI Xinhao1，2，ZHU Yuxuan3
（1.Electronic Engineering Institute of PLA，Hefei 230037，China；2.Key Laboratory Electronic Restricting Technique，Hefei 230037，China；3.Department of Electronic Engineer，Tsinghua University，Beiiing 100084，China）

A recognition method based on code weight distributing distance was proposed to solve the problem of the identifying of the self-synchronized scrambler placed after the linear block code.Firstly，the conclusion was proved that the sequence of self-synchronized scrambler after a linear block encoder in the different dimension matrix structure was periodic exist linear correlation matrix，and the period was the length of linear block code；Then，the weight distribution characteristic of the linear block code was analyzed.Finally，the length of linear block code are being identified，and the polynomial of the scrambler was determined with maximum value searching for all possible distance of code weight distributing of the extracted sequence and the random sequence. Simulation results showed that this method could effectively identify the self-synchronized scrambler when the sequence bias is equal to zero without knowing the parameters of the linear block code.

self-synchronized scrambler；blind recognition；linear block code；distance of code weight distributing

TP391

A

1008-1194（2015）05-0007-07

2015-04-07

国家自然科学基金项目资助（60972161）；安徽省自然科学基金项目资助（1408085QF115）

吕全通（1990—），男，山东人，硕士研究生，研究方向：通信与信息系统。E-mail：lvquantong90@126.com