1.LSFR基本介绍

线性反馈移位寄存器（LFSR, Linear-Feedback Shift Register）是一种其输入位由其前一个状态的线性函数决定的移位寄存器

最常用的单个位线性函数是异或（XOR）。因此，LFSR 通常是一种其输入位由整个寄存器当前值中某些位进行异或运算所得的移位寄存器。

LFSR 的初始值被称为种子（seed），由于寄存器的操作是确定性的，因此其产生的值序列完全由当前（或之前）的状态决定。同样地，由于寄存器的可能状态数量是有限的，它最终必然会进入一个循环周期。不过，一个精心选择的反馈函数可以使 LFSR 产生一个看起来随机且周期很长的比特序列。

2.Fibonacci LFSRs

1.运算

会影响下一个状态的比特位置被称为抽头（taps）。在图示中，抽头的位置是 [16, 14, 13, 11]。LFSR 最右边的比特被称为输出位（output bit），它始终也是一个抽头。

要获得下一个状态，首先将所有抽头位进行异或（XOR）运算；然后，将所有比特整体向右移动一位，最右边的比特被丢弃；最后，把之前异或运算的结果写入现在空出来的最左边比特位。

要获取伪随机输出流，每次状态变换后读取最右边的比特即可。

img

总而言之，LSFR的运作就是抽出一些位来运算，丢掉最后一位，然后将抽头运算得到的结果补充到第一位，保持LSFR始终长度不变

计算反馈位：对指定抽头位进行异或（XOR），得到一个新比特；

右移：整个寄存器向右移动一位，最右边的位被丢弃；

左端注入反馈位：把新计算出的反馈位放入最左边的位置；

输出当前的最右位：输出变换完之后的最右位

LSFR是每次变换完的最右边的位，注意是舍弃最后一位之后的最右位（如果我们输出的是被丢弃的位的话，种子就会在前面的16个输出中泄露）

不过即使这样，依旧泄露了15位，因为只有第16位被舍弃了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def lfsr(seed, taps, size=16, rounds=16):
    """
    seed: 初始状态（整数）
    taps: 抽头位置列表，如 [16,14,13,11]
    size: LFSR 的位宽
    rounds: 要生成的输出比特数
    """
    state = seed & ((1 << size) - 1)
    output_stream = []
    for i in range(rounds):
        # 1) 计算反馈位：抽头异或
        feedback = 0
        for t in taps:
            feedback ^= (state >> (size - t)) & 1

        # 2) 记录移位前的状态（仅用于展示）
        before = state

        # 3) 右移并插入反馈位
        state = (state >> 1) | (feedback << (size - 1))

        # 4) 读取新的 LSB 作为输出
        output_bit = state & 1
        output_stream.append(output_bit)
    print("\nGenerated output stream:")
    print(''.join(map(str, output_stream)))


# 示例运行
seed = 0b1001001010010010
s = bin(seed)[2:][::-1]
taps = [16, 14, 13, 11]
lfsr(seed, taps, size=16, rounds=16)
print(s)
Generated output stream:
1001001010010010
0100100101001001

这里注意左移就是舍弃第一位

2.反馈多项式

LFSR所产生的比特序列，可视作与格雷码或自然二进制码同样有效的一种二元数制。

在有限域 GF(2) 中，LFSR 的反馈抽头位置可以用模 2 的多项式来表示——系数只能是 0 或 1，这就是所谓的反馈多项式（feedback polynomial）或互补特征多项式（reciprocal characteristic polynomial）。例如，当抽头位于第 16、14、13、11 位时，对应的反馈多项式为：

其中，“+1”并不对应某个物理抽头，而是对应将结果反馈到第 0 位（即 ，恒等于 1）。

多项式中每一项的指数表示相应的抽头位置，自寄存器最左端开始计数；第一位始终作为反馈输入，最后一位始终作为输出抽头。

当且仅当反馈多项式在 GF(2) 上为本原多项式（primitive polynomial）时，LFSR 才能达到最大周期（即周期为 ）。以下条件是判断本原性所需的（但并不充分）：

  1. 抽头数量为偶数。
  2. 抽头位置集合在数值上两两互质；即除了 1 之外，不存在能同时整除所有抽头位置的公约数。

有关可构造最大周期 LFSR 的本原多项式列表，可参见下表及相关文献。

对于给定的寄存器长度 ，可能存在不止一种最大周期的抽头序列；而且，一旦找到一种序列，其“镜像”序列也自动给出：

  • 若某 位 LFSR 的抽头序列为 （其中 0 对应 ），
  • 则对应的“镜像”序列为 。

例如，抽头序列 的镜像即为 ，两者均可产生最大周期序列。

注意这个反馈多项式只是表示抽头位置，不是用来计算反馈值的！

不能把寄存器的“状态”当作一个数，直接带入多项式 去算数值乘法那样处理。这里的多项式并不是要用某个具体的 值去“计算多项式值”，而是 一种标记结构，告诉你：“多项式里哪些幂次为 1，就把对应的寄存器位做 XOR”。

  • 在普通代数里，你可以给 一个数值（比如 ），然后算 ；
  • LFSR 的情况恰恰相反：这里的 不代表数值，而是“移位操作”的抽象符号。
  • 反馈多项式中的每一项 ，都对应“拿出当前寄存器的第 位”──不是去求 的数值

3.矩阵形式

3.周期

m-bit长的LSFR的周期是