8.12 Error Detection through Redundancy

Error detection through redundancy is the practice of appending or embedding extra information to a transmitted message—information that is not part of the original data content but is calculated from it—so that the receiver can determine whether the received message matches the transmitted message by checking whether the redundant information is consistent with the received data. If the check passes, no error has been detected; if the check fails, at least one error has occurred during transmission. Error detection does not by itself identify which bits were corrupted or repair them; it only signals that corruption has taken place, after which the receiver can request retransmission (using an automatic repeat request protocol) or discard the corrupted data. The power of error detection through redundancy lies in its ability to make the presence of errors visible to the receiver, transforming the problem from silent corruption to detectable failure.

The fundamental mechanism of error detection through redundancy is the parity check. A simple even parity bit is appended to a block of n − 1 data bits to make the total number of 1s in the n-bit codeword even:

where ⊕ denotes XOR (addition modulo 2). At the receiver, the same XOR of all n received bits (data plus parity) is computed; if the result is 0, the parity check passes; if it is 1, an error has been detected. A single parity bit detects all odd-numbered errors in the block (1, 3, 5, ... errors) but fails to detect even-numbered errors: two bit errors can cancel each other's effect on the parity, leaving the check passing on corrupted data. This fundamental limitation of single-bit parity—undetected double-error rates—motivates the use of more powerful detection codes for applications where double errors are not negligible.

Cyclic Redundancy Check (CRC) codes are among the most widely used and powerful error detection codes in practice. A CRC appends a multi-bit checksum to the message, computed by treating the message as a polynomial over a binary field and dividing it by a fixed generator polynomial, keeping the remainder. For a message polynomial M(x) of degree m and a generator polynomial G(x) of degree r, the transmitted polynomial is:

where R(x) is the remainder of x^r M(x) divided by G(x). The receiver divides the received polynomial by G(x); if the remainder is zero, no error has been detected. The choice of generator polynomial determines the detection capability: well-chosen CRC polynomials can detect all single-bit errors, all double-bit errors, all odd numbers of errors, and all burst errors of length ≤ r. The CRC-32 polynomial used in Ethernet, ZIP, and many other standards can detect all single-bit errors, all burst errors of 32 bits or fewer, and 99.9999998% of longer burst errors, making it extremely effective in practice.

Checksum methods compute an arithmetic sum of groups of bytes or words in the message, appending the sum (or its complement) as a redundancy field. The Internet Checksum used in IP, TCP, and UDP headers is a 16-bit ones-complement sum of all 16-bit words in the header, stored in the checksum field with the checksum itself set to zero during computation. The receiver computes the same sum including the checksum field and checks that the result is all ones; if not, the datagram contains an error. The Internet Checksum is computationally efficient (simple addition) but provides weaker error detection than CRC: it fails to detect any transposition of adjacent 16-bit words, and provides limited protection against burst errors that affect multiple words.

Hash functions serve an error detection role when the sender and receiver compare hash values of the message rather than transmitting an algebraic redundancy field. Cryptographic hash functions like SHA-256 produce a fixed-length digest from an arbitrary-length message with the property that even a single bit change in the message produces a completely different digest (the avalanche effect). When a file is transferred over a network, the sender can separately communicate the SHA-256 hash of the file; the receiver computes the hash of the received file and compares it to the expected value. If the hashes match, the probability that the file was corrupted without the hash changing is astronomically small (2^{-256} for SHA-256). This hash-based integrity checking is widely used in software distribution, version control systems, and data storage systems to detect accidental corruption or deliberate tampering.

In human communication, error detection through redundancy operates through confirmation protocols and consistency checks. Reading back a verbal number or address to the sender—"You said 14723 Elm Street, correct?"—is a behavioral CRC: the receiver's repetition provides the sender with a means to check whether the received message matches the sent one. Spelling alphabets that translate each letter into an unambiguous spoken word (Alpha, Bravo, Charlie) add phonetic redundancy that makes individual letter errors detectable as inconsistencies between the spelled word and the context of the communication. Double-entry bookkeeping in accounting is a form of structural error detection through redundancy: every transaction is recorded twice, once as a debit and once as a credit, and the requirement that total debits equal total credits at all times acts as a continuous parity check that detects any recording error that breaks the balance—because any single recording error will cause the books to fail to balance, signaling that a transmission error has occurred in the accounting record.

The distinguishing limitation of error detection through redundancy is that detection is not correction: detecting that an error has occurred does not by itself produce the corrected message. The receiver knows that the received data is wrong but not which bits are wrong or what the correct values should be. In systems where retransmission is practical (most data communication networks), this is entirely acceptable: the receiver discards the corrupted data and sends a retransmission request, the sender retransmits, and with high probability the retransmitted copy arrives without error. In systems where retransmission is impractical—one-way broadcast communication, deep-space communication where round-trip times are hours, real-time systems where retransmission latency is unacceptable—error detection must be supplemented with or replaced by error correction coding, which adds enough redundancy to allow the receiver to recover the correct message from the corrupted one without requesting retransmission.