Fletcher's Checksum - Fletcher-16

Fletcher-16

When the data word is divided into 8 bit blocks, as in the example above, two 8-bit sums result and are combined into a 16-bit Fletcher checksum. Usually, the second sum will be multiplied by 256 and added to the simple checksum, effectively stacking the sums side-by-side in a 16-bit word with the simple checksum at the least significant end. This algorithm is then called the Fletcher-16 checksum. The use of the modulus 255 is also generally implied.

The choice of modulus must obviously be such that the results will fit in the block size. 256 is therefore the largest possible modulus for Fletcher-16. It is a poor choice, however, as bits that overflow past bit 7 of the sum are simply lost. A modulus that takes the overflow bits and mixes them into the lower bits provides better error detection. The modulus should, however, be large so as to obtain the largest universe of checksum values. The value 255 takes the second consideration over the first, but has been found to have excellent performance.