LFSR原理

发表于 2025-08-18 分类于知识储备

线性移位寄存器原理及其实例

定义

线性反馈移位寄存器（Linear Feedback Shift Register，LFSR），其运算是确定的，所以，由寄存器所生成的数据流完全决定于寄存器当时或者之前的状态
- 种子：赋给 LFSR 的初始值
- 抽头：影响 LFSR 下一个状态的比特位

f(x) = g_n x^n + g_{n-1} x^{n-1} + \cdots + g_1 x + 1

本源多项式：决定了线性移位寄存器的反馈结构
- 反馈系数 g_i 可以为0或1，但g_n和g_0只能为1
- 因为当 g_i 为0时表示不存在该反馈路径
逻辑运算：异或、同或
- 使用异或门的 LFSR 全0状态下为无效状态
- 使用同或门的 LFSR 全1状态下为无效状态
- 不管是异或还是同或，都需避免选择全0或全1的种子，避免 LFSR 进入死循环
抽头序列：选取的某些位构成的序列
- 不同的抽头序列对应不同的本源多项式，产生不同的反馈路径
- 抽头的位置会影响LSFR的输出状态的最大长度序列（Maximum Length Sequence, MLS）
  - 一个n bits的LFSR最多能输出 $2^n-1$ 种状态
  - 能使LFSR拥有MLS的抽头序列不唯一

分类

外部型

Fibonacci LFSR：斐波那契（外部 LFSR），又称 many-to-one

下例是一个本源多项式为 $f(x) = x^{16} + x^{14} + x^{13} + x^{11} + 1$ $f (x) = x^{16} + x^{14} + x^{13} + x^{11} + 1$ 的 Fibonacci LFSR
- 抽头序列是 [16,14,13,11]
- 抽头依次与输出比特进行异或运算，然后反馈回最左端的位
- LFSR 最右端的比特为输出比特，当前状态为0x8735 ，下一个状态是0x0E6A

内部型

Galois LFSR：伽罗瓦（内部LFSR），又称one-to-many

下例是一个本源多项式为 $f(x) = x^3 + x^2 + 1$ $f (x) = x^{3} + x^{2} + 1$ 的 Galois LFSR
- 抽头序列为[3，2]

这个3位的LFSR的伪功能代码可以用C描述为

void lfsr3()
{
    unsigned int temp0, temp1, temp2;
    temp0 = ff0; 
    temp1 = ff1; 
    temp2 = ff2; 
    ff0 = temp2;
    ff1 = temp0 ^ (0 * temp2);
    ff2 = temp1 ^ (1 * temp2);
}

从上述代码的状态转移图中可以发现7个状态组成一个循环，这也是3为LFSR所能达到的最多状态

实例

抽头序列为[3,2]的3级Fibonacci LFSR

module Fibonacci_LFSR3_D(
    input clk,
    output reg [2:0] LFSR = 1
);
always @(posedge clk)
    begin
        LFSR[0] <= LFSR[1] ^ LFSR[2];
        LFSR[2:1] <= LFSR[1:0];
    end
endmodule

// state sequence(LSB->MSB)
0 100   // 种子为1
1 010   // 2
2 101   // 5
3 110   // 3
4 111   // 7
5 011   // 6
6 001   // 4

抽头序列为[4，2]的4级Fibonacci LFSR

module Fibonacci_LFSR4_15(
input clk,
output reg [3:0] LFSR = 15
);
always @(posedge clk)
    begin
        LFSR[0] <= LFSR[1] ^ LFSR[3];
        LFSR[3:1] <= LFSR[2:0];
    end
endmodule

// Fibonacci_LFSR4_15
// status hex sequence(LSB->MSB)
0 F 1111
1 E 0111
2 C 0011
3 9 1001
4 3 1100
5 7 1110
...

抽头序列为[4，1]的4级Fibonacci LFSR

module Fibonacci_LFSR4_13(
input clk,
output reg [3:0] LFSR = 15
);
always @(posedge clk)
    begin
        LFSR[0] <= LFSR[0] ^ LFSR[3];
        LFSR[3:1] <= LFSR[2:0];
    end
endmodule

// Fibonacci_LFSR4_13
// status hex sequence(LSB->MSB)
0 F 1111
1 E 0111
2 D 1011
3 A 0101
4 5 1010
5 B 1101
6 6 0110
7 C 0011
8 9 1001
9 2 0100
10 4 0010
11 8 0001
12 1 1000
13 3 1100
14 7 1110

抽头序列为[16,14,13,11]的16级Fibonacci LFSR

module Fibonacci_LFSR16_16801(
    input clk,
    output reg [15:0] LFSR = 34613
);
always @(posedge clk)
    begin
        LFSR[0] <= LFSR[10] ^ LFSR[12] ^ LFSR[13] ^ LFSR[15];
        LFSR[15:1] <= LFSR[14:0];
    end
endmodule

//status hex sequence(LSB->MSB)
0 8735 1010110011100001
1 0E6A 0101011001110000
2 1CD5 1010101100111000
3 39AA 0101010110011100
4 7354 0010101011001110
5 E6A8 0001010101100111
6 CD51 1000101010110011
7 9AA2 0100010101011001
8 3544 0010001010101100
9 6A89 1001000101010110
10 D513 1100100010101011
11 AA27 1110010001010101
12 544E 0111001000101010
13 A89C 0011100100010101
14 5138 0001110010001010
15 A271 1000111001000101
16 44E2 0100011100100010
...

若需要将全0状态加入上述LFSR的循环中

module Fibonacci_LFSR16_16801_0(
    input clk,
    output reg [15:0] LFSR = 0
);
always @(posedge clk)
    begin
        LFSR[0] <= LFSR[10] ^ LFSR[12] ^ LFSR[13] ^ LFSR[15] ^ (LFSR[14:0]==15'b000000000000000);
        LFSR[15:1] <= LFSR[14:0];
    end
endmodule

//status hex sequence(LSB->MSB)
0 0000 0000000000000000
1 0001 1000000000000000
2 0002 0100000000000000
3 0004 0010000000000000
4 0008 0001000000000000
5 0010 0000100000000000
6 0020 0000010000000000
7 0040 0000001000000000
8 0080 0000000100000000
9 0100 0000000010000000
10 0200 0000000001000000
11 0400 0000000000100000
12 0801 1000000000010000
13 1002 0100000000001000
14 2005 1010000000000100
15 400B 1101000000000010
16 8016 0110100000000001
...

应用

伪随机数生成
- LFSR只能产生伪随机，是伪随机数生成器（Pseudo Random Number Generator，PRNG）的一种实现方案，在实际应用中，可以使用一些分立器件如D触发器构造LFSR
- 虽然在反馈路径确定后，LFSR的输出状态序列也是确定的，且最终会实现循环，但随着n的增大，任意时刻的输出状态的随机性也会随之增大
数据加密
- 数据发送端通过加扰将源数据流与一个随机序列异或后，再发送出去，异或操作完成后的数据流基本是伪随机的
- 在数据接收端也有解扰操作，解扰与加扰必须完全同步，即LFSR使用相同的公式、相同的初始值、相同时刻的输出
CRC校验
- LFSR还可用于CRC的校验，会用到模2的多项式运算，遵循如下的运算原则：