# Polynomial generator required to detect single bit error in Cyclic Redundancy Check codes

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$:

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.

## 1 Answer

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.

• 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.
– Maha
Jan 21 '17 at 19:25
• yes you are correct this analysis holds For any $x^i +1$ @Mahesha999 Jan 21 '17 at 19:38
• Every two term polynomial can be expressed as a product of two polynomials with one being $x^i +1$ Jan 21 '17 at 19:39
• 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...
– Maha
Jan 21 '17 at 19:51
• 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."
– Maha
Jan 21 '17 at 19:51