我想了解 galois 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);
我无法理解维基百科上给出的数字并与代码相关联。切换掩码在做什么?任何人都可以解释该操作如何使用示例位序列及其移位版本。我不知道字段,也不理解代码。我在网上查过,但如果不进入领域术语,就找不到该算法的任何好的解释。请帮忙。
最佳答案
如果您实际运行代码并添加一些行来查看 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"
反转 lfsr
的 16 位中的四位,因为运算符 "^"
计算按位异或。 0xB400
在二进制中是 1011 0100 0000 0000
。因此,最高有效位(= 位 15)、位 13、位 12 和位 10 被反转。
关于c - Galois LFSR 代码解释,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16891655/