30 Jan
2011
30 Jan
'11
7:30 p.m.
Hi guys,
As the subject says: are there any EDC/ECC code experts hanging around
on the list?
I'm working on implementing the 4-byte (32-bit) ECC code Western Digital
used on the WD2010 Winchester HDD Controller IC. This appears to be an
implementation of the ECC scheme explained in section 7.6 of National
Semiconductor's "Disk Interface Design Guide and User's Manual" (appnote
AN-413).
It looks like the ECC scheme is based on running a CRC forwards over the
data to produce a 32-bit CRC, which is used to validate the data in the
same way the 16-bit CRC validates the IDAM. Error correction apparently
operates by running the CRC in reverse using an "inverse polynomial". I
can't see how this could work -- isn't a CRC by its very nature a
one-way operation?
The application note calls this a "Glover 140A0443" code, but doesn't
bother to reference any papers, books or similar on the subject. There's
an example on how to program NSC's controller chips to use the code, but
nothing on the mathematical background behind it. For instance: how does
it work, and why is the maximum correctable error burst 5 bits long?
Does anyone recognise this polynomial?
x^32 + x^28 + x^26 + x^19 + x^17 + x^10 + x^6 + x^2 + 1
aka. x^32 + x^28 + x^26 + x^19 + x^17 + x^10 + x^6 + x^2 + x^0
or: 0x140A0443
It's not a standard CRC32 polynomial (according to Das Wiki), and I
don't *think* it's a Fire code... though I've been looking for the
original paper on those (P. Fire, "A class of multiple-error-correcting
binary codes for non-independent errors". Sylvania Reports RSL-E-2,
Sylvania Reconnaissance Systems, Mountain View, California, 1959) and
haven't had any success -- a few hits on Citeseer, but it appears all
copies of the paper have vanished into thin air.
What I'd really like to find out is more about how this algorithm
works... a model implementation (e.g. in C, Python or similar) would be
extremely useful, but at this point even a basic worked example ("here's
a chunk of data, now watch what happens if we flip some bits, and here's
how we fix it") would be extremely useful...
Thanks,
--
Phil.
classiccmp at philpem.me.uk
http://www.philpem.me.uk/
30 Jan
30 Jan
7:43 p.m.
The "Glover" is almost certainly Neal Glover, he of Cirrus Logic and
the disk drive ECC codes. I don't know if his stuff would be used in
an old WD controller, but at least you have a start with a name.
--Chuck
31 Jan
31 Jan
8:01 a.m.
Date: Mon, 31 Jan 2011 03:30:11 +0000
From: classiccmp at philpem.me.uk
To: cctalk at classiccmp.org
Subject: Any error correction gurus in the audience?
Hi guys,
As the subject says: are there any EDC/ECC code experts hanging around
on the list?
I'm working on implementing the 4-byte (32-bit) ECC code Western Digital
used on the WD2010 Winchester HDD Controller IC. This appears to be an
implementation of the ECC scheme explained in section 7.6 of National
Semiconductor's "Disk Interface Design Guide and User's Manual"
(appnote
AN-413).
It looks like the ECC scheme is based on running a CRC forwards over the
data to produce a 32-bit CRC, which is used to validate the data in the
same way the 16-bit CRC validates the IDAM. Error correction apparently
operates by running the CRC in reverse using an "inverse polynomial". I
can't see how this could work -- isn't a CRC by its very nature a
one-way operation?
---snip---
Hi
The CRC operation is deterministic. That means one can play it forwards
and backward.
The are two main ways of doing the corrections. One is to break
it into its prime factors and use the part with the largest span of
zeros in the polynomial to determine the error mask and the other
partials to determine the offset, based on the Chinese remainder
theorum.
It is a little complicated to describe but is what most of the crc chips used.
The other method is what you are seeing, playing the crc backwards
with no data coming in ( zeros for the data ) until the eror mask is seen.
the applying that mask to the data.
What I mean by the error mask is that in the polynomial, there is
a span of zeros. If you play it backwards until there are zeros in
all but the center portion where the zeros are, you have found
the error mask. Shifting it until is would be at the input edge of the
polynomial would give you the offset.
When playing backwards, you are only un-inputting zeros.
To tell you how to do it, you do the shift and xor in reverse order.
Run a CRC with some data in the sum, with zeros as input data
forwardwards and you'll see how on one can run it backwards
by shift and xor to get the same values going backwards.
If you go beyond the data size backwards without finding
an error mask, the error burst was too large and could not
be corrected.
I hope this makes some sense?
Dwight
1 Feb
1 Feb
5:54 a.m.
On 31/01/11 16:01, dwight elvey wrote:
What I mean by the error mask is that in the
polynomial, there is
a span of zeros. If you play it backwards until there are zeros in
all but the center portion where the zeros are, you have found
the error mask. Shifting it until is would be at the input edge of the
polynomial would give you the offset.
I noticed that Silicon Systems provided a different polynomial in the
SSI 32C452 datasheet:
x^32 + x^30 + x^26 + x^22 + x^15 + x^13 + x^6 + x^4 + x^0
0x14440A051
This polynomial is claimed to be capable of repairing up to an 8-bit
long error burst.
So what determines the longest error burst which can be corrected?
I hope this makes some sense?
Enough that I managed to figure out the algorithm -- with a little help
from:
* Adaptec AIC-100 Winchester Controller Chip datasheet -- VERY nice
description of the 5-bit error correction algorithm, but no polynomials.
* SSI 32C452 datasheet -- reasonable description of how
error-correction works
* NatSemi AN-413 -- good description of most disk-related subjects,
but out-and-out wrong in places. Do your own math, and find a secondary
reference for anything you find in here!
* WD 1002-05 Winchester controller OEM manual -- polynomials are
listed on page 1-3
* WD 1014 Error Detection/Support Logic Device datasheet -- p. 4-19
explains what parts of the disc data are included in the CRC calculation.
Note that the binary polynomial is loaded into the SSI chip shifted one
bit to the right and ANDed by 0x7FFFFFFF. To get the real polynomial as
you'd use for the XOR factor in a CRC32 routine, shift it one bit left
and set the LSbit (OR with 0x01).
Also note that AN413 has an incorrect binary value for the polynomial:
x^32 + x^28 + x^26 + x^19 + x^17 + x^10 + x^6 + x^2 + x^0
is really 0x1140A0445, not 0x140A0443. This cost me quite a few hours of
debugging...
And yes, the A1F8 header block is included in the CRC... the IV is
0xFFFFFFFF, then the first bytes clocked in are A1 followed by F8. Data
bits are clocked into the LFSR in order MSB to LSB. The CRC is stored on
the track as a 4-byte big-endian value. Clock everything from A1 to the
last CRC byte in exactly as it is, and you'll get a CRC remainder of
zero if the track data is valid. If it's anything else, do a couple of
re-reads (three or four), and if all else fails... bail out and do the ECC.
That was a "fun" way to spend two days... Ah well, long code-fests
aren't all bad when you've got some nice music and a big pot of tea on
standby. Snow Patrol, the Dixie Chicks, Genesis, Little Big Town, Sting
and The Police....
--
Phil.
classiccmp at philpem.me.uk
http://www.philpem.me.uk/
4844
days inactive
4845
days old
3 comments
3 participants
participants (3)
-
cclist＠sydex.com -
classiccmp＠philpem.me.uk -
dkelvey＠hotmail.com