I'm trying to understand how to calculate CRC (Cyclic Redundancy Codes) of a message using polynomial division modulo 2. The textbook Computer Networks: A Systems Approach gives the following rules for division:
Any polynomial $B(x)$ can be divided by a divisor polynomial $C(x)$ if $B(x)$ is of higher degree than $C(x)$.
Any polynomial $B(x)$ can be divided once by a divisor polynomial $C(x)$ if $B(x)$ is of the same degree as $C(x)$.
The remainder obtained when $B(x)$ is divided by $C(x)$ is obtained by performing the exclusive OR on each pair of matching coefficients.
For example: the polynomial $x^3 +1$ can be divided by $x^3 + x^2 + 1$ because they are both of degree 3. We can find the remainder by XOR the coefficients: $1001 \oplus 1101 = 0100$ and the quotient is obviously 1.
Now, onto long division - and the source of my confusion. The book says: "Given the rules of polynomial division above, the long division operation is much like dividing integers. We see that the division $1101$ divides once into the first four bits of the message $1001$, since they are of the same degree, and leaves the remainder $100$. The next step is to bring down a digit from the message polynomial until we get another polynomial with the same degree as $C(x)$, in this case, $1001$. We calculate the remainder and repeat until the calculation is complete.
So, given an example where I want to divide $010000$ by $1101$ where I know in advance that the quotient is $011$.
0 ________ 1101 | 010000 // 1101 does not divide 0100. 1101 01 ________ 1101 | 010000 1101 // Bring down a digit from the right so we get the same degree as C(x). ---- // 1101 divides into 1000 as they have the same degree. 1010 // Now XOR to find the remainder. Bring down the zero. 011 ________ 1101 | 010000 1101 ---- 1010 // Now XOR to find the remainder. Bring down the zero. 1101 // 1101 divides 1010. 011 ________ 1101 | 010000 1101 ---- 1010 1101 ---- 111 // The remainder is 111.
Would this be correct based on the algorithm above?