Hacker News new | comments | show | ask | jobs | submit login
Fletcher's Checksum (wikipedia.org)
87 points by mrccc 45 days ago | hide | past | web | favorite | 11 comments



The original paper "An Arithmetic Checksum for Serial Transmissions" is worthwhile reading. Fletcher's background as a physicist shows through and the analysis is interesting as it contrasts to many other papers I have read on codes.

Also: note the section in the Wikipedia page on the Adler checksum, which was an attempt to improve Fletcher's checksum by substituting a prime modulus. This stands to reason as a prime modulus is usually important in codes. This change was probably not backed up by analysis and through direct simulation has shown to actually weaken the checksum.

Just pointing this out as an example of what I have observed personally: people tinkering with codes (nothing wrong with that) to improve them, without bothering to understand the analysis they would have to do to prove that they hadn't made things actually worse.

[yet another edit:] If you find error-detecting and -correcting codes interesting or mysterious, read the original papers! So many fun and interesting things to see there, and it is a chance to motivate a look into areas of math you might be unfamiliar with. 'Nuff said.


For some context, the Fletcher checksum algorithm is used by bother ZFS and APFS (the new Apple filesystem for iOS and macOS). So it is a fairly wildly used checksum algorithm.


That was my first thought: "ZFS, Jeff Bonwick!"


Related:

Modulus without Division, a tutorial

http://homepage.divms.uiowa.edu/~jones/bcd/mod.shtml



That is an alternative to using the modulo function for hashing, not an alternative implementation of the modulo function.


'The Fletcher checksum cannot distinguish between blocks of all 0 bits and blocks of all 1 bits.'

For some reason, I find it fascinating to read about such a fundamental limitation. But I understand it doesn't apply much in the real world.


Presumably it depends on the modulus used? I think the article is assuming a modulus of 2^n-1.

As the article says, Adler-32 is a specialization of Fletcher-32 that specifies a modulus of 65521 - that would seem to avoid this limitation.


related, the Mojette transform used by ROzoFS (an HPC filesystem): https://en.wikipedia.org/wiki/Mojette_Transform


i have used this on couple projects most notably:

- wireless network packet checksum - filesystem checksum

good thing is that comes in variations, 16, 32 and 64 bits wide


Not quite my tempo.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: