线性反馈移位寄存器（linear feedback shift register, LFSR）是指，给定前一状态的输出，将该输出的线性函数再用作输入的移位寄存器。异或运算是最常见的单比特线性函数：对寄存器的某些位进行异或操作后作为输入，再对寄存器中的各比特进行整体移位。下面小编给大家介绍一下“线性反馈移位寄存器原理详解 线性反馈移位寄存器的实现”
一、线性反馈移位寄存器原理详解
移位寄存器是产生信号和序列的常用设备，它分为线性和非线性两大类，著名的一序列和序列就是分别由线性和非线性反馈移位寄存器所生成的。
线性反馈移位寄存器通常由动态或静态主从型触发器构成。反馈回路由异或门构成。其特性通常由一个特征多项式表征。使用二输入异或门计算反馈函数的最大长度或近最大长度不纠立寄存器的特征多项式。这种电路的特点是结构简单，它的上限移位速度取决于移位单元的延迟时间和二输入异或门的延迟时间，因此，能获得较高的速度 。线性反馈移位寄存器中的移位单元是由主一从型边沿触发器构成的。在这种结构的移位单元中，主从两极锁存器在两相不交叠时钟的控制下，使数据在时钟上升沿被采样，并一直保持到下一个时钟上升沿。电路中四个移位单元都是由动态主从边沿型触发器构成的，每次移位的操作都需要数据串行依次经过两级锁存器。
赋给寄存器的初始值叫做“种子”，因为线性反馈移位寄存器的运算是确定性的，所以，由寄存器所生成的数据流完全决定于寄存器当时或者之前的状态。而且，由于寄存器的状态是有限的，它最终肯定会是一个重复的循环。然而，通过本原多项式，线性反馈移位寄存器可以生成看起来是随机的且循环周期非常长的序列。移位寄存器结构简单，运行速度快，实用的密钥流产生器大多基于移位寄存器，移位寄存器理论也成了现代流密码体制的基础。
移位寄存器包括两个部分：
1）级，每一级包含一个比特，比如11010110是一个8级的移位寄存器产生的
2）反馈函数，线性反馈移位寄存器的反馈函数是线性的，非线性反馈移位寄存器的反馈函数是非线性的
一个级的移位寄存器产生的序列的最大周期为，当然这个最大周期跟反馈函数有很大关系，线性反馈函数实际上就是这个级的移位寄存器选取“某些位”进行异或后得到的结果，这里的“某些位”的选取很重要，得到线性反馈函数之后，把这个移位寄存器的每次向右移动一位，把最右端的作为输出，把“某些位”的异或结果作为输入放到最左端的那位，这样所有的输出对应一个序列，这个序列叫做M序列，是最长线性移位寄存器序列的简称。
选取的“某些位”构成的序列叫做抽头序列，理论表明，要使LFSR得到最长的周期，这个抽头序列构成的多项式加1必须是一个本原多项式，也就是说这个多项式不可约，比如。
下面以一个4位的线性反馈移位寄存器为例说明它的工作原理。
（图片来源于互联网）
如果a3,a2,a1,a0的值分别是1 0 0 0，反馈函数选取，那么得到如下序列
（图片来源于互联网）
可以看出周长为15。在这一个周期里面涵盖了开区间内的所有整数，并且都是没有固定顺序出现的，有很好的随机性。
二、线性反馈移位寄存器的实现
1、写出n阶线性反馈移位寄存器的实现过程
2、假设一个GF（2）上的5阶线性反馈移位寄存器的反馈函数为f（x1，x2，x3，x4，x5）=x1+x5，初始状态为10011，试写出该线性反馈移位寄存器的输出序列
程序：
#include《iostream》
#include《math.h》
using namespace std;
void GF（int a，int n）
{
int b;
for（int i=1;i《32;i++）
{
cout《《（a&1）;
b=a&1^（（a》》4）&1）;
a=a》》1^（b《《4）;
}
}
int main（）
{
int a=0，b;
int n;
cout《《“请输入线性移位寄存器的阶数：”;
cin》》n;
cout《《“请输入初始状态：”;
for（int i=1;i《=n;i++）
{
cin》》b;
a=a^（b《《（i-1））;
}
cout《《“输出序列为：”;
GF（a，n）;
cout《《endl;
return 0;
}
（图片来源于互联网）
评论 (0)