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

To solve this problem, we will calculate the Cyclic Redundancy Check (CRC) bits for the given message using the specified generator polynomial. The generator polynomial is \(X^3 + X + 1\), which translates to the binary representation \(1101\).

1. First, we represent the given message \(m_4 m_3 m_2 m_1 m_0 = 11000\) in binary. 
2. Append 3 zeros (equal to the degree of the generator polynomial) to the message to perform the division. So, the new message becomes \(11000 \, 000\).
3. Perform binary division of \(11000 \, 000\) by the generator polynomial \(1101\).

Performing the binary division:

1. Divide the first four bits \(1100\) by \(1101\):
   1. 1 (leftmost bits match, so leading bit of the quotient is 1)
   2. Perform XOR operation with the divisor: \((1100 \,\,\, \oplus \,\,\, 1101 = 0001\\)
2. Bring down the next bit from the dividend, so the number now is \(00010\).
3. Since the modified dividend \(0010\) is lower than the divisor \(1101\), append a 0 to the quotient and bring down the next bit.
4. Now consider \(00100\) (obtained by bringing down another 0).
5. Repeat division steps:
   1. 0 (leading bit of the quotient remains 0 as 0010 < 1101)
   2. Continue by bringing down the remaining bits.
6. Eventually, you will have exhausted the bits of the appended zeros along with the message bits, completing the division process with remainder (or CRC bits).

Performing XOR with the rest until obtaining the CRC bits:

1. At conclusion of entire division process, the remainder will be the CRC bits, \(c_2 c_1 c_0 = 100\).
2. This is because:
   • For the last XOR operation, the binary string resulting after regular division steps produces \(100\).
   • This remainder will be the CRC bits appended to the message.

So, the value of the checkbit sequence \(c_2 c_1 c_0\) is \(100\).

Therefore, the correct answer is 100.