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:

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:

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".

Example 2: "024000001669".

Example 3: "5010061001613".

See also Cyclic Redunadncy Check (CRC)


Gorry Fairhurst - Date: 21/02/2012 EG3557