# 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
20,057
5,644
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
20,057
5,644
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
20,057
5,644
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
20,057
5,644
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.