Editing Linear-feedback shift register (section)

== Galois LFSRs ==
[[File:LFSR-G16.svg|thumb|right|393 px|A 16-bit Galois LFSR. The register numbers above correspond to the same primitive polynomial as the Fibonacci example but are counted in reverse to the shifting direction. This register also cycles through the maximal number of 65535 states excluding the all-zeroes state. The state ACE1 hex shown will be followed by E270 hex.]]

Named after the French mathematician [[Évariste Galois]], an LFSR in Galois configuration, which is also known as '''modular''', '''internal XORs''', or '''one-to-many LFSR''', is an alternate structure that can generate the same output stream as a conventional LFSR (but offset in time).<ref>
{{cite book
  |last1 = Press
  |first1 = William
  |last2 = Teukolsky
  |first2 = Saul
  |last3 = Vetterling
  |first3 = William
  |last4 = Flannery
  |first4 = Brian
  |title = Numerical Recipes: The Art of Scientific Computing, Third Edition
  |publisher = [[Cambridge University Press]]
  |year = 2007
  |page = 386
  |isbn = 978-0-521-88407-5
}}
</ref> 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 XORed 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 XORing 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 [[C (programming language)|C]] code example for the 16-bit maximal-period Galois LFSR example in the figure:
<syntaxhighlight lang="c">
#include <stdint.h>
unsigned lfsr_galois(void)
{
    uint16_t start_state = 0xACE1u;  /* Any nonzero start state will work. */
    uint16_t lfsr = start_state;
    unsigned period = 0;

    do
    {
#ifndef LEFT
        unsigned lsb = lfsr & 1u;  /* Get LSB (i.e., the output bit). */
        lfsr >>= 1;                /* Shift register */
        if (lsb)                   /* If the output bit is 1, */
            lfsr ^= 0xB400u;       /*  apply toggle mask. */
#else
        unsigned msb = (int16_t) lfsr < 0;   /* Get MSB (i.e., the output bit). */
        lfsr <<= 1;                          /* Shift register */
        if (msb)                             /* If the output bit is 1, */
            lfsr ^= 0x002Du;                 /*  apply toggle mask. */
#endif
        ++period;
    }
    while (lfsr != start_state);

    return period;
}
</syntaxhighlight>

The branch <syntaxhighlight lang="c" inline>if (lsb) lfsr ^= 0xB400u;</syntaxhighlight>can also be written as <syntaxhighlight lang="c" inline>lfsr ^= (-lsb) & 0xB400u;</syntaxhighlight> which may produce more efficient code on some compilers. In addition, the left-shifting variant may produce even better code, as the [[most significant bit|msb]] is the [[Carry flag|carry]] from the addition of <code>lfsr</code> to itself.
<!-- NOTE: The C standard guarantees that arithmetic operations on unsigned types are computed modulo 2^bitsize (i.e., as if in two's complement arithmetic). Thus, the "-lsb" is fully portable and gives the intended result even if the target environment uses natively a different integer representation. -->

=== Galois LFSR parallel computation ===
State and resulting bits can also be combined and computed in parallel. The following function calculates the next 64 bits using the 63-bit polynomial <math>x^{63} + x^{62} + 1</math>:

<syntaxhighlight lang="c">
#include <stdint.h>

uint64_t prsg63(uint64_t lfsr) {
    lfsr = lfsr << 32 | (lfsr<<1 ^ lfsr<<2) >> 32;
    lfsr = lfsr << 32 | (lfsr<<1 ^ lfsr<<2) >> 32;
    return lfsr;
}
</syntaxhighlight>

=== Non-binary Galois LFSR ===
Binary Galois LFSRs like the ones shown above can be generalized to any ''q''-ary alphabet {0, 1, ..., ''q''&nbsp;−&nbsp;1} (e.g., for binary, ''q'' = 2, and the alphabet is simply {0, 1}). In this case, the exclusive-or component is generalized to addition [[Modular arithmetic|modulo]]-''q'' (note that XOR is addition modulo 2), and the feedback bit (output bit) is multiplied (modulo-''q'') by a ''q''-ary value, which is constant for each specific tap point. Note that this is also a generalization of the binary case, where the feedback is multiplied by either 0 (no feedback, i.e., no tap) or 1 (feedback is present). Given an appropriate tap configuration, such LFSRs can be used to generate [[Finite field|Galois fields]] for arbitrary prime values of ''q''.