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

代码不正确：lsb2 == 1 永远不会是真的

unsigned int lsb2 = lfsr & 2;
...
if (lsb1 == 1 && lsb2 == 1 ....  // bad

应该是

if (lsb1 && lsb2 ....  // better

同意@Olaf，考虑uint32_t。

Answer 2

unsigned int lfsr = 0x000001 // actually int is 4 bytes so result is 0x00000001
while(1)
{
  lfsr >>= 1                    // now lfsr = 0
  unsigned int lsb1 = lfsr & 1; // == 0
  unsigned int lsb2 = lfsr & 2; // == 0

   // the following line will 'work' however, it is always better/clearer
   // to force the correct precedence via parens
   // and lsb2 will be 0 or 2, never 1
  if (lsb1 == 1 && lsb2 == 1 || lsb1 == 0 && lsb2 == 0)
    lfsr |= 0x000000;  // this will always be executed and makes no change to the value in 'lfsr'
  else
    lfsr |= 0x800000;  // unsigned int is 4 bytes, so this is actually 0x00800000
}

Answer 3

这些 LFSR 示例将循环遍历 (2^24)-1 个数字（所有 2^24 个数字，但零除外）。第一个例子是异或与（反馈多项式）然后移动的伽罗瓦 LFSR。第二个例子是 Galois LFSR，它用（反馈多项式 >> 1）进行异或运算。第三个例子是斐波那契 LFSR。请注意，对于 0x000001 的 start_state，所有三个示例的 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 斐波那契 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);
}

LFSR 未按预期工作

LFSR not working as intended

c

bits

bit-shift