Error detection: parity, checksum and CRC

Why it exists

Noise flips bits. The data link layer therefore adds redundancy to each frame so the receiver can detect (and then discard, or ask for a repeat) damaged frames. The redundancy is a few bits computed from the data; the receiver recomputes and compares. Methods differ in cost and in which errors they catch. (Methods that also locate the wrong bit are error-correcting codes, as in the Hamming code, and cost more bits.)

Prerequisites

You need the idea that the link layer builds frames (layering). No algebra beyond modulo-2 arithmetic is used.

Precise definitions

Error types. A single-bit error flips one bit. A burst error of length $b$ is a pattern whose first and last wrong bits are $b$ positions apart (the bits between may or may not be wrong). The Hamming distance between two bit strings is the number of positions in which they differ; a code in which every two codewords differ in at least $d$ positions detects every pattern of fewer than $d$ bit errors.

Parity. Even parity: append one bit so the number of ones is even. Detects every odd number of bit errors, misses every even number.

Two-dimensional parity. Arrange the data in rows, append a parity bit to each row and a parity row for the columns.

Internet checksum (used by IP, TCP, UDP): divide the data into $16$-bit words, add them in ones' complement arithmetic (a carry out of the top is added back at the bottom), and send the complement of the sum. The receiver adds all words including the checksum; the result must be all ones.

CRC (cyclic redundancy check). Choose a generator of $r + 1$ bits, written as a polynomial over the field with two elements (for example $1011 = x^3 + x + 1$, $r = 3$). To send a data word $D$:

1. append $r$ zeros to $D$ (this is $D \cdot x^r$);
2. divide by the generator using modulo-2 arithmetic (subtraction is XOR, no borrows); the remainder has $r$ bits;
3. send $D$ followed by the remainder: the codeword, which is exactly divisible by the generator.

The receiver divides the received bits by the generator: remainder $0$ means "no error detected".

An error pattern $E$ (a polynomial with ones where bits flipped) goes undetected exactly when the generator divides $E$: the received word is codeword $+ E$.

How it works

Long division step by step

Data $1101011011$, generator $10011$ ($x^4 + x + 1$, $r = 4$). Write the data with four zeros appended: $11010110110000$. Whenever the leftmost bit of the current window is $1$, XOR the generator into the window; otherwise slide. The four XOR steps leave the remainder $1110$. The frame sent is $11010110111110$. Dividing it by $10011$ gives remainder $0$.

What a CRC detects

A generator with a nonzero constant term (a $1$ in the last place) and at least two terms:

• detects all single-bit errors (the pattern $x^i$ is never a multiple of such a generator);
• detects all burst errors of length at most $r$ (a pattern with ones only within $r$ consecutive positions has degree less than $r$ after removing the trailing zeros, so a multiple of the generator of degree $r$ cannot fit);
• detects all odd numbers of bit errors if $(x + 1)$ divides the generator, which happens exactly when the generator has an even number of terms (an even number of ones);
• detects every double-bit error if the frame is shorter than the order of $x$ modulo the generator (for $x^3 + x + 1$ the order is $7$, for $x^4 + x + 1$ it is $15$).

The number of error patterns that escape is exactly the number of non-zero multiples of the generator that fit in the frame: $2^{n-r} - 1$ for an $n$-bit frame.

For $1011$ and $7$ bits: of the $127$ error patterns exactly $15$ are undetected, and none of them has one or two flipped bits. At $8$ bits one double error escapes (positions $7$ apart). The generator $1001 = x^3 + 1$ has two terms, so $x + 1$ divides it: odd-weight errors cannot escape, but five double-bit patterns do. Real protocols use generators of degree $16$ or $32$ (Ethernet uses the CRC-32 polynomial, quoted, and checked here against the standard library implementation).

The other methods on the same errors

Parity misses all even numbers of errors, including two flipped bits. Two-dimensional parity on a $4 \times 5$ block:

All patterns of $1$, $2$ and $3$ flipped bits are detected, and a single flipped bit can even be located (the wrong row and the wrong column) and corrected. Four flipped bits at the corners of a rectangle change each affected row and column parity twice and are missed: $60$ of the $4845$ patterns.

The Internet checksum:

The ten words are the words of a sample IPv4 header (checksum field set to zero). The sum is $479E$, the checksum $B861$ (the complement), and the receiver's sum of all eleven words is $FFFF$. The checksum is cheap to compute in software but weaker than a CRC: it cannot detect two words swapped, or errors in different words that compensate, and its sum is the same if words are reordered.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Ethernet frames end with a $32$-bit CRC (Ethernet); the IPv4 header has a checksum that routers recompute (IPv4 fragmentation and the header). Detecting an error leads to retransmission, handled by the sliding window protocols (sliding window); error-correcting codes avoid retransmission at the cost of more bits (Hamming code).

PYQs

Consider the cyclic redundancy check (CRC) based
error detecting scheme having the generator
polynomial
x3+x+1.
Suppose
the
message
m4m3m2m1m0=11000 is to be transmitted. Check
bits c2c1c0 are appended at the end of the message
by the transmitter using the above CRC scheme.
The transmitted bit string is denoted by
m4m3m2m1m0c2c1c0. The value of the check bit
sequence c2c1c0 is:

A computer network uses polynomials over GF(2)
for error checking with 8 bits as information bits
and uses x3+x+1 as the generator polynomial to
generate the check bits. In this network, the
message 01011011 is transmitted as:

Let G(x) be the generator polynomial used for CRC
checking. What is the condition that should be
satisfied by G(x) to detect odd number of bits in
error?

The message 11001001 is to be transmitted using the
CRC polynomial x3 + 1 to protect it from errors. The
message that should be transmitted is:

Self-check

Revision card

References