Binary calculation problem

Discussion in 'Homework Help' started by gte, Oct 28, 2014.

  1. gte

    Thread Starter Active Member

    Sep 18, 2009
    347
    4
    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

    Code (Text):
    1.  
    2.   |--53--||--D2--|   (hex)
    3.   %0101001111010010  
    4.  
    5.   000000000_0101001111010010  start  
    6.   000000000_101001111010010  shift the bitstream left until bit 8 of the working register is set  
    7.   000000001_01001111010010  shift  
    8.   000000010_1001111010010  shift  
    9.   000000101_001111010010  shift  
    10.   000001010_01111010010  shift  
    11.   000010100_1111010010  shift  
    12.   000101001_111010010  shift  
    13.   001010011_11010010  shift  
    14.   010100111_1010010  shift  
    15.   101001111_010010  shift - bit 8 is set  101001111  
    16.   100010011  xor with the polynomial: 100010011  
    17.   001011100_010010  result  = 001011100  
    18.   101110001_0010  shift - bit 8 is set  
    19.   100010011  xor  
    20.   001100010_0010  result  
    21.   110001000_10  shift - bit 8 is set  
    22.   100010011  xor  
    23.   010011011_10  result  
    24.   100110111_0  shift - bit 8 is set  
    25.   100010011  xor  
    26.   000100100_0  result - all bits are shifted
    27.   001001000  shift - out of bits
    28.  
     
    Last edited: Oct 28, 2014
  2. WBahn

    Moderator

    Mar 31, 2012
    17,720
    4,788
    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
     
  3. gte

    Thread Starter Active Member

    Sep 18, 2009
    347
    4
    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.
     
  4. gte

    Thread Starter Active Member

    Sep 18, 2009
    347
    4
    FYI, I had to append a 0 byte to the end of it

    Code (Text):
    1.  
    2. | --53-- ||--D2--| (hex)
    3. %0101001111010010
    4.  
    Should have been

    Code (Text):
    1.  
    2. | --53--||--D2--||--00--|  (hex)
    3. %010100111101001000000000
    4.  
    And then the calculations will work out
     
  5. WBahn

    Moderator

    Mar 31, 2012
    17,720
    4,788
    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.
     
    Last edited: Oct 29, 2014
  6. gte

    Thread Starter Active Member

    Sep 18, 2009
    347
    4
    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?


    Code (Text):
    1.  
    2. 0101001111010010110010000000000011101001
    3.  100000100
    4.  001001011010010110010000000000011101001
    5.   100000100
    6.   0001010010010110010000000000011101001
    7.   100000100
    8.   0010001010110010000000000011101001
    9.   100000100
    10.   00001000110010000000000011101001
    11.   100000100
    12.   0000101010000000000011101001
    13.   100000100 *******
    14.   001001100000000011101001
    15.   100000100
    16.   0001011000000011101001
    17.   100000100
    18.   0010111000011101001
    19.   100000100
    20.   00110110011101001
    21.   100000100
    22.   010101111101001
    23.   100000100
    24.   00101101101001
    25.   100000100
    26.   001101001001
    27.   100000100
    28.   0101000001
    29.   100000100
    30.   000111101
    31.  
    32.  
    33.   or
    34.    
    35.    
    36. 0101001111010010110010000000000011101001 00000000
    37.  100000100
    38.  001001011010010110010000000000011101001 00000000
    39.   100000100
    40.   0001010010010110010000000000011101001 00000000
    41.   100000100
    42.   0010001010110010000000000011101001 00000000
    43.   100000100
    44.   00001000110010000000000011101001 00000000
    45.   100000100
    46.   0000101010000000000011101001 00000000
    47.   100000100 *******
    48.   001001100000000011101001 00000000
    49.   100000100
    50.   0001011000000011101001 00000000
    51.   100000100
    52.   0010111000011101001 00000000
    53.   100000100
    54.   00110110011101001 00000000
    55.   100000100
    56.   010101111101001 00000000
    57.   100000100
    58.   00101101101001 00000000
    59.   100000100
    60.   001101001001 00000000
    61.   100000100
    62.   0101000001 00000000
    63.   100000100
    64.   000111101 00000000
    65.   100000 100
    66.   011100 10000000
    67.   10000 0100
    68.   01100 01000000
    69.   1000 00100
    70.   0100 00100000
    71.   100 000100
    72.   000 00010000
    73.   100000100
    74.  
     
  7. gte

    Thread Starter Active Member

    Sep 18, 2009
    347
    4
    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)

    Code (Text):
    1.  
    2. 0101001111010010110010000000000011101001 00000000
    3. 100000100
    4. 001001011010010110010000000000011101001 00000000
    5.   100000100
    6.   0001010010010110010000000000011101001 00000000
    7.   100000100
    8.   0010011010110010000000000011101001 00000000
    9.   100000100
    10.   00011000110010000000000011101001 00000000
    11.   100000100
    12.   01000100010000000000011101001 00000000
    13.   100000100
    14.   0000101010000000000011101001 00000000
    15.   100000100
    16.   001010100000000011101001 00000000
    17.   100000100
    18.   0010101000000011101001 00000000
    19.   100000100
    20.   00101010000011101001 00000000
    21.   100000100
    22.   001010100011101001 00000000
    23.   100000100
    24.   0010101011101001 00000000
    25.   100000100
    26.   00101001101001 00000000
    27.   100000100
    28.   001001001001 00000000
    29.   100000100
    30.   0001000001 00000000
    31.   1000001 00
    32.   0000000 00000000
    33.  
    34.  
     
  8. gte

    Thread Starter Active Member

    Sep 18, 2009
    347
    4
    Another way with more readable formatting, still wrong I believe and I don't know why

    Code (Text):
    1.  
    2.  
    3.   000000000_0101001111010010110010000000000011101001
    4.   000000000_101001111010010110010000000000011101001
    5.   000000001_01001111010010110010000000000011101001
    6.   000000010_1001111010010110010000000000011101001
    7.   000000101_001111010010110010000000000011101001
    8.   000001010_01111010010110010000000000011101001
    9.   000010100_1111010010110010000000000011101001
    10.   000101001_111010010110010000000000011101001
    11.   001010011_11010010110010000000000011101001
    12.   010100111_1010010110010000000000011101001
    13.   101001111_010010110010000000000011101001
    14.   100000100
    15.   001001011_010010110010000000000011101001
    16.   100101101_0010110010000000000011101001  
    17.   100000100
    18.   000101001_0010110010000000000011101001
    19.   101001001_0110010000000000011101001
    20.   100000100
    21.   001001101_0110010000000000011101001
    22.   100110101_10010000000000011101001
    23.   100000100
    24.   000110001_10010000000000011101001
    25.   110001100_10000000000011101001
    26.   100000100
    27.   010001000_10000000000011101001
    28.   100010001_0000000000011101001  
    29.   100000100
    30.   000010101_0000000000011101001
    31.   101010000_000000011101001
    32.   100000100
    33.   001010100_000000011101001
    34.   101010000_0000011101001
    35.   100000100
    36.   001010100_0000011101001
    37.   101010000_00011101001
    38.   100000100
    39.   001010100_00011101001
    40.   101010000_011101001
    41.   100000100
    42.   001010100_011101001
    43.   101010001_1101001
    44.   100000100
    45.   001010101_1101001
    46.   101010111_01001
    47.   100000100
    48.   001010011_01001
    49.   101001101_001  
    50.   100000100
    51.   001001001_001
    52.   100100100_1
    53.   100000100
    54.   000100000_1
    55.   100000100
    56.   100000100
    57.   000000000
    58.  
     
  9. WBahn

    Moderator

    Mar 31, 2012
    17,720
    4,788
    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.
     
    Last edited: Oct 31, 2014
  10. WBahn

    Moderator

    Mar 31, 2012
    17,720
    4,788
    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.

    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:

    Code (Text):
    1.  
    2. 0101001111010010110010000000000011101001_00000000
    3.  100000100
    4.  001001011010010110010000000000011101001_00000000
    5.    100000100
    6.    0001010010010110010000000000011101001_00000000
    7.       100000100
    8.       0010011010110010000000000011101001_00000000
    9.         100000100
    10.         00011000110010000000000011101001_00000000
    11.            100000100
    12.            01000100010000000000011101001_00000000
    13.             100000100
    14.             0000101010000000000011101001_00000000
    15.                 100000100
    16.                 001010100000000011101001_00000000
    17.                   100000100
    18.                   0010101000000011101001_00000000
    19.                     100000100
    20.                     00101010000011101001_00000000
    21.                       100000100
    22.                       001010100011101001_00000000
    23.                         100000100
    24.                         0010101011101001_00000000
    25.                           100000100
    26.                           00101001101001_00000000
    27.                             100000100
    28.                             001001001001_00000000
    29.                               100000100
    30.                               0001000001_00000000
    31.                                  1000001_00
    32.                                  0000000_00000000
    33.  
    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

    Code (Text):
    1.  
    2.                01010010100110001010101010101010_01000000
    3.                                             x 1_00000100
    4. --------------------------------------------------------
    5.              0101001010011000101010101010101001_000000
    6. +       101001010011000101010101010101001000000
    7. ========================================================
    8.        0101001111010010110010000000000011101001_00000000
    9.  
    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.
     
Loading...