Close

What about EAC ?

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 08/05/2021 at 02:460 Comments

This PEAC algorithm is just a Pisano-type algo, with some added End Around Carry.

As I'm about to test it against other algos, and I have already examined the Pisano/Fibonacci aspect, the EAC side now looks strangely and sadly under-covered. This is an essential sub-system that has deep effects on the behaviour of whatever uses it, so it should be fully characterised.

I have noted before that EAC seems to perform a mod-2^n-1 for very cheap but I suspect there is more to it than that.

 
-o-O-0-O-o-
 

When working with an 8-bit byte, values mod 255 will range from 0 to 254, leaving the value 255 "untouched". This is a weakness because this reduces the odds of detecting an error by 1/256th. OTOH if the checksum is 255 this is a clear sign that something very bad has happened.

With end-around-carry, this range is shifted and now, 0 is the "forbidden value"... If the sum is 256, then the byte wraps around to 0 but the carry is added to give 1. Thus 0 is never encountered, unless the system is initialised to 0 and fed with 0s.

This is an important distinction because PEAC allows 0 as a valid value, while Fletcher does not. As mentioned there, mod and EAC are not the same but have enough similarities that EAC could be studied by going through mod.

...

(tbc)

...

Discussions