CODEWITHSUNDEEP
algorithmxorbitcrcpolynomial-math
George Irimiciuc
George Irimiciuc

Reputation: 4633

CRC polynomial calculation

I am trying to understand this document, but can't seem to get it right. http://www.ross.net/crc/download/crc_v3.txt

What's the algorithm used to calculate it?

I thought it uses XOR but I don't quite get it how he gets 0110 from 1100 XOR 1001. It should be 101 (or 0101 or 1010 if a bit goes down). If I can get this, I think the rest would come easy, but for some reason I just don't get it.

    9= 1001 ) 0000011000010111 = 0617 = 1559 = DIVIDEND
DIVISOR   0000.,,....,.,,,
          ----.,,....,.,,,
           0000,,....,.,,,
           0000,,....,.,,,
           ----,,....,.,,,
            0001,....,.,,,
            0000,....,.,,,
            ----,....,.,,,
             0011....,.,,,
             0000....,.,,,
             ----....,.,,,
              0110...,.,,,
              0000...,.,,,
              ----...,.,,,
               1100..,.,,,
               1001..,.,,,
               ====..,.,,,
                0110.,.,,,
                0000.,.,,,
                ----.,.,,,
                 1100,.,,,
                 1001,.,,,
                 ====,.,,,
                  0111.,,,
                  0000.,,,
                  ----.,,,
                   1110,,,
                   1001,,,
                   ====,,,
                    1011,,
                    1001,,
                    ====,,
                     0101,
                     0000,
                     ----
                      1011
                      1001
                      ====
                      0010 = 02 = 2 = REMAINDER

Upvotes: 0

Views: 1501

Answers (2)

Vincent van der Weele
Vincent van der Weele

Reputation: 13187

The link you provided says:

we'll do the division using good-'ol long division which you learnt in school (remember?)

You just repetitively subtract, but since it is in binary, there are only two options: either the number fits once in the current selection, or 0 times. I annotated the steps:

0000011000010111
0000
1001             x  0
---- -
 0000
 1001            x  0
 ---- -
  0001
  1001           x  0
  ---- -
   0011
   1001          x  0
   ---- -
    0110
    1001         x  0
    ---- -
     1100       
     1001        x  1
     ---- -
      0110
      1001       x  0
      ---- -
       1100
       1001      x  1
       ---- -
        0110

and so on

Upvotes: 1

interjay
interjay

Reputation: 110191

The part you quoted is just standard long division like you learned in elementary school, except that it is done on binary numbers. At each step you perform a subtraction to get the remainder, and this is done in the example you gave: 1100 - 1001 = 0110.

Note that the article just uses this as a preliminary example, and it is not actually what is done in calculating CRC. Instead of normal numbers, CRC uses division of polynomials over the field GF(2). This can be modeled by using normal binary numbers and doing long division normally, except for using XOR instead of subtraction.

Upvotes: 2

Related Questions