I was going through some problems related to the single bit error detection based on the CRC generators and was trying to analyse which generator detect single-bit error and which don't.
Suppose, If I have a CRC generator polynomial as x4 + x2. Now I want to know whether it guarantees the detection of a single-bit error or not ?
According to references 1 and 2 , I am concluding some points :-
1) If k=1,2,3 for error polynomial xk, then remainders will be x,x2,x3 respectively in the case of polynomial division by generator polynomial x4 + x2 and according to the references, if generator has more than one term and coefficient of x0 is 1 then all the single bit errors can be caught. But It does not say that if coefficient of x0 is not 1 then single bit error can't be detected. It is saying that "In a cyclic code , those e(x) errors that are divisible by g(x) are not caught."
2) I have to check the remainder of E(x)/g(x) where E(x)(suppose, it is xk) where, k=1,2,3,... is error polynomial and g(x) is generator polynomial. If remainder is zero then I can't detect error and when it is non-zero then I can detect it.
So, According to me, generator polynomial x4 +x2 guarantees the detection of single-bit error based on the above 2 points.Please confirm whether I am right or not.
if coefficient of x0 is not 1 then single bit error can't be detected?
If the coefficient of x0 is not 1, it is the same as shifting the CRC polynomial left by 1 (or more) bits (multiplying by some power of x). Shifting a CRC polynomial left 1 or more bits won't affect it's ability to detect errors, it just appends 1 or more zero bits to the end of codewords.
generator polynomial x4 + x2 guarantees the detection of single-bit error
Correct. x4 + x2 is x2 + 1 shifted left two bits, x4 + x2 = (x2) (x2 + 1) = (x2) (x + 1) (x + 1) , and since x2 + 1 can detect any single bit error, then so can x4 + x2. Also with the (x + 1) term (two of these), it adds an even parity check and can detect any odd number of bit errors.
In general, all CRC polynomials can detect a single bit error regardless of message length. All CRC polynomials have a "cylic" period: if you use the CRC polynomial as the basis for a Linear Feedback Shift Register, and the initial value is 000...0001, then after some fixed number of cycles, it will cycle back to 000...0001. The simplest failure for a CRC is to have a 2 bit error, where the 2 bits are separated by a distance equal to the cyclic period. Say the period is 255 for an 8 bit CRC (9 bit polynomial), then a 2 bit error, one at bit[0] and one at bit[255] will result in a CRC = 0, and fail to be detected, This can't happen with a single bit error, it will just continue to go through the cycles, none of which include the value 0. If the period is n cycles, then no 2 bit error can fail if the number of bits in the message + CRC is <= n. All CRC polynomials that are a product of any polynomial times (x + 1) can detect any odd number of bit errors (since x + 1 is essentially adds an even parity check).
Shifting a CRC polynomial left by z bits means that every codeword will have z trailing zero bits. There are cases where this is done. Say you have a fast 32 bit CRC algorithm. To use that algorithm for a 16 bit CRC, the 17 bit CRC polynomial is shifted left 16 bits so that the least significant non-zero term is x16. After computing using the 32 bit CRC algorithm, the 32 bit CRC is shifted right 16 bits to produce the 16 bit CRC.