Hi, I'm having a hard time calculating a CRC remainder value.

Can someone tell me what am I doing wrong here? According to the online calculator, the answer is $14 but I am coming up with 100100 or 1001000?

Thank you.

https://ghsi.de/CRC/index.php?Polynom=100010011&Message=53D2

  |--53--||--D2--|   (hex)
  %0101001111010010  
  
  000000000_0101001111010010  start  
  000000000_101001111010010  shift the bitstream left until bit 8 of the working register is set  
  000000001_01001111010010  shift  
  000000010_1001111010010  shift  
  000000101_001111010010  shift  
  000001010_01111010010  shift  
  000010100_1111010010  shift  
  000101001_111010010  shift  
  001010011_11010010  shift  
  010100111_1010010  shift  
  101001111_010010  shift - bit 8 is set  101001111  
  100010011  xor with the polynomial: 100010011  
  001011100_010010  result  = 001011100  
  101110001_0010  shift - bit 8 is set  
  100010011  xor  
  001100010_0010  result  
  110001000_10  shift - bit 8 is set  
  100010011  xor  
  010011011_10  result  
  100110111_0  shift - bit 8 is set  
  100010011  xor  
  000100100_0  result - all bits are shifted
  001001000  shift - out of bits

 

Just knowing that you are performing a CRC is not enough since CRC involves a polynomial. Are you sure that you and the calculator you are using are using the same polynomial? My guess based on your URL is that you are and that this is not your problem, but best to confirm.

Try working with a simpler input, such as one or two bits, and see if you get the same result. Then build up a few bits at a time and see if and when your results start diverging from the calculator.


These references might help:

http://en.wikipedia.org/wiki/Cyclic_redundancy_check

http://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks

 

Hi,

The other ones that I've tried by hand I have calculated it correctly, but this one I cannot seem to get right. That calculator has a poly input and therefore is using the same poly that I am using. There has to be some rule that I don't know about, which is causing this. I've read the wiki pages a few times.

 

FYI, I had to append a 0 byte to the end of it

| --53-- ||--D2--| (hex)
%0101001111010010

Should have been

| --53--||--D2--||--00--|  (hex)
%010100111101001000000000

And then the calculations will work out

 

Why did you have to do that?

Added: Hint: They key is that you are looking for the remainder after dividing the message by the polynomial.

 

I'm not really sure? Maybe it's similar to significant digits in that it represents how many binary decimal values you want left over?

I'm having a hard time with 0101001111010010110010000000000011101001 divided by 100000100, it should equal 11001100 but I cannot get that to work out mathematically?

Any ideas what I've done wrong here?

Why did you have to do that?

Added: Hint: They key is that you are looking for the remainder after dividing the message by the polynomial.

0101001111010010110010000000000011101001
 100000100
 001001011010010110010000000000011101001
  100000100
  0001010010010110010000000000011101001
  100000100
  0010001010110010000000000011101001
  100000100
  00001000110010000000000011101001
  100000100
  0000101010000000000011101001
  100000100 *******
  001001100000000011101001
  100000100
  0001011000000011101001
  100000100
  0010111000011101001
  100000100
  00110110011101001
  100000100
  010101111101001
  100000100
  00101101101001
  100000100
  001101001001
  100000100
  0101000001
  100000100
  000111101


  or
   
   
0101001111010010110010000000000011101001 00000000
 100000100
 001001011010010110010000000000011101001 00000000
  100000100
  0001010010010110010000000000011101001 00000000
  100000100
  0010001010110010000000000011101001 00000000
  100000100
  00001000110010000000000011101001 00000000
  100000100
  0000101010000000000011101001 00000000
  100000100 *******
  001001100000000011101001 00000000
  100000100
  0001011000000011101001 00000000
  100000100
  0010111000011101001 00000000
  100000100
  00110110011101001 00000000
  100000100
  010101111101001 00000000
  100000100
  00101101101001 00000000
  100000100
  001101001001 00000000
  100000100
  0101000001 00000000
  100000100
  000111101 00000000
  100000 100
  011100 10000000
  10000 0100
  01100 01000000
  1000 00100
  0100 00100000
  100 000100
  000 00010000
  100000100

 

Or another way that is still wrong? (for some reason it will not keep my formatting from the location that I am doing it, I am sorry about that)

0101001111010010110010000000000011101001 00000000
100000100
001001011010010110010000000000011101001 00000000
  100000100
  0001010010010110010000000000011101001 00000000
  100000100
  0010011010110010000000000011101001 00000000
  100000100
  00011000110010000000000011101001 00000000
  100000100
  01000100010000000000011101001 00000000
  100000100
  0000101010000000000011101001 00000000
  100000100
  001010100000000011101001 00000000
  100000100
  0010101000000011101001 00000000
  100000100
  00101010000011101001 00000000
  100000100
  001010100011101001 00000000
  100000100
  0010101011101001 00000000
  100000100
  00101001101001 00000000
  100000100
  001001001001 00000000
  100000100
  0001000001 00000000
  1000001 00
  0000000 00000000

 

Another way with more readable formatting, still wrong I believe and I don't know why

  000000000_0101001111010010110010000000000011101001
  000000000_101001111010010110010000000000011101001
  000000001_01001111010010110010000000000011101001
  000000010_1001111010010110010000000000011101001
  000000101_001111010010110010000000000011101001
  000001010_01111010010110010000000000011101001
  000010100_1111010010110010000000000011101001
  000101001_111010010110010000000000011101001
  001010011_11010010110010000000000011101001
  010100111_1010010110010000000000011101001
  101001111_010010110010000000000011101001
  100000100
  001001011_010010110010000000000011101001
  100101101_0010110010000000000011101001   
  100000100
  000101001_0010110010000000000011101001
  101001001_0110010000000000011101001
  100000100
  001001101_0110010000000000011101001
  100110101_10010000000000011101001
  100000100
  000110001_10010000000000011101001
  110001100_10000000000011101001
  100000100
  010001000_10000000000011101001
  100010001_0000000000011101001  
  100000100
  000010101_0000000000011101001
  101010000_000000011101001
  100000100
  001010100_000000011101001
  101010000_0000011101001
  100000100
  001010100_0000011101001
  101010000_00011101001
  100000100
  001010100_00011101001
  101010000_011101001
  100000100
  001010100_011101001
  101010001_1101001
  100000100
  001010101_1101001
  101010111_01001
  100000100
  001010011_01001
  101001101_001   
  100000100
  001001001_001
  100100100_1
  100000100
  000100000_1
  100000100
  100000100
  000000000

 

Okay, are we talking about dividing one polynomial into another, or dividing one binary value into another -- they are NOT the same thing!

For instance, if we are talking numbers, then 1101 divided by 101 is 10 with a remainder of 11 (i.e., 13 divided by 5 is 2 r 3).

But if these are polynomials, then 1101 represents x^3 + x^2 + 1 and 101 represents x^2 + 1. Dividing these (modulo 2) we get x+1 r x, or 11 r 10.

 

I'm not really sure? Maybe it's similar to significant digits in that it represents how many binary decimal values you want left over?

Nope, but that's not a bad guess.

What we are doing when we compute a CRC and add it to a message is we append the CRC value to the end of the message to get the transmitted message. If the original message is represented by a polynomial, then what we are doing is multiplying the original message by x^n where n is the length of the CRC value and then adding on the CRC polynomial. The intent is to make the transmitted message evenly divisible by the divisor polynomial.

To actually compute the CRC remainder polynomial, we are simply leveraging the fact that, modulo 2, addition is the same as subtraction.

So tacking on n zero bits is nothing more than multiplying the message polynomial by x^n.

I'm having a hard time with 0101001111010010110010000000000011101001 divided by 100000100, it should equal 11001100 but I cannot get that to work out mathematically?

Any ideas what I've done wrong here?

Okay, since the result would be MUCH bigger than 8 bits if this were integer division, I will assume you are still talking about polynomial division.

I get a CRC of zero:

0101001111010010110010000000000011101001_00000000
 100000100
 001001011010010110010000000000011101001_00000000
   100000100
   0001010010010110010000000000011101001_00000000
      100000100
      0010011010110010000000000011101001_00000000
        100000100
        00011000110010000000000011101001_00000000
           100000100
           01000100010000000000011101001_00000000
            100000100
            0000101010000000000011101001_00000000
                100000100
                001010100000000011101001_00000000
                  100000100
                  0010101000000011101001_00000000
                    100000100
                    00101010000011101001_00000000
                      100000100
                      001010100011101001_00000000
                        100000100
                        0010101011101001_00000000
                          100000100
                          00101001101001_00000000
                            100000100
                            001001001001_00000000
                              100000100
                              0001000001_00000000
                                 1000001_00
                                 0000000_00000000

To check this, all we need to do is recover the quotient and see if dividing the message by the quotient equals the divisor polynomial or, alternatively, if multiplying the quotient by the divisor polynomial (and adding the checksum remainder, if nonzero) yields the message. For the quotient, I get:

0101001010011000101010101010101001000000

               01010010100110001010101010101010_01000000
                                            x 1_00000100
-------------------------------------------------------- 
             0101001010011000101010101010101001_000000
+       101001010011000101010101010101001000000
========================================================
       0101001111010010110010000000000011101001_00000000

I checked using the calculator that you linked in your first post and I agree that it says the CRC value should be 11001100. But I'm not at all convinced that this is correct, since my result passes my test. But that doesn't mean that I'm not simply doing something wrong and that my check is merely consistent with my wrong approach. But it also could be that the online calculator you are using has a bug. I couldn't find another online calculator that let you enter an arbitrary polynomial, but I didn't look very hard.