Data Link Layer Error Control: Detection, Correction and ARQ with One End-to-End Example

Follow one frame through error detection, local correction and retransmission, with explicit CRC, ARQ timing and Hamming(7,4) calculations.

KnowledgeGate Team

Exam prep & CS education

Updated 11 Nov 20266 min read
Data Link Layer Error Control: Detection, Correction and ARQ with One End-to-End Example

Parity, checksum, CRC, Hamming code and ARQ are often memorised separately, so a mixed question can blur what detects, corrects and triggers retransmission. One frame moves from added redundancy across a noisy link to acceptance, local correction or retransmission. CS Fundamentals is the wider home for core Computer Networks notes. Use the stated assumptions to re-derive each number.

Error detection asks whether the received unit violates a redundancy rule. Forward error correction adds enough redundancy to identify and repair a bounded error pattern locally. Error recovery uses acknowledgements, sequence numbers, timers and retransmission after corruption or loss.

The chain is data bits, encoder, frame, noisy link and receiver check, followed by accept, correct or retry. Parity, checksum and CRC detect, Hamming-style codes can correct limited patterns, and ARQ closes recovery. A lost frame gives CRC no bits to inspect, so a timer is still needed. For separate parity, CRC, Hamming and checksum derivations, use Data Link Layer Error Control in Computer Networks. The chain here follows one rejected frame through ARQ and asks when Hamming correction avoids retransmission.

Parity, checksum, CRC, Hamming code and ARQ: roles and limits

Method

Redundancy or feedback

Receiver test

What it can do

What it cannot promise

Even parity

One parity bit

Number of 1s must be even

Detect every odd number of flips

Detect all even-numbered flips

Checksum

Fixed-width one's-complement sum

Data plus checksum should give all 1s

Detect many changed-bit patterns

Locate or repair the change

CRC

r remainder bits for a degree-r generator

Divide and inspect the remainder

Strong structured detection

Repair the corrupted bit

Hamming code

Parity at power-of-two positions

Read parity checks as a syndrome

Correct one-bit errors in Hamming(7,4)

Safely correct two-bit errors

ARQ

ACK or NAK, sequence numbers and timers

Track accepted, missing and timed-out frames

Recover by retransmitting

Detect changed data without a detector

For even parity, 1101101 has five 1 bits, so append 1 to send 11011011. If the third bit changes to give 11111011, the receiver counts seven 1 bits and rejects it. Flipping the third and sixth bits together gives 11111111, which is still even, so parity accepts a corrupted frame.

For a 4-bit checksum, the three words are 0110, 1011, and 0001. First, 0110 + 1011 = 10001. Wrap the carry to get 0010, then add 0001 to get 0011. Complement it for checksum 1100; the receiver gets 0011 + 1100 = 1111. Detection still does not repair data, and ARQ needs a trustworthy detector.

CRC gives the detection verdict for the worked frame

For a standalone treatment of this same 101101/1101 division, use Checksum and CRC Error Detection. Here the non-zero verdict feeds the ARQ timeline. Let data D = 101101 and generator G = 1101. The generator represents x^3 + x^2 + 1, so its degree is r = 3. Append three zeroes: 101101000. Modulo-2 division uses XOR, with no carry or borrow.

The sender trace, using zero-based generator alignments, is:

  1. Start with 101101000.

  2. XOR 1101 at position 0 to get 011001000.

  3. XOR at position 1 to get 000011000.

  4. XOR at position 4 to get 000000010.

The last three bits give R = 010, so transmit D || R = 101101010. Dividing it by 1101 gives 000, so it passes. Flip the third transmitted bit and the receiver sees 100101010, whose remainder is 110. The block is corrupt, but CRC alone does not identify the changed bit.

ARQ timing connects detection to acknowledgements and windows

For error-free window sizing and sequence-space rules, use Flow Control in the Data Link Layer. The model below instead measures the retransmission cost of a CRC rejection. Use this idealised link: L = 1,024 bits, R = 2.048 Mb/s, T_p = 4 ms one way, negligible ACK and NAK transmission time, modulo-8 sequence numbers and W = 4.

Frame transmission time is

T_t = 1,024 / (2.048 x 10^6) = 0.0005 s = 0.5 ms.

Thus a = T_p/T_t = 4/0.5 = 8. A no-error Stop-and-Wait cycle takes T_t + 2T_p = 0.5 + 8 = 8.5 ms, so utilisation is 0.5/8.5 = 1/17 = 5.88%. With four pipelined frames, the bound is min(1, W/(1+2a)) = 4/17 = 23.53%. Continuous filling needs at least 1 + 2a = 17 frames.

Frames 0, 1, 2 and 3 occupy sender intervals 0-0.5, 0.5-1.0, 1.0-1.5 and 1.5-2.0 ms. Their last bits arrive at 4.5, 5.0, 5.5 and 6.0 ms. At 5.0 ms, frame 1 produces CRC remainder 110, so the receiver rejects it and sends NAK 1. With the stated feedback assumption, that NAK reaches the sender at 9.0 ms.

Go-Back-N and Selective Repeat recover differently

In this textbook NAK model, Go-Back-N is waiting for frame 1, so it discards frames 2 and 3. At 9.0 ms, NAK 1 makes the sender repeat frames 1, 2 and 3: 3 x 1,024 = 3,072 bits, taking 3,072/(2.048 x 10^6) = 1.5 ms to serialize.

Selective Repeat buffers frames 2 and 3 and repeats only frame 1: 1,024 bits in 0.5 ms. With three sequence bits, Go-Back-N allows up to 2^3 - 1 = 7, while Selective Repeat allows at most 2^(3-1) = 4. Thus W = 4 is valid for both.

Selective Repeat saves 3,072 - 1,024 = 2,048 bits, but needs out-of-order buffering and per-frame state. Go-Back-N is simpler at the receiver but repeats correct frames after the gap.

Timeline of the four-frame window with frame 1 rejected at 5.0 ms, then Go-Back-N and Selective Repeat retransmissions.

Hamming correction changes the recovery decision

Use even-parity Hamming(7,4) with data 0110 in positions 3,5,6,7. The layout is [p1,p2,0,p4,1,1,0].

  • Group {1,3,5,7} gives p1 = 1.

  • Group {2,3,6,7} gives p2 = 1.

  • Group {4,5,6,7} gives p4 = 0.

The codeword is 1100110. Flip bit 5 to receive 1100010. The parity checks are s1 = 1, s2 = 0, s4 = 1, so syndrome s4s2s1 = 101 base 2 = 5. Flip position 5 back and extract data 0110. Three parity bits protect four data bits, giving code rate 4/7 = 57.14%.

This one-bit error is repaired locally, without feedback or replacement transmission. Ordinary Hamming(7,4) guarantees single-error correction, not safe double-error correction. SECDED adds an overall parity bit. FEC spends redundancy on every block; detection plus ARQ spends retransmission bandwidth when an error or loss occurs.

Hamming(7,4) codeword 1100110 received as 1100010, with syndrome 101 locating and correcting the flipped bit 5.

Error-control question patterns and cross-concept traps

Typical questions ask you to classify a method; compute parity, checksum or CRC bits; calculate utilisation; trace the two ARQ schemes; or decode a Hamming syndrome.

Remember these correction rules:

  • CRC division uses XOR. A zero remainder means the frame passes the test, not that it is certainly error-free.

  • A CRC remainder flags corruption but is not a bit-position syndrome.

  • Hamming correction cannot replace a timer for a lost frame.

  • ACK, NAK and sequence numbers do not detect changed data without a detector.

  • Go-Back-N repeats from the first missing frame. Selective Repeat repeats only the missing or corrupt frame.

Three checks catch the common numerical errors. Generator 1101 has degree 3, so append three zeroes and return three remainder bits. With a = 8, W = 4 gives 4/17 = 23.53%, not full utilisation. With three sequence bits, W = 4 is valid for both and exactly the Selective Repeat maximum.

Parity, checksum and CRC reveal changed bits. Hamming-style redundancy can repair a bounded pattern. ARQ uses feedback, numbering and timers to replace corrupt or missing frames. Windowing keeps data moving while feedback travels.

Reproduce the joined example once: CRC codeword 101101010 changes to 100101010 and produces remainder 110; frame 1 then causes 3,072 retransmitted bits with Go-Back-N but only 1,024 with Selective Repeat. The CRC verdict determines whether the receiver accepts, corrects or requests retransmission.

For a GATE-focused Computer Networks sequence, continue with GATE Guidance by Sanchit Sir.