Skip to content
Free public beta until December 4, 2026: every course is open, no card needed. After that, the first chapter of each course stays free and full access is a one-time $39 ($19 for up to 100 founding members chosen for helpful feedback). Your progress is kept. How the beta works

Recipe

Compute a CRC codeword, and check a received word against it

Use when: you have a message, a generator polynomial g(D), and either need to produce the transmitted codeword or need to check whether a received word passes the CRC test

Goal: the transmitted codeword x, or a definite pass/fail verdict on a received word

Taught in CRC and error detection

Quick recipe

  1. Shift the message left by the generator's degree
  2. Divide the shifted message by the generator using XOR
  3. Read off the final remainder
  4. XOR the remainder into the shifted message to get the codeword
  5. To check a received word, repeat the division and see whether the remainder is zero
  1. 1

    Append r zero bits to the k-bit message, where r is the generator's degree, one less than its own bit length.

    Example

    u=1011 and g=1101 (degree r=3): append 3 zeros, giving 1011000.

    Why: shifting makes room for a remainder to occupy without disturbing any of the original message bits.

  2. 2

    Repeatedly check the leading bit of the current 4-bit window: if it's 1, XOR the window with the generator; if it's 0, leave the window as is. Either way, drop the leading bit and bring down the next message bit.

    Example

    1011 \oplus 1101 = 0110, bring down 0 \to 1100. 1100 \oplus 1101 = 0001, bring down 0 \to 0010. Leading bit is 0, no XOR this step, bring down 0 \to 0100. Leading bit is 0 again, no XOR, no more bits to bring down.

    Why: this is ordinary polynomial long division over \mathrm{GF}(2), where addition and subtraction are both XOR, so there's never a borrow or a carry to track, only the leading bit's value to check.

  3. 3

    Once every bit has been brought down, the r digits left in the window are the remainder c.

    Example

    c=100.

    Why: this remainder is exactly what's needed to make the shifted message divide evenly by the generator.

  4. 4

    Combine the shifted message from Step 1 and the remainder from Step 3 with XOR.

    Example

    1011000 \oplus 0000100 = 1011100.

    Why: XOR-ing in the remainder is precisely what cancels it, making the transmitted codeword exactly divisible by g(D), the property the receiver's check relies on.

  5. 5

    Apply Steps 2 and 3 to the received word y instead of the shifted message.

    Example

    Received y=1011000 (the codeword 1011100 with one bit flipped): dividing gives remainder 100 \neq 000, so the error is detected.

    • the remainder is zero — no error detected (though a rare error that itself happens to be a multiple of g(D) would slip through undetected).
    • the remainder is nonzero — an error is definitively flagged.

    Why: divisibility by g(D) is exactly the property construction guaranteed for a genuine codeword; any received word failing that test cannot be the codeword that was actually sent.

Common mistakes

  • Forgetting to XOR when the leading bit is 1, or forgetting to drop the leading bit and bring down the next one when it's 0; both steps happen every time, only the XOR is conditional.
  • Using the generator's bit length as r instead of its degree, one less than the bit length, and appending the wrong number of zeros.
  • Stopping the division early, before every message bit has been brought down.
  • Assuming a nonzero remainder somewhere in the middle of the division (before all bits are brought down) is the final answer, instead of continuing to the actual last step.