3.3 Error Detection: Check Digits & CRC

Theory: Error Detection: Check Digits & CRC

No recording or transmission medium is perfect for its whole working life. As more bits are packed into each square centimetre of disk and as transmission speeds rise, the chance of an error rises too, sometimes geometrically. So computers add redundant information to the data: extra digits or bits computed from the data, which let the receiver test whether what arrived is consistent. This lesson covers detection (is there an error?). The next lesson, Hamming codes, covers correction (which bit is wrong?).

Check digits

Intuition: append one extra digit that is a fixed function of all the other digits. A typing or scanning mistake in any one digit almost always changes that function, so the check digit no longer matches. The last digit of UPC (Universal Product Code) barcodes and of ISBNs (book numbers) are check digits.

UPC-A rule (12 digits; the 12th is the check digit). Number the first 11 digits 1 to 11 from the left.

Add the digits in the odd positions (1, 3, 5, 7, 9, 11).
Multiply that sum by 3.
Add the digits in the even positions (2, 4, 6, 8, 10).
Add the results of steps 2 and 3 to get $S$ .
Check digit $= 10 - (S \bmod 10)$ ; if $S \bmod 10 = 0$ the check digit is 0.

Mini-example (as in the lecture)

The UPC-A barcode on a box of tissues is 036000 241457. Odd positions: $0+6+0+2+1+5 = 14$ , times 3 = 42. Even positions: $3+0+0+4+4 = 11$ . $S = 42 + 11 = 53$ , $53 \bmod 10 = 3$ , check digit $= 10 - 3 = 7$ , which matches the last digit ✓.

Systematic error detection for blocks: the syndrome

For data streams (large blocks of data) we want something more systematic and economical than a check digit per number. A group of error-control bits is appended to the end of the block; this group of bits is called the syndrome. The most widely used method is the Cyclic Redundancy Check (CRC), which treats bit strings as polynomials over modulo-2 arithmetic.

Modulo-2 arithmetic

Modulo-2 arithmetic works bit by bit with no carries and no borrows:

$a$	$b$	$a + b$	$a - b$
0	0	0	0
0	1	1	1
1	0	1	1
1	1	0	0

So addition and subtraction are both XOR and are the same operation. Long division works like ordinary long division, except each “subtract” is an XOR, and we “subtract” the divisor whenever the leading bit of the current part is 1 (there is no “is it big enough?” comparison).

Mini-example

$1011 + 0110 = 1101$ and $1011 - 0110 = 1101$ (the same). Compare decimal binary addition, $1011_2 + 0110_2 = 10001_2$ , which needs carries.

Polynomial keys

A bit string is read as the coefficients of a polynomial, the leftmost bit being the highest power:

$1101 \;\longleftrightarrow\; 1\cdot x^3 + 1\cdot x^2 + 0\cdot x + 1 = x^3 + x^2 + 1$

The sender and receiver agree in advance on such a polynomial, the key (or generator). If the key has $n + 1$ bits (degree $n$ ), the CRC (syndrome) has $n$ bits.

The CRC procedure

Diagram loads as you scroll.

Sender

Let the key have $n + 1$ bits. Shift the information string left by $n$ places, i.e. append $n$ zeros (one fewer than the number of bits in the key).
Divide this by the key using modulo-2 division.
The remainder ( $n$ bits) is the CRC. Replace the appended zeros with the remainder (equivalently, add the remainder): codeword = information string + syndrome.

Receiver

Divide the received codeword by the same key.
If the remainder is 0, accept the data (no error detected). If it is not 0, an error has occurred: reject the block and ask for retransmission.

Why it works: the codeword is $T(x) = M(x)\,x^n + R(x)$ , and in modulo-2 arithmetic adding $R(x)$ is the same as subtracting it, so $T(x)$ is an exact multiple of the key $G(x)$ . If the channel adds an error pattern $E(x)$ , the receiver divides $T(x) + E(x)$ and gets the remainder of $E(x)$ alone. The error is missed only if $E(x)$ happens to be a multiple of $G(x)$ .

Mini-example

Key 1101 (4 bits) → append 3 zeros. Information 1 → divide 1000 by 1101: $1000 \oplus 1101 = 0101$ , remainder 101. Codeword 1101, which is the key itself, so it divides exactly ✓.

Standard polynomials

Real applications use longer keys so that larger blocks are protected:

Name	Polynomial	Used in
CRC-12	$x^{12} + x^{11} + x^3 + x^2 + x + 1$	telecom systems
CRC-16	$x^{16} + x^{15} + x^2 + 1$	USB
CRC-16-CCITT	$x^{16} + x^{12} + x^5 + 1$	XMODEM, X.25, V.41, Bluetooth, PPP, IrDA
CRC-32 (IEEE 802.3)	$x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1$	Ethernet, MPEG-2

What a CRC detects

For a key of degree $n$ (with more than one term, and a constant term 1):

all single-bit errors ( $E(x) = x^i$ is never a multiple of such a key);
all burst errors of length $\le n$ (a burst is a run of damaged bits starting and ending with a wrong bit);
all errors with an odd number of wrong bits when $(x + 1)$ is a factor of the key (true for CRC-16 and CRC-16-CCITT, whose number of terms is even);
most longer bursts: a fraction $1 - 2^{-n}$ of long random error patterns is caught, e.g. about 99.998% for a 16-bit CRC. In practice CRCs catch well over 99.8% of all errors.

CRC only detects. That is fine for transmission (just ask the sender to send again) but not for memory or long-term storage, where the original is gone: there we need an error-correcting code such as Hamming or Reed-Solomon.

Worked Examples

Exercise 1

(a) Verify the check digit of the UPC-A code 036000241457. (b) Find the check digit for the 11-digit UPC body 01234567890.

Show solution ↓

Solution

(a) Digits in positions 1–11: 0 3 6 0 0 0 2 4 1 4 5.

Step	Calculation	Result
Odd positions (1,3,5,7,9,11)	$0 + 6 + 0 + 2 + 1 + 5$	14
× 3	$14 \times 3$	42
Even positions (2,4,6,8,10)	$3 + 0 + 0 + 4 + 4$	11
Total $S$	$42 + 11$	53
Check digit	$10 - (53 \bmod 10) = 10 - 3$	7

The 12th digit printed is 7 ✓.

(b) Digits: 0 1 2 3 4 5 6 7 8 9 0.

Odd positions: $0 + 2 + 4 + 6 + 8 + 0 = 20$ , × 3 = 60.
Even positions: $1 + 3 + 5 + 7 + 9 = 25$ .
$S = 60 + 25 = 85$ , $85 \bmod 10 = 5$ , check digit $= 10 - 5 =$ 5.

Full code: 012345678905.

Exercise 2

(a) Compute $1011 + 0110$ and $1101 - 0111$ in modulo-2 arithmetic. (b) Write the key 1101 as a polynomial, and write $x^4 + x + 1$ as a bit string. (c) Write CRC-16-CCITT as a bit string. How many bits is its CRC? (d) Multiply $(x + 1)(x^2 + x + 1)$ in modulo-2 arithmetic and give the bit string.

Show solution ↓

Solution

(a) Bitwise XOR:

  1011        1101
⊕ 0110      ⊕ 0111
  ----        ----
  1101        1010

$1011 + 0110 = 1101$ and $1101 - 0111 = 1010$ .

(b) 1101 → coefficients of $x^3, x^2, x^1, x^0$ are 1, 1, 0, 1 → $x^3 + x^2 + 1$ . $x^4 + x + 1$ → coefficients of $x^4 \dots x^0$ are 1, 0, 0, 1, 1 → 10011.

(c) $x^{16} + x^{12} + x^5 + 1$ has 1s at powers 16, 12, 5, 0 → 17 bits:

power: 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
bit:    1  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  1

i.e. 1 0001 0000 0010 0001 ( $11021_{16}$ ). The key has 17 bits (degree 16), so the CRC has 16 bits.

(d) $(x + 1)(x^2 + x + 1) = x^3 + x^2 + x + x^2 + x + 1$ . Terms that appear twice cancel ( $1 + 1 = 0$ ): $x^3 + 1$ → 1001. (Bit form: $11 \times 111$ with XOR-adds: $1110 \oplus 0111 = 1001$ ✓.)

Exercise 3

(Lecture example) Using the key 1101 ( $x^3 + x^2 + 1$ ), compute the CRC codeword for the information string 1111101.

Show solution ↓

Solution

Step 1: the key has 4 bits, so append $4 - 1 = 3$ zeros: 1111101 → 1111101000.

Step 2: modulo-2 division by 1101. At each step, XOR the key under the leftmost remaining 1:

           1011011   ← quotient
      ┌───────────
1101  │ 1111101000
        1101  ← XOR key (step 1)
        ──────────
        0010101000
          1101  ← XOR key (step 2)
        ──────────
        0001111000
           1101  ← XOR key (step 3)
        ──────────
        0000010000
             1101  ← XOR key (step 4)
        ──────────
        0000001010
              1101  ← XOR key (step 5)
        ──────────
        0000000111
remainder = last 3 bits = 111

The intermediate values are $1111101000 \to 0010101000 \to 0001111000 \to 0000010000 \to 0000001010 \to 0000000111$ .

Step 3: the remainder (syndrome) is 111. Replace the three appended zeros with it:

$1111101000 + 111 = 1111101111$

Codeword: 1111101111 (information 1111101 | CRC 111).

Exercise 4

The receiver gets (a) 1111101111 and (b) 1111100111. Using the key 1101, decide whether each is accepted.

Show solution ↓

Solution

(a) Divide the whole received string by 1101 (no zeros are appended at the receiver):

           1011011   ← quotient
      ┌───────────
1101  │ 1111101111
        1101  ← XOR key (step 1)
        ──────────
        0010101111
          1101  ← XOR key (step 2)
        ──────────
        0001111111
           1101  ← XOR key (step 3)
        ──────────
        0000010111
             1101  ← XOR key (step 4)
        ──────────
        0000001101
              1101  ← XOR key (step 5)
        ──────────
        0000000000
remainder = last 3 bits = 000

Remainder 000 → no error, accept ✓. The quotient 1011011 is the same as at the sender.

(b)

           1011010   ← quotient
      ┌───────────
1101  │ 1111100111
        1101  ← XOR key (step 1)
        ──────────
        0010100111
          1101  ← XOR key (step 2)
        ──────────
        0001110111
           1101  ← XOR key (step 3)
        ──────────
        0000011111
             1101  ← XOR key (step 4)
        ──────────
        0000000101
remainder = last 3 bits = 101

Remainder 101 ≠ 000 → error detected, reject and request retransmission.

Comparing with the sent codeword, bit $x^3$ (4th from the right) was flipped. The remainder 101 is exactly the remainder of $x^3$ divided by the key: $x^3 = 1\cdot(x^3 + x^2 + 1) + (x^2 + 1)$ , and $x^2 + 1$ = 101 ✓. The receiver sees only the effect of the error pattern.

Exercise 5

Using the generator $x^4 + x + 1$ , compute the CRC codeword for the information string 1101011011, then check it at the receiver.

Show solution ↓

Solution

Key: $x^4 + x + 1$ = 10011 (5 bits) → append 4 zeros: 11010110110000.

Sender division:

             1100001010   ← quotient
       ┌───────────────
10011  │ 11010110110000
         10011  ← XOR key (step 1)
         ──────────────
         01001110110000
          10011  ← XOR key (step 2)
         ──────────────
         00000010110000
               10011  ← XOR key (step 3)
         ──────────────
         00000000101000
                 10011  ← XOR key (step 4)
         ──────────────
         00000000001110
remainder = last 4 bits = 1110

Remainder 1110 → codeword 11010110111110 (information 1101011011 | CRC 1110).

Receiver division:

             1100001010   ← quotient
       ┌───────────────
10011  │ 11010110111110
         10011  ← XOR key (step 1)
         ──────────────
         01001110111110
          10011  ← XOR key (step 2)
         ──────────────
         00000010111110
               10011  ← XOR key (step 3)
         ──────────────
         00000000100110
                 10011  ← XOR key (step 4)
         ──────────────
         00000000000000
remainder = last 4 bits = 0000

Remainder 0000 → accepted ✓.

Exercise 6

The codeword 1111101111 (key 1101) is hit by each error pattern below (a 1 marks a flipped bit). Which errors does the CRC detect? Explain the one it misses.

(a) 0000000011 (b) 0000111000 (c) 0001101000

Show solution ↓

Solution

Received = codeword XOR error. The receiver’s remainder equals the remainder of the error pattern itself.

	Error pattern	Received word	Remainder	Result
(a)	0000000011 (burst of 2)	1111101100	011	detected
(b)	0000111000 (burst of 3)	1111010111	001	detected
(c)	0001101000	1110000111	000	missed

(a) and (b) are bursts of length $\le 3$ , the degree of the key, so they are always caught.

(c) The error pattern 0001101000 is $x^6 + x^5 + x^3 = x^3(x^3 + x^2 + 1)$ , i.e. the key shifted left by 3: a multiple of the key. Adding a multiple of the key to a multiple of the key gives another multiple, so the division of the received word comes out exact:

           1010011   ← quotient
      ┌───────────
1101  │ 1110000111
        1101  ← XOR key (step 1)
        ──────────
        0011000111
          1101  ← XOR key (step 2)
        ──────────
        0000010111
             1101  ← XOR key (step 3)
        ──────────
        0000001101
              1101  ← XOR key (step 4)
        ──────────
        0000000000
remainder = last 3 bits = 000

This is a burst of length 4, longer than the degree 3 of the key. Real CRCs use degree 16 or 32 keys, so an undetected pattern must be a multiple of a much larger polynomial, which is extremely unlikely.