GATE 2024 EC – Question 47
The information bit sequence $\{1\ 1\ 1\ 0\ 1\ 0\ 1\ 0\ 1\}$ is to be transmitted by encoding with Cyclic Redundancy Check 4 (CRC-4) code, for which the generator polynomial is $C(x)=x^4+x+1$. The encoded sequence of bits is ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) $\{1\ 1\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 1\ 1\ 0\ 0\}$
Explanation
The generator $x^4+x+1$ is the bit string 10011. Append four zeros to the message: 1110101010000. Dividing by 10011 with XOR long division gives the remainder 1100 (11101→01110, 11100→01111, 11111→01100, 11000→01011, 10111→00100, then 01000, 10000→00011, 00110, 01100). The transmitted word is the message followed by the remainder: 1110101011100.