Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #5900

Re: Size of a CRC (or similar) code for a given length of message

Show all headers | View raw

On 25/09/15 14:42, James Harris wrote:
> On 25/09/2015 12:05, David Brown wrote:
>> On 25/09/15 11:59, James Harris wrote:
>>> I see from
>>>
>>>    https://en.wikipedia.org/wiki/Cyclic_redundancy_check
>>>
>>> that, typically, an n-bit CRC applied to a data block of arbitrary
>>> length will detect a single error burst up to n bits long.
>>>
>>> That's fine - or as fine as the complex mathematics of CRCs gets! - but
>>> if looking to select a CRC calculation (or some other data integrity
>>> check) are there any guidelines on how wide the CRC code should be for
>>> given levels of assurance against random corruption for a given size of
>>> message?
>>>
>>> At the moment I am looking to protect a very short header of about 12
>>> bytes, give or take, and wonder what levels of confidence a certain
>>> number of CRC bits would give against data corruption.
>>>
>>> For example, if I used a 3-bit CRC to protect a 12-byte header how
>>> 'good' would that be compared to a 5-bit CRC? And if the header became
>>> 24 bytes, say, what effect would that have on the effectiveness of 3-bit
>>> and 5-bit CRCs? (Always assuming that other aspects of the CRC
>>> calculation are chosen well.)
>>>
>>> If I later wanted to protect a message of a thousand or a
>>> hundred-thousand bytes how wide would the CRC need to be to maintain a
>>> similar level of confidence?
>>>
>>> Any ideas?
>>>
>>> James
>>>
>>
>> There are no fixed rules here - it depends not only on the message
>> length, but also on the risk of corruption, the type of corruption, and
>> the consequence of incorrectly accepting a corrupted message.  Very
>> roughly speaking, if there is no pattern in the corruption, then an
>> n-bit CRC gives you a 1 in 2^n chance of accepting a corrupted message.
> 
> I can see that to an extent /if/ there's no pattern. With a 4-bit CRC
> there's a 1 in 16 chance that a bunch of *random* bits will match. But
> corruptions don't occur that way. There would normally be some bits
> which had not changed. Unless listening to random noise then some of the
> bits should be the same as the originals.
> 
> Therefore, AIUI, CRC-type codes are rated on how well they do at
> detecting things such as short runs of corruption and N random bit changes.

Correct - that's why I said "very roughly speaking" :-)  It's a pretty
complex subject if you want to dig into the depths of the maths, and I
don't claim to understand it all.  Unless you need the details, it is a
lot easier to simply accept that an n-bit CRC will detect a run of n
corrupt bits, and has a 1 in 2^n chance of detecting random corruption.
 Otherwise a full analysis requires detailed information about the type
of corruption or noise you can expect to see.

> 
>> If you are doing this in software rather than hardware (such as an
>> FPGA), then it is much easier if your crc is 8-bit, 16-bit, 32-bit, etc.
>>   My rule of thumb is that I use a 16-bit CRC for up to about 100 byte
>> telegrams, and 32-bit CRC for bigger transfers or as a crc over a series
>> of transfers.  For small 8-bit micros and short telegrams, I use an
>> 8-bit CRC to reduce the calculations.  But if the application already
>> has crc checks for one size, then I typically use that for everything
>> rather than mixing and matching.
> 
> IIUC the Wikipedia article showed the use of N + 1 bits of calculation
> for an N-bit CRC. The article showed use of 4 bits to generate a 3-bit
> code. If you have, say, a 16-bit CPU wouldn't it be much easier to
> calculate a 15-bit CRC rather than a 16-bit one?

A 16-bit CRC requires 17 bits to describe the 16-degree polynomial, but
the highest bit of the polynomial is always 1 (since we are using
binary, so the factor of x^16 is either 0 or 1 - and if it were 0, we
would not have a 16-degree polynomial).  When doing the calculations bit
for bit, the 17-bit shift register can be treated as a 16-bit register
with a carry bit (marginally inconvenient in C, but easy in assembly).
But if you use a table-based approach, it all works out nicely and
everything is done in bunches of 8 or 16 bits.


> 
> James
> 

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Size of a CRC (or similar) code for a given length of message James Harris <james.harris.1@gmail.com> - 2015-09-25 10:59 +0100
  Re: Size of a CRC (or similar) code for a given length of message David Brown <david.brown@hesbynett.no> - 2015-09-25 13:05 +0200
    Re: Size of a CRC (or similar) code for a given length of message James Harris <james.harris.1@gmail.com> - 2015-09-25 13:42 +0100
      Re: Size of a CRC (or similar) code for a given length of message David Brown <david.brown@hesbynett.no> - 2015-09-25 15:15 +0200
  Re: Size of a CRC (or similar) code for a given length of message Julio Di Egidio <julio@diegidio.name> - 2015-09-25 04:07 -0700
    Re: Size of a CRC (or similar) code for a given length of message David Brown <david.brown@hesbynett.no> - 2015-09-25 14:32 +0200
      Re: Size of a CRC (or similar) code for a given length of message Julio Di Egidio <julio@diegidio.name> - 2015-09-25 05:40 -0700
    Re: Size of a CRC (or similar) code for a given length of message James Harris <james.harris.1@gmail.com> - 2015-09-25 13:45 +0100
  Re: Size of a CRC (or similar) code for a given length of message Öö Tiib <ootiib@hot.ee> - 2015-09-25 04:17 -0700
    Re: Size of a CRC (or similar) code for a given length of message David Brown <david.brown@hesbynett.no> - 2015-09-25 14:36 +0200
      Re: Size of a CRC (or similar) code for a given length of message James Harris <james.harris.1@gmail.com> - 2015-09-25 13:49 +0100

csiph-web