Coursify

CRC Encoding with Generator x3+1x^3+1 (Polynomial CRC-3) — Finding the Transmitted Codewords

CRC Encoding with Generator x3+1x^3+1 (Polynomial CRC-3) — Finding the Transmitted Codewords

Verified Sources
Nov 4, 2026

In CRC (Cyclic Redundancy Check) encoding, a generator polynomial G(x)G(x) is used to compute a remainder by polynomial (binary) division. The generator here is G(x)=x3+1.G(x)=x^3+1. For CRC, if G(x)G(x) has degree rr, you append rr zeros to the message, divide the resulting polynomial by G(x)G(x), and append the rr-bit remainder to form the transmitted codeword 3.

Key items for this specific problem:

  • keywordG(x)/keyword
  • keyworddegree rr[/keyword]
  • keywordremainder[/keyword]
  • keywordcodeword[/keyword]

Because G(x)=x3+1G(x)=x^3+1 has degree 33, we append 3 zeros to each message before dividing, and the transmitted codeword length becomes message length + 3 2.

Footnotes

  1. CRC (Cyclic Redundancy Check) basics - General CRC procedure and concept of generator polynomial/remainder. ↩ ↩2

  2. Cyclic redundancy check long division (mod-2) - Describes modulo-2 division and appending zeros. ↩ ↩2

  3. Polynomial division in GF(2) for CRC - Explains XOR-based polynomial division logic. ↩

type="tip" title="How to read x3+1x^3+1 as a binary generator" content="Write G(x)G(x) coefficients in order from highest degree to x0x^0. For x3+1x^3+1, the bit pattern is 1001 (since the x2x^2 and x1x^1 coefficients are 0). So the CRC divisor is 1001 ."

Footnotes

  1. Generator polynomial representation (bit form) - Connection between polynomial form and binary generator/divisor representation. ↩

type="warning" title="CRC division is over GF(2) (mod-2)" content="Subtraction and addition are both XOR in binary polynomial arithmetic. So during long division, “borrow” never happens; you just XOR with the shifted generator when the leading bit is 1 2."

Footnotes

  1. Cyclic redundancy check long division (mod-2) - Describes modulo-2 division and appending zeros. ↩

  2. Polynomial division in GF(2) for CRC - Explains XOR-based polynomial division logic. ↩

CRC Encoding Roadmap (for this generator)

Identify generator degree

1

G(x)=x3+1G(x)=x^3+1 has degree r=3r=3 so append 3 zeros."

Form message polynomial

2

Treat the message bits as coefficients in GF(2)."

Append zeros

3

Compute M(x) x3M(x)\,x^3 by appending 000."

Divide by $G(x)$

4

Compute remainder R(x)R(x) from modulo-2 division."

Transmit message + remainder

5

Transmitted codeword is C(x)=M(x) x3+R(x)C(x)=M(x)\,x^3+R(x)."

Compute the transmitted codeword using generator $G(x)=x^3+1$

  1. 1
    Step 1

    Use G(x)=x3+1 ⇒ G(x)=x^3+1 \,\Rightarrow\, generator bit pattern is 1001.

  2. 2
    Step 2

    Since r=3r=3, append 000 to the given message to get the dividend.

  3. 3
    Step 3

    Perform long division: whenever the current leftmost bit is 1, XOR the generator (shifted to that position) with the current dividend segment.

  4. 4
    Step 4

    The remainder will be exactly 3 bits (degree < 3).

  5. 5
    Step 5

    Append the 3-bit remainder to the original message bits to obtain the transmitted codeword.

Let the message be: M=11001001(8 bits).M=11001001 \quad (\text{8 bits}). Since r=3r=3, append 3 zeros: M x3=11001001 000.M\,x^3 = 11001001\,000.

We must compute the remainder when dividing this 11-bit dividend by the generator bits 1001 (i.e., x3+1x^3+1).

Below is the modulo-2 long division result (XOR-based). We track the dividend and perform XOR with the shifted divisor whenever the leftmost bit is 1.

Long-division outcome (remainder)

The remainder turns out to be: R=011.R = 011.

Therefore the transmitted codeword is: C=M ∥ R=11001001 011=11001001011.C = M\,\|\,R = 11001001\,011 = 11001001011.

This matches option (ii).

Option Check vs CRC-3 (degree 3) requirement

A CRC with x3+1x^3+1 must append 3 bits to an 8-bit message → transmitted length must be 11.

Why options (i) and (ii) are both length 11, but only (ii) is correct

  • Options (i) and (ii) both append 3 bits to the 8-bit message (length 11), so they are structurally consistent with CRC degree 33.
  • The correct CRC remainder for the given message with generator 10011001 is 011011, so only: 11001001 ∥ 011=1100100101111001001\,\|\,011 = 11001001011 is valid.

Why the other options cannot be correct

  • (iii) has no extra 3 CRC bits (length remains 8), contradicting r=3r=3.
  • (iv) appends 4 extra bits (length 12), which contradicts the degree-3 generator requirement.

Common CRC pitfalls (and how they affect this question)

Knowledge Check

Question 1 of 4
Q1Single choice

For CRC with generator G(x)=x3+1G(x)=x^3+1, how many zero bits are appended to an 8-bit message before division?

References (Footnotes)

Explore Related Topics

1

Finite Automata: Which Option Is NOT Accepted?

2

Maximum Window Size in Selective Reject (Selective Repeat) with $n$-Bit Sequence Numbers

3

CRC Sender-Side and Receiver-Side Steps (with Worked Examples)

Browse all research articles