GATE 2024 EC Q.47: solution and answer

GATE 2024 · ECQ.47 · 2 marks · MCQ

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 ________.

(A)
{1 1 1 0 1 0 1 0 1 1 1 0 0}
(B)
{1 1 1 0 1 0 1 0 1 1 1 0 1}
(C)
{1 1 1 0 1 0 1 0 1 1 1 1 0}
(D)
{1 1 1 0 1 0 1 0 1 0 1 0 0}

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The encoded sequence is {1 1 1 0 1 0 1 0 1 1 1 0 0}, option (A).

Official answer: ASource: Official answer key, GATE 2024 EC (IISc Bengaluru)

The generator $C (x) = x^{4} + x + 1$ has coefficients $10011$ , so $r = 4$ check bits are added. The message is $m = 111010101$ ( $k = 9$ bits), so the codeword has $n = 13$ bits.
Multiply the message by $x^{4}$ by appending four zeros: $1110101010000$ .
Divide $1110101010000$ by $10011$ using modulo-2 (XOR) long division. Take $11101$ : $11101 \oplus 10011 = 01110$ . Bring down $0$ : $11100 \oplus 10011 = 01111$ .
Bring down $1$ : $11111 \oplus 10011 = 01100$ . Bring down $0$ : $11000 \oplus 10011 = 01011$ .
Bring down $1$ : $10111 \oplus 10011 = 00100$ . Bring down $0$ : $01000$ . The leading bit is $0$ , so XOR with $00000$ and the remainder is $1000$ .
Bring down $0$ : $10000 \oplus 10011 = 00011$ . Bring down $0$ : $00110$ (leading bit 0, no XOR). Bring down the last $0$ : $01100$ (leading bit 0, no XOR).
The remainder is $R (x) = 1100$ , that is $x^{3} + x^{2}$ .
Independent check using $x^{4} \equiv x + 1 (mod C (x))$ . Reducing the powers gives $x^{6} \equiv x^{3} + x^{2}$ , $x^{8} \equiv x^{2} + 1$ , $x^{10} \equiv x^{2} + x + 1$ , $x^{11} \equiv x^{3} + x^{2} + x$ and $x^{12} \equiv x^{3} + x^{2} + x + 1$ . The message times $x^{4}$ is $x^{12} + x^{11} + x^{10} + x^{8} + x^{6} + x^{4}$ . Adding the residues in GF(2) gives $1111 \oplus 1110 \oplus 0111 \oplus 0101 \oplus 1100 \oplus 0011 = 1100$ , matching the long division.
In GF(2) subtraction equals addition, so the codeword is the message followed by the remainder: ${1110101011100}$ . This is option (A).

KEY IDEA

A systematic CRC codeword is the message followed by the remainder of $m (x) \cdot x^{r}$ divided by the generator, using modulo-2 arithmetic. Here $r = 4$ for $x^{4} + x + 1$ .

WATCH OUT FOR

Forgetting to append the four zeros before dividing, or appending the quotient instead of the remainder. Another slip is skipping the XOR when the leading bit is 0 but still bringing the wrong bit down. Options B, C and D differ from the correct codeword only in the last four check bits.

From the GATE 2024 EC paper. Every question of this paper · Download the full paper · All 5 Error control questions, with notes

GATE 2024 EC Q.47: solution and answer

Answer and solution

More Error control questions