Error detection and correction: parity, checksum, CRC, Hamming

The physical layer is not perfect. Noise, interference and weak signals flip some bits. The link layer’s first job is to detect these errors (detection), and sometimes to correct them (correction). On the exam this topic is almost always a hand-calculation question: “compute the CRC”, “compute the checksum”, “which bit is in error?”. You will memorize procedures, not formulas.

Golden rules:

1. Mod-2 arithmetic = XOR. Addition and subtraction are the same, with no carry and no borrow.
2. In CRC, append as many zeros to the data as the degree. If the generator has 4 bits, append 3 zeros.
3. In the Internet checksum, the carry wraps around to the start (wraparound), and the bits are inverted at the end.
4. The Hamming syndrome gives the position of the bad bit in binary.

Detection or correction?

The sender adds $EDC$ (error detection and correction) bits to the $D$ data bits. The receiver gets $D'$ and $EDC'$ and checks consistency. No method gives a 100% guarantee; the goal is to make the probability of an undetected error very small.

Error correction (FEC, forward error correction) lets the receiver correct errors without asking for retransmission. It is valuable on links with large delay, such as satellites. Error detection + retransmission (ARQ) is cheaper on short-delay links. You will see retransmission on the second page of this week.

Parity

One-dimensional parity. One bit is appended to the data. With even parity the total number of 1s is even, with odd parity it is odd.

Data 1011001  -> 1s: 4 (even)
even parity bit = 0  -> 10110010
odd  parity bit = 1  -> 10110011

If a single bit flips, the parity breaks and the error is caught. If two bits flip, the parity still holds: an even number of errors escapes. Since errors usually come in bursts, this is a serious weakness.

Two-dimensional parity. The data is written in a table, and parity is computed for every row and every column:

          c0 c1 c2 c3 | row parity
row 1:     1  0  1  1 |  1
row 2:     0  1  1  0 |  0
row 3:     1  1  0  0 |  0
-----------------------+---
column:    0  0  0  1 |  1   (corner)

If the bit in row 2, column 2 flips (0110 → 0100), the parity of row 2 and the parity of column 2 break. The intersection points to a single bit: the bad bit is found and corrected.

PITFALL · the rectangle error. If the bits at the four corners of a rectangle flip together, every row and every column sees two changes, and all parities look correct. 2D parity misses this.

Hamming distance

The Hamming distance of two bit strings is the number of bits in which they differ (the number of 1s in the XOR). The minimum distance $d_{min}$ of a code is the smallest distance between two valid codewords.

$\text{detection: } d_{min} \ge s + 1 \qquad \text{correction: } d_{min} \ge 2t + 1$

A code with $d_{min} = 3$ detects 2 errors or corrects 1 error. Intuition: draw a sphere of radius $t$ around each valid word; if the spheres do not overlap, you can correct by “rounding” to the nearest valid word.

Internet checksum

Used in IP, UDP and TCP headers. The data is split into 16-bit words.

1. Add the words. If a carry goes beyond 16 bits, add it to the bottom of the result (wraparound, one’s complement addition).
2. Invert all bits of the sum. The result is the checksum.
3. The receiver adds all the words including the checksum. If there is no error, the result is 0xFFFF (all bits 1).

Worked example

Words: 0x6E2B, 0x9C71, 0x13A5.

  6E2B
+ 9C71
------
 10A9C      bit 17 overflowed (carry = 1)
  0A9C + 1 = 0A9D        wraparound
+ 13A5
------
  1E42      no overflow
checksum = ~1E42 = FFFF - 1E42 = E1BD

Receiver: 6E2B + 9C71 + 13A5 + E1BD  ->  FFFF  (no error)

Computing the checksum is cheap in software but weak: for example, it does not notice at all if two words are swapped. That is why the stronger CRC is used at the link layer.

CRC (cyclic redundancy check)

In CRC, bit strings are treated as the coefficients of polynomials. The sender and receiver agree on a generator $G$ of $r+1$ bits. The degree of the generator is $r$.

From polynomial to bit string: one bit for each degree, 0 for a missing degree.

x^3 + x + 1      = 1·x^3 + 0·x^2 + 1·x + 1  -> 1011
x^4 + x + 1      -> 10011
x^4 + x^3 + 1    -> 11001

Procedure:

1. Append $r$ zeros to the end of the data $D$ ($D \cdot 2^r$).
2. Divide this by $G$ with mod-2 division. At each step, align $G$ under the leading 1 and take the XOR. If the leading bit is 0, shift one to the right.
3. The last $r$ bits are the remainder $R$. Transmitted: $D$ followed by $R$.
4. The receiver divides the received string $D R$ (without appending zeros) by $G$. If the remainder is 0, accept; otherwise there is an error.

Worked example: $D$ = 11010110, $G$ = 1011

$r = 3$, append three zeros. On each line we write the dividend as it looks after the XOR:

11010110000        D + 000
1011               align with the leading 1, XOR
01100110000
 1011
00111110000
  1011
00010010000
   1011
00000100000        skip the leading zeros
     1011
00000001100
       1011
00000000111        remainder R = 111 (last 3 bits)

Transmitted: 11010110 111
Check      : 11010110111 / 1011  -> remainder 000  (correct)

TIP · quick check. The remainder is always $r$ bits (one bit shorter than the generator). If your remainder came out as 4 bits, you misaligned something.

Why is CRC strong?

• A generator of degree $r$ catches all burst errors of length less than or equal to $r$. Ethernet’s CRC-32 catches all bursts of 32 bits and below; longer ones with probability $1 - 0.5^{r}$.
• Single-bit errors are always caught if $G$ has at least two terms.
• A generator containing the factor $(x+1)$ catches all odd numbers of errors.
• In hardware it runs at line rate with a shift register and a few XOR gates.

PITFALL · CRC is not a security mechanism. CRC was designed against random errors. A malicious party can modify the frame and recompute the CRC, because the algorithm is not secret. Against deliberate modification you need a keyed MAC (week 12).

Hamming code: single-bit correction

Hamming(7,4) adds 3 parity bits to 4 data bits. The parity bits sit at positions that are powers of 2 (1, 2, 4), and the data bits at the rest (3, 5, 6, 7). Each parity bit checks the positions whose binary representation contains its own bit.

Encoding: data 1011

d3=1, d5=0, d6=1, d7=1
p1 = d3 ⊕ d5 ⊕ d7 = 1 ⊕ 0 ⊕ 1 = 0
p2 = d3 ⊕ d6 ⊕ d7 = 1 ⊕ 1 ⊕ 1 = 1
p4 = d5 ⊕ d6 ⊕ d7 = 0 ⊕ 1 ⊕ 1 = 0
position : 1  2  3  4  5  6  7
bit      : 0  1  1  0  0  1  1     -> 0110011

Decoding: bit 6 flipped, 0110001 received

s1 = b1⊕b3⊕b5⊕b7 = 0⊕1⊕0⊕1 = 0
s2 = b2⊕b3⊕b6⊕b7 = 1⊕1⊕0⊕1 = 1
s4 = b4⊕b5⊕b6⊕b7 = 0⊕0⊕0⊕1 = 1
syndrome s4 s2 s1 = 110 (binary) = 6   -> flip bit 6 -> 0110011

If the syndrome is 0, there is no error. This code cannot correctly fix two errors; it “corrects” a wrong bit.

How many parity bits are needed? With $m$ data bits and $r$ parity bits there are $m + r$ positions in total; the syndrome must distinguish each of them and also the “no error” case:

$2^r \ge m + r + 1$

$m = 4 \Rightarrow r = 3$, $m = 8 \Rightarrow r = 4$, $m = 16 \Rightarrow r = 5$, $m = 32 \Rightarrow r = 6$.

Common mistakes