Linear Feedback Shift Register - Galois LFSRs

Galois LFSRs

Named after the French mathematician Évariste Galois, an LFSR in Galois configuration, which is also known as modular, internal XORs as well as one-to-many LFSR, is an alternate structure that can generate the same output stream as a conventional LFSR (but offset in time). In the Galois configuration, when the system is clocked, bits that are not taps are shifted one position to the right unchanged. The taps, on the other hand, are XOR'd with the output bit before they are stored in the next position. The new output bit is the next input bit. The effect of this is that when the output bit is zero all the bits in the register shift to the right unchanged, and the input bit becomes zero. When the output bit is one, the bits in the tap positions all flip (if they are 0, they become 1, and if they are 1, they become 0), and then the entire register is shifted to the right and the input bit becomes 1.

To generate the same output stream, the order of the taps is the counterpart (see above) of the order for the conventional LFSR, otherwise the stream will be in reverse. Note that the internal state of the LFSR is not necessarily the same. The Galois register shown has the same output stream as the Fibonacci register in the first section. A time offset exists between the streams, so a different startpoint will be needed to get the same output each cycle.

  • Galois LFSRs do not concatenate every tap to produce the new input (the XOR'ing is done within the LFSR and no XOR gates are run in serial, therefore the propagation times are reduced to that of one XOR rather than a whole chain), thus it is possible for each tap to be computed in parallel, increasing the speed of execution.
  • In a software implementation of an LFSR, the Galois form is more efficient as the XOR operations can be implemented a word at a time: only the output bit must be examined individually.

Below is a code example of a 32-bit maximal period Galois LFSR that is valid in C:

#include uint32_t lfsr = 1; unsigned period = 0; do { /* taps: 32 31 29 1; feedback polynomial: x^32 + x^31 + x^29 + x + 1 */ lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0xD0000001u); ++period; } while(lfsr != 1u);

And here is the code for the 16 bit example in the figure

#include uint16_t lfsr = 0xACE1u; unsigned period = 0; do { /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */ lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0xB400u); ++period; } while(lfsr != 0xACE1u);

These code examples create a toggle mask to apply to the shifted value using the XOR operator. The mask is created by first removing all but the least significant bit (the output bit) of the current value. This value is then negated (two's complement negation), which creates a value of either all 0s or all 1s, if the output bit is 0 or 1, respectively. By ANDing the result with the tap-value (e.g., 0xB400 in the second example) before applying it as the toggle mask, it acts functionally as a conditional to either apply or not apply the toggle mask based on the output bit. A more explicit but significantly less efficient code example is shown below.

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

Read more about this topic:  Linear Feedback Shift Register