# PEAC vs LFSR

A project log for PEAC Pisano with End-Around Carry algorithm

Add X to Y and Y to X, says the song. And carry on.

Yann Guidon / YGDES 10/17/2021 at 14:090 Comments

After 6 months of study and exploration, it is possible to objectively compare PEAC and LFSRs, in all 4 configurations.

When choosing between either, it is crucial to understand their differences, and respective benefits and drawbacks, so I'm listing them here "As far as I know". Of course all comments are welcome.

Don't be mistaken: I'm not "anti-LFSR", far from it ;-) The point is that I have studied them "in quite some depth" already and got tired of their many shortcomings, despite their undeniable qualities. PEAC is an alternative and this is good, as long as each type of circuit is used where they make most sense, and not "because that's how things are / have always been done" or "because I love it more". I do engineering, not algorithm pageant.

In fact, in some cases, LFSR can be combined with PEAC to get the benefits of both.

# Mathematics.

• LFSR: Well-established theory based on binary polynomials / Galois fields.
• PEAC: Derived from the long-known Pisano sequences (related to Fibonacci) but does not fit a well-known theory. So it's mostly uncharted here and this project documents the known properties.

# Size/Width.

• LFSR:
• Pro: can have any size. Set the width with as many bits as you like.
• Con: Once you settle on a given size, you're going on a wild ride. You must find a suitable list of "generating polynomials" (there is no widely available program to generate the generators though freely available databases exist online) then choose the most suitable one: either with the fewest possible terms (for speed/size) or the best mixing behaviour (dense poly), though this is only a shuffling because ALL combinations will appear anyway, just in a different order. However, in CRC mode, different polys will have different characteristics, like catching certain kinds of errors, so we often end up reusing "established" polys. There is no easy way to know by looking at it.
• PEAC
• Con: Only a few valid sizes : 2, 3, 4, 10, 16 and probably 26. (×2 because there are 2 registers of equal size, and a carry bit)
Width 8 is absent/bad and width 32 is "not impossible" but not highly likely either and must still be proved.
Note: I haven't explored other possible alternatives inspired by Marsaglia, such as using 2 versions of subtraction, which could provide more sizes (note for later: check these)
• Pro: none of the LFSR's shenanigans, nothing to choose, it works as is, out of the box.

# Size/Period/Orbits.

• A n-bit LFSR has a single orbit with a length of 2^n -1 states.
• A n-bit PEAC has two complementary orbits, each of length 2^(2n-1) + 2^(n-1) -1.
Non-maximal PEAC have pairs of complementary orbits, often with unequal lengths (and must be avoided)

A n-wide PEAC is roughly equivalent to a 2n-1 wide LFSR. But because of the 2^(n-1) term of PEAC, they can't be directly, exactly compared. This small difference is great however when LFSR are combined with PEAC because their combined periods may give even longer orbits, if their respective periods have no common factors.

# Stuck states.

• LFSR have one stuck state at 0, which can not be reached in the generator mode, but it is possible in checksum/scrambler mode!
Designer either ignore this case, or must implement extra circuits or code to prevent the checksum from missing runs of 0s.
• PEAC has 2 stuck states but is naturally immune to reaching them in checksum mode (and scrambler mode as well, by extension). No extra "desticking" circuit/code required.

# Circuit size/Complexity.

This is another huge difference between LFSR (meant to work serially) and PEAC (working in parallel).

• One LFSR cycle performs a multiplication over the Galois field, of the (variable) internal state by the (constant) generator polynomial. The result is one bit per cycle, provided by a handful of XOR gates. Two equivalent configurations (Galois or Fibonacci) can be selected, depending on electronic (delay, fanout) constraints.
Trying to output more than one bit per cycle makes the circuit crazy complex and/or slow and this depends a lot on the chosen polynomial. Using the whole state of the LFSR as output only provides a shifted version of the last value.
• PEAC works with a different mathematical principle and deals with whole numbers: a PEAC of width n will output n bits per cycle. Binary addition complexity is O(n×log(n)) to output n bits. Hence: the "gates per generated bit" ratio is roughly equivalent to LFSR but the throughput is better because a standard LFSR requires n cycles to output n bits.

As the width increases, PEAC is clearly a "faster" scrambler than LFSR: each word takes a latency of log(n) gates to output, instead of n slightly cycles. A really fast SER/DES circuit will do the rest at full speed, instead of being limited to the LFSR's speed...

Getting a fast LFSR in software is a PITA as well, with a crazy hit on L1 cache for each byte (requiring 512 or 1024 bytes of lookup table), or you need a dedicated instruction... Nothing of that sort for PEAC as it uses plain old arithmetics, not fancy carry-less multiplies.

# Avalanche.

That may be the sore/muddy point because it depends on so many things.

At least, by their very nature, both PEAC and LFSR checksums "keep" any trace of a perturbation, though the amplitude is different.

PEAC can spread one bit flip over the whole checksum but is intended for systems where "perfect mixing" is not a strong requirement. In a SW protocol, a single-bit mismatch is enough to drop the affected packet.

PEAC16 takes one or two dozens of cycles to fully avalanche on a flipped LSB. It is pretty stable, unlike LFSRs that have many parameters (the poly, the shifting direction...).

The avalanche behaviour also differs because PEAC is "data-dependent" (the amplitude of the avalanche depends on the carry which depends on the current state and data word). LFSRs work in ℤ2 where any perturbation will behave as individual/independent data, and the LFSR's state will just be a superposition of ALL the individual bits that are fed. Hence, the "attack" angle is different: the way to increase or even counter an avalanche changes.

LFSR are well known for their spectral properties. They have a particular spread, their single bit output provides sequences of consecutive 1s and 0s with lengths inversely proportional to their occurences.

• 1/2 of sequences are 1-bit long (1/4 are 1 and 1/4 are 0)
• 1/4 of sequences are 2-bit long (1/8 are 11 and 1/8 are 00)
• 1/8 of sequences are 3-bit long (1/16 are 111 and 1/16 are 000)
• etc.

The longest sequence of 1s has the length of the LFSR, but by design there can't be an equally long sequence of 0s (this would stall the generator). This is a well known bias.

OTOH, PEAC outputs numbers, not sequences of bits. A maximal PEAC of width w repeats all symbols between 0 and (2^w)-1, approximatively 1+2^(w-1) times before looping. This can easily be inferred from looking at the statespace diagrams.

# Composition.

It is possible to combine two CRCs and calculate the CRC of the merged block. It seems possible to do this with PEAC but I don't know how (yet). This might not be worth the efforts because:

• A well-defined protocol rarely requires blocks to be combined/merged/split (aside from TCP/IP)
• Merging blocks and their CRCs loses granularity, and reduces the ability to repair or isolate altered data.

Comment below if you want me to cover another aspect.