线性反馈移位寄存器(LFSR)

线性反馈移位寄存器（linear feedback shift register, LFSR）是指，给定前一状态的输出，将该输出的线性函数再用作输入的移位寄存器。异或运算是最常见的单比特线性函数：对寄存器的某些位进行异或操作后作为输入，再对寄存器中的各比特进行整体移位。

移位寄存器是产生信号和序列的常用设备，它分为线性和非线性两大类，著名的一序列和序列就是分别由线性和非线性反馈移位寄存器所生成的。线性反馈移位寄存器（Linear feedback shift register，LFSR）是

通常由动态或静态主从型触发器构成。反馈回路由异或门构成。其特性通常由一个特征多项式表征。使用二输入异或门计算反馈函数的最大长度或近最大长度不纠立寄存器的特征多项式。这种电路的特点是结构简单，它的上限移位速度取决于移位单元的延迟时间和二输入异或门的延迟时间，因此，能获得较高的速度 [1]  。线性反馈移位寄存器中的移位单元是由主一从型边沿触发器构成的。在这种结构的移位单元中，主从两极锁存器在两相不交叠时钟的控制下，使数据在时钟上升沿被采样，并一直保持到下一个时钟上升沿。电路中四个移位单元都是由动态主从边沿型触发器构成的，每次移位的操作都需要数据串行依次经过两级锁存器。

赋给寄存器的初始值叫做“种子”，因为线性反馈移位寄存器的运算是确定性的，所以，由寄存器所生成的数据流完全决定于寄存器当时或者之前的状态。而且，由于寄存器的状态是有限的，它最终肯定会是一个重复的循环。然而，通过本原多项式，线性反馈移位寄存器可以生成看起来是随机的且循环周期非常长的序列。移位寄存器结构简单，运行速度快，实用的密钥流产生器大多基于移位寄存器，移位寄存器理论也成了现代流密码体制的基础。

线性反馈移位寄存器的应用包括生成伪随机数，伪随机噪声序列，快速数字计数器，还有扰频器。线性反馈移位寄存器在硬件和软件方面的应用都非常得普遍。循环冗余校验中用于快速校验传输错误的数学原理，就与线性反馈移位寄存器密切相关。

#include <stdint.h>
unsigned lfsr_fib(void)
{
    uint16_t start_state = 0xACE1u;  /* Any nonzero start state will work. */
    uint16_t lfsr = start_state;
    uint16_t bit;                    /* Must be 16-bit to allow bit<<15 later in the code */
    unsigned period = 0;

    do
    {   /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
        bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) & 1u;
        lfsr = (lfsr >> 1) | (bit << 15);
        ++period;
    }
    while (lfsr != start_state);

    return period;
}