关于如何正确编码 LFSR 的问题

Question

我在维基百科上找到了下面的线性反馈移位寄存器程序的例子，但我完全不明白：

#include <stdint.h>
#include <stdio.h>

unsigned lfsr_fib()
{
    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;
}

int main()
{
  printf("%d\n", lfsr_fib());
  return 0;
}

Answer 1

首先，关于 LFSR 的小知识。使用 LFSR 计算滚动反馈，最终确定单个比特值。然后在将寄存器向下移动一位后，将该值放入寄存器的 most-significant 位。您发布的 LFSR 进展中最重要的两个操作是：

/* 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);

您在 bit = 行中看到的移位对应于相应指数的多项式项 >= 1。它们的一系列拉取和 XOR 最终输入到最后一位的计算中。

((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5))
      16            14            13            11

然后将寄存器下移一位后将结果放入前导位：

lfsr = (lfsr >> 1) | (bit << 15);

当与适当的原始多项式一起使用时（其生成超出了本文的范围，但如果您愿意的话，这是一项有趣的调查），这可以生成最大周期（所有值都是在序列开始重复之前已经精疲力尽，除了零，这是基本 LFSR 的死亡，希望出于显而易见的原因）。提供的代码通过确保原始素数不会再次出现 2^N-1 来对此进行测试，其中 N 是 LFSR 的位宽。您提供的示例使用 16 位 LFSR，并且当运行时，将按预期打印 65535。下面显示了一个八位版本：

unsigned lfsr_fib8()
{
    uint8_t start_state = 0x01;
    uint8_t lfsr = start_state;
    uint8_t bit;
    unsigned period = 0;

    do
    { /* taps: 8 6 5 4 ; feedback polynomial: x^8 + x^6 + x^5 + x^4 + 1 */
        bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 4)) & 1u;
        lfsr = (lfsr >> 1) | (uint8_t)(bit << 7);
        ++period;
    } while (lfsr != start_state);

    return period;
}

如预期的那样，这将产生 255。最后，针对您的问题，一个 4 位版本。在这里我们必须有点创意（但不要太多），因为我们没有只有 4 位宽的固有本机类型。没关系。只需确保您只使用低半字节，并且不要使用高于 0x0F 的任何内容来启动起始状态。

unsigned lfsr_fib4()
{
    uint8_t start_state = 0x01;
    uint8_t lfsr = start_state;
    uint8_t bit;
    unsigned period = 0;

    do
    { /* taps: 4 1 ; feedback polynomial: x^4 + x + 1 */
        bit = ((lfsr >> 0) ^ (lfsr >> 3)) & 1u;
        lfsr = ((lfsr >> 1) | (uint8_t)(bit << 3)) & 0x0F;
        ++period;
    } while (lfsr != start_state);

    return period;
}

这将 return 15，正如预期的那样。

关于如何正确编码 LFSR 的问题

Question about how to code the LFSR correctly

c

lfsr