Large-Block Checksums

Large-Block Modular Addition Checksum Algorithms

Philip Koopman

Checksum algorithms are widely employed due to their use of a simple algorithm with fast computational speed to provide a basic detection capability for corrupted data. This paper describes the benefits of adding the design parameter of increased data block size for modular addition checksums, combined with an empirical approach to modulus selection. A longer processing block size with the right modulus can provide significantly better fault detection performance with no change in the number of bytes used to store the check value. In particular, a large-block dual-sum approach provides Hamming Distance 3-class fault detection performance for many times the data word length capability of previously studied Fletcher and Adler checksums. Moduli of 253 and 65525 are identified as being particularly effective for general-purpose checksum use.

Download the full paper here: https://arxiv.org/abs/2302.13432





Comments

Post a Comment

Popular posts from this blog

Effect of Initial Seed Values on CRCs and Checksums

Checksums and CRCs involve a repeated computation over the length of a dataword that accumulates a result to form an FCS value. The accumulation value must be initialized to some known value for this process to produce a predictable result for any given codeword. When the initial value is unstated, it is typically assumed to be zero. In some cases, a non-zero value is used instead, such as 0xFFFF for a 16-bit checksum or CRC. This has the advantage of making an all zero codeword impossible. Perhaps more importantly for Fletcher checksum, ATN-32, and CRCs, this has the additional advantage of causing leading zeros of a message to affect the FCS value. To better understand, consider a CRC initialized with an all zero seed value. Any number of all zero dataword chunks can be fed into the CRC and it will stay at a zero value, throwing away information about how many zero chunks have been processed. However, if the CRC computation is initialized to any non-zero value, processing
Read more

CRC Information Quick Start

I'm not able to spend much if any time on this lately due to my work in self driving car safety. Here is a quick start for those looking for info. A tutorial on using CRCs and Checksums (how to apply them, pitfalls, system considerations; not a deep crawl through the math): https://betterembsw.blogspot.com/2013/11/crc-webinar.html A report written for the FAA on CRCs and Checksums (goes with the tutorial) https://betterembsw.blogspot.com/2015/04/faa-crc-and-checksum-report.html A web site of "best" CRCs, including: Description: https://betterembsw.blogspot.com/2010/05/whats-best-crc-polynomial-to-use.html Table of "best" CRCs for each size and length https://users.ece.cmu.edu/~koopman/crc/index.html A zoo that has performance of most published CRCs (there is a page for each polynomial size): https://users.ece.cmu.edu/~koopman/crc/crc32.html Software you can run yourself to confirm performance as a double-check on the tables (which were generated wi
Read more

Explanation of CRC Operation: Polynomial Division, Shift Register, and Comparison (video)

Image
 Here is a video explaining the mechanics of Cyclic Redundancy Check computations, including: An example of the polynomial division approach An example of the XOR-feedback shift register approach A step-by-step comparison of how the polynomial division and shift register approaches are actually doing exactly the same computation. If you've ever wondered why it is that a shift register and polynomial division end up with the same result, this video explains it. Video links (27 minutes):    YouTube | Archive.org
Read more