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

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.

LaTeX: 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 ↔

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.

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.