Consider the cyclic redundancy check (CRC) based error detecting scheme having…
2021
Consider the cyclic redundancy check (CRC) based error detecting scheme having the generator polynomial \(X^3+X+1\). Suppose the message \(m_4m_3m_2m_1m_0 = 11000\) is to be transmitted. Check bits c2c1c0 are appended at the end of the message by the transmitter using the above CRC scheme. The transmitted bit string is denoted by \(m_4m_3m_2m_1m_0c_2c_1c_0\). The value of the checkbit sequence \(c_2c_1c_0\) is
- A.
101
- B.
110
- C.
100
- D.
111
Attempted by 203 students.
Show answer & explanation
Correct answer: C
Solution:
Convert the generator polynomial to its binary divisor form: x^3 + x + 1 has coefficients for x^3, x^2, x^1, x^0 as [1, 0, 1, 1], so the divisor is 1011.
Append three zeros (degree of generator) to the message 11000: padded message = 11000000.
Perform modulo-2 (XOR) long division of 11000000 by 1011. Using the standard algorithm (for each position i from 0 to 4, if the current bit is 1 XOR the next 4 bits with 1011), the intermediate states are:
i = 0: 1100 XOR 1011 -> 0111, full state becomes 01110000.
i = 1: (window starting at bit 1) 0111 -> with divisor gives state 00101000.
i = 2: XOR yields state 00000100.
i = 3 and i = 4: leading bits are 0, so no further XOR operations.
After completing the division, the remainder is the last three bits: 100. These are the check bits c2 c1 c0.
Therefore, the check bit sequence is 100, and the transmitted bit string is the original message followed by the check bits: 11000100.
Answer: check bits c2 c1 c0 = 100.
A video solution is available for this question — log in and enroll to watch it.