Cyclic Redundancy Check: Single and double bit error

Question

Found this on the book by Forouzan (Data Communications and Networking 5E). But, not able to understand the logic behind these.

1. This is in the context of isolated double-bit errors.

The polynomial x^15 + x^14 +1 cannot divide any error of type x^t + 1 if t is less than 32,768. This means that a codeword with two isolated errors that are next to each other or up to 32,768 bits apart can be detected by this generator.

2. Also in the context of single bit errors why we need to specifically have the coefficient of x^0 as 1, as I understand if there is more than one term in the generator polynomial g(x), we should be able to detect any single bit errors. Isn't it should be enough to have any two terms in the generator (x^i + x^j, i and j not equal to zero and i not equal to j) to detect any single bit error x^k?

Please tell me where am I going wrong.

Answer 1

The maximum message length guaranteed to detect a 2-bit error with x^15 + x^14 + 1 is 32767 bits. In the case of a 32768-bit message, if bit[32767] and bit[0] are in error, the CRC will be the same as for no errors.

If x^i is the lowest non-zero term and i != 0, then it's the same as a CRC with i fewer bits, left shifted i bits. This is unrelated to being able to detect a single bit error. For a non-reflected CRC, a left shifted CRC could be used by code meant for a larger CRC polynomial, followed by a right shift. For example, "left shift" x^15 + x^14 + 1 by 17 bits to x^32 + x^31 + x^17, and use that shifted polynomial with existing 32 bit CRC code (the initial CRC value would also need to be shifted left 17 bits), then after calculating the CRC, shift right by 17 bits to get the 15 bit CRC.

Answer 2

For your second question, yes, you only need two non-zero terms in the polynomial to detect a one-bit error. However as noted by @rcgldr, if the last non-zero term is not x⁰, i.e. 1, then the resulting CRC is equivalent to shifting the polynomial down so that 1 is the last non-zero term.

For example, a "CRC" polynomial x¹⁵+x⁹ results in a 15-bit "CRC" where the low nine bits are always zero, and where the high six bits are the actual CRC you get from the polynomial x⁶+1. I put CRC in quotes there, because for this reason a valid CRC polynomial must always have an x⁰ term. x¹⁵+x⁹ is not a valid CRC polynomial.

In the limit, the CRC polynomial x+1 results in a single-bit CRC that is the parity check of the bits in the message. That always detects a one-bit error. If that's all you want, then a parity check is all you need.