CRC16-CCITT for shipborne AIS

I am trying to decode an AIS transmission and validate it by checking CRC code. However, I am not sure of the sequence of steps, nor the expected result. My question is, can anyone tell me the correct sequence of steps to use CRC to validate an AIS packet?

I am following the link layer sequence on page 2 of this guide, in reverse order: https://fidus.com/wp-content/uploads/2016/03/Guide_to_System_Development_March_2009.pdf

my steps are:

1. get stream of bits from FM demodulator
2. NRZI decode
3. find the start and stop flags and extract the data packet between them
4. remove stuffing bits from the data packet
5. split the packet into bytes and reverse each byte, so that bit 0 becomes bit 7.
6. take 16 bits CRC off the end of the packet.

Then I expect that one of these things will be true:

• CRC calculated on the packet (data only) matches the received CRC code.
• CRC calculated on the packet (data + received CRC) produces a constant product if the message was valid. All valid messages produce the same product. According to the source code of RTL-AIS, the product is 0x0f47.

however I have not been able to get a result that matches any expectation, and I also can't get two messages to make the same output even if I'm certain they are both valid.

I am using CRC-16 CCITT with polynomial 0x8408 and initial fill 0xFFFF. I have taken these parameters also from the source code of RTL-AIS. I tried to learn more from this resource, but it is densely written and without comments, and i cannot understand it. I am not sure if the CRC process itself involves further reversals.

I've tried the CRC process on data from other sources that I can find, with no luck. (https://www.dsprelated.com/showthread/comp.dsp/79522-1.php shows their data and claims success, as well as explaining the bit order reversal, but I cannot replicate it).

The data from that post is: 000010000000000010111001011100000010101010111110111011101100110001110101001111100110000010001101011110110001000011000110111011001000000100000011100000000000001100011000

the checksum is: 1110100000011111

using this online CRC tool, https://crccalc.com/, I have not been able to arrive at that same result. Can anyone show me how to do it?

Cheers to rcgldr for teaching me about the final XOR value!

I used this CRC calculator online: http://www.sunshine2k.de/coding/javascript/crc/crc_js.html

I used CRC-16 with no input reflection, no result reflection, polynomial 0x1021, initial fill 0xFFFF, final XOR value 0xFFFF.

Regarding the sequence of steps, this calculation must be performed on bits straight out of the unstuffer- before any bit or byte order change is applied.

These parameters, on the data from my question, produces CRC result 0xE81F which matches the checksum in my question.

Polynomial 0x1021 comes from the specification for CRC16-CCITT.

In the RTL-AIS source code, and other projects which inherit from it, polynomial 0x8408 is used along with some unknown sequence of changes to bit and byte order. It remains a mystery to me. To the reader in future, I would advise copying what I have done here, as it is much more straightforward!

Thanks again, I have been battling against this problem for weeks.