2.3CRC (cyclic redundancy check)
The idea
A CRC treats the message as a polynomial and divides by a generator using XOR. The remainder is sent along with the message; the receiver divides again and expects a zero remainder.
Think of it like this: Long division with no carries: you keep only the leftover, and anyone can check by redoing the division.
Why it exists
CRC computation is a guaranteed 2-mark question type: it is purely mechanical once you know the steps.
How it works
- Write the generator as bits, for example x³ + x + 1 is 1011 (degree 3, 4 bits).
- Append 3 zeros to the message (degree many zeros).
- Slide along: wherever the leading bit is 1, XOR the generator in.
- The last 3 bits are the CRC; transmit message + CRC.
Worked example: Message 01011011, generator x³ + x + 1.
Divide 01011011000 by 1011: the remainder is 101, so the sent frame is 01011011101 (GATE 2017).
Now play with it
- →Click a bit of the frame to corrupt it and watch the receiver remainder become non-zero.
- →Try a generator where the error pattern is a multiple of the generator: the error slips through.
Generator polynomial: x^4 + x + 1 (degree 4, so 4 check bits). Append 4 zeros to the message, then XOR the generator in wherever the leading bit is 1.
Check yourself
A generator polynomial of degree 4 adds how many check bits?
Exam notes (the dense version)
Treat the message as a polynomial over GF(2). For a generator of degree r (r + 1 bits), append r zeros, divide by the generator using XOR, and the remainder is the CRC appended to the message. The receiver divides the whole frame; remainder zero means accepted. A CRC with generator degree r detects all burst errors of length ≤ r and every odd number of errors if (x + 1) divides the generator. Ethernet uses CRC-32.
Previous year questions: Framing & Error Control (2)
PYQs are grouped by topic, so this is the full set for Framing & Error Control; try the ones that match this subtopic. Open all 2 on the topic page.