Close

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 / YGDESYann 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.

Size/Width.

Size/Period/Orbits.

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.

Circuit size/Complexity.

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

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.

Symbol spread/repetition

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.

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:


Comment below if you want me to cover another aspect.

Discussions