GATE CSE 2017 | Set 1 | Question: 32

Question

A computer network uses polynomials over $GF(2)$ for error checking with $8$ bits as information bits and uses $x^{3}+x+1$ as the generator polynomial to generate the check bits. In this network, the message $01011011$ is transmitted as:

• A. $01011011010$
• B. $01011011011$
• C. $01011011101$
• D. $01011011100$

Comments

@gayabaya i solved it in polynomial form but got the answer 101 got same in binary as well. One of us must be solving wrong in polynomial form. 

---

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

---

For more mathematical understanding of CRC & Hamming code read two resources :

1) Data Link layer pdf of "Free Berlin University" by Prof. Dr.-Ing. Jochen H. Schiller.

2) Computer Network By Tanenbaum 

Answer 1

The generator polynomial has degree $3.$ So, we append $3$ zeroes to the original message.

Correct Answer: $C$

Comments

that thing I know that we are doing XOR operation only, but in this question, the way we approach is similar as that of division approach.

---

what does it mean by computer network uses polynomials over 𝐺𝐹(2) for error checking

---

I did a little research (I might be wrong or my concept may be a bit loose but it might help): GF(2)Nmeans we are having a working set of only two digit and we are doing an %2 (I,e trying to find the reminder through modulus 2).

So when u do operation like 0 + 0 = 0 ,0+1 =1 ,1+1 =0 (AS 1+1=2 and applying % gives 2%2=0) similarly 0-0 =0, 0-1 =1 (as 0-1=-1 applying module -1%2=1) as u must have observed it's the same as performing XOR I,e 1 XOR 1 = 0,0 XOR 1 = 1,0 XOR 0= 0,etc.

Hence GF(2) is nothing but a fancy term for XOR :-) please feel free to add more details and debate 😉

Answer 2

So,$C)$ is the correct answer.

Answer 3

here generator is 1011

Clearly on dividing the message by it we get 101 to be padded at end

and only option C contains that

so OPTION (C) is correct

Comments

Hi,@sriv_shubham,

I tried to take decimal equivalent of both  01011011 & 01011011000 and divided it by 1011.

I didn’t get 101 as remainder.

can u pls elaborate on your answer ?

 

Thanks in advance

---

This is a wrong ans. I am also not getting 101 as remainder. The remainder is 10 and ans is A

---

I think you did mistake somewhere

Answer 4

Option C
i think this approach is much easier and fast 

 

Answer 5

Binary form:    01011011  divided by  1011

x**6+x**4+x**3+x+1
x**3+x+1

Binary form (added zeros):  01011011000  divided by  1011
Result is    01000011
Remainder is    101
Working is    

   01000011
-----------
01011011000
0000
----
 1011011000
 1011
 ----
  000011000
  0000
  ----
   00011000
   0000
   ----
    0011000
    0000
    ----
     011000
     0000
     ----
      11000
      1011
      ----
       1110
       1011
       ----
        101

Transmitted value is:    01011011101

 

Answer 6

COMMENT BELOW IF YOU HAVE ANY DOUBT