CN: CRC Rules

Question

From forouzan : If the generator has more than one term and coefficient of x^0 is 1 then all single bit error can be caught.

So if e(x)=x^i // means some power of 2 number

g(x) = at least two terms and coefficient of x^0 is always 1, means some odd number.

So is it saying that the number some 2^i will never be divisible by odd number?

Answer 1

Consider the generator G(x) = x + 1 = 11 (or any generator with coefficient of x^0 as 1 will do) and message as M(x) = 1011

After performing modulo-2 division, we get CRC bit as 1.

So, codeword = Message + CRC = 10111

Now coming to the rule, it says that if you modify exactly one bit of your codeword, error will be detected.

Let the third bit be modified from 1 to 0. So modified codeword is 10011.

Now, if you perform modulo-2 division of this newly modified codeword with our generator G(x) = x + 1, you'll get a non zero remainder indicating an error!!

Similarly you can check for any other bit of the codeword given that only bit is modified.

However if you modify 2-bits of the codeword, the remainder would be zero and error won't be detected.

This rule works only if G(x) has coefficient of x⁰ as 1 and only for single-bit modification in the codeword.

Comments

I understand the rule.i just wanted to know why this will hold ?