Computer Networking › Section F · The link layer and LANs › Topic F.2

Error detection and correction

Noise can flip bits inside a frame, and the receiver must notice. Three tools, parity, the Internet checksum and the cyclic redundancy check, trade extra bits and effort for ever stronger protection.

Redundancy catches damaged frames

The sender computes extra bits from the data and sends them along; the receiver repeats the calculation and compares. This is error detection. It is never perfect, because some corrupted frames still produce matching check bits, so the aim is to make that outcome extremely rare at a modest cost in bits and processing. The Computer Science topic Detecting and correcting communication errors introduces parity, Hamming distance and Hamming codes, which are not repeated here. This topic adds the two-dimensional parity grid, the Internet checksum and the CRC used by Ethernet.

Two-dimensional parity

A single parity bit catches any odd number of flipped bits but cannot say which bit flipped. Arrange the data bits in a grid and give every row and every column its own even-parity bit, plus a corner bit that is the parity of the row-parity bits. One flipped bit then makes exactly one row and one column fail, and their crossing is the culprit, so the receiver can flip it back. That is error correction, with no retransmission. If two bits flip, the receiver still sees failed checks and detects the damage, but it cannot always tell which bits to repair.

Worked example: a parity grid

Send the data rows 10110, 01101 and 11000 with even parity. 1. The rows hold 3, 3 and 2 ones, so the row-parity bits are 1, 1 and 0. 2. The five columns hold 2, 2, 2, 1 and 1 ones, so the column-parity bits are 0, 0, 0, 1 and 1. 3. The corner is the parity of 1, 1, 0, which is 0. The sent rows are 101101, 011011, 110000 and 000110. 4. Noise flips the third data bit of the second row, which arrives as 010011. That row now has two ones in its data bits but a parity bit of 1, so it fails. Column three now has one 1 but a parity bit of 0, so it fails too. 5. The crossing is row 2, column 3: flip it back.

The Internet checksum

IP, UDP and TCP use a cheap check that suits software. The data is read as 16-bit words. The sender adds them with one's complement arithmetic, which means any carry out of the top bit is wrapped round and added back at the bottom, and then inverts every bit of the sum; the result is the checksum. The receiver adds all the words, checksum included, and an undamaged message gives sixteen 1s. The IPv4 checksum covers only the header and must be recomputed at each router because the time-to-live changes, whereas TCP and UDP cover their whole segment. RFC 1071 describes the method.

Worked example: computing a checksum

Take the words 0x1A2B, 0xF0F0 and 0x8C4D. 1. Add the first two: 0x1A2B + 0xF0F0 = 0x10B1B. The extra leading 1 is a carry, so wrap it: 0x0B1B + 1 = 0x0B1C. 2. Add the third: 0x0B1C + 0x8C4D = 0x9769. 3. Invert all 16 bits: the checksum is 0x6896. 4. The receiver adds 0x9769 and 0x6896 and gets 0xFFFF, so the message passes. 5. If the bit worth 4 in the first word flips, the receiver's total is 0x0004, so the damage is detected. 6. But swapping the first two words still gives 0xFFFF, so reordering goes unnoticed. Compensating changes, such as adding 1 to one word and subtracting 1 from another, also slip through.

Cyclic redundancy check

Link layers use a stronger check, the CRC. Treat the data \(D\) as a binary number and agree on a generator \(G\) of \(r+1\) bits that starts with 1. The sender picks \(r\) check bits \(R\) so that \(D\) followed by \(R\) divides exactly by \(G\) in modulo-2 arithmetic, where addition and subtraction are both XOR and nothing carries. To find \(R\), append \(r\) zeros to \(D\), divide by \(G\) and keep the remainder. The receiver divides what arrived by \(G\), and a non-zero remainder means the frame is damaged. Engineers write \(G\) as a polynomial: 1101 stands for \(x^3 + x^2 + 1\).

Worked example: a CRC by long division

Let \(D = 1001101\) and \(G = 1101\), so \(r = 3\). 1. Append three zeros: 1001101000. 2. Wherever the leading bit of the current window is 1, XOR \(G\) into it. Starting at the first bit gives 0100101000. 3. Repeating at each later 1 gives 0010001000, then 0001011000, then 0000110000, then 0000000100. 4. The last three bits are the remainder, \(R = 100\), so the frame carries 1001101100. 5. The receiver divides 1001101100 by 1101 and gets remainder 000, so it accepts. 6. If the third bit flips, giving 1011101100, the remainder is 001, so the error is detected.

What a CRC guarantees

With \(r\) check bits, a CRC detects every burst of errors no longer than \(r\) bits. A burst of exactly \(r+1\) bits escapes with probability \(2^{-(r-1)}\), and longer bursts escape with probability \(2^{-r}\). In the worked example \(r = 3\), and checking all 28 four-bit bursts across the 10-bit frame (first and last bits wrong, the middle two arbitrary) finds 7 that pass, which is 1 in 4. If \(G\) has \(x+1\) as a factor, every odd number of flipped bits is caught as well. Ethernet's 32-bit CRC lets only about 1 in \(2^{32}\) badly garbled frames through, and Python's zlib.crc32 uses the same generator polynomial. A frame that fails the check is simply dropped.

Why check at two layers?

The CRC protects one hop and is computed fast in hardware. The Internet checksum protects the datagram from end to end in software. Both are worth having because a router can corrupt a datagram in its own memory after the incoming CRC passed; the outgoing link then computes a fresh, valid CRC over the damaged bytes. Only the end-to-end checksum can catch that. Some links also have no strong check of their own.

Correcting without resending

Forward error correction adds enough redundancy for the receiver to repair errors itself. It pays off when resending is slow or impossible, as with deep-space probes, broadcasts to many receivers and real-time calls. Reed-Solomon codes protect CDs, QR codes and DSL lines, and LDPC and polar codes are used on 5G radio links, with LDPC also appearing in modern Wi-Fi.

Common mistakes to avoid

First, thinking a passed check proves the data is correct; it only means no detectable error occurred. Second, forgetting to wrap the carry when adding checksum words, or forgetting the final inversion. Third, using ordinary subtraction in a CRC: modulo-2 division is XOR with no borrows. Fourth, dividing \(D\) without appending \(r\) zeros first. Fifth, expecting the Internet checksum to catch reordered words.

Key takeaways

Error detection adds redundant bits that the receiver recomputes. Two-dimensional parity locates and corrects one flipped bit and detects two. The Internet checksum is the inverted one's complement sum of 16-bit words: cheap, but blind to reordering and compensating changes. A CRC divides the data, followed by \(r\) zeros, by a generator using XOR; the remainder is appended, and a zero remainder at the receiver means the frame passes. A CRC catches every burst of up to \(r\) bits. Link CRCs and end-to-end checksums complement each other, and forward error correction repairs errors without resending.

Flashcards

Flashcard

Error detection

Extra bits computed from the data and rechecked by the receiver

Never perfect, but rarely fooled.

Test your understanding

Question 1 of 5

In a 2D even-parity grid, the receiver finds that only row 4 and only column 2 fail their parity checks. What should it conclude?

Question 2 of 5

What is the Internet checksum of the two 16-bit words 0xB1C4 and 0x7E3A?

Question 3 of 5

A sender uses CRC generator G = 1011 (r = 3) on data D = 110101. What check bits R does it append?

Question 4 of 5

A router swaps two 16-bit words of a datagram it is forwarding. What does the Internet checksum do?

Question 5 of 5

A CRC uses a generator of 17 bits (r = 16). Which errors is it guaranteed to detect?

← Previous topicNext topic →