Error Detection: Parity, Hamming Distance and Internet Checksum

Noise, interference and faulty hardware flip bits. A receiver that cannot tell a damaged frame from a good one will pass garbage upward. Error detection adds redundant bits computed from the data; the receiver recomputes them and compares. If they disagree, the frame is discarded (and, if the protocol provides it, retransmitted). Error correction adds enough redundancy to locate and fix the flipped bits without retransmission.

On wired links errors are rare, so networks mostly detect and retransmit. The three detection schemes that matter are parity (one bit or a two-dimensional grid of bits), the Internet checksum (a 16-bit ones' complement sum used in IP, UDP and TCP), and the cyclic redundancy check (CRC, used in Ethernet frames, covered in Cyclic Redundancy Check (CRC)). The common language for comparing them is Hamming distance.

Before any check can be applied, the receiver must know where a frame starts and ends. That is framing. A receiver can find frame boundaries with a length field, byte stuffing, bit stuffing, or physical-layer coding violations.

The Hamming distance $d(x, y)$ between two equal-length words is the number of positions where they differ, which is the number of 1s in $x \oplus y$. The minimum distance $d_{\min}$ of a code is the smallest distance between two different codewords.

Reason: $s$ flips can turn a codeword into another codeword only if $s \ge d_{\min}$. For correction, the received word must stay strictly closer to the sent codeword than to any other, which needs the spheres of radius $t$ around codewords to be disjoint.

Detection versus correction. A code with $d_{\min} = 4$ detects 3 errors or corrects 1 (and detects 2 while correcting 1), but it cannot correct 3. The two uses compete for the same distance.

Append one bit so that the number of 1s is even (even parity) or odd (odd parity). $d_{\min} = 2$: every odd number of flipped bits is detected, every even number is missed. It is cheap and weak.

Arrange the data as a grid, add a parity bit to every row and every column, plus a corner bit (the parity of the parity row, which equals the parity of the parity column). $d_{\min} = 4$:

Used in the IPv4 header (header only), and in UDP and TCP (over a pseudo-header, the transport header and the data). The data is treated as a sequence of 16-bit words:

If the data has an odd number of bytes, a zero byte is appended for the computation only. The order in which the words are added does not matter, and the end-around carries can be folded at the end instead of after every addition: both give the same result.

What the checksum misses. Because addition is commutative, swapping two 16-bit words gives the same checksum. Two errors that add some value to one word and subtract it from another in the same bit column cancel. Its strength is speed in software, not error coverage; that is why links use a CRC and the checksum is the end-to-end backstop.

A receiver finds frame boundaries in one of four ways: a length field (fragile, because a corrupted count loses synchronisation), byte stuffing, bit stuffing, or physical-layer coding violations.

Byte stuffing. Each frame starts and ends with a special FLAG byte. If a FLAG byte occurs inside the data, the sender inserts an ESC byte before it; an ESC in the data is also preceded by an ESC. The receiver removes every ESC and treats the next byte as data. The overhead depends on how many FLAG and ESC bytes the data contains; in the worst case the frame doubles.

Bit stuffing. Each frame is bounded by the flag pattern 01111110. Inside the frame, the sender inserts a 0 after every run of five consecutive 1s, whatever the next bit is. The receiver deletes the 0 that follows any five consecutive 1s. Six 1s in a row can then occur only in a flag. The frame can be any number of bits, not a whole number of bytes.

Bit versus byte stuffing. Byte stuffing works on whole bytes and needs two special byte values; bit stuffing works on the bit stream and needs one 8-bit flag pattern. A question about "how many bits are added" means bit stuffing: count runs of five 1s, restarting the count after each inserted 0.

Parity detects exactly the odd-weight errors. The parity of the received word is the parity of the sent word XOR the parity of the error pattern. The check fails exactly when the error pattern has an odd number of 1s.

Check bits needed for single-error correction (Hamming bound for $t = 1$). Each of the $n = m + r$ positions, plus "no error", must have its own syndrome among the $2^r$ values:

For $m = 4$ this gives $r = 3$; for $m = 7$, $r = 4$; for $m = 11$, $r = 4$; for $m = 32$, $r = 6$.

Ones' complement sum. Adding with end-around carry is addition modulo $2^{16} - 1$ on the 16-bit values (with 0x0000 and 0xFFFF both representing zero). If the sum of the data words is $S$, the checksum is $C = \overline{S}$, and $S + C$ (ones' complement) is 0xFFFF.

Code $\{00000, 01011, 10101, 11110\}$. Distances: $d(00000, 01011) = 3$, $d(00000, 10101) = 3$, $d(00000, 11110) = 4$, $d(01011, 10101) = 4$, $d(01011, 11110) = 3$, $d(10101, 11110) = 3$. So $d_{\min} = 3$: the code detects up to 2 errors or corrects 1.

The 7-bit word 1011001 has four 1s. Even parity bit: 0 (codeword 10110010). Odd parity bit: 1. If bits 2 and 5 flip, the received word still has even weight and the error is missed.

For the block in Figure 1, the row parities are 1, 0, 0, 0, the column parities 0, 1, 0, 0, and the corner bit 1. If the bit in row 2, column 3 flips, row 2 and column 3 fail and the receiver flips that bit back. If the four bits at rows 1 and 3, columns 1 and 3 (all 1, 1, 1, 0 in the data) all flip, every check still passes.

Words 0x4F2A, 0xB3C1, 0x9E07. $0x4F2A + 0xB3C1 = 0x102EB$; end-around carry gives 0x02EC. $0x02EC + 0x9E07 = 0xA0F3$. Checksum $= \overline{0xA0F3} = 0x5F0C$. Receiver: $0x4F2A + 0xB3C1 + 0x9E07 + 0x5F0C$ with end-around carries is 0xFFFF. Swapping the first two words before sending gives the same checksum, so a reordering of these words is not detected.

Data 0111111111100 (13 bits) becomes 011111011111000 (15 bits): a 0 is inserted after the first five 1s and after the next five. The flag pattern 01111110 sent as data becomes 011111010. Fourteen 1s in a row become 1111101111101111 (two inserted zeros: after the 5th and the 10th original 1).

Data bytes A, FLAG, ESC, B. The sender puts an ESC before the FLAG and before the ESC, then adds the delimiting flags: FLAG A ESC FLAG ESC ESC B FLAG, 8 bytes for 4 data bytes. A receiver that finds ESC ESC ESC FLAG inside a frame delivers ESC FLAG: each ESC makes the byte after it ordinary data.

Bit destuffing runs the other way. The bits 0111110111110110 received between two flags contain two stuffed 0s, each right after five 1s; deleting them gives the 14 data bits 01111111111110.

Positions 1 to 7; parity bits at positions 1, 2 and 4; even parity; position $p$ is covered by the parity bit $2^i$ when bit $i$ of $p$ is 1. Data 1011 in positions 3, 5, 6, 7 gives check bits $p_1 = 0$, $p_2 = 1$, $p_4 = 0$ and the codeword 0110011. If position 5 flips (received 0110111), recomputing the three checks gives the syndrome $s_4 s_2 s_1 = 101$, which is 5: the receiver flips position 5. $d_{\min} = 3$, so two errors are miscorrected rather than detected.

Common misconceptions.