特征多項式的倒量即為m序列的推導(dǎo)

【摘要】 本文主要結(jié)合矩陣論知識分析了m序列與其特征多項式之間的關(guān)系，并利用matlab進(jìn)行仿真實驗，將長除特征多項式與仿真輸出序列得到的序列進(jìn)行比對。

【關(guān)鍵詞】 特征多項式 m序列 MATLAB

m序列是一種最長的線性移位寄存器序列，同時也是一種非常重要的偽隨機(jī)序列，這種序列有比較好的自相關(guān)特性而且易于產(chǎn)生。m序列在直擴(kuò)系統(tǒng)中用來對要傳遞的信號進(jìn)行擴(kuò)展，m序列在跳頻系統(tǒng)中主要用于控制跳頻系統(tǒng)的頻率合成器，并生成隨機(jī)跳頻圖案[1]。更重要的是m序列可由它的特征多項式直接計算產(chǎn)生出來，本文將對它的計算式進(jìn)行推導(dǎo)，并給出基于matlab的軟件仿真結(jié)果。

此外，本文的涉及到的運算都是模二運算，運算結(jié)果最終都是除2取余，即xmod2，例如：2mod2=0，7mod2=1等等。

一、問題描述

m序列是一種最長的線性移位寄存器序列且經(jīng)常使用的，是移位寄存器加反饋后得出的。結(jié)構(gòu)圖如圖1所示。圖中an-i（i=1，2，3，…，r）是每位寄存器在移位寄存器中的狀態(tài)；ci（i=1，2，3，…，r）反饋系數(shù)是第i位寄存器的。當(dāng)ci=0時，意味著是沒有反饋的，這時反饋線要斷開；當(dāng)ci=1時，意味著有反饋，這就要將反饋線連接起來。在這個結(jié)構(gòu)中c0= cr=1，c0=0說明著不存在反饋，是靜態(tài)移位寄存器，反饋移位寄存器：cr=0則降級為r-1級。

序列多項式：

（1）

序列{an}即為m序列，且為周期序列，滿足：

（2）

二、理論推導(dǎo)

令移位寄存器的現(xiàn)在表達(dá)的狀態(tài)和下一次表達(dá)的狀態(tài)分別由矢量bn和bn+1表示，分別為：

bn=[an-1 an-2 an-3 … an-r]T （3）

bn+1=[a（n+1）-1 a（n+1）-2 a（n+1）-3 … a（n+1）-r]T （4）

取狀態(tài)轉(zhuǎn)移矩陣A為：

（5）

則將有：

（6）

那么m時刻的狀態(tài)與現(xiàn)態(tài)之間的關(guān)系為：

（7）

當(dāng)Ammod2=E且m=2r-1時，m序列為該反饋移位寄存器產(chǎn)生的序列。

下面求A的特征多項式：

（8）

由此可得：

（9）

即

（10）

經(jīng)整理后

（11）

由Caley-Hamilton定理：一個滿足自己的特征方程rxr矩陣，即

（12）

根據(jù)A的特征方程，我們定義特征多項式f（x）為：

（13）

接下來推導(dǎo)G（x）與f（x）之間的關(guān)系：

令線性移位寄存器序列為：

{an}=a0，a1，a2，…，an，…

相應(yīng)的序列多項式為：

（14）

{an}的線性遞歸反饋函數(shù)為

（15）

則

（16）

交換求和次序并做變量代換：

（17）

整理后，并考慮c0=1，則有

（18）

選擇移位寄存器的最初狀態(tài)為a-r，a-r+1=…=a-2=a-1=0，則式（17）的分子

（19）

由此可得：

（20）

三、實驗數(shù)據(jù)和結(jié)果

3.1給定m序列性質(zhì)的驗證

特征多項式為，m=2r-1=25-1=31，其狀態(tài)轉(zhuǎn)移矩陣為：

（21）

1、周期性

運行matlab，輸入A^31得：

（22）

對A^31進(jìn)行模二運算rem（A^31，2）得：

（23）

2、最長序列性

下面抽取計算A的11，13，23，29，30次冪，驗證其最長性：計算結(jié)果如下：

3.2 m序列的產(chǎn)生

仍以特征多項式為f（x）=1+x2+x5的m序列為例。

1、長除法求

由理論推導(dǎo)結(jié)果G（x）=1/ f（x）對f（x）進(jìn)行長除得：

（24）

2、Matlab反饋仿真移位寄存器

取移位寄存器起始值為pninitial=[0 0 0 0 1]，由特征多項式能得反饋系數(shù)為：

（25）

狀態(tài)矩陣為：

（26）

產(chǎn)生的m序列如圖2：

由圖2可以看出m序列的周期為31，即：

（27）

五、結(jié)果分析與說明

從以上實驗，我們可以得出以下結(jié)論：

1）多項式長除法和matlab仿真反饋移位寄存器得出的結(jié)果完全一致，這充分說明了序列多項式與特征多項式之間存在倒量關(guān)系；

2）m序列特征矩陣的周期性由A^31mod2=E驗證；

3）周期恰好為2r-1時，A的其它次冪均不等于E充分說明了序列的最長性。

參 考 文 獻(xiàn)

[1]李新，何傳江.矩陣?yán)碚摷捌鋺?yīng)用.重慶：重慶大學(xué)出版社，2005

[2]曾興雯，劉乃安，孫獻(xiàn)璞.擴(kuò)展頻譜通信及其多址技術(shù).西安：西安電子科技大學(xué)出版社，2004

[3]趙鴻圖，茅艷，趙軍良等，通信原理MATLAB仿真教程，北京：人民郵電出版社，2010

[4]陳海龍，李宏.基于MATLAB 的偽隨機(jī)序列的產(chǎn)生和分析[J].計算機(jī)仿真.2005

作者簡介：房萬順（1991.05）男，天津人，就讀于山西師范大學(xué)，所學(xué)專業(yè)：電子信息工程。