Medium ●●

🧮 Framing & Error Control

Why it matters: CRC, Hamming and checksum calculations are mechanical and appear regularly. Know the procedures cold.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 4 done.

Formulas

Bit stuffing
insert a 0 after every 5 consecutive 1s in the data
CRC frame length
message + r bits, r = degree of the generator
Hamming distance d
detect d − 1, correct ⌊(d − 1)/2⌋ errors
Hamming check bits
2^r ≥ m + r + 1
12-bit Hamming (8 data bits)
r = 4, check bits at positions 1, 2, 4, 8
Internet checksum
~(sum of 16-bit words with end-around carry)

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Compute the CRC for a message and generator
Long XOR division; match the polynomial (x³ + x + 1 = 1011) before dividing.
★★★
Hamming codeword: find a missing data or check bit
Use even or odd parity over the covered positions.
★★★
Error detection capability / distance
d − 1 detected, (d − 1)/2 corrected; checksum and parity limits.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

2 real questions from the official GATE CSE papers (2017 to 2021), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

2 questions · 0 correct of 0 attempted · marks 0 / 4

Year:
GATE 2021 Set 1 · Q29MCQ2 marks
Assume that a 12-bit Hamming codeword consisting of 8-bit data and 4 check bits is d8d7d6d5c8d4d3d2c4d1c2c1, where the data bits and the check bits are given in the following tables. Data bits: d8 = 1, d7 = 1, d6 = 0, d5 = x, d4 = 0, d3 = 1, d2 = 0, d1 = 1. Check bits: c8 = y, c4 = 0, c2 = 1, c1 = 0. Which one of the following choices gives the correct values of x and y?
GATE 2017 Set 1 · Q32MCQ2 marks
A computer network uses polynomials over GF(2) for error checking with 8 bits as information bits and uses x3 + x + 1 as the generator polynomial to generate the check bits. In this network, the message 01011011 is transmitted as

Common traps

The generator x³ + x + 1 has 4 bits (1011) but only 3 check bits.
Do not append the generator; append zeros, divide, then append the remainder.
In Hamming codes the parity bits are interleaved at powers of two, not at the end.
Stuffed bits count towards the frame length.