Error Detection Techniques
Bits travel as voltage pulses, light flashes or radio waves, and none of these carriers is perfect. A little noise can turn a 0 into a 1 somewhere along a cable, and a single frame may arrive with a few bits wrong. A receiver that accepts damaged data without noticing will pass wrong values up the stack, which can mean a corrupted bank transfer, a garbled web page or a crashed program. The data link layer, which moves frames between directly connected devices, is the first place where this can be caught. Its job here is to attach a small amount of extra information to each frame so the receiver can tell whether the bits it got are the bits that were sent.
The extra information is called redundancy: bits added to the data that depend on the data in a predictable way. The receiver recomputes the same calculation over what arrived and compares the result with the redundant bits. A match suggests the frame is intact, and a mismatch proves something went wrong. Notice what this does and does not do. It detects that an error happened. It does not say which bit flipped, so the receiver's usual response is to discard the frame. Recovery then falls to a higher layer or to a retransmission scheme, which is why reliable delivery in the transport layer depends on error detection below it.
Detection codes fall into a few families, and they trade simplicity against strength. The simplest add a single check bit. Stronger ones compute a short summary of the whole frame. Stronger still treat the frame as a large binary number and perform a division on it. Every technique in this family accepts a small chance of missing an error in exchange for a tiny amount of overhead, and the real question is which errors are likely and how much protection you can afford. That trade-off is what the two sections below explore.
Parity Bits and Internet Checksum
The simplest way to detect a flipped bit is to count. A parity bit is one extra bit added so that the total number of 1s in a block is always even (even parity) or always odd (odd parity). Suppose you send the byte 1011001, which has four 1s. Even parity appends a 0 so the count stays even. If one bit flips in transit, the receiver counts an odd number of 1s and knows something broke. The idea is that a single flip changes the count's parity, and the receiver just checks whether that parity still holds.
Parity has an obvious blind spot. If two bits flip, the count of 1s changes by two, and the parity looks correct again. A burst of errors that flips an even number of bits goes straight through. So a single parity bit is useful only when errors are rare and isolated. Arranging the data in rows and columns with a parity bit on each row and each column, called two-dimensional parity, catches more patterns and can even locate a single flipped bit, but it still misses many multi-bit combinations.
The Internet checksum takes a different route. Instead of counting bits, the sender splits the data into 16-bit words, adds them together using ones' complement arithmetic (where carries wrap back around into the low bit), and transmits the complement of that sum. The receiver adds everything again, including the checksum, and expects to get a value of all 1s. Because it is a sum, it is cheap to compute in software and is the reason it appears in the headers of IP, TCP and UDP, which are covered at the network and transport layers. Its weakness is that it can miss errors that cancel out in addition, such as two bit errors that offset each other in the same column of the sum, and it is weaker than CRC at catching bursts of errors.
Cyclic Redundancy Check
A cyclic redundancy check, or CRC, handles the errors that counting and summing miss. Instead of a few bits of arithmetic, it treats the whole frame as a long binary number and divides it by a fixed agreed pattern called the generator. The division uses XOR in place of ordinary subtraction, which means no borrowing and no carrying. The remainder left over after dividing is appended to the frame as the check sequence. Both sides know the generator in advance, so the receiver can repeat the division on the whole received frame, including the check bits, and get a remainder of zero if nothing changed.
Intuitively, the remainder works like a fingerprint that is sensitive to the position of every bit. A single flipped bit changes the remainder. Two flipped bits in different places change it too, unless the generator happens to divide the difference exactly, and good generators are chosen so that this seldom or never happens for the error patterns that occur in practice. The most important guarantee is about bursts: a CRC with a generator of a given length detects every burst of consecutive errors no longer than that length. An error burst is a run of bits that is damaged together, typically from a short noise spike, and real links produce bursts far more often than scattered single flips.
CRC is not magic, and it does not guarantee detection of every possible error. Some long error patterns can align with the generator and produce a remainder of zero, so the receiver accepts a corrupted frame. The chance of this is very small for a well-chosen generator, which is why CRC is the standard in practice. Ethernet, covered in its own section, appends a 32-bit CRC to every frame, and the receiver silently discards any frame whose check fails. Framing, the topic that defines where each frame starts and ends, matters here because the receiver must know exactly which bits belong to the frame before it can run the division.
AI-generated study article from SophistAI. Sign up free to study it with an AI tutor.