- Tutorial: Cyclic Redundancy Check (CRC) Computation
- Background: Asynchronous Serial Communications (RS-232C)
- Parity Bits
- Intermission: Classes of errors
- Check Digits
- Error Correction Codes (ECC)
- Cyclic Redundancy Check sequences (CRC): A Big Mystery?
- CRC Hardware Operation
- Software CRC Computation
- Mathematical Background
While reordering of words may be uncommon in data communication networks, it is quite common for humans to swap digits in large numbers consisting of seemingly random digits, such as those used in the ISBN system or UPC/EAN product codes. Therefore, a checksum is not suitable for these numbers. A common algorithm is to multiply each digit with a different number before it is added to the sum. In addition to digit substitutions, this helps detect many swapped digits, as the position now becomes significant as well.
Using ISBN as an example, we find the following definition: The number consists of 9 decimal digits, followed by the check digit which is decimal or X, a digit representing 10. Each of these digits is weighted: The first has weight 10, the second, 9, and so on until the last data digit with weight 2 and the check digit with weight 1. The check digit is chosen such that the weighted sum is zero (modulo 11).
What is the check digit of 3-423-10735-_ (the dashes in the sequence are for grouping only)? We have to ensure that 3*10 + 4*9 + 2*8 + 3*7 + 1*6 + 0*5 + 7*4 + 3*3 + 5*2 + c*1 = 0 (mod 11). Simplified, this is 156 + c = 0 (mod 11). As 156 mod 11 = 2, we get c = 9 and thus an ISBN of 3-423-10735-9.
This behavior is much closer to CRCs than you probably would expect. If you understand this, you are a good step into understanding CRCs.
Error detection capability
As 11 is relatively prime to each of the weights used, the check digit will protect against any single-digit modification. A single check digit is unable to detect all two-digit modifications, the simplest example being the adjustment of the check digit after a modification of a data digit. Most modifications to one data digit can be compensated with a modification to another data digit, it is not necessary to revert to updating the check digit. (It is only „most“, not „all“, as only the check digit allows for all necessary 11 values, the data digits are limited to 0…9, lacking the possibility for the special value X.)