Question

Find a 13-bit burst error polynomial that cannot be detected by the CRC-8 check. The burst error polynomial must have the form E(x) = x^12 + … + 1, and the terms x^k for k = 1, 2, …, 11 can have a coefficient of either 0 or 1. Here is a 13-bit burst error polynomial that can be detected: x^12 + x^8 + x^2 + x + 1. The CRC-8 generator polynomial is x^8 + x^2 + x + 1. (By a 13-bit burst error we mean that there has been a burst of energy that causes noise on the communication channel during the span of 13 bits. For example, the energy may drive the voltage to a high value for all 13 bits. Some of those bits might have been 1’s (and represented by the high voltage), so the energy does not cause those bits to be in error. So, assume the first and thirteenth bits are incorrect, and the bits in between those two end points may or may not be in error.)

Answer 1

As per the question, we have the following fields:

Let us understand how error detection with CRC occurs: Let

• M(x) = message
• G(x) = generator polynomial
• C(x) = checksum generated by the polynomial
• T(x) = message transferred with checksum

1. Multiply M(x) with the highest power of G(x).
2. Divide the result by G(x) to generate remainder C(x).
3. Transmit message by adding C(x) to the result obtained in step 1.
   
4. Receiver receives T(x) and divides by G(x).
5. If the remainder is zero, there is no error.

This is simply because a multiple of M(x) divided by G(x) gives remainder C(x). So when we add C(x) to the multiple of M(x), the division by G(x) would result in no remainder.

Now if during transmission, any error E(x) is added to T(x)

will not give remainder zero. Thus, an error would be detected.

Now, there is a catch, what if E(x) would itself be a multiple of G(x)? In such a case, the remainder would be zero again and thus the error would go undetected.

If E(x) is a multiple of G(x), the error will not be detected.

Find a 13-bit burst error polynomial that cannot be detected by the CRC-8 check

Now, all we need to do is find an E(x) of the form , which is also a multiple of our G(x). The easiest way to do this is to divide by , which is our G(x). The remainder then can be added to E(x) and we would get our undetectable E(x).

The whole division is attached in the pic below. Note that the whole division follows modulo 2 process.

Thus our undetectable burst error is :

Cheers! Feel free to ask more.