CRC codes

[RichD]

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

[Phil Allison]

"Rich Dope"

** If you look for something in places where it is not

- do not be surprised when it is not there.



... Phil

[Youdidnt buildthat]

"RichD" <r_dela...@yahoo.com> wrote in message
news:b0fd8915-dc4d-4c66...@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

[upsid...@downunder.com]

On Thu, 2 Aug 2012 19:21:18 -0700 (PDT), RichD
<r_dela...@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.

[glen herrmannsfeldt]

In comp.dsp RichD <r_dela...@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

[Eric Jacobsen]

On Thu, 2 Aug 2012 19:21:18 -0700 (PDT), RichD
<r_dela...@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

[Robert Wessel]

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.

[Robert Wessel]

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

[Jon Kirwan]

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

[Bryan]

Youdidnt buildthat wrote:
> "RichD" wrote in message

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

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 hardware,
> on the fly XOR, and fast. (also in firmware) good fit with computer memory
> 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

[Eric Jacobsen]

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.

[David Bernier]

[...]

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

[Jasen Betts]

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


--
⚂⚃ 100% natural

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

[Syd Rumpo]

On 03/08/2012 03:58, upsid...@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

[glen herrmannsfeldt]

In comp.dsp Syd Rumpo <use...@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

[Scott Fluhrer]

"Syd Rumpo" <use...@nononono.co.uk> wrote in message
news:jvgdvu$3jt$1...@dont-email.me...

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

[Robert Wessel]

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.

[glen herrmannsfeldt]

In comp.dsp Robert Wessel <robert...@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

[Martin Michael Musatov]

On Aug 3, 11:45 am, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:

consist of CRC CRC CRC in various combinations of CRC

[Jamie]

Yes, Quantum mechanics.


Jamie

[Jasen Betts]

On 2012-08-03, Syd Rumpo <use...@nononono.co.uk> wrote:

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

ECC memory uses a Hamming code, the payload and hash are interleaved
such that the computed hash gives the address of the error bit,

Hash computation is done by XORING th addresses of all the set bits.

Address 0 is not used, and the hash goes into the bits that are powers
of two. except for address zero all the other addresses are for payload.

[Robert Wessel]

True, but my point was more along the lines of does CRC32 have any
actual advantages over SHA-1 for this sort of task? Probably CRC32
would have an advantage in startup/completion overhead on small
datasets. Other than that...?

[unruh]

On 2012-08-04, Robert Wessel <robert...@yahoo.com> wrote:
> On Fri, 3 Aug 2012 16:45:38 +0000 (UTC), glen herrmannsfeldt
><g...@ugcs.caltech.edu> wrote:
>
>>In comp.dsp Robert Wessel <robert...@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.

It depends on if you want to just detect errors or be able to fix them
as well (or even know where they occured).SHA1 is good for detecting
errors ( and making sure that some malicious person has not inserted a
deliberate error such that it is undetectable by the hash) but it is not
good at knowing what the errors was or correcting it.

[Robert Wessel]

On Sat, 04 Aug 2012 16:32:15 GMT, unruh <un...@invalid.ca> wrote:

>On 2012-08-04, Robert Wessel <robert...@yahoo.com> wrote:
>> On Fri, 3 Aug 2012 16:45:38 +0000 (UTC), glen herrmannsfeldt
>><g...@ugcs.caltech.edu> wrote:
>>
>>>In comp.dsp Robert Wessel <robert...@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.
>
>It depends on if you want to just detect errors or be able to fix them
>as well (or even know where they occured).SHA1 is good for detecting
>errors ( and making sure that some malicious person has not inserted a
>deliberate error such that it is undetectable by the hash) but it is not
>good at knowing what the errors was or correcting it.

But neither is CRC.

[Eric Jacobsen]

On Sat, 04 Aug 2012 11:55:00 -0500, Robert Wessel

Right. Since CRCs don't include error location capability it isn't
really good for that task. They can be brute-forced to fix a single
bit error as previously described in this thread (which requires
assuming that there was only one bit in error), but they are not
generally used for error correction because they suck at it.

From a system perspective for most communication systems CRCs are used
for residual error detection (e.g., for cases where retransmission can
be used) and FEC is used for channel error correction. The jobs are
different.

[Youdidnt buildthat]

"Robert Wessel" <robert...@yahoo.com> wrote in message
news:ofhm18lasc532t7r8...@4ax.com...

CRC cant correct large block errors, other codes can.

[Youdidnt buildthat]

"Eric Jacobsen" <eric.j...@ieee.org> wrote in message
news:501d5a71...@www.eternal-september.org...

a check sum can be used faster than CRC for one bit correction (brute
forced).
check sum horzontal and vertical can correct one bit error fast. need odd
parity too.

[Youdidnt buildthat]

"Scott Fluhrer" <sflu...@ix.netcom.com> wrote in message
news:1344009733.580710@rcdn-nntpcache-3...

not so.
the crc is too short,
out of a codeword set 2^128 (128 bits) and a crc of 16 bits 2^16 , you will
have the same crc generated for 128/16 or 8 codewords



> --
> poncho
>
>

[Robert Wessel]

No, if you have a 128 bit block and a 16 bit check code, you'll get
the same check code for approximately 2**(128-16) blocks (aka 2**112).

[Rick Lyons]

On Sat, 4 Aug 2012 20:21:36 -0500, "Youdidnt buildthat"
<inv...@invalid.com> wrote:

[Snipped by Lyons]

>
>not so.
>the crc is too short,
> out of a codeword set 2^128 (128 bits) and a crc of 16 bits 2^16 , you will
>have the same crc generated for 128/16 or 8 codewords
>
>> --
>> poncho

Hello Poncho,
I haven't read this complete thread.
But remember, if someone does build a reliable
CRC system, they didn't build that. Some one
else made that happen.

[-Rick-]

[David Bernier]

I was under the impression that CRCs are generally designed and
used to detect errors, for example in packets sent over
the Internet ...


I was looking for strong evidence that advanced error-correcting codes
were used in hard drives.

Hitachi produces enterprise-class hard-drives, which tend to
pack more GB per square inch, spin faster and have lower
error rates.

From this piece from 2008, one learns that they produced dense
packing based in part on LDPC codes (low-density parity check codes):

< http://techon.nikkeibp.co.jp/english/NEWS_EN/20080804/155945/ > .

---

More recently, they've done production od drives that use
LDPC codes:

From the spec. document for Deskstar 5K3000 & Ultrastar 5K3000
hard disk drives:

"576 bit LDPC in 512 byte format"
-->
"Deskstar 5K3000 (3TB) and Ultrastar 5K3000 OEM Specification"
-->
http://www.hgst.com/tech/techlib.nsf/products/Ultrastar_5K3000

For the Ultrastar 5K3000, they give a mean time before failure
of ~= 2.0 million hours.

But enterprise-class disk drives are more expensive ...

David Bernier

[Shmuel Metz]

In <jvffng$rpf$1...@speranza.aioe.org>, on 08/03/2012
at 03:14 AM, glen herrmannsfeldt <g...@ugcs.caltech.edu> said:

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

Early tape drives used longitudinal and vertical parity bits for error
checking. AFAIK the first use of a CRC was in data communications
during the mid 1960's.

--
Shmuel (Seymour J.) Metz, SysProg and JOAT <http://patriot.net/~shmuel>

Unsolicited bulk E-mail subject to legal action. I reserve the
right to publicly post or ridicule any abusive E-mail. Reply to
domain Patriot dot net user shmuel+news to contact me. Do not
reply to spam...@library.lspace.org