Error Detection & Control

🧭

On this page — click any heading below to jump straight to it. ⬅️ Back to P-II.II. Computer Communications & Networks

---

OSI Layer: Data Link Layer (L2)

Definition

Error detection and control covers techniques (mainly at the Data Link layer, though checksums also appear at Transport/Network layers) used to detect — and in some schemes correct — errors introduced during transmission due to noise, interference, or attenuation on the physical medium.

Error Detection vs Error Correction

• Error detection — flags that something went wrong (a bit or bits changed); the receiver cannot fix it, so the corrupted unit is simply discarded and a retransmission is requested (typically via ARQ).
• Error correction (Forward Error Correction, FEC) — the receiver can identify and fix the error itself, without needing a retransmission — essential for one-way or high-latency links (e.g., deep-space communication) where asking for a resend is impractical.

Types of Error Detection/Correction Techniques

1. Parity Check

• Adds a single parity bit to a block of data, chosen to make the total count of 1s even (even parity) or odd (odd parity).
• Simple/single parity: detects any odd number of bit errors (1, 3, 5, …) but fails silently if an even number of bits flip, since the count of 1s returns to the expected parity.
• Two-dimensional parity — data arranged as a grid with a parity bit for every row and every column; can detect (and even correct) a single-bit error by locating the exact row/column whose parity fails, at the cost of more overhead bits.
• Cheap but weak — rarely sufficient alone in modern high-speed networks.

2. Checksum

• The sender divides data into fixed-size segments, adds them together (with end-around carry), and sends the complement of the sum as the checksum.
• The receiver repeats the same sum including the checksum field; if the result is not all 1s (all zeros after complementing), an error is flagged.
• Used at the Transport and Network layers (e.g., the IP header checksum, TCP/UDP checksum) rather than the Data Link layer.
• Detects most, but not all, error patterns — weaker than CRC for burst errors.

3. Cyclic Redundancy Check (CRC)

• Treats the data as a binary polynomial, divides it by a fixed, pre-agreed generator polynomial using modulo-2 (XOR) arithmetic, and appends the remainder as the Frame Check Sequence (FCS).
• The receiver performs the same division on the received frame (data + FCS); a zero remainder confirms no detected error.
• Extremely effective at detecting burst errors (a common real-world noise pattern) — far stronger than simple parity or checksum — which is why it is the standard for Ethernet frames (CRC-32) and most link-layer protocols.
• Detects, but does not correct — a failed CRC check simply causes the frame to be silently dropped.

4. Hamming Code (Forward Error Correction)

• Adds multiple redundant parity bits at specifically calculated positions (powers of 2: positions 1, 2, 4, 8, …) within the codeword, each covering a different, overlapping subset of data bits.
• On receipt, the parity bits are recomputed to form a binary syndrome, whose value directly points to the exact bit position that is in error (0 = no error) — enabling correction without retransmission.
• Standard Hamming(7,4) code: 4 data bits + 3 parity bits = 7-bit codeword, able to correct any single-bit error (but not detect all double-bit errors reliably).

Worked Example — CRC

Data (message) = 1101011011, Generator polynomial = 10011 (degree 4, so 4 zeros are appended).

1. Append 4 zeros: 11010110110000
2. Divide by 10011 using modulo-2 (XOR) division; the remainder obtained is 1110.
3. Transmitted frame = original data + remainder = 11010110111110.
4. Verification: the receiver divides the full received frame 11010110111110 by the same generator 10011 — the remainder comes out as 0000, meaning no error was detected (some error patterns can remain undetected).

Worked Example — Hamming(7,4)

Encode data bits 1011 (d1 d2 d3 d4) into a 7-bit Hamming codeword, with parity bits at positions 1, 2, and 4:

• Data placed at positions 3, 5, 6, 7 → position 3 = 1, position 5 = 0, position 6 = 1, position 7 = 1
• p1 (checks positions 1,3,5,7) = 1 ⊕ 0 ⊕ 1 = 0
• p2 (checks positions 2,3,6,7) = 1 ⊕ 1 ⊕ 1 = 1
• p4 (checks positions 4,5,6,7) = 0 ⊕ 1 ⊕ 1 = 0
• Encoded 7-bit codeword (positions 1–7): 0 1 1 0 0 1 1

Error correction in action: suppose the bit at position 5 flips in transit, so the received codeword is 0 1 1 0 1 1 1.

• Recomputing the parity checks gives syndrome bits c1 = 1, c2 = 0, c4 = 1.
• Reading c4 c2 c1 as a binary number: 101 = 5 — the syndrome directly identifies position 5 as the error location, which the receiver then flips back to correct it, with no retransmission needed.

Comparison Table

CSS Exam Angle

• Be ready for a numeric CRC or Hamming code worked example — practice the exact style shown above, since examiners often ask for a step-by-step demonstration rather than just a definition.
• Structure the answer around the detection vs correction distinction first — it immediately frames why Hamming code exists alongside CRC rather than replacing it.
• CRC's strength against burst errors (vs parity's weakness against even-numbered flips) is the key comparative fact examiners look for.

Example

Ethernet frames append a CRC-32 checksum in their trailer; if a receiving NIC recomputes a different CRC value than what was sent, the frame is silently dropped and higher layers (e.g., TCP) request retransmission — a direct real-world instance of detection without correction at the link layer.

Likely Questions

1. Explain different error detection techniques used in data communication, with a worked example of CRC.
2. What is Forward Error Correction? Demonstrate Hamming code's single-bit error correction with an example.
3. Why is CRC preferred over simple parity checking for detecting burst errors?
4. Differentiate error detection from error correction with one technique representing each.

📜 Past-Paper Questions & Structured Answers

Questions are paraphrased; answer focus is suggested guidance, not an official marking scheme.

2019 · Paper-II · Q3(c) · 6 marks

Question (paraphrased): Demonstrate CRC for data 1001001 using a chosen generator.

Answer focus: State the generator, show XOR division, append the remainder and verify.

Assumption: choose G = 1011, representing x³+x+1. It has degree 3, so append three zeros to data 1001001: 1001001000.

Modulo-2 division: XOR means subtraction without borrowing.

1001001000 XOR 1011000000 = 0010001000
0010001000 XOR 0010110000 = 0000111000
0000111000 XOR 0000101100 = 0000010100
0000010100 XOR 0000010110 = 0000000010

The final three bits are 010. Transmit data + remainder = 1001001010.

Receiver check: dividing 1001001010 by 1011 produces remainder 000; therefore no error is detected. If, for example, the final bit flips, the received word is 1001001011 and the remainder is 001, so the receiver detects an error.

Limit: a zero remainder means no detected error, not proof that every possible error is absent. CRC detects errors; retransmission or another mechanism performs recovery.