LFSR的数学原理
LFSR的定义
线性反馈移位寄存器（英语：Linear feedback shift register，LFSR）是指给定前一状态的输出，将该输出的线性函数再用作输入的移位寄存器。异或运算是最常见的单比特线性函数：对寄存器的某些位进行异或操作后作为输入，再对寄存器中的各比特进行整体移位。
赋予寄存器的初始值叫做“种子”，因为LFSR的传输函数的运算是确定的，所以给定不同的种子可以得到不同的序列。而且，由于寄存器的所有状态是一个有限值，因此其一定会循环。通过本原多项式，LFSR可以生成看起来是随机的且循环周期非常长的序列，也就是M序列(伪随机数)。
LFSR的应用
- 生成伪随机数
- 伪随机噪声序列
- 快速数字计数器
- 扰频器
- 循环冗余校验CRC
异或的数学表达
逻辑表达
异或在数字逻辑上的操作为：相同为0，相异为1。用符号xor或者⊕表示。同时，异或也可以理解为模2加法和模2减法。
模2运算
模2运算是二进制算法的一种，是CRC校验中的核心算法。模2运算与普通的四则运算一样，使用＋－×÷的符号来表达加减乘除，但是它与普通的四则运算的区别在于，模2运算不考虑进位和借位。
模2加法
可以由以下式子定义。
- 0 + 0 = 0
- 0 + 1 = 1
- 1 + 0 = 1
- 1 + 1 = 0
从上面的定义可以看出，模2加法与异或操作得到的结果是一致的。
模2减法
同理，给出模2减法的定义式。
- 0 - 0 = 0
- 0 - 1 = 1
- 1 - 0 = 1
- 1 - 1 = 0
从上面的定义可以看出，模2减法也与异或操作得到的结果一致。
模2乘法
两个二进制数的模2乘法是指在乘法竖式运算中，需要用到加法的地方都使用模2加法，即异或运算。例如模2乘法1010*101=100010，1⊕0⊕1=0，没有进位。
1 0 1 0
x 1 0 1
————————————
1 0 1 0
0 0 0 0
1 0 1 0
————————————
1 0 0 0 1 0
模2除法
同模2乘法，在需要做减法的地方都使用模2减法，即异或运算。
1 0 1
___________
1 0 1 ) 1 0 0 0 0
1 0 1
——————
0 1 0
0 0 0
——————
1 0 0
1 0 1
——————
1
LFSR的反馈函数
LFSR的反馈函数就是简单地对移位寄存器中的某些位进行异或，并将异或的结果输入到LFSR的最左端(假设最左端为输入端)。我们把参与异或的那一位称为抽头。如图所示，抽头依次与输出比特进行异或运算，然后反馈回最左端的位。最右端位置所生成的序列被称为输出流。
- 影响LFSR下一个状态的比特位叫做抽头（图中黑色数字）
- 最大长度的LFSR生成一个M序列（例如，只有与有一定抽序列的LFSR才能通过所有 2n − 1 个内部状态，不包括全零状态），除非它本身为全零，亦即状态永不改变
- 作为基于异或运算的LFSR的替换，LFSR也可以给予同或运算。与使用异或门的LFSR全0状态下为无效状态相应的，使用同或门的LFSR在全1状态下也是无效的。
LFSR的特征多项式
在LFSR中，抽头的设定可以用有限域算数中模2的多项式来表示。这就意味着，多项式中的所有系数必须是“1”或者“0”。这个多项式被称作回授多项式或特征多项式。例如图中的抽头为在第16，14，13，11个比特，则相应的特征多项式为：
$ x{16}+x+x{13}+x+1$
多项式中常数“1”并不代表某一个抽头，它所指的是一个比特位的输入（例如 x0,等效为 1 ）。多项式中的指数代表从左至右的抽头位。第一个和最后一个比特一般相应的是输入和输出位。
当且仅当相应的特征多项式是本原多项式时，LFSR才能达到最大长度。这表示以下条件是必须的：
- 抽头的数量必须为偶数
- 抽头之间不能成对出现，必须是互质的
本原多项式产生的寄存器序列被称之为M序列，在固定的N位下，由上述条件可知，本原多项式不是唯一的，也就是说M序列也不是唯一的