Koopman Checksum

An Improved Modular Addition Checksum Algorithm

Philip Koopman

This paper introduces a checksum algorithm that provides a new point in the performance/complexity/effectiveness checksum tradeoff space. It has better fault detection properties than single-sum and dual-sum modular addition checksums. It is also simpler to compute efficiently than a cyclic redundancy check (CRC) due to exploiting commonly available hardware and programming language support for unsigned integer division. The key idea is to compute a single running sum, but introduce a left shift by the size (in bits) of the modulus before performing the modular reduction after each addition step. This approach provides a Hamming Distance of 3 for longer data word lengths than dual-sum approaches such as the Fletcher checksum. Moreover, it provides this capability using a single running sum that is only twice the size of the final computed check value, while providing fault detection capabilities even better than large-block variants of dual-sum approaches that require larger division operations. A variant that includes a parity bit achieves Hamming Distance 4 for about half the data word length as the baseline version for the same size check value.

Full paper here: https://arxiv.org/abs/2304.13496

Below is a simplistic comparison of execution time for 32-bit checksums. Every system will have a different outcome, but this gives a general idea of what to expect. Koopman checksums have about the same run time as a Fletcher or Adler checksum, and likely have slightly faster run time for a machine such as an Intel server that has strong hardware support for division. (The DualSum32 implementation includes an optimization of delaying the SumB modulo operation until the end of the computation.) Nonetheless, Koopman checksums provide better Hamming Distance performance.  CRC_R32T is a CRC implementation that uses a 256-element lookup table to speed up the computation.

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