关于如何正确编码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

首先，是关于LFSRs的小贴士。对于LFSR，计算滚动反馈，最终确定单个位值。然后，在将寄存器向下移动一位后，将该值放入寄存器中最重要的位中。在您发布的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的多项式项相对应。它们的拉和异或序列最终被输入到最终位的计算中。

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

然后，在将寄存器向下移动一位后，将结果放入铅位：

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

当与适当的原语多项式一起使用时(其生成超出了本文的范围，但如果您对此进行了有趣的调查)，这将产生一个最大周期(在序列开始重复之前，所有的值都会被耗尽，除了零，这是基本LFSR的死亡，希望是出于明显的原因)。所提供的代码通过确保2^N1不再出现原始素数来测试这一点，其中N是LFSR的位宽。您提供的示例使用一个16位的LFSR，运行时将按预期打印65535。8位版本如下：

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;
}

这将像预期的那样返回15。