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

From	James Harris <james.harris.1@gmail.com>
Newsgroups	comp.programming
Subject	Re: Size of a CRC (or similar) code for a given length of message
Date	2015-09-25 13:42 +0100
Organization	A noiseless patient Spider
Message-ID	<mu3fbb$r07$1@dont-email.me> (permalink)
References	<mu35qo$o6g$1@dont-email.me> <mu39mh$6gg$1@dont-email.me>

Show all headers | View raw

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.

> 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?

James

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