How to apply the CRC16 on a received bitstream? (Python)

Question

could anyone here help me understand, how I apply the CRC16 on the received string?

stream = [0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0]


rest = [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1]

https://pastebin.com/7CMtSEE6

I received this APRS message. I decoded it also with mutlimon directly and the I got the same ascii message as with my own PYTHON code. Inside the stream variable is the received message after removing the bitstuffing and before reversing the bit sequence of each byte.

What I tried so far, but did not work, was to apply the x^16+x^12+x^5+1 on it. I wanted to get the same "rest" as you can see it in the pastebin. This rest was also inside the stream but for better readability I put that to the other variable. Bits inside the rest were just copynpasted out, so they have the same order.

So, where in my train of thoughts am I wrong?
Be frankly with me and I would like to ask you to tell me step by step, because I need to "see" how it works to understand it better. That would be really helpful for me.

So starting first: stream = [0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, ...

I would now have the stream devided by the reverse of 0x11021

0,1,1,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,1,...
  1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1

---

0,0,1,0,0,0,1,1,0,1,0,0,0,0,0,1,0,1

Is that the correct start? Or do I have to reverse each set of bytes in the stream first?

Thank you in advance,

Andreas

This question is related to this one, but specifically around crc16... How to decode Bell 202 signal? (APRS data from International Space Station)

Answer 1

There are eleven CRC-16's in Greg Cook's catalog with that polynomial, and probably more that aren't in his catalog. So when you say "CRC-16", it could be a lot of different things.

Your binary data can be interpreted as bytes in two different ways, either most significant bit first, or least significant bit first. If the former, then the CRC in "rest" would be the CRC-16/GENIBUS. If the latter, then it is the X-25 CRC-16.

In both cases the CRC register is initialized with all 1's (0xffff), and at the end is inverted, i.e. exclusive-or'ed with 0xffff. It is that initialization and post-processing that you are probably missing in your attempt to replicate the CRC.

Here is some simple C code for the X-25 CRC-16, which would operate on your data assuming least significant bit first:

unsigned crc16x25(unsigned char *data, size_t len) {
    unsigned crc = 0xffff;
    while (len--) {
        crc ^= *data++;
        for (unsigned k = 0; k < 8; k++)
            crc = crc & 1 ? (crc >> 1) ^ 0x8408 : crc >> 1;
    }
    crc ^= 0xffff;
    return crc;
}

So if you feed that 0x86 0xa2 ... 0x47, you will get 0xec3f as the CRC.