CRC codes

On Thu, 02 Aug 2012 21:27:20 -0700, Jon Kirwan
<jonk@infinitefactors.org> wrote:

>On Thu, 02 Aug 2012 23:02:57 -0500, Robert Wessel
><robertwessel2@yahoo.com> wrote:
>
>>On Fri, 03 Aug 2012 03:48:39 GMT, eric.jacobsen@ieee.org (Eric
>>Jacobsen) wrote:
>>
>>>On Thu, 2 Aug 2012 19:21:18 -0700 (PDT), RichD
>>><r_delaney2001@yahoo.com> wrote:
>>>
>>>>I notice  that the disk drive industry uses CRC error correction
>>>>codes.  Can anybody tell me where these come from, do they
>>>>have their own standards?
>>>
>>>As has been pointed out, Cyclic Redundancy Check codes are for error
>>>detection only.   They generally do not have error correction
>>>capability.
>>>
>>>There are tons of different CRCs, but a particular CRC is usually
>>>specified in standards that use them.   Many communication standards
>>>include CRCs at the end of headers or data packets so that if
>>>undetected errors get through the FEC or ECC, the CRC will still catch
>>>the error.
>>>
>>>>The question arises after study of the academic literature,
>>>>in communications.  There are many codes, going way
>>>>back;  BCH, convolutional, etc  .But no mention of CRC.
>>>>I don't get it, didn't the storage engineers learn from the
>>>>same textbooks as everyone else?
>>>
>>>BCH and convolutional codes are used for error correction and actually
>>>don't do nearly as good of a job at error detection as a CRC does.
>>>The two jobs are different.
>>
>>
>>Well, the two jobs overlap to a fair degree, and there's a tradeoff -
>>for a fixed size check block, increasing the number of bits
>>correctable decreases the size of detectable errors, and vice-versa.
>>The exact codes used and the expected error rates and patterns have a
>>huge impact on the balance.  In addition, different check codes have
>>different biases on the patterns of errors detected - CRCs are
>>particularly good at detecting single bursts up to the size of the CRC
>>(which matches the error patterns expected for the serial
>>communications devices for which they were originally developed).
>
>The tradeoff you mention makes a great deal of sense to me.
>You can detect errors better by separating valid codes by
>larger Hamming distances. But "correction" implies that you
>accept nearby (Hamming distance wise) codes as valid so that
>you can then correct them to the actual nearby valid code.
>But doing that means you must sacrifice error detection for
>the manifest reasons.

Yup.   That's why ECCs aren't good at residual error detecting;
decoding is generally essentially selecting the valid codeword with
the minimum Hamming distance to the received pattern.   This will be
the most likely transmitted codeword, but it could still be the wrong
codeword and the decoder has no way of knowing that. 

A CRC or other residual error detecting code, however, doesn't need to
care about correction, so a properly designed system gets away with
only checking whether the codeword is valid or not.   It is not
difficult to constrain the system such that detection of an invalid
codeword is a highly reliable indicator of remaining error(s); far
more reliable than the ECC/FEC.


Eric Jacobsen
Anchor Hill Communications
www.anchorhill.com

On 08/02/2012 10:21 PM, RichD wrote:
> I notice  that the disk drive industry uses CRC error correction
> codes.  Can anybody tell me where these come from, do they
> have their own standards?
>
> The question arises after study of the academic literature,
> in communications.  There are many codes, going way
> back;  BCH, convolutional, etc  .But no mention of CRC.
> I don't get it, didn't the storage engineers learn from the
> same textbooks as everyone else?
[...]

CRC codes produce check-bits for information bits so that
[information bits]+[check-bits] can be thought as a polynomial
over F_2, the field with two elements, that is divisible by
a fixed polynomial  q(x): (or something like that).

One common polynomial is a 32-bit polynomial:

"The design of the 32-bit polynomial most commonly used by standards 
bodies, CRC-32-IEEE, was [...]"

cf.:
<http://en.wikipedia.org/wiki/Cyclic_redundancy_check#Designing_CRC_polynomials 
 > .





This article below makes it clear that Reed-Solomon codes are
very much used in CDs.

"The Ubiquitous Reed-Solomon Codes"
by Barry A. Cipra

< http://www.eccpage.com/reed_solomon_codes.html > .

He writes:

"The paper, "Polynomial Codes over Certain Finite Fields," by Irving S. 
Reed and Gustave Solomon, then staff members at MIT's Lincoln 
Laboratory, introduced ideas that form the core of current 
error-correcting techniques for everything from computer hard disk 
drives to CD players."

and:

"Disk drives pack data so densely that a read/write head can (almost) be 
excused if it can't tell where one bit stops and the next one (or zero) 
begins."

Maybe disk-failure is a different thing than read-errors.

RAID arrays use several (physical?) disks in case one fails or
is mixed up.

Dave

On 2012-08-03, RichD <r_delaney2001@yahoo.com> wrote:
> I notice  that the disk drive industry uses CRC error correction
> codes.  Can anybody tell me where these come from, do they
> have their own standards?
>
> The question arises after study of the academic literature,
> in communications.  There are many codes, going way
> back;  BCH, convolutional, etc  .But no mention of CRC.
> I don't get it, didn't the storage engineers learn from the
> same textbooks as everyone else?

??? CRC was in my textbooks when I did comp-sci ~1990

CRC is not an error correcting code. the are other codes for 
forward error correction, CRC is a check-code or hash.


-- 
&#9858;&#9859; 100% natural

--- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---

On 03/08/2012 03:58, upsidedown@downunder.com wrote:

<snip>

> In principle, the ordinary CRCs could be used to correct _one_ bit
> error in a message or block. If the CRC check fails, invert each bit
> at a time in the message frame and recalculate CRC, until a match is
> found :-). This make sense only if the error probability is very low
> and it is a single bit error and when the retransmission delay would
> be unacceptable due to half-duplex delay in space communication.


I've used that in a memory system, where CRCs were cheap and fast and 
bit errors scarce.  Is there a faster way to correct than the 
suck-it-and-see method outlined above?  I couldn't find one, but I'm no 
expert.

Cheers
-- 
Syd

In comp.dsp Syd Rumpo <usenet@nononono.co.uk> wrote:

(snip)

> I've used that in a memory system, where CRCs were cheap and fast and 
> bit errors scarce.  Is there a faster way to correct than the 
> suck-it-and-see method outlined above?  I couldn't find one, but I'm no 
> expert.

CRCs are also used as hash functions in comparisons. That allows
one to quickly determine that two things are different, or that
they might be the same.

-- glen

On Fri, 3 Aug 2012 14:53:07 +0000 (UTC), glen herrmannsfeldt
<gah@ugcs.caltech.edu> wrote:

>In comp.dsp Syd Rumpo <usenet@nononono.co.uk> wrote:
>
>(snip)
>
>> I've used that in a memory system, where CRCs were cheap and fast and 
>> bit errors scarce.  Is there a faster way to correct than the 
>> suck-it-and-see method outlined above?  I couldn't find one, but I'm no 
>> expert.
>
>CRCs are also used as hash functions in comparisons. That allows
>one to quickly determine that two things are different, or that
>they might be the same.


They are, but they're a mediocre choice at best.  SHA-1, for example,
is usually no slower than a CRC (in software), while taking less
memory and not being nearly as easy to spoof.

"Syd Rumpo" <usenet@nononono.co.uk> wrote in message 
news:jvgdvu$3jt$1@dont-email.me...
> On 03/08/2012 03:58, upsidedown@downunder.com wrote:
>
> <snip>
>
>> In principle, the ordinary CRCs could be used to correct _one_ bit
>> error in a message or block. If the CRC check fails, invert each bit
>> at a time in the message frame and recalculate CRC, until a match is
>> found :-). This make sense only if the error probability is very low
>> and it is a single bit error and when the retransmission delay would
>> be unacceptable due to half-duplex delay in space communication.
>
>
> I've used that in a memory system, where CRCs were cheap and fast and bit 
> errors scarce.  Is there a faster way to correct than the suck-it-and-see 
> method outlined above?  I couldn't find one, but I'm no expert.

Well, with CRC's, if you flip a bit at a specific position (say, bit 7) of 
the input, a specific pattern of bits will flip in the CRC (and yes, for any 
decent CRC, this specific pattern will differ for every position).  So, what 
you do is exclusive-or the CRC you received and the CRC you calculated, and 
look that result in a table of precomupted error vectors (for example, what 
the error vector would look like if we flipped bit 7).  This will tell you 
immediately what single bit error we got, and which bit needed to be flipped 
(if any, the error might have been in the CRC itself)

-- 
poncho

In comp.dsp Robert Wessel <robertwessel2@yahoo.com> wrote:

(snip, I wrote)
>>CRCs are also used as hash functions in comparisons. That allows
>>one to quickly determine that two things are different, or that
>>they might be the same.

> They are, but they're a mediocre choice at best.  SHA-1, for example,
> is usually no slower than a CRC (in software), while taking less
> memory and not being nearly as easy to spoof.

Certainly there are some cases where spoofing is important.

The usual implentations of the unix diff command use a hash.
At least for comparing ones own files, one shouldn't need to
worry about spoofing.

-- glen

On Aug 3, 11:45=A0am, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> In comp.dsp Robert Wessel <robertwess...@yahoo.com> wrote:
>
> (snip, I wrote)
>
> >>CRCs are also used as hash functions in comparisons. That allows
> >>one to quickly determine that two things are different, or that
> >>they might be the same.
> > They are, but they're a mediocre choice at best. =A0SHA-1, for example,
> > is usually no slower than a CRC (in software), while taking less
> > memory and not being nearly as easy to spoof.
>
> Certainly there are some cases where spoofing is important.
>
> The usual implentations of the unix diff command use a hash.
> At least for comparing ones own files, one shouldn't need to
> worry about spoofing.
>
> -- glen

consist of CRC CRC CRC in various combinations of CRC

Phil Allison wrote:
> "Rich Dope"
> 
> 
>>I notice  that the disk drive industry uses CRC error correction
>>codes.  Can anybody tell me where these come from, do they
>>have their own standards?
>>
>>The question arises after study of the academic literature,
>>in communications.  There are many codes, going way
>>back;  BCH, convolutional, etc  .But no mention of CRC.
>>I don't get it, didn't the storage engineers learn from the
>>same textbooks as everyone else?
> 
> 
> 
> ** If you look for something in places where it is not
> 
>   -  do not be surprised when it is not there.
> 
> 
> 
> ...  Phil 
> 
> 
Yes, Quantum mechanics.


Jamie