See also log 81. PEAC vs LFSR.

_____________________________________

General definition

As the name says, PEAC is a Pisano sequence with the added twist of "End-Around Carry", where the sum is post-incremented when an overflow (or wrap around) occurred.

The sequence is performed by simple iterations using 2 variables and only one parameter: the modulus (written m). Depending on this modulus, there can be one, two or more cyclic sequences, or "orbits":

• When there is one orbit, which is the ideal case, the system is called "perfect" and its period is m² + m - 2.
• When there are two orbits, which is still "good enough" for most cases, the system is called "maximal" (for historical reasons) and each of the symmetrical orbits has a period of ((m² + m) / 2 ) -1.
• The other cases have not been named.

There are a total of m² + m states but we don't usually count the degenerate states ("stuck points") at (0, 0) and (m-1, m-1). These values are avoided in PRNG mode but the scrambler and the checksum configurations are immune.

The +m accounts for 2 cases where X=Y, so if only X or Y is looked at, its sequence of values has all the possible values from 0 to m-1, with a 1/2 bias for those limit values.

Note: just like a LFSR, it is a purely linear iterative function that is reversible and can be unwound with a strategy similar to the Berlekamp-Massey algorithm.

Binary PEAC

For practical reasons, the first PEAC sub-family that has been studied has a width parameter w such that m = 2^w.

• widths w=3, 4, 10 and 16 are maximal, they have 2 complementary orbits.
• widths 2 and 26 are perfect (26 still needs a computational proof though, but it is not a priority)

This binary PEAC has a very straight-forward and efficient implementation in hardware and software, making it a sweet spot for PRNG, checsum and (de)scrambler. However it has poor mixing.

Generalised PEAC

Any other modulus is possible, and gPEAC are all the other moduli that are not a power of two. The operations are slightly less convenient for HW implementation but the high-level code is still quite simple and this uncovers some of the mathematical elements required for its analysis.

With a higher "bit density" (just like with LFSR with "dense polynomials"), they have better mixing properties and might become an element for hashing functions.

Here are 2 sub-families where we can tune the biases for a specific application (here: binary words). Other applications and constraints may lead to the creation of other sub-families. Note that the modulus should still be carefully chosen and the "spectrum" of valid values is sparse.

Sqrt(2) moduli

Sqrt(2) is an irrational value with a "good enough" bit density that can be easily scaled, making it appropriate for basic hashes. The other interesting property is that when the modulus is squared, the product is a power of two, suitable for a binary representation with the least bias. This makes it appropriate for indexing hash tables with dynamic size, where the MSB are masked off (or discarded).

This type of moduli is under investigation at this time.

Adjusted moduli

A "perfect" modulus m has a period of m² + m - 2.  The extra m-2 can be a nuisance so a modulus of the form 2^w- 2^w-1 could absorb most of the bias and boost the mixing. This is only a speculation for now.