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).
If $g(x)$ contains two or more terms, $e(x)$ will never divide into $g(x)$, so all single-bit errors will be detected.
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.