The Gateway to Computer Science Excellence
+33 votes
8.1k views

Let $G(x)$ be the generator polynomial used for CRC checking. What is the condition that should be satisfied by $G(x)$ to detect odd number of bits in error?

  1. $G(x)$ contains more than two terms
  2. $G(x)$ does not divide $1+x^k$, for any $k$ not exceeding the frame length
  3. $1+x$ is a factor of $G(x)$
  4. $G(x)$ has an odd number of terms.
in Computer Networks by Veteran (52.2k points)
edited by | 8.1k views
0
can somebody explain in simple word ?Actually i am not able to get the que ????
0

 for any k not exceeding the frame length

pls explain this line

+2

A, B and D are properties of a good a polynomial generator. But (C) is itself enough to detect all odd numbers of errors.

0
@manu sir can you please explain it little bit more?

5 Answers

+60 votes
Best answer

Let me first explain building blocks to this problem. Before answering this, we shouldknow the relationship between Sent codeword,  Received codeword, CRC generator and error polynomial.

let's take an example:

Sent codeword $=10010\ (=x^4+x)$

Received codeword $= 10\color{blue}{1}10$ (error at $2nd$ bit )  $(=x^4+x^2+x)$

Now, i can write Sent codeword = Received codeword + error
$(10010 =10\color{blue}{1}10 + 00100,$ here we do modulo $2$ arithmetic
i.e $1+1 =0$ without carry   )

in polynomial also we can see $x^4+x = x^4+x^2+x+x^2 = x^4+\bf{2}x^2+x=\bf{x^4+x}$
(here multiplying with 2 means 0 because it corresponds to binary modulo 2 arithmetic which is 1+1 = 0 (not 2) )  

OR 

We can also write,

Received codeword = Sent codeword + error   (Check it using same method as above)

Sent codeword $C(x),$ Received codeword $R(x)$ and  error $E(x)$.

Now we have R(x) = C(x) + E(x). and let CRC polynomial be G(x).
$G(x)$ always divides $C(x),$ and if there is an error then $G(x)$ should not divide $R(x)$.

Lets check - 

$R(x) \bmod G(x) =\left(C(x) + E(x)\right) \bmod G(x)$ (for simplicity i am writing mod as division)

$\dfrac{R(x)}{G(x)}=\dfrac{C(x)}{G(x)}+\dfrac{E(x)}{G(x)}$

$G(x)$ always divides $C(x)$

$\Rightarrow \dfrac{R(x)}{G(x)}=0+\dfrac{E(x)}{G(x)}$

If $G(x)$ divides $E(x)$ also this would mean $G(x)$ divides $R(x)$. We know that, if $G(x)$ does not properly divide $R(x)$ then there is an error but we are never sure if there is error or not when $G(x)$ divides $R(X)$.

As we saw, $G(x)$ divides $R(x)$ or not totally depends on $G(x)$ divides $E(x)$ or not.
Whole strength of $G(x)$ lies if it does not divide any possible $E(x)$. 

Lets see again $E(x)$, if there is an error in $3^{rd}$ and $4^{th}$ bit from left $\text{(LSB is  0th bit )}$ then $E(X) = x^4+x^3$.( it does not matter error is from toggling $1$ to $0$ or $0$ to $1$ ) Check with above example.

Now come to question. it says $G(x)$ should detect odd number of bits in error?.
If number of bits are odd then terms in $E(x)$ would be odd.

for instance if $1^{st}, 2nd$ and $5^{th}$ bit got corrupted then $E(x) = x^5+x^2+x.$

It is clear that if any function $f(x)$ has a factor of $x-k,$ then at x=k, $f(x)$ would be zero. I.e. $f(x) = 0$ at $x=k$.

  • We want to detect odd number of bits that means received message $R(x)$ contains an odd number of inverted bits, then $E(x)$ must contain an odd number of terms with coefficients equal to $1$.
  • As a result, $E(1)$ must equal to $1$ (remember 1+1 = 0, 1+1+1 = 1.
    Any Odd number of times sum of one's is = 1). 
    $E(1)$ is not zero, this means $x+1$ is not a factor of $E(x)$.
  • Now I want $G(x)$ not to be a factor of $E(x),$ So that $G(x)$ wont divide $E(x)$ and i would happily detect odd number of bits.
  • So, if we make sure that $G(1) = 0,$ we can conclude that $G(x)$ does not divide any $E(x)$ corresponding to an odd number of error bits. In this case, a CRC based on $G(x)$ will detect any odd number of errors.
  • As long as $1+x$ is a factor of $G(x), G(x)$ can never divide $E(x).$ Because we know $E(x)$ dont have factor of $1+x$.

Option C.

(Option B might confuse you, If  $G(x)$ has some factor of the form $x^k+1$ then also $G(x)$ would detect all odd number of errors, But in Option B, language is changed, and that too we should not have any upper bound on $k$)

by Boss (17.9k points)
edited by
0
plzzzzzz ....... complete  the solution
+1
Yes please complete the solution sir .
+1
Is it clear now ?
+3

@Sachin Mittal1 , 

  • As a result, E(1) must equal to 1 (remeber 1+1 = 0, 1+1+1 = 1. Any Odd number of times sum of one's is = 1). E(1) is not zero, this means x+1 is not a factor of E(x).

How does E(1) not equal to zero means x+1 is not a factor of E(x)?? Shouldn't it be x-1 instead of x+1 here? 

0

Yes I also agree with shraddha priya

If at X=1 E(X)!=0 it means X-1 is not a factor of E(X) .

also

if at X=1 we want E(1)=1 and G(1)=0

then E(1) mod G(1)=1 mod 0= NaN

+1
it is GF(2) + and - is same.
0
why $\frac{C\left ( x \right )}{G\left ( x \right )}=0$ ?
0

why C(x)/G(x)=0 ?

Because C(X) is construct in such a way that C(x)/G(x) should be zero. 

+2
@ shraddha priya  @akb1115 this is not proper polynomial arithmetic its different here x+1 if its generator shouldn't divide the error polynomial hence as error polynomial contains odd no of digits when we do E(1) we get a 1 as we should do x-or  to odd no of 1s and if  the polynomial x+1 we substitute 1 we get 0 hence 0 doesnt divide 1 hence our polynomial doesn't divide the error and thats what we want... if our polynomial contains odd no of ones it divides the E(x) as  we get 1
0
@Venkat Sai What if we want to detect even no of bit errors? What should be the generator polynomial then?
+8

or we can do this by taking an example,

as we can see that only odd no. of error can detect

0
Thanks sir for this detailed explanation.
+1
what about even no of error???
0

yea @Abhisek Tiwari 4 what about it?

0

For even number of bit errors - 

It's impossible to tell if there are exactly $0$ error bits, when we're using CRC, because there's always a chance that the error goes undetected. 

However, if we exclude $0$ from even numbers, then the helpful/important things are- 

1. $G(x)$ should not divide $E(x)$. 

2. Since there are even no. of error bits, the polynomial $E(1) = 0$   

3. $G(x)$ will divide $E(x)$ if $G(1) = 0$, and by point $1$, we want to avoid that. 

4. So, if we have $G(x) = 1$, then $G(x)$ won't divide $E(x)$.

5. What does it mean for $G(x)$ to be equal to $1$? It means the generator polynomial $G(x)$ should have odd number of terms.

6. So, if I do $G(x) = 1 + x^m + x^{n}$, then $G(1) $ which will always be an odd number, which are represented by $1$ in modular $2$ arithmetic, whereas even numbers are represented by $0$.  

7. I don't know if it's okay to say that $1 + x + x^2$ is enough to detect even no. of errors. 

 

Someone please verify.

+7 votes
if we have any odd number of errors the arithmetic modulo sum will be 1.

example: $x^{3}+x^{2}+x^{1}$

Now if generator polynomial g(x) has x+1 as factor, substituting x as 1 should  give zero. Here we are substituting x as 1 and not -1 because it is modulo 2. In $x^{3}+x^{2}+x^{1}$ put x as 1, 1+1+1=3 mod2=1. Hence x+1 does not divide this and can detect the error. same is true for all odd number of errors but not for even number of errors.
by Boss (17.6k points)
0
Thanks for explanation.
0
too short..
+1 vote
ans c)
by Loyal (5.2k points)
+2
Please elaborate
+2
Please elaborate the reason for the answer
+1
please explain.
+4
In most of the answers answered by you, you just tell the options. Please elaborate so that it can b helpful for others.
0
everyone knows the answer either right or wrng explaination matters
+1 vote

G(x) contains more than two terms = No meaning here
If 1+x is factor of generator polynomial then we can find all odd number of error. So B is true.
To detect 1 bit error we need xk +1. where k is any constant.

by Veteran (63k points)
+1 vote

The better the generator polynomial, the more likelihood of detecting the errors.

There's no universal CRC polynomial that can detect all errors, but we can establish some guidelines of a good CRC generator polynomial. Let's denote the generator polynomial function by g(x).


  • To detect single bit errors, g(x) must have at least two terms.
    »For eg: g(x) = x + 1.
     
  • To detect all odd number of errors, g(x) must have an even number of terms.
    This means (1 + x) should be a factor of g(x). [Option C is correct]
    »For eg: g(x) = x + 1 or,
    »g(x) =  $x^{4} + x^{3} + x + 1$
     
  • To detect burst errors, ie, errors of the form "1 <any combo of 0's and 1's> 1", we must pick g(x) such that it has a degree b, where b is the length of the burst error.
    Moreover, If g(x) does not have x as a factor, it'll detect any error except a specific error of length b+1.

     

Source: http://web.mit.edu/6.02/www/f2010/handouts/lectures/L7.pdf

Hence, Option C

by Loyal (6.3k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
198,225 comments
104,909 users