m序列的产生与本原多项式

由n级串联的移位寄存器和反馈逻辑线路可组成动态移位寄存器，如果反馈逻辑线路只由模2和构成，则称为线性反馈移位寄存器。带线性反馈逻辑的移位寄存器设定初始状态后，在时钟触发下，每次移位后各级寄存器会发生变化，其中任何一级寄存器的输出，随着时钟节拍的推移都会产生一个序列，该序列称为移位寄存器序列。n级线性移位寄存器如下图所示：
在这里插入图片描述

图（2）n级线性移位寄存器
图中Ci表示反馈线的两种可能连接方式，Ci=1表示连线接通，第n-i级输出加入反馈中；Ci=0表示连线断开，第n-i级输出未参加反馈。因此，一般形式的线性反馈逻辑表达式为
在这里插入图片描述
将等式左边的an移至右边，并将an=C0an（C0=1）带入上式，则上式可以写成
在这里插入图片描述
定义一个与上式相对应的多项式
在这里插入图片描述
其中x的幂次表示元素的相应位置。该式为线性反馈移位寄存器的特征多项式，特征多项式与输出序列的周期有密切关系。当F(x)满足下列三个条件时，就一定能产生m序列：

（1）F(x)是不可约的，即不能再分解多项式；

（2）F（x）可整除xn+1，这里p=2n+1；

（3）F（x）不能整除xn+1，这里q<q.

满足上述条件的多项式称为本原多项式，这样产生m序列的充要条件就变成了如何寻找本原多项式。

***本原多项式的寻找

一、求n次本原多项式F（x）的方法：

（1）将xm+1（xm-1）（m=xn-1）因式分解到已经不能再分解；
（2）在得到的因式集合中，排除掉所有少于n次的因式；
（3）其余的因式若不能整除任何xq+1（q<m），则这个因式为本原多项式F（x），可能不止一个。
（注：这里的n可理解成线性反馈移位寄存器的级数）

二、本原多项式F（x）与m序列的联系：

（1）m序列的特征多项式即为n阶本原多项式；
（2）1/F（x）作多项式长除法得到的商多项式系数序列就是m序列。

例子：求n=4本原多项式并得到m序列（n=4相当于级数为4）

xm + 1 = xm - 1=（x4 + x3 + x2 + x + 1) (x4 + x + 1) (x4 + x3 + 1) ( x2 + x + 1) (x+1)
其中 ( x2 + x + 1) 、(x+1)的次数小于4被排除。
其中（x4 + x3 + x2 + x + 1)可整除x5 + 1 = x5 - 1，也被排除。其长除法如下图（3）：

在这里插入图片描述
故本原多项式有 x4 + x + 1、 x4 + x3 + 1。F（x）= x4 + x + 1，F1（x）= x4 + x3 + 1 分别对应一个m序列，可以由多项式1/F（x）长除法算出m序列，如下图（4）：
在这里插入图片描述
q(x)= x-4 + x-7 + x-8 + x-10 + x-12 + x-13 + x-14 + x-15 +x-19+…
对应m序列：100110101101000（15个码元，即周期为15）、100110101101000…（周期性循环）

三、 互反多项式

F1（x）= F（x-1）xn，即F1（x）与 F（x）为 互反多项式，也就是说它们产生的序列顺序互反的，m序列的反序列亦是m序列。