Intro to Galois LFSRs

There is another, natural way to write the code for an LFSR.  This article describes the Galois implementation of an LFSR.  This also shows how LFSRs are related to Galois fields.  This implementation is claimed to be a bit faster than the Fibbonacci implementation.

The mathematical description starts with an understanding of fields and of polynomials.  One way of extending a field is to invent a solution to an irreducible polynomial.  For example, has no solution in real numbers.  A solution could be invented.  Then a larger field of complex numbers can be expressed as a simple polynomial in the form .

For the 1-bit binary field, where addition and subtraction are the XOR operator, and multiplication is AND, similar things can be done.  The polynomial is irreducible.  A root can be invented, and called .  This is equivalent to saying .  Subtracting from both sides gives the useful relation, .

The field is then constructed by repeatedly multiplying by .  This is shows below:

The first elements are trivial to determine.  The next element is .  From above, we realize that we already have a relation for this:

At this point, the remaining elements can be generated.  Everytime is encountered, it is replaced with .

The final equation, , shows how any power can be calculated as .

One nice thing about this method is that it is easier to implement in software than the Fibbonacci implementation of an LFSR.  For example, C would allow:

x = (x&0x4) ? ((x <<1) ^ POLY) : (x << 1);
// if POLY is stored as 1101, then the xor operation will return
// a 0 for the MSB every time.

For HDL, the above can be directly written as a function:

-- x is a vector N downto M, poly is a vector of the same length.
-- for this example, poly = "101" -- the msb=1 is assumed.
function lfsr_shift (x : std_logic_vector; poly : std_logic_vector)
    return std_logic_vector is
begin
  if x(x'high) = '1' then
    return ((x(x'high-1 downto x'low)&'0') xor poly);
  else
    return (x(x'high-1 downto x'low)&'0');
  end if;
end function;

In terms of implementation, ISE is able to determine an efficient implementation for this.  The synthesis report will list it as an N-bit xor, but it will map to fewer LUTs.  For the 3b LFSR in this example, the resulting circuit will be:

Resulting 3bit LFSR