CRC codes

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?




--
Rich

"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 

"RichD" <r_delaney2001@yahoo.com> wrote in message 
news:b0fd8915-dc4d-4c66-8beb-9c9f24ba38c8@w8g2000vbx.googlegroups.com...
>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?

yes, cyclic redundance codes,

they are 'prime number' polynomials

Peterson has written several books on them (invented/discovered in 1961)
CRC16 is one specific polynomial,
x^16+x^15+x^2+1

but there are about 50 other crc 16 bit poly generators that will work just 
as well


> 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 earlier, and a very good set of codes, easily executed in hardware, 
on the fly XOR, and fast. (also in firmware) good fit with computer memory 
and files

Other codes may be for different types of error patterns which depend upon 
the communication channel, (bursts) or for error detection and correction.

CRC is error detection, but does not detect all error patterns

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?

The disk drive industry use CRC error _detection_ codes, not CRC
_correction_ codes. The drive industry is only interested if the data
block is completely OK or if it is faulty.

 A faulty disk block usually contains a large burst error, which would
be impossible to correct anyway, even with advanced ECCs, unless the
data is interleaved between several blocks or even disk drives (RAID).
The deinterleaving will convert a burst error to random errors which
may recoverable with a suitable ECC.

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.
 

In comp.dsp 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?

There is a reasonably good description of them in "Numerical Recipes"
(in C, or other language).

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

As far as I know, they originated as part of tape coding, and
then carried over to disk drives. 

-- glen

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.


Eric Jacobsen
Anchor Hill Communications
www.anchorhill.com

On Fri, 03 Aug 2012 05:58:24 +0300, upsidedown@downunder.com 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?
>
>The disk drive industry use CRC error _detection_ codes, not CRC
>_correction_ codes. The drive industry is only interested if the data
>block is completely OK or if it is faulty.
>
> A faulty disk block usually contains a large burst error, which would
>be impossible to correct anyway, even with advanced ECCs, unless the
>data is interleaved between several blocks or even disk drives (RAID).
>The deinterleaving will convert a burst error to random errors which
>may recoverable with a suitable ECC.
>
>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.


That's wrong.  These days all physical (hard) disk blocks have large
error checking/correcting blocks attached, and at current densities,
its rare (to the point of non-existence) that a block reads completely
cleanly.  The Seagate Cheetah's, for example, can correct error bursts
up to 320 bits.  The newer Savio's can correct bursts up to 520 bits.
And both of those are with 512 byte sectors.  Non-enterprise drives
are a bit skimpier, though.

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).

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.

Jon

Youdidnt buildthat wrote:
> "RichD" wrote in message
> >I notice =A0that the disk drive industry uses CRC error correction
> > codes. =A0Can anybody tell me where these come from, do they
> > have their own standards?
>
> yes, cyclic redundance codes,

Or cyclic redundancy check.

> they are 'prime number' polynomials
>
> Peterson has written several books on them (invented/discovered in 1961)
> CRC16 is one specific polynomial,
> x^16+x^15+x^2+1

Many standard CRC polynomials, including that one, are reducible.
Specifically they have a factor of (x + 1) to detect any odd number of
bit errors with certainty.

[...]
> CRC was earlier, and a very good set of codes, easily executed in hardwar=
e,
> on the fly XOR, and fast. (also in firmware) good fit with computer memor=
y
> and files

Right. The table-drive software method is reasonably fast, but where
they really shine is in hardware. A linear feedback shift register
with taps corresponding to the positions of the 1 coefficients
computes the CRC on the fly using very few gates.

I'm reading this on sci.crypt, where we deal with the frightening
record of CRC misuse. They're great for detecting accidental errors,
but intelligent adversaries easily exploit their linear mathematical
properties.

-Bryan