线性反馈移位寄存器LFSR（斐波那契LFSR（多到一型）和伽罗瓦LFSR（一到多型）|verilog代码|Testbench|仿真结果）

数字IC经典电路设计

经典电路设计是数字IC设计里基础中的基础，盖大房子的第一部是打造结实可靠的地基，每一篇笔者都会分门别类给出设计原理、设计方法、verilog代码、Testbench、仿真波形。然而实际的数字IC设计过程中考虑的问题远多于此，通过本系列希望大家对数字IC中一些经典电路的设计有初步入门了解。能力有限，纰漏难免，欢迎大家交流指正。快速导航链接如下：

个人主页链接

1.数字分频器设计

2.序列检测器设计

3.序列发生器设计

4.序列模三检测器设计

5.奇偶校验器设计

6.自然二进制数与格雷码转换

7.线性反馈移位寄存器LFSR

8.四类九种移位寄存器总结

9.串并转换

一．前言

移位寄存器是一种可以将二进制数据按照一定的规律进行向左或向右的移动，并在输出端获取相应结果的数字电路。

假如我们将右端的移出的数据置于左端的空位就形成了一个反馈回路。

在现代密码学中存在一种特殊移位寄存器——线性反馈移位寄存器（Feedback Shift Register，FSR）。

线性反馈移位寄存器由N级触发器和若干异或门组成，事先选定初始值即随机种子(seed)和抽头（参与运算的比特位），再在种子的基础和抽头的运算下得到一组人工生成的伪随机序列。之所以是伪随机序列，是因为该随机数是按照一定算法模拟产生的，其结果是确定的并且可预见的，因此并不是真正的随机数。对于LFSR随机种子和抽头的选择就十分重要，如果随机种子和抽头发生改变，线性反馈移位寄存器LFSR产生的随机数也会相应改变。

LFSR广泛应用于伪随机数生成、伪噪声序列生成、计数器、数据的加密和CRC校验、扰码器/解码器、信号生成和测试等领域，是一种非常有用的数字电路设计技术。

下面对其中的一些典型应用进行介绍。

伪随机序列发生器：LFSR 可以按比特位顺序产生一个周期性序列，并通过适当的反馈多项式来调节其生成的序列，可作为数字化通信中的伪随机序列发生器使用。 LFSR计数器:LFSR可用于构建通过随机序列状态进行计数的计数器。 与常见的计数器相比， LFSR计数器具有速度快 、 消耗逻辑门少的特点。 数据的加密和CRC校验：在通信系统中使用 CRC 校验时通常需要使用一个预定义的 LFSR 系列和特定的反馈多项式来计算校验码。这种结构可以有效地检测数据传输过程中发生的错误，保证数据的完整性和正确性，提高系统的可靠性与稳定性。 扰码器/解扰器: 用户数据发送前和扰码器生成的序列进行异或然后发出，此时发送的数据就是经过扰码的数据。 接收电路与发送电路采用相同的多项式，解扰器就可以将发送端原始的用户数据恢复出来。

二、LFSR简介

反馈移位寄存器的工作原理是什么呢？

反馈移位寄存器（Feedback Shift Register，FSR）：每个时钟脉冲，移位寄存器向右移动一位，则移位寄存器的左左侧就会空出一位。这个如果左侧有输入，则移位寄存器的右侧输出端则会有源源不断的数据输出。如果来自移位寄存器的某些序列根据一定的反馈函数形成左侧输入，则称该结构为反馈移位寄存器。当反馈移位寄存器的反馈函数f(x)是线性时，则称为线性反馈移位寄存器。线性反馈移位寄存器的反馈函数为：对移位寄存器中的某些位进行异或。将反馈函数得到的计算结果反馈到移位寄存器的最左边，即得到了线性反馈移位寄存器。

除了知道LFSR的工作原理，应当还了解一些重要的基本概念：

• 状态：一个LFSR当前存储的序列被称为一个状态。当LFSR向右移动一位时，左侧会被反馈函数补上一位计算后的数据，得到一个新的LFSR序列，此时LFSR就移动到了一个新状态。
• 抽头：线性反馈移位寄存器有些位参与异或，有些位不参与异或，其中参与异或的位被称为抽头。抽头会影响下一状态的比特位。LFSR的触发器编号从1开始，因此抽头的取值范围是1~2^n-1 。
• 种子：LFSR中的初值，种子必须是非零的。如果为全零的话，下一状态任意做异或也还是为0，则线性反馈移位寄存器的输是无效的。
• 级数：LFSR中的寄存器个数称为LFSR的级数，例如由四个触发器组成的的LFSR的级数为4；
• 周期：LFSR所产生的伪随机序列所能遍布不循环不重复的最大数目，对于级数为4的LFSR的最大周期为2^n-1 。不是所有的LFSR都能达到2^n-1 个周期，这与抽头的设计相关；
• 特征多项式：特征多项式表示的是抽头系数，3bit的抽头为【3,2】会产生7个状态（多项式对应为：x^3+x^2+1 )，若抽头为【3,1】会产生2个状态（多项式对应为：x^3+x+1 )。抽头的设计关系到LFSR的最大周期，一般要使LFSR得到最大周期2^n-1 。

如图所示，这是一个三级反馈移位寄存器，此时选择种子即初始值001可以遍布除000外的所有状态，此时LFSR级数为3且周期为7。

那么LFSR有哪些分类呢？

主要有两种类型的LFSR（多到一，一到多）。对于多到一类型，多个触发器输出进行异或运算，输出结果进入一个寄存器，对于一到多类型，一个触发器的输出进入异或函数，计算结果驱动多个触发器

1.斐波那契LFSR：多到一型LFSR(many to one)

斐波那契LFSR：抽头序列对应bit位置的多个寄存器的输出异或后驱动一个寄存器输入。

2.伽罗瓦LFSR：一到多型LFSR(one to many)

伽罗瓦LFSR：最后一个寄存器的输出通过与抽头序列对应位置寄存器前一级寄存器的输出异或后驱动多个抽头序列对应位置的寄存器。

斐波那契LFSR与伽罗瓦LFSR有哪些差异呢？

LFSR计数器具有速度快，消耗逻辑门少的特点。伽罗瓦LFSR具有更高的速度，因为两个触发器之间只有一个异或门。斐波那契LFSR在首尾两个寄存器之间有多个异或门，组合逻辑延时更大，因为为了满足建立保持时间的要求，其频率更小（周期更大），速度更慢。

Tips： 种子的选择十分重要，种子初始值一定不能为全0； 抽头的设计也十分重要，抽头设计时尽量使LFSR达到最大周期； 通常N bits的线性反馈寄存器能产生最长的不重复序列为2^N-1 。因为当所有寄存器的输出为全零状态时，线性反馈寄存器陷入死循环，故Nbit的线性反馈寄存器的输出状态有2^N-1 。 一定要防止出现全0状态，一般有两种方法：一是verilog中一但出现全0状态则置位到全1状态；二是引入额外的电路或非门（NOR）使得电路进入全零状态后自动退出。（有兴趣的可以查阅相关资料，此处不展开细说。）

三、斐波那契LFSR和伽罗瓦LFSR

3.1 斐波那契LFSR

3.1.1 斐波那契LFSR

斐波那契LFSR为多到一型LFSR，即多个触发器的输出经过异或逻辑来驱动一个触发器的输入。反馈多项式为 f(x)=x^3 + x^2 +1 ，即x_1 的输入为x_3 和x_2 的输出异或后的结果，电路图如下所示：

输出序列的顺序为：111-110-100-001-010-101-011-111

3.1.2 verilog代码

//三级斐波那契LFSR设计
//反馈多项式为 f(x)=x^3 + x^2 +1
module lfsr_fibonacci(
    input	     	 clk,
    input	     	 rst_n,
    output reg [2:0] q
    );

//时序逻辑LFSR移位模块
always @(posedge clk or rst_n) begin
    if (!rst_n) begin
        q <= 3'b111;	//种子值为111
    end
    else begin
        q <= {q[1],q[0],q[1]^q[2]};	//根据三级斐波那契LFSR电路拼接输出
    end
end

endmodule

3.1.3 Testbench

`timescale 1ns/1ps	//仿真时间单位1ns 仿真时间精度1ps
module lfsr_fibonacci_tb();

//信号申明
reg				clk;
reg				rst_n;
wire   [2:0]    q;

//模块实例化（将申明的信号连接起来即可）
lfsr_fibonacci u_lfsr_fibonacci(
    .clk	(clk), 
    .rst_n	(rst_n), 
    .q		(q)
    );

always #5 clk = ~clk;	//生成时钟信号

//为输入数据赋值
initial begin
    clk        = 1;
    rst_n      = 1;
    #5  rst_n  = 0;
    #5  rst_n  = 1;
    #1000
    $stop;
end

endmodule

3.1.4 仿真结果

3.2 伽罗瓦LFSR

3.2.1 伽罗瓦LFSR

伽罗瓦LFSR为一到多型LFSR，即一个触发器的输出经过异或逻辑来驱动多个触发器的输入。对于同样的反馈多项式x^3+x^2+1 而言：触发器x_1 的输入通常来源于触发器x_2 的输出，x_3 （最高项）的输入通常来自于x_1 的输出，此多项式中剩余触发器的输入是x_1 的输出与前级输出异或的结果，x_2 的输入由x_1 的输出与x_3 的输出通过异或运算得到。其电路图如下所示：

输出序列的顺序为：111-101-100-010-001-110-011-111

3.2.2 verilog代码

//三级伽罗瓦LFSR设计
//反馈多项式为 f(x)=x^3 + x^2 +1
module lfsr_galois(
    input	     	 clk,
    input	     	 rst_n,
    output reg [2:0] q
    );

//时序逻辑LFSR移位模块
always @(posedge clk or rst_n) begin
    if (!rst_n) begin
        q <= 3'b111;	//种子值为111
    end
    else begin
        q <= {q[0],q[2]^q[0],q[1]};		//根据三级伽罗瓦LFSR电路拼接输出
    end
end

endmodule

3.2.3 Testbench

`timescale 1ns/1ps		//仿真时间单位1ns 仿真时间精度1ps
module lfsr_galois_tb();

//信号申明
reg		clk;
reg		rst_n;
wire   [2:0]    q;

//模块实例化（将申明的信号连接起来即可）
lfsr_galois u_lfsr_galois(
    .clk	(clk), 
    .rst_n	(rst_n), 
    .q		(q)
    );

always #5 clk = ~clk;	//时钟信号生成

//为输入数据赋值
initial begin
    clk        = 1;
    rst_n      = 1;
    #5  rst_n  = 0;
    #5  rst_n  = 1;
    #1000
    $stop;
end

endmodule

3.2.4 仿真结果

四、总结

LFSR广泛应用于伪随机数生成、伪噪声序列生成、计数器、数据的加密和CRC校验、扰码器/解码器、信号生成和测试等领域，是一种非常有用的数字电路设计技术。 LFSR主要分为斐波那契LFSR（多到一型）和伽罗瓦LFSR（一到多型）。对于斐波那契LFSR（多到一型）多个触发器输出进行异或运算，输出结果进入一个寄存器，对于伽罗瓦LFSR（一到多型），一个触发器的输出进入异或函数，计算结果驱动多个触发器。 LFSR具有速度快，消耗逻辑门少的特点。 设计LFSR有两要求一禁止两方法： 两要求：简而言之就是，一要求种子初始值不能为全0（同或门构成的LFSR要求不能为全1），二要求抽头的设计时尽量使LFSR达到最大周期。 一禁止：简而言之就是，禁止输出中存在全0（同或门构成的LFSR禁止为全1）的状态使LFSR陷入死循环。通常N bits的线性反馈寄存器能产生最长的不重复序列为2^N-1 （除了全0），当所有寄存器的输出为全零状态时，线性反馈寄存器陷入死循环，故Nbit的线性反馈寄存器的输出状态有2^N-1 。 两方法：对于复杂和状态多的LFSR要防止出现全0状态，一般有两种方法：一是verilog中一但出现全0状态则置位到全1状态； 二是引入额外的电路或非门（NOR）使得电路进入全零状态后自动退出。

不定期检查、补充、纠错，欢迎随时交流纠错

最后修改日期：2023.5.16

软件版本：

仿真软件：Modelsim 10.6c

绘图软件：亿图图示

描述语言：verilog