Galois线性反馈移位寄存器代码的解释

Question

Galois线性反馈移位寄存器代码的解释

3

我正在尝试理解伽罗瓦LFSR代码的工作原理。在维基百科页面上有一个带有示例的图形。其中有一段C片段代码。

#include <stdint.h>
uint16_t lfsr = 0xACE1u;
unsigned period = 0;

do {
unsigned lsb = lfsr & 1;  /* Get lsb (i.e., the output bit). */
lfsr >>= 1;               /* Shift register */
if (lsb == 1)             /* Only apply toggle mask if output bit is 1. */
lfsr ^= 0xB400u;        /* Apply toggle mask, value has 1 at bits corresponding
                         * to taps, 0 elsewhere. */
++period;
} while(lfsr != 0xACE1u);

我无法理解维基百科上给出的图形并将其与代码相关联。开关掩码是做什么的？有人能够解释一下操作如何使用示例位序列及其移位版本进行工作吗？我不了解字段，也不理解代码。我在网上查找了一些信息，但没有找到任何不涉及字段术语的算法的好的解释。请帮帮忙。

- Karan Talasila

我正在尝试实现Galois LFSR来混淆一个字符串，我想了解LFSR的工作原理。在维基百科的上述示例中，0xACE1u是起始状态，请问'0xB400u'是什么？ - Ravi Kiran

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Axel Kemper · Accepted Answer

如果你实际运行代码并添加一些行来查看lfsr移位寄存器变量的中间内容，事情可能会变得更加清晰：

如果您实际运行代码并添加一些行来查看 lfsr 移位寄存器变量的中间内容，则可能会更清晰。

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

int main(int argc, char* argv[])
{
    uint16_t lfsr = 0xACE1u;
    unsigned period = 0;
    char s[16+1];

    do {
          unsigned lsb = lfsr & 1;  /* Get lsb (i.e., the output bit). */
          lfsr >>= 1;               /* Shift register */
          if (lsb == 1)             /* Only apply toggle mask if output bit is 1. */
            lfsr ^= 0xB400u;        /* Apply toggle mask, value has 1 at bits corresponding
                                    /* to taps, 0 elsewhere. */
          ++period;

          for (int i = 0; i < 16; i++)
          {
             s[15 - i] = (lfsr & (1 << i)) ? '1' : '0';
          }
          s[16] = '\0';
          printf("\n%10d: %s", period, s);
    } while(lfsr != 0xACE1u);

    return 0;
}

输出结果如下：

     1: 1110001001110000
     2: 0111000100111000
     3: 0011100010011100
     4: 0001110001001110
     5: 0000111000100111
     6: 1011001100010011
     7: 1110110110001001
     8: 1100001011000100
    ....

 65527: 1000000110011100
 65528: 0100000011001110
 65529: 0010000001100111
 65530: 1010010000110011
 65531: 1110011000011001
 65532: 1100011100001100
 65533: 0110001110000110
 65534: 0011000111000011
 65535: 1010110011100001   (= 0xACE1u)

位移运算符">>"将所有位向右移动一位。对于无符号整数，这与除以二相同。"lfsr & 1"返回最低有效位（=位0）。在lfsr ^= 0xB400u中，“^” 运算符执行按位异或操作，因此会反转16个比特中的4个：最高有效位（=位15），位13、12和10。0xB400的二进制为1011 0100 0000 0000。