Алгоритм Флетчера: вычисление контрольной суммы для обнаружения ошибок

Algorithm
The Fletcher checksum is an algorithm for computing a position dependent checksum devised by John G. Fletcher (1934–2012) at Lawrence Livermore Labs in the late 1970s. The objective of the Fletcher checksum was to provide error detection properties approaching those of a cyclic redundancy check but with the lower computational effort associated with summation techniques.

As with simpler checksum algorithms, the Fletcher checksum involves dividing the binary data word to be protected from errors into short "blocks" of bits and computing the modular sum of those blocks. (Note that the terminology used in this domain can be confusing. The data to be protected, in its entirety, is referred to as a "word", and the pieces into which it is divided are referred to as "blocks".) As an example, the data may be a message to be transmitted consisting of 136 characters, each stored as an 8 bit byte, making a data word of 1088 bits in total. A convenient block size would be 8 bits, although this is not required. Similarly, a convenient modulus would be 255, although, again, others could be chosen. So, the simple checksum is computed by adding together all the 8 bit bytes of the message, dividing by 255 and keeping only the remainder. (In practice, the modulo operation is performed during the summation to control the size of the result.) The checksum value is transmitted with the message, increasing its length to 137 bytes, or 1096 bits. The receiver of the message can re compute the checksum and compare it to the value received to determine whether the message has been altered by the transmission process.

The first weakness of the simple checksum is that it is insensitive to the order of the blocks (bytes) in the data word (message). If the order is changed, the checksum value will be the same and the change will not be detected. The second weakness is that the universe of checksum values is small, being equal to the chosen modulus. In our example, there are only 255 possible checksum values, so it is easy to see that even random data has about a 0.4% probability of having the same checksum as our message.

Fletcher addresses both of these weaknesses by computing a second value along with the simple checksum. This is the modular sum of the values taken by the simple checksum as each block of the data word is added to it. The modulus used is the same. So, for each block of the data word, taken in sequence, the block's value is added to the first sum and the new value of the first sum is then added to the second sum. Both sums start with the value zero (or some other known value). At the end of the data word, the modulus operator is applied and the two values are combined to form the Fletcher checksum value. Sensitivity to the order of blocks is introduced because once a block is added to the first sum, it is then repeatedly added to the second sum along with every block after it. If, for example, two adjacent blocks become exchanged, the one that was originally first will be added to the second sum one fewer times and the one that was originally second will be added to the second sum one more time. The final value of the first sum will be the same, but the second sum will be different, detecting the change to the message. The universe of possible checksum values is now the square of the value for the simple checksum. In our example, the two sums, each with 255 possible values, result in 65025 possible values for the combined checksum.

While there is an infinity of parameters, the original paper only studies the case K=8 (word length) with modulus 255 and 256. The 16 and 32 bits versions (Fletcher 32 and 64) have been derived from the original case and studied in subsequent specifications or papers.

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 28−1=255 is also generally implied.

When the data word is divided into 16 bit blocks, two 16 bit sums result and are combined into a 32 bit Fletcher checksum. Usually, the second sum will be multiplied by 216 and added to the simple checksum, effectively stacking the sums side by side in a 32 bit word with the simple checksum at the least significant end. This algorithm is then called the Fletcher 32 checksum. The use of the modulus 216−1=65,535 is also generally implied. The rationale for this choice is the same as for Fletcher 16.

When the data word is divided into 32 bit blocks, two 32 bit sums result and are combined into a 64 bit Fletcher checksum. Usually, the second sum will be multiplied by 232 and added to the simple checksum, effectively stacking the sums side by side in a 64 bit word with the simple checksum at the least significant end. This algorithm is then called the Fletcher 64 checksum. The use of the modulus 232−1=4,294,967,295 is also generally implied. The rationale for this choice is the same as for Fletcher 16 and Fletcher 32.

The Adler 32 checksum is a specialization of the Fletcher 32 checksum devised by Mark Adler. The modulus selected (for both sums) is the prime number 65,521 (65,535 is divisible by 3, 5, 17 and 257). The first sum also begins with the value 1. The selection of a prime modulus results in improved "mixing" (error patterns are detected with more uniform probability, improving the probability that the least detectable patterns will be detected, which tends to dominate overall performance). However, the reduction in size of the universe of possible checksum values acts against this and reduces performance slightly. One study showed that Fletcher 32 outperforms Adler 32 in both performance and in its ability to detect errors. As modulo 65,535 addition is considerably simpler and faster to implement than modulo 65,521 addition, the Fletcher 32 checksum is generally a faster algorithm.

A modulus of 255 is used above and in examples below for Fletcher 16, however some real world implementations use 256. The TCP protocol's alternate checksum has Fletcher 16 with a 256 modulus, as do the checksums of UBX * messages from a U blox GPS. Which modulus is used is dependent on the implementation.

The Fletcher checksum cannot distinguish between blocks of all 0 bits and blocks of all 1 bits. For example, if a 16 bit block in the data word changes from 0x0000 to 0xFFFF, the Fletcher 32 checksum remains the same. This also means a sequence of all 00 bytes has the same checksum as a sequence (of the same size) of all FF bytes.

These examples assume two's complement arithmetic, as Fletcher's algorithm will be incorrect on ones' complement machines.

As with any calculation that divides a binary data word into short blocks and treats the blocks as numbers, any two systems expecting to get the same result should preserve the ordering of bits in the data word. In this respect, the Fletcher checksum is not different from other checksum and CRC algorithms and needs no special explanation. An ordering problem that is easy to envision occurs when the data word is transferred byte by byte between a big endian system and a little endian system and the Fletcher 32 checksum is computed. If blocks are extracted from the data word in memory by a simple read of a 16 bit unsigned integer, then the values of the blocks will be different in the two systems, due to the reversal of the byte order of 16 bit data elements in memory, and the checksum result will be different as a consequence. The implementation examples, above, do not address ordering issues so as not to obscure the checksum algorithm. Because the Fletcher 16 checksum uses 8 bit blocks, it is not affected by byte endianness.