Question

Consider the cyclic redundancy check (CRC) based error detecting scheme having the generator polynomial $X^3 + X + 1$. Suppose the message $m_4 m_3 m_2 m_1 m_0 = 11000$ is to be transmitted. Check bits $c_2 c_1 c_0$ are appended at the end of the message by the transmitter using the above CRC scheme. The transmitted bit string is denoted by $m_4 m_3 m_2 m_1 m_0 c_2 c_1 c_0$. The value of the checkbit sequence $c_2 c_1 c_0$ is

• A. 101
• B. 110
• C. 100
• D. 111

Hint:

In CRC computation, the check bits are always equal to the remainder obtained from modulo-2 division of the padded message by the generator polynomial.

Answer 1

The Correct Option is C

Step 1: Identify the generator polynomial and its degree.
The generator polynomial is \[ G(x) = x^3 + x + 1 \] The degree of $G(x)$ is $3$, hence $3$ check bits are required.

Step 2: Append zeros to the message.
The original message is \[ m(x) = 11000 \] Appending three zeros gives \[ 11000\,000 \]

Step 3: Perform modulo-2 division.
Divide $11000000$ by the generator polynomial $1011$ (binary form of $x^3 + x + 1$) using modulo-2 division.
Carrying out the division step-by-step, the remainder obtained after division is \[ 100 \]

Step 4: Determine the check bits.
The remainder of the division gives the CRC check bits. Therefore, \[ c_2 c_1 c_0 = 100 \]

Step 5: Conclusion.
Hence, the correct checkbit sequence appended to the message is $100$.