Question about how to code the LFSR correctly

Question

I found an example below of a linear feedback shift register program on Wikipedia but I didn't understand it at all :

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

unsigned lfsr_fib()
{
    uint16_t start_state = 0xACE1u;  /* Any nonzero start state will work. */
    uint16_t lfsr = start_state;
    uint16_t bit;                    /* Must be 16-bit to allow bit<<15 later in the code */
    unsigned period = 0;

    do
    {   /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
        bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) & 1u;
        lfsr = (lfsr >> 1) | (bit << 15);
        ++period;
    }
    while (lfsr != start_state);

    return period;
}

int main()
{
  printf("%d\n", lfsr_fib());
  return 0;
}

Answer 1

First, a tidbit about LFSRs. With an LFSR a rolling feedback is calculated that ultimately determines a single bit value. That value is then placed into the most-significant bit of the register after shifting the register down one bit. The two most important operations in the LFSR advance you posted are:

/* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) & 1u;
lfsr = (lfsr >> 1) | (bit << 15);

The bit shifts you see in the bit = line correspond to the polynomial terms of corresponding exponents >= 1. Their series of pulls and XOR are what ultimately feed into the calculation of the final bit.

((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5))
      16            14            13            11

That result is then fed into the lead bit by dropping it in after shifting the register down one bit:

lfsr = (lfsr >> 1) | (bit << 15);

When used with the proper primitive polynomial(s) (generation of which is beyond the scope of this text, but an intriguing investigation if you're up for it), this can generate a maximal period (all values are exhausted before the sequence begins repeating, save for zero, which is death to a basic LFSR, hopefully for obvious reasons). The code provided tests this by ensuring the original prime value does not occur again for 2^N-1, where N is the bit width of the LFSR. The example you provided uses a 16bit LFSR, and, when run, will print 65535, as expected. An eight bit version appears below:

unsigned lfsr_fib8()
{
    uint8_t start_state = 0x01;
    uint8_t lfsr = start_state;
    uint8_t bit;
    unsigned period = 0;

    do
    { /* taps: 8 6 5 4 ; feedback polynomial: x^8 + x^6 + x^5 + x^4 + 1 */
        bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 4)) & 1u;
        lfsr = (lfsr >> 1) | (uint8_t)(bit << 7);
        ++period;
    } while (lfsr != start_state);

    return period;
}

This will produce 255, as expected. Finally, to your question, a 4 bit version. Here we have to get a little creative (but not much) since we have no intrinsic native type that is only 4 bits wide. That's ok. just make sure you only use the low nibble, and do NOT prime the start state with anything above 0x0F.

unsigned lfsr_fib4()
{
    uint8_t start_state = 0x01;
    uint8_t lfsr = start_state;
    uint8_t bit;
    unsigned period = 0;

    do
    { /* taps: 4 1 ; feedback polynomial: x^4 + x + 1 */
        bit = ((lfsr >> 0) ^ (lfsr >> 3)) & 1u;
        lfsr = ((lfsr >> 1) | (uint8_t)(bit << 3)) & 0x0F;
        ++period;
    } while (lfsr != start_state);

    return period;
}

This will return 15, as expected.