Consider the message M = 1010001101. The Cyclic Redundancy Check (CRC)…

Concept.

A CRC treats bit strings as polynomials over GF(2). For a generator G(x) of degree n, the message M(x) is first multiplied by xn (equivalently, n zero bits are appended). The CRC is the remainder R(x) of the modulo-2 division of that padded message by G(x); the remainder always has n bits. All arithmetic is XOR-based with no carries or borrows, and the transmitted codeword is, by construction, exactly divisible by G(x).

How many zeros to pad? A generator whose highest power is n has n + 1 bits; the number of appended zeros equals n, the degree of the generator (one less than its bit length).

Application.

1. Write the generator. x5 + x4 + x2 + 1 has degree n = 5, so its binary form is 110101 (6 bits) and we append 5 zeros.

2. Pad the message. M = 1010001101 becomes 101000110100000 (five zeros appended).

3. Divide modulo-2. Align the generator under each leading 1 of the running dividend and XOR; bring down bits and repeat until every bit is processed.

4. Read the remainder. The final 5 bits left after the last XOR form the CRC: 01110.

Polynomial view.

M(x) = x9 + x7 + x3 + x2 + 1, and multiplying by x5 gives x14 + x12 + x8 + x7 + x5. Dividing this by G(x) = x5 + x4 + x2 + 1 over GF(2) leaves the remainder x3 + x2 + x, whose coefficients from x4 down to x0 are 01110 — the same result as the bit-wise division.

Cross-check.

Form the codeword by appending the remainder to M: 101000110101110. Dividing this codeword by 110101 modulo-2 leaves remainder 00000. A zero remainder confirms the CRC is correct.

Quick tip (do it faster).

You do not have to write out all 15 bits at once. Keep only a 5-bit register (n = degree of the generator), initialised to 0, and feed in the padded message one bit at a time:

1. Note the register's current leftmost bit, then shift the register left by one and bring in the next message bit on the right (keep only the last 5 bits).

2. If the leftmost bit noted in step 1 was 1, XOR the register with the generator's own lower n bits — here 10101 (110101 without its own leading 1). If it was 0, do nothing this step.

3. Repeat for every bit of the message and every appended zero. Whatever is left in the register at the end is the CRC — no need to track a full 15-bit row at each step.

This is exactly how a hardware CRC circuit (an LFSR) works, and it is faster to execute on paper than rewriting the whole padded string at every row.