The message 1001 is to be transmitted using the CRC polynomial x³ + x + 1 to…

Concept: Cyclic Redundancy Check (CRC) detects transmission errors using binary (mod-2) polynomial division. For a generator polynomial of degree r, the sender appends r zero bits to the message, divides the result by the generator's binary bit pattern using XOR (mod-2, no-borrow) division, and replaces the appended zeros with the resulting remainder — the Frame Check Sequence (FCS) — to form the transmitted frame. The receiver divides the received frame by the same generator; a zero remainder confirms that no error altered the frame in transit.

Application: For this message, the generator polynomial x3+x+1 corresponds to the binary bit pattern 1011 (coefficients of x3, x2, x1, x0), so its degree is r = 3.

1. Append r = 3 zero bits to the message 1001, forming the augmented dividend 1001000.

2. Divide 1001000 by 1011 using mod-2 (XOR) division: the leading 4 bits 1001 XOR 1011 = 0010; bring down the next bit (0) to get 0100.

3. The leading bit of 0100 is 0, so no XOR is applied; bring down the next bit (0) to get 1000.

4. 1000 XOR 1011 = 0011; bring down the last bit (0) to get 0110.

5. The leading bit of 0110 is 0, so the division stops; the final 3 bits give the remainder = 110.

6. Replace the 3 appended zero bits of the augmented dividend with this remainder: 1001 followed by 110 gives the transmitted message 1001110.

Cross-check: A correctly formed frame divides evenly (remainder 000) by the generator. Dividing 1001110 by 1011 using the same mod-2 process leaves remainder 000, confirming 1001110 is the valid transmitted message.