Checksums

CRCs (Cyclic Redundancy Checks)

CRCs (Cyclic Redundancy Checks)

Fletcher’s Checksum

Fletcher’s checksum is a simple checksum algorithm that is used to detect errors in data transmission. It was developed by John G. Fletcher at Lawrence Livermore Labs in the late 1970s.¹ It was aimed to be an improvement over simple add-and-modulo checksums which are insensitive to block reordering. The key idea is that rather than have a single checksum value, a second value is added and sent along with the data. This value is the sum of the running totals of the first sum. This makes it sensitive to block reordering, as once a block is applied it is then reapplied to the second sum on every block thereafter.

Fletcher-16

Fletcher-16 is where the data is divided into 8-bit blocks (bytes). The sums are calculated modulo 255. Two 8-bit sums are calculated which are combined into a 16-bit Fletcher checksum. The second sum is usually the one that shifted by 8 bits (i.e. multiplied by 256) and added to the first sum.

Note

You may wonder why modulus 255 was chosen instead of modulus 256. Fletcher considered both in his original paper², and Nakassis later summarised the trade-off explicitly³. Any modulus larger than 256 produces residues that don’t fit in a single byte (so some messages can’t be encoded), and any modulus smaller than 256 (other than 255) makes pairs of byte values indistinguishable in the sum. That narrows the meaningful choice to 255 vs 256.

ISO chose 255. The reason is better error detection: Nakassis reports that with mod 256, roughly 1 in 85 two-bit errors goes undetected; with mod 255, only 1 in 4080 — about a 48x improvement. The underlying mechanism is that mod $2^n$ is just truncation, so any error pattern that affects bits beyond the $n$-th position of the running sum is invisible. Mod $2^n - 1$ has carries from the high bits wrap back into the low bits, so every bit position contributes to the final sum. (This is the same property that makes ones’-complement arithmetic the basis of TCP and IP checksums.)

The cost of choosing mod 255 is a real, acknowledged weakness: input byte values 0x00 and 0xFF become indistinguishable to the checksum, since adding 255 mod 255 is the same as adding 0. Nakassis turns this into a feature in one specific way — because you can always pick non-zero check bytes, an all-zero pair of trailing check octets can serve as a sentinel for “no checksum present”.

A visual way to see the carry-loss problem: when sending a stream of identical bytes, the running sum cycles through values determined by $\gcd(M, b)$ (greatest common divisor). With mod 256 sending many 0x80 (128), the sum cycles through just 2 values: 0, 128, 0, 128, .... With mod 255 the same stream cycles through all 255 values: 0, 128, 1, 129, 2, 130, 3, 131, .... Mod 255 isn’t immune — sending many 0x55 (85) cycles through only 3 values: 0, 85, 170, 0, 85, 170, ... — but its worst case (3) is still better than mod 256’s worst case (2).

Nakassis’s overall verdict is more measured than the ISO choice suggests: “Some, but not all, of the detection properties are better when M=255… neither option emerges clearly superior to the other.” On the VAX-11 he benchmarks, the speed difference between the two is also negligible. ISO presumably went with 255 for the two-bit error detection bonus, and that’s the convention that has stuck.

Error detection comparison between Fletcher’s checksum and CRC error detection. Taken from Anastase Nakassis’s paper.³

Sometimes a further step is taken in where a second checksum is calculated which is chosen so that the global checksum (the checksum over all bytes including the checksum itself) is zero. If this is desired, the second checksum can be calculated as:

$$\begin{aligned} C_{B0} = 255 - ((C_0 + C_1) \bmod 255) C_{B1} = 255 - ((C_0 + C_{B0}) \bmod 255) \end{aligned}$$

Example

Calculate the Fletcher-16 checksum for the following data:

0x01 0x02

Initialise both running sums to zero: $C_0 = 0$, $C_1 = 0$.

Process byte 0x01:

$$\begin{aligned} C_0 &= (C_{0,\text{prev}} + \text{0x01}) \bmod 255 = (0 + 1) \bmod 255 = 1 \\ C_1 &= (C_{1,\text{prev}} + C_0) \bmod 255 = (0 + 1) \bmod 255 = 1 \end{aligned}$$

Process byte 0x02:

$$\begin{aligned} C_0 &= (C_{0,\text{prev}} + \text{0x02}) \bmod 255 = (1 + 2) \bmod 255 = 3 \\ C_1 &= (C_{1,\text{prev}} + C_0) \bmod 255 = (1 + 3) \bmod 255 = 4 \end{aligned}$$

Combine into the 16-bit checksum, with $C_1$ as the high byte and $C_0$ as the low byte:

$$\text{checksum} = (C_1 \ll 8) \mid C_0 = (4 \ll 8) \mid 3 = \text{0x0403}$$

If we wanted to make the global checksum zero, we would calculate the second checksum as:

$$\begin{aligned} C_{B0} &= 255 - ((C_0 + C_1) \bmod 255) = 255 - ((3 + 4) \bmod 255) = 255 - 7 = 248 = \text{0xF8} \\ C_{B1} &= 255 - ((C_0 + C_{B0}) \bmod 255) = 255 - ((3 + 248) \bmod 255) = 255 - 251 = 4 = \text{0x04} \end{aligned}$$

Combine into the 16-bit second checksum, with $C_{B1}$ as the high byte and $C_{B0}$ as the low byte:

$$\text{checksum}_2 = (C_{B1} \ll 8) \mid C_{B0} = (4 \ll 8) \mid 248 = \text{0x04F8}$$

We can verify this: appending 0xF8 0x04 to the data and re-running Fletcher-16 should yield $C_0 = 0$ and $C_1 = 0$.

All 1’s or All 0’s Checksum

One limitation of Fletcher’s checksum is that it cannot detect the difference between a data block that is all 1’s and a data block that is all 0’s. The checksum will be the same for both cases.

Footnotes

1. Wikipedia (2025, Aug 4). Fletcher’s checksum [wiki]. Retrieved 2026-04-28, from https://en.wikipedia.org/wiki/Fletcher%27s_checksum. ↩

2. J. G. Fletcher (1982, Jan). An Arithmetic Checksum for Serial Transmissions. IEEE Transactions on Communications. Retrieved 2026-04-28, from https://ieeexplore.ieee.org/document/1095369/. ↩

3. Anastase Nakassis (1988, Oct). Fletcher’s error detection algorithm: how to implement it efficiently and how to avoid the most common pitfalls [pdf]. ACM SIGCOMM Computer Communication Review. Retrieved 2026-04-28, from https://dl.acm.org/doi/pdf/10.1145/53644.53648. ↩ ↩²