Galois LFSR explanation of code

Question

I am trying to understand how the galois LFSR code works. On the wikipedia page there is a figure with an example. There is a C snippet code.

#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);

I am unable to understand figure given on wikipedia and correlate with the code. what is the toggle mask doing? Can anybody explain as to how the operation is working with example bit sequence and it's shifted versions. I am not aware of fields and am not understanding code. I checked online but couldnot find any good explanations of the algorithm without going into the fields terminology. Kindly help.

Solution

Things might become clearer, if you actually run the code and add some lines to see the intermediate contents of the lfsr shift register variable:

#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;
}

The output looks as follows:

     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)

The shift operator ">>" moves all bits one to the right. For unsigned integers this is the same as dividing by two. "lfsr & 1" returns the least significant bit (= bit 0). "lfsr ^= 0xB400u" inverts four of the 16 bits of lfsr because operator "^" evaluates a bitwise exclusive or. 0xB400 in binary is 1011 0100 0000 0000. Therefore, the most significant bit (= bit 15), bit 13, bit 12 and bit 10 are inverted.

Comments

[Karan Talasila]

Thanks for the explanation. Can I know why >> is used to divide by 2. The actual operation to be performed is lfsr*x mod p(x) where lfsr is present state and p(x) is characteristic polynomial. I am not understanding why the taps are flipped when lsb is 1 and kept as usual when lsb is 0. How the modulus operation relates to the flippin of taps, I am unable to understand.

[Axel Kemper]

Try to understand the first 4-bit example in the Wikipedia article (en.wikipedia.org/wiki/Linear_feedback_shift_register). Then expand this to 16 bits. It might pay off to look at exor gates and shift registers first.

[Ravi Kiran]

May I know what is this hex value '0xB400u' in the above example?

[Axel Kemper]

@RaviKiran: 0xB400u is binary 101101000000000. For the 4 bits, status of the respective shift register cells is toggled if the input bit is 1. The specific value is from a Wikipedia example, but does not refer to a widely used CRC algorithm.