GATE CSE 2009 | Question: 48

Question

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?

• A. $G(x)$ contains more than two terms
• B. $G(x)$ does not divide $1+x^k$, for any $k$ not exceeding the frame length
• C. $1+x$ is a factor of $G(x)$
• D. $G(x)$ has an odd number of terms.

Comments

Polynomials having cofficients in GF(2) form polynomial rings. Polynomial rings follow ring arithmetic.
Odd bit errors should be detected, so we'll choose the polynomial in which both odd and even bit errors are possible, i.e (x+1)
This is a minimum polynomial which should be a factor of the dividend polynomial for the error to be detected. (because we want 0 remainder)
Hence the answer. (we can think of {x+1} in polynomial ring as 2 in ring over Integer numbers with usual {+,*} operations, although that is not exactly how it is, we need to define isomorphism first)

---

Forouzan  4th edition  Page :-  294 onwards

---

I think $Option (B)$ can be interpreted like this too -

It is saying that if we talk of the error pattern $E(x)$ being of type $1 + x^k$, i.e. there is error in exactly $2$ bits that are $k -1$ bits apart.

For e.g. if $E(x)$ is $1 + x^3$ i.e. $1001$, then the $1$'s are two bits apart.

So, if $G(x)$ is such that it does not divide $1 + x^k$, then it will be able to detect errors of exactly two bits that are $k - 1$ bits apart.

It does not say anything about detecting odd number of bits of error, hence incorrect option.

Answer 1

Let me first explain building blocks to this problem. Before answering this, we should know 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 2^nd 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 form we can see: \[ x^4 + x = x^4 + x^2 + x + x^2 = x^4 + \mathbf{2x^2} + x = \mathbf{x^4 + x} \] (Here multiplying with 2 means 0 because it corresponds to binary modulo-2 arithmetic where 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) \).
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) \).

Let's check:

\[ R(x) \bmod G(x) = (C(x) + E(x)) \bmod G(x) \] (For simplicity I am writing mod as division) \[ \frac{R(x)}{G(x)} = \frac{C(x)}{G(x)} + \frac{E(x)}{G(x)} \] \( G(x) \) always divides \( C(x) \)
\[ \Rightarrow \frac{R(x)}{G(x)} = 0 + \frac{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) \) dividing \( E(x) \) or not.
Whole strength of \( G(x) \) lies if it does not divide any possible \( E(x) \).

Let's 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 whether error is from toggling 1→0 or 0→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, 2^nd 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) = 0 \). 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) = 1 \). (Remember 1+1=0, 1+1+1=1. Any odd number of ones = 1.)
  \( E(1) \neq 0 \), 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) \) won’t 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) \) doesn’t have factor \( 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 \).)

Comments

(Here multiplying with 2 means 0 because it corresponds to binary modulo-2 arithmetic where 1 + 1 = 0 (not 2).)
by doing XOR ?

---

Anything multiplied by 2 and then mod by 2 will give 0.

---

In modulo 2 arithmetic x + 1 is same as x - 1. Clarified here.

Answer 2

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.

Comments

Thanks for explanation.

---

too short..

Answer 3

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

Comments

@Jashan sir, If  $G(x) = x^4 + x + 1$ then $1+x$ is not factor of $G(x)$ right?

Even if $G(x)$ contains the term $1+x$ it’s NOT necessary that $1+x$ is factor of $G(x)$. $1+x$ is factor of $G(x)$ if and only if $G(x)$ contains even number of terms.

Is my understanding correct?

Answer 4

Let G(x) be the generator polynomial.

C(x) be the sent codeword, R(x) be the received code and E(x) be the error polynomial.

We can write: R(x) = C(x) + E(x)                             { This can be written by mod 2 addition and skipping the carry}

As we know that: "To detect error, G(x) should not divide R(x)".   

=> G(x) should not divide E(x). As, $\frac{R(x)}{G(x)} = \frac{C(x)}{G(x)} + \frac{E(x)}{G(x)}$

Further, $\frac{R(x)}{G(x)} = 0 + \frac{E(x)}{G(x)}$

This means if E(x) is not divisible by G(x) then R(x) will not also be divisible by G(x).

Now, To detect odd number of bits in error, E(x) will contain odd number of terms. 

Example: let sent codeword= 101010 and Received codeword = 100100 i.e three bits (1st, 2nd and 3rd bit) are in error.

Therefore, $E(x) = x^{3}+x^{2}+x$.

A) G(x) contain more than 2 terms.

let, $G(x) = x^{3}+x^{2}+x$ then $\frac{E(x)}{G(x)} = \frac{x^{3}+x^{2}+x}{x^{3}+x^{2}+x}$

So, E(x) is divisible by G(x). So, A is not the right option.

B) G(x) does not divide by $1+x^{k}$, for any k not exceeding frame length.

here, k=6 [ frame length or code length ]

let $G(x) = x$   &   $E(x) = x^{3}+x^{2}+x$.

$\frac{E(x)}{G(x)} = \frac{x^{3}+x^{2}+x}{x}$. here, E(x) can be divisible by G(x). So, B is not the right option.

C) $(1+x)$ is a factor of G(x).

$\frac{E(x)}{G(x)} = \frac{x^{3}+x^{2}+x}{(1+x)G(x)} = \frac{odd no. of terms}{even no. of terms}$

here, E(x) wil never be divisible by G(x). So, (C) is correct option.

D) G(x) has odd number of terms

let $G(x) = x^{3}+x^{2}+x$.

$\frac{E(x)}{G(x)} = \frac{odd No of terms}{Odd number of terms}$ 

here, G(x) may divide E(x). So, this canot be the option.

Hence, Correct Ans: (C)

 

Comments

B option can be right away eliminated by taking a counter example if its confusing you.

counter example:

g(x)=x^2.

now take e(x)=1+x^2 where k=2 . now e(x) % g(x) is not equal to 0 => g(x) can detect it

but let e(x)=x^3+x^4+x^5. e(x) %g (x) =0, so there is some e(x) with odd number of error bits which cant be detected by this g(x) hence b got eliminated.

Answer 5

ans c)

Comments

please explain.

---

In most of the answers answered by you, you just tell the options. Please elaborate so that it can b helpful for others.

---

everyone knows the answer either right or wrng explaination matters

Answer 6

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 x^k +1. where k is any constant.