Sorry, I just saw it today.
Let me briefly talk about CRC related concepts, and then start to solve the problem.
1, the polynomial form is related to the binary form, and the factors correspond.
For example, in the problem, the sending polynomial is x1+x 8+x 7+x 6+x 4+x 3+x 2+1,
Namely: 211+28+27+26+24+23+22+1,
So the corresponding binary form is:10011111,
The transmission polynomial here means that the original data has not undergone CRC check operation,
2. Similarly, the CRC generator polynomial also corresponds to a set of binary numbers.
For example, the generating polynomial of CRC is: x 4+x 2+x1+1,
Namely: 2 4+2 2+2 1+ 1,
The corresponding binary is:10111,
The generator polynomial is artificially specified and has no fixed value. It can be specified as x 4+x 3+x 2+x 1+ 1, that is,11.
3. The binary form of the sending polynomial is:10011111,which is our original data.
The binary form of CRC generator polynomial is:10111. We will use it and the original data to operate according to CRC rules, and after CRC check, we will get the CRC code of the original data we want to transmit on the line.
The simple understanding is that we need to generate a polynomial through a given CRC and calculate a series of binary numbers with CRC check from the original data. We call this string of binary numbers with CRC check the CRC code of the original data, that is, the CRC code of transmission polynomial in the title.
4. The next step is CRC calculation rules.
The binary form of the transmit polynomial is shifted to the left (the exponent of the highest power of the CRC generator polynomial). The highest power of the CRC generating polynomial is x 4, so the sending polynomial should be shifted to the left by 4 digits.
The calculation is as follows:
100 1 1 10 1 1 10 1 *? 2^4
= 100 1 1 10 1 1 10 1 0000,
In this way, after calculation, there are four zeros on the right side of the original data, which means there are four spaces. In the future, the calculated CRC codes will be placed in these four vacant spaces, and the 4-digit CRC codes will be filled in the four parking spaces that have moved out.
According to the CRC rule, the binary form of deformed transfer polynomial is used:10011kloc-0/10000. Remove the binary form of the polynomial generated by CRC: 1065400.
Please note that the division used here is not the division in the field of mathematics, but the calculation method of modular division in the computer, which is actually XOR operation. The actual operation method is to align two high-order numbers, that is, to the left, and then perform bitwise XOR. If they are the same, the result is 0, if they are different, the result is 1, and then the obtained number is divided by the divisor (that is, the generating polynomial) until the final remainder is obtained. We operate according to the CRC check rule, which is usually endless. This remainder is the CRC check code we need. Combining this CRC check code with the deformed original data (that is, the original data with four zeros on the right) according to CRC rules is the final answer.
The calculation steps are as follows:
100 1 1 10 1 1 10 10000/ 10 1 1 1
…………………………………………
1001111010000 dividend, original data after deformation,
1011divisor, CRC generator polynomial.
—————————
001001011010000 quotient. Then continue to divide by CRC to generate polynomial:10111.
…………………………………………
100 10 1 1 10 10000? Dividend, the quotient from the last operation,
10 1 1 1? divisor
————————
00 10 1 1 1 10 10000? Quotient, the next step is to divide by CRC to generate a polynomial:1011.
……………………………………………
10111010000 dividend, that is, the quotient obtained in the previous step.
1011divisor
———————
00000 10 10000 quotient
………………………………………………
10 10000 divider
1011divisor
———
000 1 100 remainder (also the quotient obtained in the last operation, because the number of digits is less than 5, so you can't divide by 4 digits? 1 100 cannot generate polynomial 10 1 1 with 5-bit CRC, so this quotient is called remainder. )
According to the CRC check operation rules, the CRC check code obtained after the last operation is 1 100, and the original data after deformation is10011065438.
The calculation process is as follows:
100 1 1 10 1 1 10 10000+ 1 100
………………………………………………
100 1 1 10 1 1 10 1? 0000
+ ? 1 100
——————————
100 1 1 10 1 1 10 1? 1 100
What needs to be explained here is that only by understanding the rules of CRC coding can you calmly deal with such problems in the future. My advice to you is to do more questions, preferably with correct answers, so that in the process of doing the questions, you will deepen your understanding of CRC coding.
Finally, let's review the rules of CRC coding.
1, the original data polynomial, we generally call it: C(X), also called m(x),
2. Generate polynomial? Generating polynomial, we generally call it: G(x).
3.CRC check code, which we generally call:? r(x)，
4. We first remove G(x) from deformed C(X) to get r(x), and then combine the deformed C(X) and r(x) to get the CRC code with CRC check that we finally need.
Here I want to say again why the highest power of the generating polynomial is a few digits, and the last remainder is a few digits.
For example, in this example, the generating polynomial is: x 4+x 2+x1+1,and the final remainder is 4 digits 1 100.
This rule can be deduced,
First, rewrite 1 in the generator polynomial into x 0, and? x^4+x^2+x^ 1+x^0，
Obviously, the exponent starts from 0. Although there is an exponent 3 in the middle that is not written in the generator polynomial because the value of the weight is 0, in the binary form of the generator polynomial, the weight is the number 0, which is not the point.
The key is that we can see at a glance that the index starts from 0, not from 1 Therefore, taking this topic as an example, when the highest power of the generator polynomial is X 4, that is, the exponent is 4, there must be a 4-bit binary number on the right side of the power, because the power of the power determines that the generator polynomial must be a 5-bit binary number, and the power of the highest power is 4.
Combined with the description at the beginning, the original value should be multiplied by 2 to generate the highest power of polynomial, that is, how many bits should the original value be shifted to the left to make the remainder.
There is also a very clever place, because in the binary form of the generator polynomial, the highest bit must be 1. Therefore, after XOR with the original value plus 0, the number of digits of the final remainder must be less than that of the binary form of the generated polynomial. In this case, the generating polynomial is:
x^4+x^2+x^ 1+ 1
The corresponding binary form is:
10 1 1 1
Therefore, no matter what combination of the original values is, as long as it is1011left-aligned, the highest bit must become 0 because of XOR operation, so the binary digits of the final remainder must be less than the binary digits of the generator polynomial.
Combine again, the index starts from 0,
Therefore, the number of digits of the remainder can be determined by generating the highest power of the polynomial.