GATE CSE 2007 | Question: 68, ISRO2016-73

Question

The message $11001001$ is to be transmitted using the CRC polynomial $x^3 +1$ to protect it from errors. The message that should be transmitted is:

• A. $11001001000$

• B. $11001001011$

• C. $11001010$

• D. $110010010011$

Comments

(B)

---

perform XOR each time

---

All questions related to CRC Polynomial:

Computer Networks: GATE CSE 2007 | Question: 68, ISRO2016-73

Computer Networks: GATE CSE 2017 Set 1 | Question: 32

Computer Networks: GATE CSE 2021 Set 2 | Question: 34

Computer Networks: GATE IT 2005 | Question: 78

Computer Networks: GATE CSE 2026 | Set 2 | Question: 33

Answer 1

Answer - B.

Degree of generator polynomial is $3$ hence $3\text{-bits}$ are appended before performing division

After performing division using $2's$ complement arithmetic remainder is $011$

The remainder is appended to original data bits and we get  $M' = 11001001\bf{011}$ from $M = 11001001.$

Courtesy, Anurag Pandey

Comments

@Sumaiya23 Since the degree of CRC polynomial is 3 that's why 3 bits are appended.

---

In polynmial method , We continue to divide until degree of rmainder is less than degree of divisor => x3 degree 3 so remainder of the form x2 + x + 1 , hence 3 bits.

---

thank you @Pratik Gawali this was my doubt and you cleared it up beautfully!

Answer 2

B option is correct
i think this method is easier and have less chances of mistakes 

Answer 3

The length of the CRC remainder is always equal to the degree of the generator polynomial.

In this case:

• Generator polynomial: x³ + 1

• Binary form of the generator: 1001

• Degree of the polynomial = 3

👉 So the CRC remainder must be exactly 3 bits long, no more and no less.

Answer 4

The given generator polynomial is $G(x) = x^3 + 1$.

• This represents bits at positions $x^3$, $x^2$, $x^1$, and $x^0$.

• Since we have $1 \cdot x^3 + 0 \cdot x^2 + 0 \cdot x^1 + 1 \cdot x^0$, the binary divisor is 1001.

Some important points:

• Degree of Polynomial ($n$): The highest power is 3.

• Number of Appended Bits: In CRC, we append exactly $n$ zeros (the degree of the polynomial) to the message before dividing.

• The CRC Length: The resulting remainder (the CRC) will also be 3 bits long.

Analyzing the Options:

• Original Message: 11001001 (8 bits).

• Option D (110010010011): This has 4 extra bits (0011). We only need 3. Eliminated.

• Option C (11001010): This is only 8 bits long. It hasn't appended a CRC at all. Eliminated.

• Option A (11001001000): This just shows the message with 3 zeros appended (000). This is what the message looks like before division, not after the CRC is calculated. Eliminated.

• Option B (11001001011): This has exactly 3 extra bits (011) appended to the original 8-bit message. Correct.

Therefore, option (B) is correct.

 

Answer 5

 

Answer 6

Here is the answers, convert the polynomial CRC generator or divisor into bits, then proceed