Message Integrity Check

A range of algorithms are in use in communications systems to verify correct reception of a message. The basic method uses a calculated check value at the sender that depends on the content of the message. The check value and the message are both sent to the receiver. The receiver recomputes the check value based only on the received message conents and then compares the result with the check value that it receivered over the communications link. If the two agree, then the message is judged to be correct.

One simples method to compute a check value is to accumulate the sum of the numercial value of each byte in a message. This method can detect a missing non-zero byte and can detect some patterns of corruption, however the method is not able to detect many common patterns of corruption. It also has a drawback that the size of the check (length in bits) value depends on the message - longer messages produce larger sums. Fortunately, there are many better algorithms. These algorithms trade, probability of catching errors against implementation cost.

Check Digits

One simple method, used for short runs of data is the check digit. This method is used for runs of decimal digits, for example serial numbers of product identifiers, and adds one additional check digit to the sequence of digits. The check digit is communicated as if it were a part of the number to verify correctness before use - for instance when decoding a bar code or transmitting the data along a communications link, the check-value is recomputed and compared with the received data.

A check digit value suitable for short runs of digits (e.g. 10-20) can be accumulated in the following way:

Process each digit in turn (count the first position as "odd", the second as "even", etc working through the entire number, but excluding the check digit if there is one).
Add the values of the odd position digits
(not including the check digit)
Multiply by 3
Add the values of the even position digits
Add results together
Take remainder of division by 10 modulo 10)
Subtract from 10
If remainder is 0, use 0 as the check digit. (This ensures the result is a value 0-9.)

This simple check digit computation is easily understood and implemented by humans, equally it can easily be hanlded by a low cost mircoprocessor/controller. It can correct the following patterns of error:

single digit errors, such as 1 → 2
transposition errors, such as 12 → 21
human errors, such as 19 → 90

This method is used in the Universal Product Code (UPC-A), used to identify products at a supermarket checkout. Some examples are provided below. The method is also used in a modified form to encode the ISBN 13 code used since January 2007 to identify book and written beneath the barcode. This uses the same method as for theUPC, except that the sum of the even position digits is multiplied by 3 instead of the sum of the odd ones.

Although this method can detect many errors, a more sophisticated method is required for binary communications of large messages - see CRC.

Examples use of Check Digits in Universal Product Code (UPC)

Example 1: "01010101010x".

The check value is unknown, shown as "x".
Add odd digits: 0+0+0+0+0+0 = 0
Multiply by 3: 0 x 3 = 0
Add even digits: 1+1+1+1+1 = 5
Add results together: 0 + 5 = 5
Take remainder of (5 / 10), (5 modulo 10), and subtract from 10 i.e. (10 - 5 modulo 10) = 5.
Therefore, the check value is 5.

Example 2: "024000001669".

The last digit is the check digit "9".
Add odd digits: 4+6+1 = 11
Multiply by 3: 11 x 3 = 33
Add even digits: 2+6 = 8
Add results together: 33 + 8 = 41
Take remainder of (41 / 10) = 1
Subtract from 10 i.e. (10 - 1 ) = 9.
Therefore, the check value is 9.

Example 3: "5010061001613".

The last digit is the check digit "3"
Add odd digits: 5+1+0+1+0+6 = 13
Multiply by 3: 13 x 3 = 39
Add even digits: 0+0+6+0+1+1 = 8
Add results together: 39 + 8 = 47
Take remainder of (47 / 10) = 7
Subtract from 10 i.e. (10 - 7 ) = 3.
Therefore, the check value is 3.