CRC-16 and CRC-32

[SCPD]

I, along with other people that I have talked to before, have been confused regarding CRC-16 and CRC-32. I specifically don't know much about CRC except for doing some research on CRC's in different (smaller) bit lengths. I attempted to ask this question on StackOverflow awhile ago but it seems there wasn't enough information to go off of (see c# - CRC-16 and CRC-32 Checks - Stack Overflow).

After reading the specifications in TIA-102.BAAA-A, I see functions with GH(x) and IH(x) with a combined result of FH(x) but I still don't understand. Can anybody offer any help with understanding CRC-16 and CRC-32? I really want to understand CRC-16 first as most of the messages I'm dealing with are CRC-16. I am coding in C# (which is based on C/C++) so any code offered would be valuable (or even information so I can piece together).

I watched a video that showed how to calculate a CRC manually using a set of bits obtained from a polynomial but I don't know which polynomial to use when there are many.

I see GH(x) = x^16 + x^12 + x^5 +1. If I understand everything correctly that translates to 1000100000010000 or is that incorrect?

 

[DSheirer]

After reading the specifications in TIA-102.BAAA-A, I see functions with GH(x) and IH(x) with a combined result of FH(x) but I still don't understand. Can anybody offer any help with understanding CRC-16 and CRC-32? I really want to understand CRC-16 first as most of the messages I'm dealing with are CRC-16. I am coding in C# (which is based on C/C++) so any code offered would be valuable (or even information so I can piece together).

I watched a video that showed how to calculate a CRC manually using a set of bits obtained from a polynomial but I don't know which polynomial to use when there are many.

Good luck understanding the math. I bought the book Error Correcting Codes 2e and ended up with a severe headache. If you're just trying to implement the CRC in code, there's a practical approach. Assuming that you're dealing with fixed-length messages, pre-calculate the CRC checksum for each bit position in your message and store those values in a lookup table. Create a message of all zeros and set the first message bit position to one and then calculate the CRC. Put that value in your CRC lookup table for bit position one. Repeat the process for all message bit positions. Your CRC-16, using the 17-bit polynomial should generate 16-bit CRC checksums. The wikipedia entry (Computation of CRC section) offers a pretty good explanation/example of how to calculate the CRC:

Cyclic redundancy check - Wikipedia, the free encyclopedia

When you want to check a message, start with a fill value of all zeros for your running checksum. For each bit in the message that is set to a one, XOR the corresponding checksum from your lookup table for that bit position to your running checksum. When you're done, the running checksum result should match the CRC value that was transmitted with the message.

A variation is to apply the lookup table checksum values against the original message checksum and at the end you should have all zeros. This approach helps when you're trying to figure out the initial fill value when they're using a non-zero fill value ...

Sometimes they use a non-zero initial fill value, instead of all zeros. LTR-Passport uses three initial fill values (0x0, 0x89 and 0x98) so that they can send trunking control messages for voice (0 value) and data messages like Fleetsync GPS with the other (0x89 value) to allow the receiving radio to distinguish between the traffic types. If the CRC checksum doesn't pass, the receiver throws away the message, thereby making it only listen for the correct message that it's interested in.

... but I don't know which polynomial to use when there are many.

You can reverse-engineer the polynomial if you have enough messages. Collect enough messages where you have lots of repeats so that you have a higher-confidence level that the messages are not just random messages. Find two messages that differ only in the final message bit like:

(48-bit message, 16-bit crc)
Message 1: 110001010011110010001001000101010011001100110011 1001100110000110
Message 2: 110001010011110010001001000101010011001100110010 1001100110100111
Difference: 000000000000000000000000000000000000000000000001 0001000000100001

The XOR difference value, including the final message bit, is the generator polynomial. You can then use the polynomial to recreate the entire lookup table.

Not all CRC algorithms are straight forward like this. LTR-Standard CRC checksums don't seem to follow a normal polynomial generated table. However, you can reverse-engineer the lookup table following the same approach. It's painful but, collect enough messages and you can use the same approach as above to find the CRC difference value for each bit position. Just use the XOR difference value (excluding the message bit) as the lookup value for that bit position, in your table.

I see GH(x) = x^16 + x^12 + x^5 +1. If I understand everything correctly that translates to 1000100000010000 or is that incorrect?

Don't forget the +1 at the end which represents the x^0 term (any number to zero power is 1). The binary polynomial representation should be one bit longer than your CRC type. Your CRC16 polynomial is 17-bits long.

10001000000100001

Denny

 

[SCPD]

Thank you Denny! I'll see where I end up with this!

Sent from my SPH-L710 using Tapatalk 4

 

[aharry]

Try this

        static bool crc16(ref byte[] data)
        {
            uint polynom = 0x1021;
            uint crc = 0xc921;
            uint i, j, bit;
            uint crcin = (uint)((data[10] << 8) | data[11]);

	        for (i=0; i<10; i++) {
	            for (j=0x80; j!=0; j>>=1) {
		        bit = crc & 0x8000;
		        crc <<= 1;
                    if ((data[i] & j) != 0) 
                        bit ^= 0x8000;
                    if (bit !=0 ) 
    		        crc^= polynom;
		        }
	        }	

	        crc &= 0xFFFF;
	        return (crc ^ crcin)!=0 ? false: true;
        }

Pass it the 12 bytes as a byte array and it will return true or false:

byte[] data = { 0x06, 0x00, 0x05, 0x4B, 0x0F, 0x52, 0x9D, 0x0F, 0x52, 0xE1, 0x90, 0x75};

bool crc_ok = crc16(ref data);

 

[SCPD]

Try this

        static bool crc16(ref byte[] data)
        {
            uint polynom = 0x1021;
            uint crc = 0xc921;
            uint i, j, bit;
            uint crcin = (uint)((data[10] << 8) | data[11]);

	        for (i=0; i<10; i++) {
	            for (j=0x80; j!=0; j>>=1) {
		        bit = crc & 0x8000;
		        crc <<= 1;
                    if ((data[i] & j) != 0) 
                        bit ^= 0x8000;
                    if (bit !=0 ) 
    		        crc^= polynom;
		        }
	        }	

	        crc &= 0xFFFF;
	        return (crc ^ crcin)!=0 ? false: true;
        }

Pass it the 12 bytes as a byte array and it will return true or false:

byte[] data = { 0x06, 0x00, 0x05, 0x4B, 0x0F, 0x52, 0x9D, 0x0F, 0x52, 0xE1, 0x90, 0x75};

bool crc_ok = crc16(ref data);

I don't know how to thank you enough aHarry! It works perfectly and will be very useful for me and others that have a hard time grasping CRCs. I don't want to ask for too much but would you also have one for the CRC-32 messages that pop up on MBTs? This code is great for me to reverse and start to understand CRCs!

 

[aharry]

I don't know how to thank you enough aHarry! It works perfectly and will be very useful for me and others that have a hard time grasping CRCs. I don't want to ask for too much but would you also have one for the CRC-32 messages that pop up on MBTs? This code is great for me to reverse and start to understand CRCs!

        static bool crc32(ref byte[] data)
        {
            ulong polynom = 0x04c11db7;
            ulong crc = 0x0;
            ulong crcxor = 0xFFFFFFFF;
            ulong i, j, bit;
            ulong crcin = (ulong)((data[8] << 24) | (data[9] << 16) | (data[10] << 8) | data[11]) & 0xFFFFFFFF;

            for (i = 0; i < 8; i++)
            {
                for (j = 0x80; j != 0; j >>= 1)
                {
                    bit = crc & 0x80000000;
                    crc <<= 1;
                    if ((data[i] & j) != 0)
                        bit ^= 0x80000000;
                    if (bit != 0)
                        crc ^= polynom;
                }
            }

            crc ^= crcxor;
            crc &= 0xFFFFFFFF;
            return (crc ^ crcin) != 0 ? false : true;
        }

Here you go. I know you are working on P25 Control Channel decoding and this routine will verify CRC on a single data block following a header block which has 8 octets of data and 4 octets of CRC code, as per the samples you sent me.

Such as RFSS Status Broadcast (RFSS_STS_BCST) messages.

 

[SCPD]

That works! I would like to point out to others that see this code that you must input the last block first and then go backwards.

byte[] data = new byte[] {
                0x01, 0x46, 0x63, 0xA0, 0x61, 0x8A, 0x70, 0x00, 0x7B, 0xAB, 0xCE, 0x21,
                0x37, 0xFD, 0x00, 0x00, 0x31, 0x44, 0x81, 0x3A, 0x00, 0x00, 0x5F, 0x6E
            };
bool crc_ok = crc32(ref data);

 

[aharry]

That works! I would like to point out to others that see this code that you must input the last block first and then go backwards.

byte[] data = new byte[] {
                0x01, 0x46, 0x63, 0xA0, 0x61, 0x8A, 0x70, 0x00, 0x7B, 0xAB, 0xCE, 0x21,
                0x37, 0xFD, 0x00, 0x00, 0x31, 0x44, 0x81, 0x3A, 0x00, 0x00, 0x5F, 0x6E
            };
bool crc_ok = crc32(ref data);

Not sure what you mean here...
The line starting with 0x37 is a header block and uses CRC-16, the line beginning with 0x01 is a data block that uses CRC-32 so really you would call crc16() with the 12 bytes starting with 0x37 and crc32() with the 12 bytes starting with 0x01 because they each have their own CRC check using different methods.

Both methods take exactly 12 bytes any less will throw an exception (note I didn't do any error checking) any less it will just ignore the extras.

 

[aharry]

The crc32 method really just works on 8 data bytes/4 crc bytes. In reality the sequence could be:

Header Block (crc16)
Data Block 1
Data Block 2
..
Last Data Block (crc32)

The last data block in the sequence has the crc32 for the proceeding data blocks. For example the below UU_V_CH_GRANT Message. You can see the header has two octets for CRC and the last data block has four octets of CRC.

If I had some multi-block samples I would expand it to include multi-blocks, but for your purpose it will work.

 

[mikey60]

The 32 bit CRC at the end of a multi-block message includes all bytes of the message, including all 12 bytes of the initial header block. So in a 2 block message, the data is 20 bytes long (12 + 8) . In a 3 block message, the data is 32 bytes long (12 + 12 + 8). In both cases the last 4 bytes (not included in the totals above) are the stored 32 bit CRC.

Edit: Guess I needed to look at the code a little closer, the first block is not included in the 32 bit CRC...

Mike

 

[aharry]

The 32 bit CRC at the end of a multi-block message includes all bytes of the message, including all 12 bytes of the initial header block. So in a 2 block message, the data is 20 bytes long (12 + 8) . In a 3 block message, the data is 32 bytes long (12 + 12 + 8). In both cases the last 4 bytes (not included in the totals above) are the stored 32 bit CRC.

Mike

Doesn't seem right from the data he supplied:
(These were PM'ed to me and were not in the proceeding thread)

Some sample packets are as following:

Packet 1.1: 37FD00003144813A00005F6E (37 FD 00 00 31 44 81 3A 00 00 5F 6E)
Packet 1.2: 014663A0618A70007BABCE21 (01 46 63 A0 61 8A 70 00 7B AB CE 21)

Packet 2.1: 37FD00003144813C0143A658 (37 FD 00 00 31 44 81 3C 01 43 A6 58)
Packet 2.2: 64096133700000007CE6BFD4 (64 09 61 33 70 00 00 00 7C E6 BF D4)

Packet 3.1: 37FD00003144813A00005F6E (37 FD 00 00 31 44 81 3A 00 00 5F 6E)
Packet 3.2: 014663A0618A70007BABCE21 (01 46 63 A0 61 8A 70 00 7B AB CE 21)

The first line of each packet is a header block, the second is a single data block. If you do a CRC-16 check of the header it verifies. If you do a CRC-32 check of the data block using only the first 8 data bytes it verifies. Adding the 12 bytes of the header certainly will not return the exact same CRC-32 result as just the eight data bytes.

 

[mikey60]

I corrected myself after looking at the Pro96Com source. You are correct, the first block is not included in the CRC32 calculations.

But it still will be either 8 bytes or 20 depending on the actual number of blocks in the message, and there are some that are 3 blocks long (including the header).

Mike

 

[aharry]

I corrected myself after looking at the Pro96Com source. You are correct, the first block is not included in the CRC32 calculations.

But it still will be either 8 bytes or 20 depending on the actual number of blocks in the message, and there are some that are 3 blocks long (including the header).

Mike

Yeah, I just put these together to get ActiveHat started, if I had samples I would expand it to include multiple blocks, but I don't want to try without real data to test.

 

[mikey60]

Thought I had some examples of a 3 block message. Not finding it at the moment though.

Mike

 

[SCPD]

Here's a triple TSBK OSP ...

37 FD 00 35 F1 24 82 31 BE E0 73 A9
01 A7 35 F1 24 5A C9 5B 90 DC 35 02
42 5B 4B DA 59 87 81 34 40 1C CF B0

 

[aharry]

Thanks Unitrunker

 

[SCPD]

I didn't realize that only the last block is checked with crc32. It would make sense (to me I guess) that they only do a crc16 if they don't include all blocks in the data but I guess that's why I'm still learning.

So, if I understand everything correctly, I check the first block with CRC16 and the last block with CRC32 (only last block, nothing else with it). What would I do for any blocks in the middle (in the attachment above, it is called the first data block). Is that included in the CRC32 check since it doesn't have its own CRC?

 

[SCPD]

Sorry, it took me some time to understand previous messages. Would you mind changing this to include multiple blocks? I think I understand now that I would put the first data block (middle) and last block or just last block (depending on how many blocks there are) and CRC16 of the header block.

Also, just so I'm clear, in the header block, I look at Octet 6, bits 6-0 to see how many blocks (or packets in my case) I need to keep after the header packet? I think I understand that one just fine.

 

[aharry]

Sorry, it took me some time to understand previous messages. Would you mind changing this to include multiple blocks? I think I understand now that I would put the first data block (middle) and last block or just last block (depending on how many blocks there are) and CRC16 of the header block.

Also, just so I'm clear, in the header block, I look at Octet 6, bits 6-0 to see how many blocks (or packets in my case) I need to keep after the header packet? I think I understand that one just fine.

Correct, you retrieve the header block, verify it's validity with crc16, retrieve the number of data blocks in the message as indicated by the header and crc32 all the bytes in all the message blocks together. The last four bytes of the last data block holds the crc code for the entire string of data blocks.

I will update the code and post it shortly.

 

[SCPD]

Thanks!