一種求解延遲型m序列線性組合的新算法

陳德宏 劉 梅

（安徽工業(yè)大學(xué)電氣信息學(xué)院，馬鞍山，243002）

引 言

偽隨機(jī)信號在CDMA通信、遙控、遙測、信息加密和衛(wèi)星導(dǎo)航系統(tǒng)有著廣泛的應(yīng)用。m序列作為最大長度線性反饋移位寄存器序列，是一類重要的也是目前研究最多的偽隨機(jī)序列。在偽隨機(jī)信號應(yīng)用處理的過程中，經(jīng)常需要產(chǎn)生相對時延不同的主m序列的平移等價序列，若采用原始方法（如設(shè)立一系列延時門），則由于器件組成龐大，求解過程繁瑣而耗時長，這在延遲型長m序列實(shí)際研究中就顯得很不現(xiàn)實(shí)。

設(shè)A0是二元域GF（2）上的m序列，用Ai表示序列A0左移i位得到的新序列，序列Ai與A0具有相同的特征多項(xiàng)式，即Ai與A0具有相同的遞歸關(guān)系。若用集合G（f）表示所有適合特征多項(xiàng)式f（x）的序列的全體，則集合G（f）中非零元素Ai都是m序列，它們具有以下性質(zhì)

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

且i≠j（modL）

則

這個性質(zhì)稱為m序列的移位相加特性，也稱為自閉特性。由于m序列發(fā)生器各級移位寄存器的輸出只是相移不同的平移等價m序列，通過m序列移位相加特性，可知延遲m序列可以由m序列發(fā)生器的各移位寄存器輸出序列經(jīng)模2和運(yùn)算獲得，即m序列的線性組合特性［1］。

m序列線性組合特性為獲得延遲m序列提供了便利，在長m序列的設(shè)計(jì)中具有經(jīng)濟(jì)靈活的實(shí)用價值。對于一個特定的延遲k位m序列是由n級移存器的哪幾級輸出序列模2和得到的問題，在理論上一直沒有一個確定性的普遍公式，文獻(xiàn)［2－4］利用有限域的代數(shù)法將延遲k位m序列分解為幾個低延遲的m序列模2和，之后再進(jìn)行多次迭代，直至分解為幾個n級以內(nèi)延遲m序列的線性模2和。

本文首先分析了m序列線性組合關(guān)系的代數(shù)迭代求解算法，針對該算法在解決多抽頭大延遲長m序列時，迭代過程冗長繁雜、工程上難以實(shí)現(xiàn)等問題，利用主m序列狀態(tài)與延遲m序列在二元域上存在的線性關(guān)系，提出了用求解二元域線性方程組獲得延遲m序列線性組合關(guān)系的方法，工程計(jì)算量得到大幅簡化，并將其成功運(yùn)用到N－CDMA移動通信系統(tǒng)用戶掩碼的分配設(shè)計(jì)中，同時通過對特定241位的大延遲長碼掩碼的求解，定量分析了采用傳統(tǒng)代數(shù)迭代法的計(jì)算復(fù)雜度。

1 m序列線性組合關(guān)系求解的代數(shù)算法

有限域上多項(xiàng)式是研究偽隨機(jī)序列的重要數(shù)學(xué)工具。代數(shù)算法就是由二元域m序列特征多項(xiàng)式f（x）和延遲算子多項(xiàng)式xk，利用在二元域上定義的多項(xiàng)式的模2運(yùn)算法則求解m序列線性組合關(guān)系［5］。

m序列A0可以寫成如下形式：A0＝｛a0a1a2…aL－1…｝，其周期L＝2n－1，特征多項(xiàng)式為

由于集合G（f）表示所有適合特征多項(xiàng)式f（x）的延遲序列全體，將G（f）用兩兩不同的元素表示出來，有

集合G（f）可看作一個含有L＋1個元素的有限域，其中θ＝｛0 0 0 … 0｝是滿足特征多項(xiàng)式f（x）零序列。G（f）中的非零元素組成周期L的循環(huán)群，非零元素就是所求的延遲m序列，任一個非零元素Ak均可表示成一本原元α的冪。

令α0＝A0＝1，α＝A1，則G（f）＝｛θ1αα2…αL－1｝。本原元α是m序列特征多項(xiàng)式f（x）的根，即f（α）＝0。由于定義Ak為延遲的左移m序列，故α應(yīng)該是f（x）的互反序列多項(xiàng)式（x）的根

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

故f（x）的互反多項(xiàng)式（x）為

由（α）＝0得

由于在二元域GF（2）上，多項(xiàng)式具有性質(zhì)

可得

這里2t≤k／n，t在運(yùn)算中選其滿足條件的最大值。

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

兩邊同乘以αk－np得

再令k＝np＋r，得

式（9）表明，αk可以分解為n個冪次低于k的α冪的線性組合。為了將αk最終分解為1，α，α2，…，αn－1的線性組合，將式（9）中αr以及滿足Cn－i的αr＋ip繼續(xù)按相同方法迭代分解為較低冪形式，同時將α的冪次相同的項(xiàng)相互抵消掉，直至將α的各次冪分解為低于冪次n為止。下面用代數(shù)算法舉例。

例1 已知特征多項(xiàng)式為f（x）＝1＋x4＋x5＋x6＋x8的8級m序列，求與移存器輸出延遲60比特的移位序列的組合內(nèi)容。

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

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

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

現(xiàn)在求解α60

因?yàn)?0＝22×8＋28r＝28，p＝22＝4

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

因?yàn)?8＝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

分解結(jié)果表明，要得到相對于主m序列延遲60比特的延遲m序列，由第1，3，4，5，8級移存器輸出序列進(jìn)行模2和。

上述給出了求解延遲m序列線性組合關(guān)系的代數(shù)分解法，分析其算法的復(fù)雜度，可以發(fā)現(xiàn)：

（1）隨著級數(shù)n的增加，對于大延遲k的分解復(fù)雜度急劇增加。

（2）若特征多項(xiàng)式的項(xiàng)數(shù)為s，對于αk，分解為α的各次冪的數(shù)目會有s－1項(xiàng)，當(dāng)s較大時，隨分解冪次的降低，分解的項(xiàng)數(shù)將不斷增加。

（3）若特征多項(xiàng)式存在低冪次項(xiàng)，αk分解后的最高冪次衰減速度較慢，迭代分解復(fù)雜度也大大增加。

文獻(xiàn)［6］用兩兩結(jié)合運(yùn)算對代數(shù)分解法進(jìn)行了改進(jìn)，簡化了計(jì)算，但沒有從根本上降低在大級數(shù)多項(xiàng)數(shù)特征多項(xiàng)式條件下的分解復(fù)雜度。文獻(xiàn)［7］把延遲m序列的線性組合問題映射成互反序列產(chǎn)生器狀態(tài)，由推導(dǎo)互反序列產(chǎn)生器的狀態(tài)遞推式，來進(jìn)行m序列組合分析的遞推算法，但是任一延遲的m序列的線性組合需要由前一位遞推得來，對于長m序列來說運(yùn)算量依然龐大，工程上難以實(shí)現(xiàn)。

2 延遲m序列線性組合特性的分析

圖1為一個n級m序列線性反饋移存器及其線性組合產(chǎn)生延遲m序列的原理圖。m序列產(chǎn)生器n位狀態(tài)和掩碼d1d2d3…dn相與運(yùn)算，當(dāng)di＝1（i＝1，2，3，…，n）時，對應(yīng)的第i級移存器的抽頭接入模2加法器；當(dāng)di＝0時則不接入，延遲m序列即為所有di＝1的移存器輸出m序列線性組合的全體。

設(shè)A0＝｛a0a1a2…aL－1…｝是n級簡單式移位寄存器（Simple shift register generator，SSRG）結(jié)構(gòu)輸出的主m序列，移存器的初始狀態(tài)為S0＝｛a0a1a2…an－2an－1｝，每來一個時鐘脈沖，移存器的狀態(tài)順次由S0變?yōu)镾1，S2，S3，…，SL－1，…。因此 m 序列也可以用狀態(tài)序列S＝｛S0S1S2…SL－1…｝表示。其中，Si是由序列A0中的連續(xù)n個元素構(gòu)成，即Si＝｛aiai＋1ai＋2…ai＋n－2ai＋n－1｝，由于L＝2n－1為m序列周期，故SL＝S0。

圖1 線性組合特性產(chǎn)生延遲m序列原理圖Fig.1 Schematic diagram of producing delayed m－sequence

序列A0中任意n個連續(xù)的狀態(tài)Si，Si＋1，Si＋2，…，Si＋n－2，Si＋n－1（i≥0）在 GF（2）上線性無關(guān)［8］，而n個元素的組合總數(shù)為可得 m序列線性組合理論：n級m序列的2n－1個平移等價序列即為n個相鄰平移序列線性組合的全體。

由圖1可知，第i時刻，主m序列狀態(tài)向量Si與掩碼向量［dndn－1…d2d1］相與后，再模2加得到延遲k位m序列第i時刻的碼元ak＋i。即

式（10）可表示成

根據(jù)式（11），只要已知n個線性無關(guān)的主m序列狀態(tài)向量及n個對應(yīng)的延遲k位m序列輸出碼元，即可通過解線性方程組，求得線性組合關(guān)系的n維掩碼向量。

為了方便獲取方程組參數(shù)，令i＝0，即可從主m序列前2n個碼元獲得連續(xù)的n個線性無關(guān)的m序列狀態(tài)向量S0，S1，S2，…，Sn－2，Sn－1，這n個狀態(tài)向量所對應(yīng)的n個延遲k位m序列碼元ak，ak＋1，ak＋2，…，ak＋n－2，ak＋n－1即為主 m 序列第k時刻開始的n個輸出碼元。由式（11）及上述參數(shù)列出n元方程組

式（12）中的這種線性關(guān)系對應(yīng)寫成矩陣形式

利用矩陣的初等變換求解形如AX＝b形式的式（13）中線性方程組。若A可逆，方程組AX＝b的增廣矩陣（A，b）經(jīng)初等行變換可以化為（E，A－1b），其中E為單位陣，A－1b就是方程組的解，即求得的掩碼向量。由于在二元域中，線性方程組進(jìn)行的是模2運(yùn)算，故矩陣亦采用模2運(yùn)算進(jìn)行矩陣初等行變換。

例2 特征多項(xiàng)式為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的移位序列的組合內(nèi)容。

從起始碼元下劃線取15個碼元得到主m序列連續(xù)的8個狀態(tài)，第2劃線起始位為相對于主m序列延遲60Byte的m序列的起始位置，灰色下劃線處為主m序列連續(xù)8個狀態(tài)對應(yīng)產(chǎn)生的延遲60～67Byte的8位碼元且（a60a61a62a63a64a65a66a67）＝10111001。

根據(jù)式（12），列出該m序列狀態(tài)與延遲碼元的線性組合關(guān)系方程，將其排成增廣矩陣的形式后進(jìn)行二元域的初等行變換，用模2運(yùn)算進(jìn)行矩陣單位化

經(jīng)過增廣矩陣的初等行變換，求得掩碼向量

對于8級m序列，延遲60位的m序列是由m序列產(chǎn)生器第1，3，4，5，8級移存器的輸出序列線性組合得來，即設(shè)置掩碼（d1d2d3d4d5d6d7d8）＝（10111001）。

3 N－CDMA通信系統(tǒng)用戶掩碼的分配設(shè)計(jì)

基于IS－95標(biāo)準(zhǔn)的N－CDMA通信系統(tǒng)是2G時代的典型代表。N－CDMA系統(tǒng)中的PN長碼是由42位的掩碼和1個42級線性反饋移位寄存器（Linear feedback shift register，LFSR）產(chǎn)生器生成。

N－CDMA系統(tǒng)給每個用戶分配不同的私人42位掩碼，這個42級長碼產(chǎn)生器是通過掩碼確定各級移存器輸出m序列的線性組合方式，不同的掩碼值能使m序列產(chǎn)生不同相位的長碼，不同的用戶使用不同相位的PN長碼來標(biāo)記各自的信道，這些長碼在前向業(yè)務(wù)信道中起到數(shù)據(jù)擾亂加密的作用。在反向業(yè)務(wù)信道中，長碼起到直接擴(kuò)頻多址的作用，PN長碼的相位隨機(jī)分配且不會重復(fù)，從而區(qū)分不同的移動臺和用戶［9］。長碼序列的特征多項(xiàng)式如下

由于該長碼序列既可以由基于式（14）中特征多項(xiàng)式、SSRG架構(gòu)的LFSR產(chǎn)生，也可以由基于該式的互反多項(xiàng)式利用模塊式移位寄存發(fā)生器（Multi－return shift register generator，MSRG）架構(gòu)的LFSR產(chǎn)生［10］。圖2給出了N－CDMA中利用MSRG架構(gòu)的長碼產(chǎn)生器生成不同相位長碼的結(jié)構(gòu)圖。

圖2 不同相位偏置的長碼MSRG實(shí)現(xiàn)Fig.2 Long code achieved through MSRG

通常陸地移動通信環(huán)境的多徑延遲小于20μs，為了實(shí)現(xiàn)多徑分離，防止本地區(qū)用戶的長碼之間出現(xiàn)太大的相關(guān)值，針對速率為1.228 8 Mcps的長碼擴(kuò)頻序列，不同用戶長碼相位間應(yīng)該滿足一定的相位差，即相位差碼元數(shù)應(yīng)大于1.228 8Mcps×20μs碼片，故在工程應(yīng)用上只對長碼相位差滿足條件的掩碼進(jìn)行隨機(jī)分配，這樣得到的私人掩碼既滿足多徑分離對擴(kuò)頻地址碼低相關(guān)性的要求，也能滿足隨機(jī)保密的要求。因此，用戶掩碼的分配設(shè)計(jì)需要由給定相位偏置的長碼求解延遲m序列的線性組合關(guān)系即計(jì)算用戶掩碼。

下面以求解延遲半個周期（241位）長碼的用戶掩碼為例，定量分析代數(shù)分解法的計(jì)算復(fù)雜度。由式（14）和式（9），可得到延遲241位的代數(shù)分解式

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

顯然式（15）中分解后的這20項(xiàng)的冪均大于級數(shù)42，需要繼續(xù)按相同方法迭代多次，直至將α的各冪次分解為低于42為止。以分解后最高冪次項(xiàng)為例，共需要迭代分解205次，由于每一項(xiàng)的分解都會產(chǎn)生20項(xiàng)低次冪，理論上用迭代分解法求解延遲241位長碼的用戶掩碼共需迭代20205次，見表1。雖然在運(yùn)算中通過抵消掉部分同次冪項(xiàng)，實(shí)際迭代次數(shù)會小于理論值，但分解的運(yùn)算量仍然相當(dāng)龐大，工程上處理起來相當(dāng)復(fù)雜。

表1 代數(shù)法求解延遲241位長碼掩碼的復(fù)雜度分析Table 1 Complexity of Algebra algorithm

若采用線性方程組求解延遲241位長碼的用戶掩碼，則不受m序列產(chǎn)生器抽頭數(shù)目以及延遲位數(shù)的影響，可以方便地解決延遲m序列線性組合的問題。首先選取任意42比特作為移存器初始狀態(tài)，利用式（14）產(chǎn)生長碼序列，有

111111111111111111111111111111111111111111 00000001100111010100110010101000001110101011010110100100001110100111011100111100010…111010110110010110011001110110110111010 000第2劃線起始位為相位延遲241位的長碼位置，之間的碼元在求解過程中沒有運(yùn)用，故省略。根據(jù)式（13），取前83碼元構(gòu)成的連續(xù)42個移存器狀態(tài)和這42個狀態(tài)對應(yīng)產(chǎn)生的延遲長碼（灰色劃線部分比特）列出42×43的增廣矩陣，編寫程序?qū)υ摼仃囘M(jìn)行二元域初等化變換得到單位陣，最后一列即為產(chǎn)生延遲241位的長碼掩00111111101011 1111111100110011001110111100。

4 結(jié)束語

本文將矩陣初等化求解二元域線性方程組的方法應(yīng)用于求解延遲m序列的線性組合關(guān)系，該方法相對于代數(shù)法運(yùn)算復(fù)雜度大為簡化，尤其對工程上難以求解的大延遲長m序列的線性組合關(guān)系而言，是一種行之有效的解決方法。

［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，F(xiàn)rance：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序列自閉規(guī)律的確定及應(yīng)用［J］.北京郵電大學(xué)學(xué)報，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序列產(chǎn)生的幾種方法［J］.電子學(xué)報，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］.南京郵電學(xué)院學(xué)報，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］萬哲先.代數(shù)與編碼［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.