0

我在 Wikipedia 上找到了以下线性反馈移位寄存器程序的示例，但我根本不明白：

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

1 回答 1

1

首先，关于 LFSR 的花絮。使用 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 的多项式项。它们的一系列拉动和 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;
}

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

于 2022-01-22T10:21:59.440 回答