# Q2(b)(ii) · CRC encoder and decoder

Subject: Computer Networks

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/cn/#tee/papers/paper-2022-ai-final/q2bii

Canonical: https://deep-learning-study-room.vercel.app/read/cn/tee/papers/paper-2022-ai-final--q2bii/

Exact historical variant. Current-syllabus questions solved; excluded topics and source limitations stated.

### Q2(b)(ii). Explain the principle and working of cyclic redundancy check with a neat encoder and decoder diagram. [6 marks]

### Answer

A **Cyclic Redundancy Check (CRC)** treats a binary message as a polynomial over GF(2). Addition and subtraction are XOR: 0⊕0=0, 1⊕0=1, 0⊕1=1, 1⊕1=0. There are no carries or borrows. A degree-r generator contains r+1 bits, with leading and constant coefficients 1.



$$
T(x)=x^rM(x)\oplus R(x),\quad R(x)=x^rM(x)\bmod G(x)
$$



1. Convert each polynomial coefficient into a bit, including zero coefficients for missing powers.
2. Append r zero bits to the message, because multiplying by x^r shifts it left r places.
3. Align the generator’s leading 1 with the current leading 1; XOR and repeat until fewer than r+1 significant bits remain. Pad the remainder to exactly r bits.
4. Replace the appended zeros with the remainder. The resulting transmitted frame is divisible by the generator.
5. The receiver divides the entire received frame by the same generator without appending more zeros. A nonzero remainder proves a detected error. Zero means no error detected; a nonzero error polynomial divisible by the generator can pass.

Swipe across the diagram to read its labels ↔

![CRC sender and receiver](https://deep-learning-study-room.vercel.app/cn/fig/tee-crc.24705171b3.svg)

Diagram: CRC sender and receiver. Labels: CRC sender and receiver | CRC sender and receiver | Message M and degree-r generator G | Write every coefficient, append r zeros to the message. | Sender: XOR long division | Divide the augmented message by G. Keep an r-bit remainder R. | Transmit message followed by remainder | T = shifted message XOR R. The full frame is divisible by G. | Receiver: divide the received complete frame | Nonzero remainder detects corruption. Zero means no detected error; some error patterns can pass.

Sender appends remainder; receiver checks divisibility.

A degree-r generator with nonzero constant term detects every burst of length at most r. Generators containing factor (x+1) detect every odd number of bit errors. Longer-error guarantees depend on the polynomial and frame length; CRC is not a general correction method.

#### Practical example

Generator 1101 has degree 3, so append three zeros, not four. A 3-bit remainder such as 001 must keep its leading zeros.

**Yaad rakho:** CRC mein subtract bhi XOR; receiver par full frame divide.

|  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| **Data + r zero bits** | → | **Modulo-2 divide by generator** | → | **Append r-bit remainder** | → | **Receiver divides full codeword** | → | **Zero remainder: no detected error** |