Why using Generator polynomial like this x^8 +x^2 +x+1 for CRC-8?

Question

Why using Generator polynomial like this G(x) =x^8 +x^2 +x+1 for CRC-8. If this is optimal How can we prove it. or using this Polynomial G(x) = x^5 + x^4 + x^2 + 1 for CRC-5-ITU.

Answer 1

The polynomial chosen determines the error detection capability of the CRC. This capability is measured in Hamming Distance, which is the minimum number of bit errors that can be introduced in the message while leaving the CRC unchanged. This would be a false positive, where the CRC says the message is ok, but it isn't. Also important is how many such bit patterns exist at each number of bit errors, called the Hamming Weight. This determines the probability than an error of n bits results in a false positive.

Exhaustive searches over all possible polynomials have been done by Koopman, et al, to find the those with the largest Hamming Distances and smallest Hamming Weights for various message lengths. As an example, the degree-8 polynomial you quote, used in the ITU-T Recommendation I.432.1 CRC, is good, but not the best you could pick. The polynomial x⁸+x⁶+x³+x²+1 provides a Hamming Distance of 3 for longer messages. These two pages provide Koopman's most recent results.

Another answer here suggests that "the optimal polynomial depends on the input data set used." The only aspect of the data that the error detection capability of a CRC polynomial depends on is the length of the block on which the CRC is applied. Due to the linearity property of CRC's, the error detection capability is in fact completely independent of the data in the message. If you exclusive-or two messages of the same length, then the CRC of that new message will be the exclusive-or of the CRC's of the original two messages. So once you find the minimum set of errors that leave the CRC unchanged, then that set of errors can be applied to any message of the same length to get a false-positive.