CRC-8 advantage over LRC?
Clyde Adams III
over a bus. Most messages are four bytes long. Maximum message length is
64 bytes. I will add an error check byte to the end of each message.
Does CRC-8 (Cyclic Redundancy Check, 8-bit) have a significant advantage, in
terms of its error-checking reliability, over LRC (Longitudinal Redundacy
Check) for my application?
Can anyone point to published references that would help make a case one way
or another?
(By CRC-8, I mean the taking the 8-bit remainder from dividing the entire
message by an appropriate constant. By LRC, I mean taking the result of
XOR-ing all the message bytes together.)
CRC-8 does have a significant added cost (either in time or in memory). I'd
like to avoid that cost if it is not justified.
I realize that CRC is better at detecting the following types of errors:
(1) errors where bytes in a message are swapped
(2) errors where a given bit position is more likely to have an error than
other positions
I don't think there is much risk of these types of errors in my application.
Therefore, I'm trying to find out if CRC-8 has any other significant
advantage. I suspect it does not.
I would appreciate any specific, relevant information. Thanks in advance!
Clyde Adams III
Marketing Technical Engineer
(212) 226-2042 x239
cad...@usar.com
Daniel Quinz
methods of error detection.
I generate random messages of a given length, inject a random error
(1,2,...,N bit) and then count the number of hits/misses.
I have tried the LRC (as per your description) and it gave poor
results. Even a simple, 8-bit checksum, performed better.
The CRC method detected 100% of the errors (for 25000 msgs).
I recently used the DOW CRC-8 in a PIC application and the amount of
time spent calculating the CRC was negligible (at 9600 baud, 20 mHz
clock).
I would suggest you use the CRC, measure the final performance, if
acceptable - leave it be. Otherwise, optimize CRC calculation with a
table driven method (memory permitting).
If you finally decide to *not* use a CRC, do a simple CHECKSUM. It is
the same amount of calculation as a LRC, but better error detection
capabilities (at least experimentally).
Regards,
Daniel Quinz, P. Eng.
Micronetics CES
e-mail: da...@micronetics-ces.com
Robert Scott
<cad...@usar.com> wrote:
>In my firmware application, I'm sending short synchronous serial messages
>over a bus. Most messages are four bytes long. Maximum message length is
>64 bytes. I will add an error check byte to the end of each message.
>
>Does CRC-8 (Cyclic Redundancy Check, 8-bit) have a significant advantage, in
>terms of its error-checking reliability, over LRC (Longitudinal Redundacy
>Check) for my application?
>
>Can anyone point to published references that would help make a case one way
>or another?
>
>(By CRC-8, I mean the taking the 8-bit remainder from dividing the entire
>message by an appropriate constant. By LRC, I mean taking the result of
>XOR-ing all the message bytes together.)
>
>CRC-8 does have a significant added cost (either in time or in memory). I'd
>like to avoid that cost if it is not justified.
>
>I realize that CRC is better at detecting the following types of errors:
>
>(1) errors where bytes in a message are swapped
>
>(2) errors where a given bit position is more likely to have an error than
>other positions
>
>I don't think there is much risk of these types of errors in my application.
>Therefore, I'm trying to find out if CRC-8 has any other significant
>advantage. I suspect it does not.
What is "significant" depends on the error characteristics of
your particular channel. You should know better than any of
us what those characteristics are.
It sounds like you already have all the relevant info. An LRC
can be fooled by two bytes with errors in the same bit position.
If your bit error distribution is random, then one out of every
eight instances of double bit errors will sneak by the LRC. One
out of every 256 double bit errors will sneak by the CRC-8.
Since your messages are 4 bytes long, there are only 496 different
two-bit errors. If you do an exhaustive search over the possible
8-bit CRC polynomials, you might find one that isn't fooled by
any of the 496 two-bit errors. If you use that polynominal, you
can claim perfect detection of all two-bit errors.
Bob Scott
Ann Arbor, Michigan (email: rscott (at) wwnet (dot) net )
(My automatic return address is intentionally invalid.)
Holger Metschulat
> CRC-8 does have a significant added cost (either in time or in memory). I'd
> like to avoid that cost if it is not justified.
Doing a CRC-8 checksum calculation can be made by simple table lookups. This
doesn't need much time and only an additional simple 256 byte table.
--
Gruss * Holger Metschulat
Holger * e-mail: ho...@sgs.wh.tu-darmstadt.de
* http://www.sgs.wh.tu-darmstadt.de/homer
** "Verstaerker schwingen immer, Oszillatoren nie!" (Murphy) **
Dan Henry
consider doing two feedback/shift operations using a 16 byte
4bit-indexed table. It's not as fast as the big table, but still faster
than the bit-at-a-time method.
--Dan Henry
Evandro Menezes
<da...@micronetics-ces.com> wrote:
>I have written a short c++ program to numerically compare various
>methods of error detection.
>
>I generate random messages of a given length, inject a random error
>(1,2,...,N bit) and then count the number of hits/misses.
Could you share with the group some numbers, even if rough ones?
TIA
________________________________________________
Evandro Menezes Austin, TX ICQ:7957253
eva...@geocities.com come.to/evandro
Daniel Quinz
Certainly! My pleasure!
The following three tables represent simulation results for a message of
length 80 bits (a 10 byte message) with 1,2, and 3 random bit errors.
Each message is generated 100,000 times, random bit errors introduced,
and the BCC's (Block Check Code) of the valid and corrupted messages are
computed and compared.
Every time the two BCC's match, a MISS is counted (since we are
expecting a mismatch!). Every mismatch, a HIT is incremented.
The total number of HITS / 100,000 * 100 = The percentage of corrupt
messages detected.
I have appended the 'C/C++' BCC routines used in these simulations just
after the tables.
Note, as mentioned by someone earlier, the *nature* of the source of
errors has to be taken into consideration before choosing a BCC
algorithm to ensure that algorithm is best suited to detect the
error(s).
Regards,
Daniel Quinz, P. Eng.
Micronetics CES
e-mail: da...@micronetics-ces.com
---------------------------------------------------------------------
MSG Length = 10 bytes
ERROR bits = 1 bits
ITERATIONS = 100000
BCC( crc_32) MISS = 0 HIT = 100000 HIT% = 100.0000
BCC( crc_8) MISS = 0 HIT = 100000 HIT% = 100.0000
BCC( mix) MISS = 0 HIT = 100000 HIT% = 100.0000
BCC( add) MISS = 0 HIT = 100000 HIT% = 100.0000
BCC( xor) MISS = 0 HIT = 100000 HIT% = 100.0000
BCC( rotadd) MISS = 0 HIT = 100000 HIT% = 100.0000
BCC(shiftadd) MISS = 1254 HIT = 98746 HIT% = 98.7460
BCC(shiftxor) MISS = 1254 HIT = 98746 HIT% = 98.7460
---------------------------------------------------------------------
MSG Length = 10 bytes
ERROR bits = 2 bits
ITERATIONS = 100000
BCC( crc_32) MISS = 0 HIT = 100000 HIT% = 100.0000
BCC( crc_8) MISS = 0 HIT = 100000 HIT% = 100.0000
BCC( mix) MISS = 2921 HIT = 97079 HIT% = 97.0790
BCC( add) MISS = 5645 HIT = 94355 HIT% = 94.3550
BCC( xor) MISS = 11328 HIT = 88672 HIT% = 88.6720
BCC( rotadd) MISS = 2923 HIT = 97077 HIT% = 97.0770
BCC(shiftadd) MISS = 2916 HIT = 97084 HIT% = 97.0840
BCC(shiftxor) MISS = 6012 HIT = 93988 HIT% = 93.9880
---------------------------------------------------------------------
MSG Length = 10 bytes
ERROR bits = 3 bits
ITERATIONS = 100000
BCC( crc_32) MISS = 0 HIT = 100000 HIT% = 100.0000
BCC( crc_8) MISS = 0 HIT = 100000 HIT% = 100.0000
BCC( mix) MISS = 412 HIT = 99588 HIT% = 99.5880
BCC( add) MISS = 893 HIT = 99107 HIT% = 99.1070
BCC( xor) MISS = 0 HIT = 100000 HIT% = 100.0000
BCC( rotadd) MISS = 412 HIT = 99588 HIT% = 99.5880
BCC(shiftadd) MISS = 531 HIT = 99469 HIT% = 99.4690
BCC(shiftxor) MISS = 251 HIT = 99749 HIT% = 99.7490
---------------------------------------------------------------------
static Word32 bcc_crc_32 (Word8 data[],unsigned size)
{
Word16 sum = 0;
while (size-- > 0)
{
Word8 d = *data++;
for (unsigned bit = 0 ; bit < 8 ; bit++)
{
Boolean bit = ((sum >> 0) ^ (sum >> 3) ^ (sum >> 5) ^ (sum >>
8) ^ (sum >> 12) ^ (sum >> 15) ^ d) & 1;
d >>= 1;
sum <<= 1;
sum |= Word8(bit);
}
}
return sum;
}
---------------------------------------------------------------------
static Word32 bcc_crc_8 (Word8 data[],unsigned size)
{
Word8 crc = 0;
while (size-- > 0)
{
Word8 d = *data++;
for (unsigned nbits = 8 ; nbits > 0 ; nbits--)
{
Boolean bit = (crc ^ d) & 0x01;
crc >>= 1;
if (bit) crc ^= 0x8C;
d >>= 1;
}
}
return Word32(crc);
}
---------------------------------------------------------------------
static Word32 bcc_add (Word8 data[],unsigned size)
{
Word16 sum = 0;
while (size-- > 0)
sum += *data++;
return sum;
}
---------------------------------------------------------------------
static Word32 bcc_xor (Word8 data[],unsigned size)
{
Word16 sum = 0;
while (size-- > 0)
sum ^= *data++;
return sum;
}
---------------------------------------------------------------------
static Word32 bcc_mix (Word8 data[],unsigned size)
{
Word16 sum = 0;
while (size-- > 0)
{
sum += *data++;
int bit = sum & (1U << 15);
sum <<= 1;
if (bit)
sum |= 1U;
}
return sum;
}
---------------------------------------------------------------------
static Word32 bcc_rotadd (Word8 data[],unsigned size)
{
Word16 sum = 0;
while (size-- > 0)
{
Boolean bit = sum & 0x8000;
sum <<= 1;
if (bit) sum++;;
Word16 prev = sum;
sum += *data++;
if (sum < prev) sum++;
}
return sum;
}
---------------------------------------------------------------------
static Word32 bcc_shiftadd (Word8 data[],unsigned size)
{
Word16 sum = 0;
while (size-- > 0)
{
sum <<= 1;
sum += *data++;
}
return sum;
}
---------------------------------------------------------------------
static Word32 bcc_shiftxor (Word8 data[],unsigned size)
{
Word16 sum = 0;
while (size-- > 0)
{
sum <<= 1;
sum ^= *data++;
}
return sum;
}
Daniel Quinz
>
> On Wed, 18 Nov 1998 20:31:59 -0500, Daniel Quinz
> <da...@micronetics-ces.com> wrote:
>
> >I have written a short c++ program to numerically compare various
> >methods of error detection.
> >
> >I generate random messages of a given length, inject a random error
> >(1,2,...,N bit) and then count the number of hits/misses.
>
> Could you share with the group some numbers, even if rough ones?
>
> TIA
>
> ________________________________________________
> Evandro Menezes Austin, TX ICQ:7957253
> eva...@geocities.com come.to/evandro
Certainly! My pleasure!
The following three tables represent simulation results for a message of
length 80 bits (a 10 byte message) with 1,2, and 3 random bit errors.
Each message is generated 100,000 times, random bit errors introduced,
and the BCC's (Block Check Code) of the valid and corrupted messages are
computed and compared.
Every time the two BCC's match, a MISS is counted (since we are
expecting a mismatch!). Every mismatch a HIT is incremented.
The total number of HITS / 100,000 * 100 = The percentage of corrupt
messages detected.
I have appended the 'C/C++' BCC routines used in these simulations just
after the tables.
Regards,
Adrian Dunn
corrupted messages that appear to have a correct CRC should be lower than 1
in 64k when using a 16-bit CRC. One of the nice advantages of using an
X-bit CRC is that it will *always* flag messages with fewer than X bit
errors. Therefore, when using a 16-bit CRC, you are are guaranteed of
always detecting errors in messages where fewer than 16 bits were corrupted.
I am not sure about the error-detecting behaviour when 16 or more bits are
corrupted, but would assume that it slowly increases until it hits a limit
of erroneously validating 1 in 64k corrupted messages. I could be wrong
though, since you'd think that there would have to be some sort of
compensatory effect for being able to always detect errors in messages with
fewer than 16 bit errors.
Adrian
Peter wrote in message <365765f4...@news.netcomuk.co.uk>...
>
>This is not a big deal, for really random data corruption. If you have
>a 16-bit CRC, then about 1 in every 64k corrupted messages will look
>"OK". This is the bottom line of any CRC.
>
>>>I generate random messages of a given length, inject a random error
>>>(1,2,...,N bit) and then count the number of hits/misses.
>>
>>Could you share with the group some numbers, even if rough ones?
>
>
>--
>Peter.
>
>Return address is invalid to help stop junk mail.
>E-mail replies to zX...@digiYserve.com but
>remove the X and the Y.
Robert Scott
wrote:
>Unless your messages experience significant corruption, the ratio of
>corrupted messages that appear to have a correct CRC should be lower than 1
>in 64k when using a 16-bit CRC. One of the nice advantages of using an
>X-bit CRC is that it will *always* flag messages with fewer than X bit
>errors.
Not exactly. An X-bit CRC will detect any single burst of less
that X bit errors. But it is possible to have two bits in error
and still not be detected if those errors are far apart.
Johnny Smooth
are not at all the same thing. I agree with Bob that two well-placed
single bit errors could go undetected. I believe your numbers about
detectable errors apply to error correcting codes and not CRCs.
John
Bill Pringlemeir wrote in message ...
>[bcc'ed to posters]
>
> > On Sun, 22 Nov 1998 02:15:47 GMT, "Adrian Dunn" wrote:
>
> >> Unless your messages experience significant corruption, the
> >> ratio of corrupted messages that appear to have a correct CRC
> >> should be lower than 1 in 64k when using a 16-bit CRC. One of
> >> the nice advantages of using an X-bit CRC is that it will
> >> *always* flag messages with fewer than X bit errors.
>
>>>>>> "Bob" == Robert Scott <Rober...@noplace.com> writes:
> Bob> Not exactly. An X-bit CRC will detect any single burst of
> Bob> less that X bit errors. But it is possible to have two bits
> Bob> in error and still not be detected if those errors are far
> Bob> apart.
>
>Not exactly ;-). I just spent my weekend reading about GF(2) fields,
>polynomials and cyclic codes (well, I went out drinking with my neighbour
>too). Anyways, according to my information a properly choosen CRC
>should detect:
>
>100% of single bit errors.
>100% of two bits in error (seperate or not).
>100% of any odd bits in error (burst)
>100% of bursts less than 'r + 1' (r= crc size)
>1-(1/2^(r-1)) Error bursts of r+1 bits in length
>1-(1/2^r) Error burst greater than r+1 bits.
>
>For an eight bit CRC the last two are 99.2% and 99.6%
>
>This is from "Telecommunications, Protocols and Design" by Spragins,
>Hammond, Pawlikowaski. Published by Addison Wesley. Pg 278.
>
>Another good bood is "Theory and Practice of Error Control codes" by
>Richard E Blahut. This one is on error correcting codes; Hamming, BCH
>Reed-solomon.
>
>It explains a lot of group theory relating to 'Galios Fields' for an
>engineering point of view. GF(2) is just binary numbers with XOR for
>addition and AND for multiplication. Polynomials also form fields and
>have some nice properties that allow the constructions of these error
>detecting codes.
>
>It is really neat the way that FIR, and IIR structures along with Fourier
>transforms can be used to achieve error correction.
>
>Charles T. Retter has a neat paper on the web related to spectral decoding
>of Reed-Solomon codes.
>
>Anyways, with an 8 bit CRC, you can detect 8 or less burst errors. Any number
>of odd burst errors (ie 9). So, you must have 10 or more errors in a row to
>fool a CRC-8. I believe that several even bit errors seperated by enough
>space could also fool the CRC. You are basically 'dividing the data' with a
>CRC and the remainder must come out the same. So you need an error that is
>a multiple of the CRC.
>
>Bill
>
>--
>Tower of Hanoi Jane stars in the Hamming syndrome.
Philip Koopman
>100% of bursts less than 'r + 1' (r= crc size)
Also be careful -- what some call "burst" errors may not be what you'd
call "burst" errors. CRC uses the mathematician's definition of burst
error length k is k bits flipped in a row. If you want to guard against
k bits stuck at zero in a row (or stuck at one in a row, such as you
might get with a prolonged induced voltage spike on a baseband
communication wire) then CRC doesn't necessarily do that for you,
because if the stuck-at matches the valid bit value, the CRC sees
scattered/clumped bits instead of a complete burst.
-- Phil
Phil Koopman -- koo...@cmu.edu -- http://www.ece.cmu.edu/~koopman
phil
<cad...@usar.com> wrote:
>In my firmware application, I'm sending short synchronous serial messages
>over a bus. Most messages are four bytes long. Maximum message length is
>64 bytes. I will add an error check byte to the end of each message.
>
>Does CRC-8 (Cyclic Redundancy Check, 8-bit) have a significant advantage, in
>terms of its error-checking reliability, over LRC (Longitudinal Redundacy
>Check) for my application?
>
>Can anyone point to published references that would help make a case one way
>or another?
>(By CRC-8, I mean the taking the 8-bit remainder from dividing the entire
>message by an appropriate constant. By LRC, I mean taking the result of
>XOR-ing all the message bytes together.)
>CRC-8 does have a significant added cost (either in time or in memory). I'd
>like to avoid that cost if it is not justified.
>
I know i'm not aswering your question but my knee-jerk reaction is
always to use CRC unless there is a significant reason to do
otherwise. A 256 byte table would work well plus a few lines of C or
maybe less than 10-15 assembler instructions. If this fits within your
budget (yes i know), it might be faster to just bite the bullet. LRC
is just not as good.
phil
Philip Koopman
Bill Pringlemeir <bpring...@yahoo.com> wrote:
>Hmmm, this is an interesting comment. It was my impression that
>the CRC polynomials were made to be 'prime polynomials'. If the
>CRC is a prime polynomial in a field, then all 'binary numbers'
>from 0...(2^r-1) will have a unique modulus. That is just saying
>that the polynomial should map all numbers from 0..(2^r-1) to a
>new unique set of numbers. This is something like the process used
>for [in]congruential random number generators.
AFAIK you always want a CRC polynomial to be divisible by (x+1) so that
it will catch all odd number of bit errors (basically this bestows upon
it a parity capability). In an LFSR, by contrast, you want a primitive
(prime) polynomial. For example, the CAN CRC polynomial is divisible by
(x+1).
>So "bursts less than 'r+1'" means any amount of flipped bits not
>seperated by more than 'r+1'. This includes bits stuck at one or
>zero. The CRC can do this, because if you only have a 32 bit message
>with a 32 bit CRC then you must transmit 64 bits. If 32 bits are set
>to zero, the remaining 32 bit of the message will detect an error.
The definition of "burst error" varies considerably depending on the
text/source. However, what you say isn't what we have seen in extensive
simulations. It is possible (not always, but often enough) that a
"burst error" (whatever that *really* means) that includes within the
burst corrupted bits equal to original data bit values will slip past
the CRC even if the burst length is less than the CRC/polynomial size.
That is because apparently it "looks" like multiple independent bit
flips. This is despite the well-known property that a CRC will detect
burst errors up to CRC size. So I'm forced to conclude that "burst
error" for a CRC means contiguous flipped bits (but I'm no
mathematician, just an engineer trying to figure out how something works
in the real world).
If you care to refute or verify this result I'd find that interesting.
Regards,