1
$\begingroup$

I was reading about CRC coding from two books:

They use following notations:

  • $d(x)$: dataword to be sent (as a polynomial)
  • $c(x)$: codeword sent (as a polynomial)
  • $e(x)$: error (as a polynomial)
  • $c(x)+e(x)$: codeword sent with error introduced (if any)
  • $g(x)$: generator polynomial to be used at CRC encoder (for creating c(x)) and decoder (for checking if error is introduced or not during transmission)

Forouzan then states following:

A single-bit error is $e(x)=x^i$, where i is the position of the bit. If a single-bit error is caught, then $e(x)=x^i$ is not divisible by $g(x)$. (Note that when we say not divisible, we mean that there is a remainder.) If $g(x)$ has at least two terms and the coefficient of $x^0$ is not zero (the rightmost bit is 1), then $e(x)$ cannot be divided by $g(x)$ and all single bits errors can be caught.

He then gives example of generator:

  • $g(x)=x+1$ saying that it can catch all single bit error (with which I have some doubts)
  • $g(x)=x^3$ saying that all single-bit errors in positions 1 to 3 are caught rest are left uncaught (with which I dont have any confusion).

For example, consider the below example for generator $g(x)=x+1$: enter image description here

Tanenbaum says:

If $g(x)$ contains two or more terms, $e(x)$ will never divide into $g(x)$, so all single-bit errors will be detected.

My doubts:

Q1. Forouzan states additional requirement to Tanenbaum that "the coefficient of $x^0$ is not zero (the rightmost bit is 1)". Whats correct? and why? Will generator $g(x)=x^3+x^2$ (which satisfies Tanenbaum's statement) capture all single bit errors? Do we always need "$+1$" in $g(x)$ for capturing any single bit error?

Q2. I feel I dont understand the reason/logic behind statements made by both authors, thats why I am not able to decide on myself whether "$+1$" should be there in $g(x)$ or not. Whats the logic then behind both of statements (whichever is correct)? More precisely: why $e(x)$ with single bit error will not be dividable by $g(x)$ if

$g(x)$ has at least two terms and the coefficient of $x^0$ is not zero

as Forouzan says or if

$g(x)$ contains two or more terms

as Tanenbaum says (whichever is correct).

I must be missing something very very basic stuff here.

$\endgroup$
1
$\begingroup$

You just need to concentrate on the polynomial division here. First consider the case where we need to detect one - bit error . For this case

$ e(x) = x^k $

we can choose any polynomial with terms >=2 , since it will not divide the error polynomial completely .

Next let us see the case of odd number of errors. Notice how this is different from one bit error. This is a burst error. Consider the polynomial

$ g(x) = (x+1) $

If we multiply this polynomial with any other polynomial the number of terms we get as a result is always even. This result in general is true you can try this for assurance.

Consider any error polynomial with odd number of errors . This polynomial will have odd number of terms in the polynomial. example :

$e(X) = x^3 + x^2 + x $

Now

$\nexists p(x) \quad such\quad that \quad p(x) * g(x) = e(x) $

In other words no polynomial could be fund which gives odd number of terms when multiplied by x+1 . This observation suggests x+1 should be a factor of our generator function in order to catch odd- number of errors. As 1 - bit error is an odd-bit error x+1 also detects one - bit errors. Both books are correct in their reasoning.

$\endgroup$
  • $\begingroup$ Nice. But then why only $x+1$? Can't we have any 2-term polynomial? Multiplying it by any other polynomial will result in polynomial having even number of terms, thus allowing to capture any odd number of errors. $\endgroup$ – anir123 Jan 21 '17 at 19:25
  • $\begingroup$ yes you are correct this analysis holds For any $ x^i +1 $ @Mahesha999 $\endgroup$ – Shubham Singh rawat Jan 21 '17 at 19:38
  • $\begingroup$ Every two term polynomial can be expressed as a product of two polynomials with one being $x^i +1$ $\endgroup$ – Shubham Singh rawat Jan 21 '17 at 19:39
  • $\begingroup$ Ok I was not talking about $x^i+1$ but about $x+1$. But I feel I got the answer. Tanenbaum has made this fact clear: "Interestingly, no polynomial with an odd number of terms has $x+1$ as a factor in the modulo 2 system." Thats why $x+1$ (not any other two term polynomial to which if we multiply we can still get non-odd or even term polynomial) should be the part of $g(x)$ to catch odd number of bit errors. So it is some sort polynomial algebraic property that is getting significance here... $\endgroup$ – anir123 Jan 21 '17 at 19:51
  • $\begingroup$ But I am still confused about who is correct about $g(x)$ for being able to detect any single bit error. Though I feel (after solving many examples) Tanenbaum is correct that any two term $g(x)$ should suffice, Forouzan keeps iterating that $g(x)$ should have "$+1$" to detect any single bit error. For example in section "Two Isolated Single-Bit Errors", he says: "If $g(x)$ has more than one term and one term is $x^0$, it cannot divide $x^i$, as we saw in the previous section." $\endgroup$ – anir123 Jan 21 '17 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.