CRC Strength

Hi all,
At work I've written an integration to a third party device and customers are frequently having reliability problems with it, which I prefer not to go further into at this stage, and one issue which really bugs me is that in both directions the comms only transmits the upper half (high 8-bits) of a 16-bit CRC (polynomial x^16 + x^15 + x^2 + 1).
What's more, the whole packet's themselves are only a maximum of six bytes long, typically only two or three bytes long (including 1 byte of CRC)!

Now my intuition tells me that although in theory a 16-bit CRC gives a 1 in 65536 chance of detecting an error, it would not necessarily hold true that transmitting only half of those CRC bits equates to a 1 in 256 chance of detecting an error. To me this seems especially true when the packet sizes are so small, such as when the whole CRC is bigger than the packet data!
Am I right that straight out using an 8-bit CRC would be far better than sending half of a 16-bit one?
Would even sending the other half of the CRC be an improvement?

Am I right that straight out using an 8-bit CRC would be far better than sending half of a 16-bit one?

I doubt it, but it depends on what you are doing.

If you are using it for error recovery... you are screwed either way with variable length (2-5) byte payloads.

If you are using it only as a transmission check, you probably are doing fine with half of "CRC16". It is unlikely that payloads just happen to flag as collisions with half of "CRC16" are more problematic when you know collisions are going to happen (1/256 even) with "CRC8" anyway.

If you are only checking for an invalid payload I'd say you are better off with "CRC8".

I'm not saying that your intuition is wrong; I'm just saying that the potential for collisions is already very high and are probably not going to be noticeable worse using only half of "CRC16". That approach can't be better so I'd so go for the change (to CRC8) first if you have that authority.

That said, if you are trying to check transmission errors you could probably do better than simply prepending a checksum depending on the type of errors you are likely to see such as interleaving checksum bits with data.

Would even sending the other half of the CRC be an improvement?

Yes, but only if you are using it as a simple checksum.

Soma

Actually, I decided to just write a quick bit of code to check what the CRC values are for every possible value of the 1 byte data + 1 CRC packet. The results were quite astounding...

Of all 256 possible values of the 1 data byte, generating the 16-bit CRC and then taking only the upper 8 bits, resulted int only 8 unique CRC values! Now I had a feeling it was bad, but this is about four times worse than I thought it was.

If I instead take the lower 8 bits of the CRC then it results in a perfect 256 different CRC values. So yes I think what you said would be true (that it would be no worse than 8-bit CRC) if they were using the lower half of the CRC. But by using the upper half, it's complete crap.

> Now my intuition tells me that although in theory a 16-bit CRC gives a 1 in 65536 chance of detecting an error
This is wrong - it's a 1 in 65536 of NOT detecting an error. That is, the data is wrong, but it has the same CRC.

Also, a CRC is only a "check" (it's in the name). It has no information to allow for error correction.
Error correction is possible, but is harder to calculate, and more (redundant) information needs to be transmitted.
Forward error correction - Wikipedia, the free encyclopedia

But if the link is that bad, how are you managing retries etc?
If the link is fundamentally unreliable, then CRC is not the answer IMO.

> What's more, the whole packet's themselves are only a maximum of six bytes long, typically only two or three bytes long (including 1 byte of CRC)!
So how are you sending the length + the data, and how do you know if any bytes have been dropped/inserted by the link?

Originally Posted by iMalc

Hi all,
At work I've written an integration to a third party device and customers are frequently having reliability problems with it, which I prefer not to go further into at this stage, and one issue which really bugs me is that in both directions the comms only transmits the upper half (high 8-bits) of a 16-bit CRC (polynomial x^16 + x^15 + x^2 + 1).
What's more, the whole packet's themselves are only a maximum of six bytes long, typically only two or three bytes long (including 1 byte of CRC)!

Now my intuition tells me that although in theory a 16-bit CRC gives a 1 in 65536 chance of detecting an error, it would not necessarily hold true that transmitting only half of those CRC bits equates to a 1 in 256 chance of detecting an error. To me this seems especially true when the packet sizes are so small, such as when the whole CRC is bigger than the packet data!
Am I right that straight out using an 8-bit CRC would be far better than sending half of a 16-bit one?
Would even sending the other half of the CRC be an improvement?

More or less the probability of not detecting an error should be around 1/256. If the packets are generally small then the chance that the error actually gets propagated to the upper bits might be somewhat less. At any rate, you should probably focus on fixing the transmission problems, if possible...

Originally Posted by Salem

> Now my intuition tells me that although in theory a 16-bit CRC gives a 1 in 65536 chance of detecting an error
This is wrong - it's a 1 in 65536 of NOT detecting an error. That is, the data is wrong, but it has the same CRC.

Thanks for pointing out the mismatch between what I meant and what I wrote.

Also, a CRC is only a "check" (it's in the name). It has no information to allow for error correction.
Error correction is possible, but is harder to calculate, and more (redundant) information needs to be transmitted.
Forward error correction - Wikipedia, the free encyclopedia

Yes I'm aware of that thanks. This project makes no attempt at error correction whatsoever. However for a totally unrelated project, I did recently implement FEC using triple modular redundancy, and even quoted that exact link to the customer. But FEC is out of the question here.

But if the link is that bad, how are you managing retries etc?
If the link is fundamentally unreliable, then CRC is not the answer IMO.

> What's more, the whole packet's themselves are only a maximum of six bytes long, typically only two or three bytes long (including 1 byte of CRC)!
So how are you sending the length + the data, and how do you know if any bytes have been dropped/inserted by the link?

The link is proving to be unreliable in some cases. However the good news is that retrying is not necessary. The information concerned here is just current status type of information. So as long as we can detect the status packet as being corrupt then we can happily ignore it and wait for the next one. So long as we get a non-corrupt response after a certain number of attempts then everything is fine and dandy.

There is no explicit length byte, the polls have a type byte and each type of packet is a predefined length. There are only about 5 packet types.

Originally Posted by gardhr

More or less the probability of not detecting an error should be around 1/256. If the packets are generally small then the chance that the error actually gets propagated to the upper bits might be somewhat less. At any rate, you should probably focus on fixing the transmission problems, if possible...

I agree. Knowing there are a moderate number of errors occurring at all in some cases made me nervous. Our software gathers statistics on packets with wrong CRCs (amoung other things), and some sites have reported error rates of at least 1 in 50,000. Even a 1 in 256 chance of not detecting the error is awful when you're receiving on the order of 500,000 packets per day.

Unfortunately I am working with a third-party product here, so whilst I don't strictly have the ability to change the protocol between devices, I am hoping to gather enough information to persuade the third party that a protocol change is necessary.

Originally Posted by iMalc

I agree. Knowing there are a moderate number of errors occurring at all in some cases made me nervous. Our software gathers statistics on packets with wrong CRCs (amoung other things), and some sites have reported error rates of at least 1 in 50,000. Even a 1 int 256 chance of not detecting the error is awful when you're receiving on the order of 500,000 packets per day.

Unfortunately I am working with a third-party product here, so whilst I don't strictly have the ability to change the protocol between devices, I am hoping to gather enough information to persuade the third party that a protocol change is necessary.

That sounds like a good strategy. Trying to interoperate with third party products can be a real pain in the arse sometimes, no doubt. Especially when the customer doesn't even make a distinction between your product and the other and ends up blaming you for something that's completely beyond your control...

FYI, here's the code I use to test the CRC high-byte for collisions, excluding the CRC class that calculates the CRC as per the polynomial I gave earlier:

Code:

int _tmain(int argc, _TCHAR* argv[])
{
	std::vector<unsigned char> crcCollisions[256];
	for (int i=0; i<256; ++i)
	{
		Crc16Modbus crc;
		crc.Calc((unsigned char)i);
		unsigned char res = (unsigned char)(crc.Result() >> 8);
		crcCollisions[res].push_back(i);
	}

	int numDistinct = 0;
	for (int i=0; i<256; ++i)
	{
		if (!crcCollisions[i].empty())
			++numDistinct;
	}
	std::cout << "There are " << numDistinct << " possible values for "
		"the CRC high byte of a packet with 1 data byte" << std::endl;

	for (int i=0; i<256; ++i)
	{
		if (!crcCollisions[i].empty())
		{
			std::cout << "CRC(" << i << ") ";
			for (size_t j=0; j<crcCollisions[i].size(); ++j)
				std::cout << (int)crcCollisions[i][j] << " ";
			std::cout << std::endl;
		}
	}

	std::getchar();
	return 0;
}

And here are the results:

Code:

There are 8 possible values for the CRC high byte of a packet with 1 data byte
CRC(62) 2 14 22 26 38 42 50 62 70 74 82 94 98 110 118 122 134 138 146 158 162 174 182 186 194 206 214 218 230 234 242 254
CRC(63) 6 10 18 30 34 46 54 58 66 78 86 90 102 106 114 126 130 142 150 154 166 170 178 190 198 202 210 222 226 238 246 250
CRC(126) 1 13 21 25 37 41 49 61 69 73 81 93 97 109 117 121 133 137 145 157 161 173 181 185 193 205 213 217 229 233 241 253
CRC(127) 5 9 17 29 33 45 53 57 65 77 85 89 101 105 113 125 129 141 149 153 165 169 177 189 197 201 209 221 225 237 245 249
CRC(190) 4 8 16 28 32 44 52 56 64 76 84 88 100 104 112 124 128 140 148 152 164 168 176 188 196 200 208 220 224 236 244 248
CRC(191) 0 12 20 24 36 40 48 60 68 72 80 92 96 108 116 120 132 136 144 156 160 172 180 184 192 204 212 216 228 232 240 252
CRC(254) 7 11 19 31 35 47 55 59 67 79 87 91 103 107 115 127 131 143 151 155 167171 179 191 199 203 211 223 227 239 247 251
CRC(255) 3 15 23 27 39 43 51 63 71 75 83 95 99 111 119 123 135 139 147 159 163 175 183 187 195 207 215 219 231 235 243 255

Don't worry, the implementation of Crc16Modbus is known to be correct, and I think it's usage above should be pretty self explanatory.

Edit: I also confirmed that for all possible packets containing two data bytes that the possible CRC values are evenly distributed. So really the big problem is really only with replies containing just a single data byte, which just so happens to be the size of every reply (it's the polls that are up to 6 bytes).

Hmm, I wonder if a polynomial with more terms (and thus more "taps") might do a better job propagating errors in smallish data streams?

Originally Posted by iMalc

Edit: I also confirmed that for all possible packets containing two data bytes that the possible CRC values are evenly distributed. So really the big problem is really only with replies containing just a single data byte, which just so happens to be the size of every reply (it's the polls that are up to 6 bytes).

In that case for your single byte packets why not just perform a CRC on the data "transposed" to two bytes. So for example if the data byte is 3F, calculate CRC(3F3F). For even better distribution you could first pass the data byte through an 8-bit linear feedback shift register to obtain the "appended" byte.

Originally Posted by gardhr

In that case for your single byte packets why not just perform a CRC on the data "transposed" to two bytes. So for example if the data byte is 3F, calculate CRC(3F3F). For even better distribution you could first pass the data byte through an 8-bit linear feedback shift register to obtain the "appended" byte.

Thanks, I understand what you mean there and yes those are probably good ideas.

To start with now it looks like we'll plan treat data that passes the CRC test but is unexpected the same as a CRC error. At the moment our code just tries to distinguish between various expected cases. We shall instead have to validate that it matches one of the exact expected values. It's a bit of a shame as the whole point of a CRC is that it does the error detection for you.
Showing that we've done all we can and that it still isn't good enough (highly likely) is probably the best way to have the third party realise that changing the protocol in some way is the only solution.
If we're really lucky there will be some way of doing it that maintains backwards compatibility, but I don't see it at this point.

If we're really lucky there will be some way of doing it that maintains backwards compatibility, but I don't see it at this point.

;_;

I've literally never been that lucky when working with a third-party vendor.

Soma

If computation cost is not an issue, use a real hash function like SHA-2 and then just select however many bytes you need/want. Polynomial checksums are well-known to suffer from these problems.