1
$\begingroup$

As I was working with a program for my CRC code calculation, I hit upon a situation where I had to divide two binary strings. Now, what I did was just convert the binary string to decimal format, did a modulo operation to find out the remainder.

But as it turns out, I am wrong in every single sample cases. For example, in this post, the dividend is 3664 and the divisor is 27.

Now, 3664 mod 27 is 19, which does not agree with the remainder presented in the figure which says it's 4.

Please help me out here.

Thanks in advance :)

$\endgroup$
  • $\begingroup$ The post you link to does not mention 3664. $\endgroup$ – marty cohen Dec 8 '16 at 19:12
  • $\begingroup$ yes, im sorry, the link of the post was wrong, now I fixed it. $\endgroup$ – Raghav Dec 9 '16 at 6:17
2
$\begingroup$

Short answer: don't do that. The CRC calculation is not division of one number by another, and if you try to treat it as such (by converting to decimal and doing ordinary division on the decimal numbers) you will usually get the wrong answer.


Long answer:

The CRC calculation represents the incoming data as a polynomial whose coefficients are in $\mathbb Z/2\mathbb Z$, that is, the coefficients are integers modulo $2$, which have the subtraction rules \begin{align} 0 - 0 \equiv 0 \pmod 2 \\ 1 - 0 \equiv 1 \pmod 2 \\ 1 - 1 \equiv 0 \pmod 2 \\ 0 - 1 \equiv 1 \pmod 2 \\ \end{align} The last equation is the one that makes it impossible to treat the XOR "division" algorithm the same as division of one multiple-digit binary number by another.

So a string of binary bits in this algorithm is never treated as a binary number, that is, as a sum of powers of $2$. Instead it is treated as a polynomial, a sum of powers of $x$. The rightmost bit is the constant term of our polynomial; the bit to the left of that is the coefficient of $x$, the next bit to the left is the coefficient of $x^2$, and so forth.

For example, suppose the bits of our divisor are $1011$ as in the example on the Wikipedia page. We do not treat these bits as a number (whose value would be eleven); instead, we treat the bits $1,1,0,1$ as coefficients of the polynomial $1x^3+0x^2+1x+1 = x^3+x+1$ modulo $2$.

Now to make this a very simple example, suppose the incoming message is not $11010011101100,$ as in Wikipedia's example, but instead is $00000000000001.$

The first step of the algorithm is to pad the message to $00000000000001000,$ which will be treated as the polynomial $1x^3+0x^2+0x+0 = x^3$ modulo $2.$ Now the synthetic division of $x^3$ by $x^3+x+1$ looks like this modulo $2$: \begin{align} 1 &\\ 1x^3+0x^2+1x+1\ \overline{)\ 1x^3 +0x^2+0x+0} &\\ \underline{1x^3+0x^2+1x+1} \\ 1x + 1 \end{align}

Notice that we used the rule $0 - 1 \equiv 1 \pmod 2$ for the last two terms on the right, that is, we used the fact that $-1\equiv1 \pmod2.$ Another way to write this is: $$ x^3 - (x^3+x+1) = x^3 - x^3 - x - 1 = -x - 1 \equiv x + 1 \pmod 2. $$ The remainder of the division is the polynomial $x+1$, which gives us the CRC bits $011.$

But notice that if you try to view the dividend and divisor as numbers and the CRC bits as the remainder when dividing one number by another, the result above makes no sense at all. The dividend is the number eight, the divisor is eleven, and therefore the remainder should just be eight again (since the divisor is greater than the dividend). But the CRC bits appear to be the number three! (Notice that this result is just as nonsensical for binary numbers as for decimal numbers, which is one reason I wrote the names of the numbers in English rather than using their decimal representations.)


Incidentally, there is a very good reason not to use an algorithm that would be equivalent to division of numbers: division of numbers is a very expensive operation compared to the XOR "division" algorithm, even if all we want is the remainder and we ignore the quotient. In fact, division of one number by another is one of the most time-consuming of the "simple" arithmetic operations on a computer. (The exception is division by a power of $2,$ which is very fast but would be useless in a CRC-like algorithm.)

By using the XOR algorithm, a computer can process a long stream of incoming data while using a lot less of its resources than would otherwise be required, leaving those resources free to do something else. If the CRC check is performed by specialized hardware, that hardware can be far simpler than it would have had to be if it needed to find the remainder of a numerical division.

$\endgroup$
  • $\begingroup$ Thank you very much. Helped me realize where I went wrong. Thank you :) $\endgroup$ – Raghav Dec 9 '16 at 16:07
  • $\begingroup$ Thank you, thank you very much. I have a homework on this but I can't understand why we can use XOR for this. This answer finally clears that for me. $\endgroup$ – Tung Nguyen Nov 16 '18 at 12:55
-1
$\begingroup$

Aha!

Here is the part you mean:

11010011101100 000 <--- input right padded by 3 bits

1011 <--- divisor (4 bits) = x³ + x + 1

If you convert 110100111011000 from binary, you get 27096.

If you convert 110100111011 from binary, you get 3387, not 3664, which is 11100101000 in binary.

$\endgroup$
  • $\begingroup$ I'm still not sure where you're getting at. For example, 11010011101100 000 = 108384. 1011 = 11 therefore, 108384 mod 11 = 1. But in the wikipedia the remainder is 4. $\endgroup$ – Raghav Dec 9 '16 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.