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, который затем сдвигает xor с (полином обратной связи). Второй пример - Galois LFSR, который сдвигается затем на xor с (полином обратной связи >> 1). Третий пример - LFSR Фибоначчи. Обратите внимание, что с start_state 0x000001 значение бит для всех трех примеров следует за одним и тем же шаблоном, хотя Galois LFSR и Fibonacci LFSR будут следовать различным шаблонам. 0x100001b - наименьший обратный полином, а 0x1c20001 - наибольший 4-кратный ответный полином для циклов (2^24) -1.

В этом примере следует вики 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); 
} 

В этом примере следует вики-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); 
} 

Answer 2

Неверный код: lsb2 == 1 никогда не верно

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

Вероятно, должно быть

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

---

Согласен с @Olaf, рассмотрим uint32_t.

Answer 3

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 
}