一种求解延迟型m序列线性组合的新算法

陈德宏 刘 梅

（安徽工业大学电气信息学院，马鞍山，243002）

引 言

伪随机信号在CDMA通信、遥控、遥测、信息加密和卫星导航系统有着广泛的应用。m序列作为最大长度线性反馈移位寄存器序列，是一类重要的也是目前研究最多的伪随机序列。在伪随机信号应用处理的过程中，经常需要产生相对时延不同的主m序列的平移等价序列，若采用原始方法（如设立一系列延时门），则由于器件组成庞大，求解过程繁琐而耗时长，这在延迟型长m序列实际研究中就显得很不现实。

设A0是二元域GF（2）上的m序列，用Ai表示序列A0左移i位得到的新序列，序列Ai与A0具有相同的特征多项式，即Ai与A0具有相同的递归关系。若用集合G（f）表示所有适合特征多项式f（x）的序列的全体，则集合G（f）中非零元素Ai都是m序列，它们具有以下性质

若Ai∈G（f），Aj∈G（f）

且i≠j（modL）

则

这个性质称为m序列的移位相加特性，也称为自闭特性。由于m序列发生器各级移位寄存器的输出只是相移不同的平移等价m序列，通过m序列移位相加特性，可知延迟m序列可以由m序列发生器的各移位寄存器输出序列经模2和运算获得，即m序列的线性组合特性［1］。

m序列线性组合特性为获得延迟m序列提供了便利，在长m序列的设计中具有经济灵活的实用价值。对于一个特定的延迟k位m序列是由n级移存器的哪几级输出序列模2和得到的问题，在理论上一直没有一个确定性的普遍公式，文献［2－4］利用有限域的代数法将延迟k位m序列分解为几个低延迟的m序列模2和，之后再进行多次迭代，直至分解为几个n级以内延迟m序列的线性模2和。

本文首先分析了m序列线性组合关系的代数迭代求解算法，针对该算法在解决多抽头大延迟长m序列时，迭代过程冗长繁杂、工程上难以实现等问题，利用主m序列状态与延迟m序列在二元域上存在的线性关系，提出了用求解二元域线性方程组获得延迟m序列线性组合关系的方法，工程计算量得到大幅简化，并将其成功运用到N－CDMA移动通信系统用户掩码的分配设计中，同时通过对特定241位的大延迟长码掩码的求解，定量分析了采用传统代数迭代法的计算复杂度。

1 m序列线性组合关系求解的代数算法

有限域上多项式是研究伪随机序列的重要数学工具。代数算法就是由二元域m序列特征多项式f（x）和延迟算子多项式xk，利用在二元域上定义的多项式的模2运算法则求解m序列线性组合关系［5］。

m序列A0可以写成如下形式：A0＝｛a0a1a2…aL－1…｝，其周期L＝2n－1，特征多项式为

由于集合G（f）表示所有适合特征多项式f（x）的延迟序列全体，将G（f）用两两不同的元素表示出来，有

集合G（f）可看作一个含有L＋1个元素的有限域，其中θ＝｛0 0 0 … 0｝是满足特征多项式f（x）零序列。G（f）中的非零元素组成周期L的循环群，非零元素就是所求的延迟m序列，任一个非零元素Ak均可表示成一本原元α的幂。

令α0＝A0＝1，α＝A1，则G（f）＝｛θ1αα2…αL－1｝。本原元α是m序列特征多项式f（x）的根，即f（α）＝0。由于定义Ak为延迟的左移m序列，故α应该是f（x）的互反序列多项式（x）的根

由于式（2）中f（x）可以写成

故f（x）的互反多项式（x）为

由（α）＝0得

由于在二元域GF（2）上，多项式具有性质

可得

这里2t≤k／n，t在运算中选其满足条件的最大值。

令2t＝p，式（8）可以表示为

两边同乘以αk－np得

再令k＝np＋r，得

式（9）表明，αk可以分解为n个幂次低于k的α幂的线性组合。为了将αk最终分解为1，α，α2，…，αn－1的线性组合，将式（9）中αr以及满足Cn－i的αr＋ip继续按相同方法迭代分解为较低幂形式，同时将α的幂次相同的项相互抵消掉，直至将α的各次幂分解为低于幂次n为止。下面用代数算法举例。

例1 已知特征多项式为f（x）＝1＋x4＋x5＋x6＋x8的8级m序列，求与移存器输出延迟60比特的移位序列的组合内容。

解：由f（x）＝x8＋x4＋x3＋x2＋1

得α8＝α4＋α3＋α2＋1

由式（9）分解式为αk＝αr＋αr＋4p＋αr＋3p＋αr＋2p

现在求解α60

因为60＝22×8＋28r＝28，p＝22＝4

所以α60＝α28＋α44＋α40＋α36

因为28＝21×8＋12 44＝22×8＋12

40＝22×8＋8 36＝22×8＋4

所以α60＝α28＋α44＋α40＋α36＝（α12＋α20＋

α18＋α16）＋（α12＋α28＋α24＋

α20）＋（α8＋α24＋α20＋α16）＋

（α4＋α20＋α16＋α12）＝α4＋

α8＋α12＋α16＋α18＋α28＝

（8＝20×8＋02， 28＝21×8＋12）

α4＋（1＋α4＋α3＋α2）＋α12＋

α16＋α18＋（α12＋α20＋α18＋

α16）＝α2＋α3＋α20＋1＝

（20＝21×8＋4）

α2＋α3＋（α4＋α12＋α10＋α8）＋

1＝α2＋α3＋α4＋α8＋（α4＋α8＋

α7＋α6）＋（α2＋α6＋α5＋α4）＋1＝

1＋α3＋α4＋α5＋α7

分解结果表明，要得到相对于主m序列延迟60比特的延迟m序列，由第1，3，4，5，8级移存器输出序列进行模2和。

上述给出了求解延迟m序列线性组合关系的代数分解法，分析其算法的复杂度，可以发现：

（1）随着级数n的增加，对于大延迟k的分解复杂度急剧增加。

（2）若特征多项式的项数为s，对于αk，分解为α的各次幂的数目会有s－1项，当s较大时，随分解幂次的降低，分解的项数将不断增加。

（3）若特征多项式存在低幂次项，αk分解后的最高幂次衰减速度较慢，迭代分解复杂度也大大增加。

文献［6］用两两结合运算对代数分解法进行了改进，简化了计算，但没有从根本上降低在大级数多项数特征多项式条件下的分解复杂度。文献［7］把延迟m序列的线性组合问题映射成互反序列产生器状态，由推导互反序列产生器的状态递推式，来进行m序列组合分析的递推算法，但是任一延迟的m序列的线性组合需要由前一位递推得来，对于长m序列来说运算量依然庞大，工程上难以实现。

2 延迟m序列线性组合特性的分析

图1为一个n级m序列线性反馈移存器及其线性组合产生延迟m序列的原理图。m序列产生器n位状态和掩码d1d2d3…dn相与运算，当di＝1（i＝1，2，3，…，n）时，对应的第i级移存器的抽头接入模2加法器；当di＝0时则不接入，延迟m序列即为所有di＝1的移存器输出m序列线性组合的全体。

设A0＝｛a0a1a2…aL－1…｝是n级简单式移位寄存器（Simple shift register generator，SSRG）结构输出的主m序列，移存器的初始状态为S0＝｛a0a1a2…an－2an－1｝，每来一个时钟脉冲，移存器的状态顺次由S0变为S1，S2，S3，…，SL－1，…。因此 m 序列也可以用状态序列S＝｛S0S1S2…SL－1…｝表示。其中，Si是由序列A0中的连续n个元素构成，即Si＝｛aiai＋1ai＋2…ai＋n－2ai＋n－1｝，由于L＝2n－1为m序列周期，故SL＝S0。

图1 线性组合特性产生延迟m序列原理图Fig.1 Schematic diagram of producing delayed m－sequence

序列A0中任意n个连续的状态Si，Si＋1，Si＋2，…，Si＋n－2，Si＋n－1（i≥0）在 GF（2）上线性无关［8］，而n个元素的组合总数为可得 m序列线性组合理论：n级m序列的2n－1个平移等价序列即为n个相邻平移序列线性组合的全体。

由图1可知，第i时刻，主m序列状态向量Si与掩码向量［dndn－1…d2d1］相与后，再模2加得到延迟k位m序列第i时刻的码元ak＋i。即

式（10）可表示成

根据式（11），只要已知n个线性无关的主m序列状态向量及n个对应的延迟k位m序列输出码元，即可通过解线性方程组，求得线性组合关系的n维掩码向量。

为了方便获取方程组参数，令i＝0，即可从主m序列前2n个码元获得连续的n个线性无关的m序列状态向量S0，S1，S2，…，Sn－2，Sn－1，这n个状态向量所对应的n个延迟k位m序列码元ak，ak＋1，ak＋2，…，ak＋n－2，ak＋n－1即为主 m 序列第k时刻开始的n个输出码元。由式（11）及上述参数列出n元方程组

式（12）中的这种线性关系对应写成矩阵形式

利用矩阵的初等变换求解形如AX＝b形式的式（13）中线性方程组。若A可逆，方程组AX＝b的增广矩阵（A，b）经初等行变换可以化为（E，A－1b），其中E为单位阵，A－1b就是方程组的解，即求得的掩码向量。由于在二元域中，线性方程组进行的是模2运算，故矩阵亦采用模2运算进行矩阵初等行变换。

例2 特征多项式为f（x）＝1＋x4＋x5＋x6＋x8的8级移存器的输出的主m序列为

1 0 0 0 0 1 0 1 1 1 1 0 0 0 11 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0 11 0 1 1 1 0 0 10 0 0 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 1 1 1 1 1 0 1…求与移存器输出延迟60Byte的移位序列的组合内容。

从起始码元下划线取15个码元得到主m序列连续的8个状态，第2划线起始位为相对于主m序列延迟60Byte的m序列的起始位置，灰色下划线处为主m序列连续8个状态对应产生的延迟60～67Byte的8位码元且（a60a61a62a63a64a65a66a67）＝10111001。

根据式（12），列出该m序列状态与延迟码元的线性组合关系方程，将其排成增广矩阵的形式后进行二元域的初等行变换，用模2运算进行矩阵单位化

经过增广矩阵的初等行变换，求得掩码向量

对于8级m序列，延迟60位的m序列是由m序列产生器第1，3，4，5，8级移存器的输出序列线性组合得来，即设置掩码（d1d2d3d4d5d6d7d8）＝（10111001）。

3 N－CDMA通信系统用户掩码的分配设计

基于IS－95标准的N－CDMA通信系统是2G时代的典型代表。N－CDMA系统中的PN长码是由42位的掩码和1个42级线性反馈移位寄存器（Linear feedback shift register，LFSR）产生器生成。

N－CDMA系统给每个用户分配不同的私人42位掩码，这个42级长码产生器是通过掩码确定各级移存器输出m序列的线性组合方式，不同的掩码值能使m序列产生不同相位的长码，不同的用户使用不同相位的PN长码来标记各自的信道，这些长码在前向业务信道中起到数据扰乱加密的作用。在反向业务信道中，长码起到直接扩频多址的作用，PN长码的相位随机分配且不会重复，从而区分不同的移动台和用户［9］。长码序列的特征多项式如下

由于该长码序列既可以由基于式（14）中特征多项式、SSRG架构的LFSR产生，也可以由基于该式的互反多项式利用模块式移位寄存发生器（Multi－return shift register generator，MSRG）架构的LFSR产生［10］。图2给出了N－CDMA中利用MSRG架构的长码产生器生成不同相位长码的结构图。

图2 不同相位偏置的长码MSRG实现Fig.2 Long code achieved through MSRG

通常陆地移动通信环境的多径延迟小于20μs，为了实现多径分离，防止本地区用户的长码之间出现太大的相关值，针对速率为1.228 8 Mcps的长码扩频序列，不同用户长码相位间应该满足一定的相位差，即相位差码元数应大于1.228 8Mcps×20μs码片，故在工程应用上只对长码相位差满足条件的掩码进行随机分配，这样得到的私人掩码既满足多径分离对扩频地址码低相关性的要求，也能满足随机保密的要求。因此，用户掩码的分配设计需要由给定相位偏置的长码求解延迟m序列的线性组合关系即计算用户掩码。

下面以求解延迟半个周期（241位）长码的用户掩码为例，定量分析代数分解法的计算复杂度。由式（14）和式（9），可得到延迟241位的代数分解式

式中：r＝755 914 244 096，p＝235。

显然式（15）中分解后的这20项的幂均大于级数42，需要继续按相同方法迭代多次，直至将α的各幂次分解为低于42为止。以分解后最高幂次项为例，共需要迭代分解205次，由于每一项的分解都会产生20项低次幂，理论上用迭代分解法求解延迟241位长码的用户掩码共需迭代20205次，见表1。虽然在运算中通过抵消掉部分同次幂项，实际迭代次数会小于理论值，但分解的运算量仍然相当庞大，工程上处理起来相当复杂。

表1 代数法求解延迟241位长码掩码的复杂度分析Table 1 Complexity of Algebra algorithm

若采用线性方程组求解延迟241位长码的用户掩码，则不受m序列产生器抽头数目以及延迟位数的影响，可以方便地解决延迟m序列线性组合的问题。首先选取任意42比特作为移存器初始状态，利用式（14）产生长码序列，有

111111111111111111111111111111111111111111 00000001100111010100110010101000001110101011010110100100001110100111011100111100010…111010110110010110011001110110110111010 000第2划线起始位为相位延迟241位的长码位置，之间的码元在求解过程中没有运用，故省略。根据式（13），取前83码元构成的连续42个移存器状态和这42个状态对应产生的延迟长码（灰色划线部分比特）列出42×43的增广矩阵，编写程序对该矩阵进行二元域初等化变换得到单位阵，最后一列即为产生延迟241位的长码掩00111111101011 1111111100110011001110111100。

4 结束语

本文将矩阵初等化求解二元域线性方程组的方法应用于求解延迟m序列的线性组合关系，该方法相对于代数法运算复杂度大为简化，尤其对工程上难以求解的大延迟长m序列的线性组合关系而言，是一种行之有效的解决方法。

［1］Abhijit M.On the properties of pseudo noise sequences with a simple proposal of randomness test［J］.International Journal of Electrical and Computer Engineering，2008，3（3）：676－681.

［2］Zeng Fanxin，Ge Lijia.An algorithm for cycle and add property of m－sequence［C］／／The 2003IEEE Information Theory Workshop （ITW2003）.Paris，France：IEEE，2003：119－112.

［3］Kai P Y.A simple method for the determination of feedback shift register connections for delayed maximal－length sequences［J］.Proceedings of IEEE，1980，68（4）：537－538.

［4］Miller A J，Brown A W，Mars P.A simple technique for the determination of delayed maximal length linear binary sequences［J］.IEEE Trans Computers，1977，268（8）：808－811.

［5］张惠民.二元m序列自闭规律的确定及应用［J］.北京邮电大学学报，1980，2：107－115.Zhang Huimin.The closure law of binary m－sequence and its application［J］.Journal of Beijing University of Posts and Telecommunications，1980，2：107－115.

［6］周大华.延迟型m序列产生的几种方法［J］.电子学报，1982，2：94－96.Zhou Dahua.Several methods for the generation of delayed m－sequence［J］.Chinese Journal of Electronics，1982，2：94－96.

［7］周井泉.延迟m序列线性组合的递推算法［J］.南京邮电学院学报，1996，16（3）：95－97.Zhou Jingquan.A recurring algorithm of multiplex problem for delayed m－sequence［J］.Journal of Nanjing Institute of Posts and Telecommunications，1996，16（3）：95－97.

［8］万哲先.代数与编码［M］.3版.北京：高等教育出版社，2008：260－273.Wan Zhexian.Algebra and coding［M］.Third Edition.Beijing：Higher Education Press，2008：260－273.

［9］TIA／EIA－95－B.Mobile station－base station compatibility standard for dual－mode spread spectrum systems［M］.Washington，America：ANSI Publication Version，1998.

［10］Kim S C，Lee B G.Parallel scrambling techniques for multibit－interleaved multiplexing environments［C］／／Proc ICC′93. Geneva： ［s.n.］，1993：1526－1530.