c - LFSR 未按预期工作

Question

如上所述，我创建了一个 LFSR 来尝试生成一些数字，但它无法正常工作。

以此开始:

unsigned int lfsr = 0x000001
while(1)
{
  lfsr >>= 1
  unsigned int lsb1 = lfsr & 1;
  unsigned int lsb2 = lfsr & 2;

  if (lsb1 == 1 && lsb2 == 1 || lsb1 == 0 && lsb2 == 0)
    lfsr |= 0x000000;
  else
    lfsr |= 0x800000;
}

但是这不起作用，lsb2 等于 2，所以经过一番研究后我现在得到了这个:

unsigned int lfsr = 0x000001
while(1)
{
  lfsr >>= 1
  lfsr |= ( (((unsigned int)((lfsr<<31)>>31)) ^ ((unsigned int)((lfsr<<30)>>31))) << 24);
}

这会生成 2^21 - 1 个数字，而我正在尝试获取生成 2^24 的数字。

我是否遗漏了一些明显的东西？任何帮助将不胜感激，谢谢。

Answer 1

这些 LFSR 示例将循环遍历 (2^24)-1 个数字(所有 2^24 个数字，但零)。第一个示例是 Galois LFSR，它与(反馈多项式)进行异或然后移位。第二个示例是 Galois LFSR，它通过 (反馈多项式 >> 1) 进行异或移位。第三个例子是斐波那契 LFSR。请注意，当 start_state 为 0x000001 时，所有三个示例的 bit 值都遵循相同的模式，尽管 Galois LFSR 和 Fibonacci LFSR 将遵循不同的模式。 0x100001b 是最小反馈多项式，0x1c20001 是 (2^24)-1 个周期的最大 4 抽头反馈多项式。

此示例遵循 wiki Galios LFSR 示例，首先完成异或:

int main(int argc, char *argv[])
{
unsigned int period, bit, lfsr, start_state;
    period = 0;
    lfsr = start_state = 0x000001;
    do
    {
        bit = lfsr&1;               /* get bit */
        lfsr ^= (0-bit)&0x100001b;  /* toggle taps if bit was 1 */
        lfsr >>= 1;                 /* shift lfsr */
        ++period;
    }while(lfsr != start_state);
    printf("%x\n", period);         /* period will == 0xffffff */
    return(0);
}

此示例遵循 wiki Galios LFSR 示例，首先完成移位:

int main(int argc, char *argv[])
{
unsigned int period, bit, lfsr, start_state;
    period = 0;
    lfsr = start_state = 0x000001;
    do
    {
        bit = lfsr & 1;             /* get bit */
        lfsr >>= 1;                 /* shift lfsr */
        lfsr ^= (0-bit)&0x80000d;   /* toggle taps if bit was 1 */
        ++period;
    } while (lfsr != start_state);
    printf("%x\n", period);         /* period will == 0xffffff */
    return(0);
}

此示例遵循 wiki Fibonacci LFSR 示例:

int main(int argc, char *argv[])
{
unsigned int period, bit, lfsr, start_state;
    period = 0;
    lfsr = start_state = 0x000001;
    do
    {
        /* taps: 24 4 3 1 */
        /* feedback polynomial: x^24 + x^4 + x^3 + x + 1 = 0x100001b */
        bit  = ((lfsr>>(24-24))^(lfsr>>(24-4))^(lfsr>>(24-3))^(lfsr>>(24-1)))&1;
        lfsr =  (lfsr >> 1) | (bit << 23);
        ++period;
    } while (lfsr != start_state);
    printf("%x\n", period);         /* period will == 0xffffff */
    return(0);
}