Error Detection and Correction

An error-detecting code appends redundant bits, computed from the data by a deterministic function agreed upon by sender and receiver, so that the receiver can recompute the function and compare. If corruption changed the data but the redundant bits still match by the function's rule, the error is invisible — a miss. The central design goal is to choose a redundancy scheme whose blind spots do not match the error patterns real channels actually produce. The unifying concept is Hamming distance: the number of bit positions in which two equal-length bit strings differ. A code is a set of allowed bit strings (codewords); its minimum distance $d_{\min}$ is the smallest Hamming distance between any two distinct codewords. This single number tells you everything about the code's power. If $d_{\min} = d$, the code can detect up to $d - 1$ bit errors (any smaller number of flips cannot turn one codeword into another), and it can correct up to $\lfloor (d-1)/2 \rfloor$ errors (each codeword owns an exclusive "ball" of that radius, so a corrupted word still lands closest to its true origin). Three broad families sit on this foundation. Parity and checksums are lightweight, additive schemes — a single parity bit, or a running sum like the Internet checksum — good for catching common, low-multiplicity errors cheaply, but with well-known blind spots. CRC (cyclic redundancy check) treats the frame as a polynomial over the two-element field GF(2) and divides it by a fixed generator polynomial; the remainder is the redundancy. CRCs are chosen so that $d_{\min}$ is large enough to catch all burst errors up to the generator's degree, and they dominate link-layer framing. Forward error correction (FEC) goes further: codes such as Hamming, Reed–Solomon, and low-density parity-check (LDPC) codes are constructed so the receiver can not only detect but reconstruct the original data, at the cost of sending more redundant bits per message.

Parity — the atomic building block

A single parity bit appended to $k$ data bits makes the total number of 1-bits even (even parity) or odd (odd parity). The receiver recomputes the parity of the received $k+1$ bits; a mismatch means at least one bit flipped. ``` function COMPUTE_PARITY(data_bits[1..k]): p = 0 for i in 1..k: p = p XOR data_bits[i] return p // append p as bit k+1 function CHECK_PARITY(received_bits[1..k+1]): x = 0 for i in 1..k+1: x = x XOR received_bits[i] return (x == 0) // true means "no error detected" ``` Parity has $d_{\min} = 2$: it detects exactly one flip (distance 1 apart from any other codeword) but a second flip restores overall parity, becoming invisible. Two-dimensional parity (a parity bit per row and per column of a data matrix) raises $d_{\min}$ to 4 and can even locate and correct a single-bit error, because the failing row and failing column pinpoint the exact bit.

The Internet checksum

Used by IP, UDP, and TCP, the Internet checksum treats the packet as a sequence of 16-bit words, sums them with ones'-complement addition (end-around carry), and sends the ones'-complement of that sum. The receiver sums all words including the checksum; a correct, unmangled packet sums to all 1s (all-1s, i.e., $-0$ in ones'-complement). ``` function ONES_COMPLEMENT_SUM(words[1..n]): sum = 0 for i in 1..n: sum = sum + words[i] if sum has a carry out of bit 16: sum = (sum mod 2^16) + 1 // end-around carry return sum mod 2^16 function COMPUTE_CHECKSUM(data_words[1..n]): s = ONES_COMPLEMENT_SUM(data_words) return BITWISE_NOT(s) // 16-bit complement function VERIFY_CHECKSUM(received_words_including_checksum[1..n+1]): s = ONES_COMPLEMENT_SUM(received_words_including_checksum) return (s == 0xFFFF) // all 1-bits means OK ``` This is cheap: pure addition, no multiplication or division, and it can be computed incrementally as packets stream by (useful for routers rewriting only the TTL field, which only needs an incremental update rather than a full recompute). Its weakness is that it is insensitive to reordering of 16-bit words and to certain compensating errors (e.g., incrementing one word while decrementing another leaves the sum unchanged) — it catches typical single-bit noise well but is not a strong adversarial code.

Cyclic Redundancy Check (CRC)

CRC treats an $n$-bit frame as the coefficients of a binary polynomial $M(x)$ and a fixed $(r+1)$-bit generator polynomial $G(x)$ of degree $r$, agreed upon in advance (e.g., CRC-32 uses a specific degree-32 generator). All arithmetic is modulo 2 (XOR, no carries). The sender appends $r$ zero bits to $M(x)$, forming $M(x) \cdot x^r$, and divides by $G(x)$ using binary long division; the $r$-bit remainder $R(x)$ becomes the frame check sequence (FCS). The transmitted bit string is

which is constructed precisely so that $T(x)$ is exactly divisible by $G(x)$ — that is, $T(x) \bmod G(x) = 0$. ``` function CRC_ENCODE(message_bits, generator_bits): r = length(generator_bits) - 1 dividend = message_bits + ZEROS(r) // append r zero bits remainder = MOD2_DIVIDE(dividend, generator_bits) return message_bits + remainder // transmitted frame function CRC_CHECK(received_frame, generator_bits): remainder = MOD2_DIVIDE(received_frame, generator_bits) return (remainder == 0) // true = accept, false = error function MOD2_DIVIDE(dividend_bits, divisor_bits): r = length(divisor_bits) - 1 rem = dividend_bits[1 .. r+1] // first r+1 bits, as a working register for i in (r+2) .. length(dividend_bits): if rem[1] == 1: rem = (rem XOR divisor_bits)[2 .. end] + dividend_bits[i] else: rem = rem[2 .. end] + dividend_bits[i] // final r-bit shift-and-test after consuming all bits if rem[1] == 1: rem = rem XOR divisor_bits return rem[2 .. end] // r-bit remainder ``` (The pseudocode above sketches the classic shift-register style long division; real implementations use a table-driven or shift-register hardware circuit for speed — see the diagram below.) Because polynomial division over GF(2) is linear, corruption on the wire adds an error polynomial $E(x)$: the received bits are $T(x) + E(x)$. The receiver's division detects the error exactly when $E(x) \bmod G(x) \neq 0$. This single fact is why CRC generators are chosen deliberately:

• If $G(x)$ has the factor $(x+1)$, all odd-weight errors are caught (an odd number of flipped bits produces $E(1)=1$, forcing non-divisibility).
• If $G(x)$ has degree $r$, all burst errors of length $\le r$ are caught (a burst error polynomial of degree less than $r$, with a leading 1, cannot be divisible by a degree-$r$ polynomial unless it is zero).
• Well-chosen generators (CRC-16, CRC-32, CRC-CCITT) also catch the overwhelming majority of longer bursts and of double-bit errors, by design and by exhaustive testing over decades of use.

Forward Error Correction: Hamming codes

Detection alone forces a retransmission when an error is found. Forward error correction adds enough structure that the receiver can locate and flip the bad bit itself. The classical example is the Hamming(7,4) code: 4 data bits protected by 3 parity bits, for a 7-bit codeword, achieving $d_{\min}=3$ and hence correcting any single-bit error. Parity bits are placed at positions that are powers of two ($p_1, p_2, p_4$ at positions 1, 2, 4), and each covers a specific subset of bit positions determined by their binary index: ``` function HAMMING74_ENCODE(d1, d2, d3, d4): // positions: 1 2 3 4 5 6 7 // p1 p2 d1 p4 d2 d3 d4 p1 = d1 XOR d2 XOR d4 p2 = d1 XOR d3 XOR d4 p4 = d2 XOR d3 XOR d4 return [p1, p2, d1, p4, d2, d3, d4] function HAMMING74_DECODE(bits[1..7]): c1 = bits[1] XOR bits[3] XOR bits[5] XOR bits[7] // recompute p1's group c2 = bits[2] XOR bits[3] XOR bits[6] XOR bits[7] // recompute p2's group c4 = bits[4] XOR bits[5] XOR bits[6] XOR bits[7] // recompute p4's group syndrome = c44 + c22 + c1 // binary number = faulty position, 0 = no error if syndrome != 0: bits[syndrome] = NOT bits[syndrome] // flip and correct return [bits[3], bits[5], bits[6], bits[7]] // extract original d1 d2 d3 d4 ``` The syndrome — the vector of parity-check mismatches — is not just "error/no error" but literally encodes the position of the flipped bit in binary. That is the elegant trick: with 3 check bits you can distinguish $2^3 = 8$ outcomes (7 possible single-error positions plus "no error"), which is exactly enough, no more, no less — a tight information-theoretic fit. ```svg ```

Parity. Time $O(k)$ to compute or verify over $k$ data bits; space overhead is a single bit ($O(1)$ extra). Correctness follows directly from the algebra of XOR: parity is the sum mod 2 of all bits, and any single bit flip changes that sum by exactly 1, so it is always caught. Any even number of flips changes the sum by an even number, which is 0 mod 2 — always missed. This is a complete characterization, not a heuristic: $d_{\min}=2$ exactly, so detect-capability is exactly 1 error, correct-capability is 0.

Internet checksum. Time $O(n)$ over $n$ 16-bit words, with simple integer addition — no multiplication, dramatically cheaper than CRC in pure software on architectures without CRC instructions. Space overhead is a fixed 16 bits regardless of packet size. It is not a maximum-distance code: it is provably blind to certain reorderings and to compensating additive errors across words, a known and accepted tradeoff for speed given that transport/network layers rely on the stronger link-layer CRC to catch most raw bit errors first, using the checksum mainly as a cheap end-to-end sanity check (e.g., against software or memory bugs, not just link noise).

CRC. Encoding and checking both cost $O(n)$ time for an $n$-bit frame with a fixed-degree generator (division is one pass with an $r$-bit shift register, where $r$ is a small constant like 32), and $O(r)$ space for the shift register — independent of frame length. This is why CRC hardware runs at line rate. Correctness rests on the algebra of GF(2) polynomials:

• Divisibility construction: by design $T(x) = M(x)x^r + R(x)$ satisfies $T(x) \bmod G(x) = 0$, because $R(x)$ was chosen as exactly that remainder, and adding it cancels the remainder in mod-2 arithmetic.
• Detection condition: the receiver sees $T(x) + E(x)$ (XOR is addition in GF(2), so corruption is additive). Since $T(x) \bmod G(x) = 0$, we get $(T(x)+E(x)) \bmod G(x) = E(x) \bmod G(x)$. The error is detected iff $E(x) \bmod G(x) \neq 0$.
• All single-bit errors caught: a single flip gives $E(x)=x^i$, a monomial. If $G(x)$ has more than one term (true for any real generator), $x^i \bmod G(x) \ne 0$ for all $i$, so single flips are always caught.
• All burst errors of length $\le r$ caught: a burst of length $\ell \le r$ can be written $E(x) = x^j (x^{\ell-1} + \dots + 1)$ with degree $< r$. Since $G(x)$ has degree exactly $r$, a nonzero polynomial of strictly smaller degree cannot be a multiple of $G(x)$, so $E(x) \bmod G(x) \ne 0$ unless $E(x)=0$.
• Undetected error probability for random errors: for a "random" long burst or scattered pattern, roughly $1/2^r$ of all possible nonzero error polynomials happen to be multiples of $G(x)$ and thus slip through — this is why $r=32$ (CRC-32) gives an undetected-error probability near $2^{-32}$ for errors that are not structured bursts, an acceptably tiny risk for most engineering purposes.

Hamming(7,4). Encoding is $O(1)$ (3 XORs of fixed-size groups); decoding is $O(1)$ (3 XOR checks plus a conditional flip). Space overhead is 3 redundant bits per 4 data bits — a 75% code rate. Correctness is the sphere-packing argument made concrete: with $d_{\min}=3$, every pair of valid codewords differs in at least 3 positions, so the "Hamming balls" of radius 1 around each of the 16 codewords (each ball containing the codeword itself plus its 7 single-flip neighbors, $1+7=8$ words) are disjoint and together cover exactly $16 \times 8 = 128 = 2^7$ possible bit strings — a perfect code, using every available 7-bit pattern with zero waste. This is why the syndrome (an integer from 0 to 7) exactly and unambiguously identifies the flipped position: there is no leftover "ambiguous" region, and no wasted encoding capacity.

The general tradeoff. Detection-only schemes (parity, checksum, CRC) are cheap per bit but require a retransmission protocol (e.g., ARQ) when they catch an error, costing at least one round-trip time. FEC schemes (Hamming, Reed–Solomon, LDPC, turbo codes) avoid that round trip by paying redundancy on every frame, whether or not an error occurs — a good trade when round trips are expensive (satellites, deep space, real-time media) or errors are frequent (noisy wireless, flash memory), and a poor trade when the channel is usually clean (a well-shielded fiber, where most frames need no repair and the FEC bits are wasted overhead).

Take generator polynomial $G(x) = x^3 + x + 1$, i.e., the 4-bit pattern 1011 (this is the standard "CRC-3" style toy example used to hand-trace the algorithm). Suppose the message is $M = 1101$. Step 1 — append $r=3$ zero bits: dividend = 1101000. Step 2 — perform mod-2 (XOR) long division by 1011:

Carrying this out bit by bit (binary long division, XOR instead of subtraction): ``` 1101000 ÷ 1011 1101 1011 ---- 0110 (bring down next bit: 0110 0) 01100 1011 ---- 0111 (bring down next bit: 0111 0... continue) ``` Working through the full division of `1101000` by `1011` yields remainder R = 100. Step 3 — transmitted frame $T$ = message + remainder = 1101 100 (7 bits). Step 4 — receiver check: divide `1101100` by `1011`. Because $T(x)$ was constructed to be exactly divisible by $G(x)$, this division yields remainder 000, so the frame is accepted. Step 5 — inject a single-bit error: suppose bit 3 flips, giving received frame 1111100. Dividing `1111100` by `1011` now yields a nonzero remainder (the error polynomial $E(x)=x^4$ is not a multiple of the degree-3 generator, since it is a single nonzero term against a generator with three terms), so the receiver correctly flags corruption and discards or requests retransmission of the frame.

Ethernet and Wi-Fi append a 32-bit CRC (the Frame Check Sequence) to every frame, computed and checked in hardware at line rate — the topic that this discussion of framing directly sets up, since a frame is only as reliable as its error-detection field, explored further in Ethernet and the Frame Format. TCP, UDP, and IP carry the 16-bit Internet checksum in every header and (for UDP/TCP) over the payload, a lightweight end-to-end sanity check layered on top of link-layer CRCs. RAID arrays and ECC (error-correcting code) RAM use parity and Hamming-style codes to survive disk or memory-cell failures without data loss, silently correcting single-bit memory errors that occur constantly at scale in data centers. Storage media — CDs, DVDs, Blu-ray, SSD flash controllers, and QR codes — rely on Reed–Solomon codes to survive scratches, dust, and flash-cell wear. Deep-space communication, from the Voyager probes to modern Mars rovers, depends on powerful FEC (concatenated Reed–Solomon/convolutional codes, and now LDPC and turbo codes) because a retransmission request can take hours to reach a probe billions of kilometers away, making forward correction the only economical option. Anywhere data must survive a noisy channel or storage medium without a cheap opportunity to ask "please resend," some descendant of parity, CRC, or Hamming coding is quietly at work.

Ask the tutor: How does a router recompute an IP checksum incrementally when it only changes the TTL field, without rescanning the whole header?