Data Link Layer Error Control in Computer Networks: Concepts, CRC, Hamming and Worked Examples

Many students can repeat CRC division but freeze when asked what errors it detects, or why a checksum is not enough. Error control then feels like a bag of unrelated tricks. It is really one idea at four price points: add redundancy to a frame, then decide whether the receiver only spots the damage or repairs it. Parity, CRC, Hamming code and the Internet checksum each buy a different amount of that protection, and each rewards being worked on paper, the way GATE CS exam preparation tests them.

What error control means at the data link layer

The physical layer provides a raw bit pipe. The data link layer turns those bits into trustworthy frames. Noise, attenuation and crosstalk can flip bits, so error control makes the receiver detect, and sometimes correct, those changes.

Do not confuse it with flow control. Error control obtains a correct frame. Flow control stops the sender from overwhelming the receiver.

A single-bit error changes exactly one bit. A burst error changes two or more bits within a span, although every bit inside that span need not be wrong. If 0100 0010 becomes 0000 0110, positions 2 and 6 from the left have flipped. The burst length is therefore 6 - 2 + 1 = 5.

Recovery takes two forms. ARQ detects an error and requests another copy. Forward error correction, or FEC, adds enough redundancy to repair the data without a resend. Correction costs more bits, so ARQ suits links where resending is cheap and errors are uncommon.

Parity and two-dimensional parity

A parity bit makes the count of 1s even or odd. With even parity, 1011001 has four 1s, so append 0 to send 10110010. It catches any odd number of flips but misses every even number.

Two-dimensional parity arranges data in rows and adds even parity for every row and column:

The bottom-right cell checks both parity lines: the row-parity column 1, 0, 0 and the column-parity row 0, 1, 0, 0 each carry a single 1, so it is 1 either way. One flipped data bit then creates one bad row and one bad column, and their intersection identifies the bit for correction. Two flips are detected, but four flips at a rectangle's corners can leave every parity even.

CRC error detection, fully worked

A cyclic redundancy check treats bits as a polynomial. For a generator G of degree r, append r zeros, divide by G using modulo-2 XOR, and replace the zeros with the remainder. The receiver repeats the division. A zero remainder means no error was detected.

Take data D = 1101011011 and generator G = 10011, which represents x^4 + x + 1. Its degree is 4, so pad the data to get 11010110110000. The opening long-division operations are:

1. 11010 XOR 10011 = 01001

2. Drop the leading zero and bring down the next bit: 10011 XOR 10011 = 00000

3. Bring down bits until the next leading 1: 10110 XOR 10011 = 00101

4. Bring down the next two bits: 10100 XOR 10011 = 00111

The final zero comes down to give 01110, whose leading zero leaves nothing to XOR, so the remainder is 1110. The transmitted frame is therefore 1101011011 1110, or 11010110111110. Dividing that entire frame by 10011 produces remainder 0000, so the receiver accepts it.

A degree-r generator detects every burst of length at most r. A generator with more than one non-zero term catches every single-bit error, and the factor x + 1 catches every odd count of errors. Ethernet therefore uses CRC, not one parity bit, for frame checking.

Hamming code and single-bit correction

Hamming distance counts positions where codewords differ. 10110 and 11011 differ at positions 2, 3 and 5, so their distance is 3. To detect up to s errors you need d_min >= s + 1; to correct up to t errors you need d_min >= 2t + 1. Thus d_min = 3 corrects one error, or detects two if correction is not attempted.

Encode 1011 as a (7,4) Hamming code with even parity. Parity bits occupy positions 1, 2 and 4; data uses 3, 5, 6 and 7.

• p1 covers 1, 3, 5, 7, so p1 = 0.

• p2 covers 2, 3, 6, 7, so p2 = 1.

• p4 covers 4, 5, 6, 7, so p4 = 0.

The codeword is 0110011. If position 5 flips, the receiver gets 0110111. Rechecking gives c1 = 1, c2 = 0, and c4 = 1. Read as c4 c2 c1, syndrome 101 equals position 5. Flip it to recover the codeword without retransmission.

This code assumes at most one error. With two errors, a non-zero syndrome can point to a third position, causing a wrong correction.

Checksum and where each method belongs

The Internet checksum adds fixed-size words using ones-complement addition with end-around carry, then complements the result. The receiver adds the words and checksum. All ones means no error was detected.

For 10011001 and 11100010, addition gives 1 01111011. Wrap the carry: 01111011 + 1 = 01111100. Its complement is checksum 10000011. Adding both words and the checksum, with carry wrapped, gives 11111111, so accept.

Parity and CRC are data-link detection tools. The checksum is tested beside them, but it belongs to upper-layer headers: IPv4 checksums only its own header, while TCP and UDP cover the header and the payload. A frame can therefore pass its CRC on every hop and still arrive corrupt, since a link check protects one hop at a time, not the router memory in between.

ARQ and retransmission

When a frame is corrupt or missing, automatic repeat request provides another copy. Stop-and-Wait sends one frame and waits for its acknowledgement. Go-Back-N allows a window of outstanding frames, then resends from a damaged or timed-out frame onward. Selective Repeat buffers good frames and resends only the specific missing or damaged one.

Sliding-window protocols can provide error control and flow control together, but the two goals stay separate: a correct copy versus a safe sending rate. Sliding Window Protocols for GATE works the utilization arithmetic and the sequence-number bounds for all three.

Common GATE and interview traps

Four mistakes account for many wrong solutions:

• CRC padding: dividing the original data instead of appending r zeros gives the wrong remainder. Pad by the generator degree first.

• Hamming positions: an off-by-one error changes the syndrome. Write p1: 1,3,5,7, p2: 2,3,6,7, and p4: 4,5,6,7 before calculating.

• Distance formulas: detection of s errors uses d_min >= s + 1; correction of t errors uses d_min >= 2t + 1. Learn them as a pair.

• Parity confidence: even parity does not guarantee detection of an even number of flips.

Numerical questions may ask for a CRC remainder such as 1110, the distance needed to correct t errors, or check bits for m data bits using 2^r >= m + r + 1. Interviews ask why CRC handles bursts better than a checksum, and why correction costs more than detection.

The official GATE CS syllabus lists framing and error detection under the Data Link Layer section of Computer Networks. Practise the calculation patterns through Computer Networks MCQs, then use the GATE Test Series to perform CRC and Hamming work under a clock.

The short version and your next step

When retransmission is cheap, detect and use ARQ: parity is the weakest guard, CRC handles bursts, and checksums protect upper-layer headers. When resending is costly or impossible, use FEC such as Hamming and pay for extra redundancy.

Next, place the data link layer beside routing and TCP or UDP so the layers stay distinct. For a structured sequence across the CS syllabus, use GATE Guidance by Sanchit Sir, then return to timed mocks until each bit calculation is reproducible.