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.

Answer 1

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.