>"Fire codes have a high miscorrection probability related to
>double-burst errors (errors at two locations separated by more than the
>detection span) and are not recommended by National."
>The DEC operating system driver works around this limitation by
>neutering the Fire Code ECC. Although the code can correct 11-bit burst
>errors, there is a comment in the software that the driver reports an
>uncorrectable disk error if the error length is greater than 4 bits.
>I guess this goes into the "fast, easy, but really sloppy" category.
I'm not sure I'd come to that conclusion. It is often sensible
to use only a fraction of the error-correction capacity of a code,
and consider anything with more errors as possibly corrupted.
Furthermore the goal in disk storage is to map out bad sectors
before they fail entirely, which may be part of what is meant by
"reporting an uncorrectable disk error".
Steve
Reply by Rob Doyle●July 29, 20152015-07-29
On 7/28/2015 5:10 PM, glen herrmannsfeldt wrote:
> Steve Pope <spope33@speedymail.org> wrote:
>
> (snip on disk drive error correction)
>>> Yeah, short packets are always a tricky thing to try to protect with
>>> sufficient FEC/ECC.
>
>> I looked it up and it is even shorter -- 184 bits before adding
>> Fire code parity (40 bits) and four BCC tail bits for a total
>> of 228 bits, becoming 456 bits after the BCC.
>> The Fire code can correct any 11-bit burst.
>
> https://en.wikipedia.org/wiki/History_of_IBM_magnetic_disk_drives?searchDepth=2#IBM_3330
>
> is the description of the IBM version of the drive.
> (Including mentioning the 11 bit burst correction.)
>
> Note that it was announced in 1970.
>
>> Should they have used an RS code instead?
>
>> I think the answer is yes -- Depth 2 interleaving of two RS codewords,
>> (22,18) and (23,19) with five-bit symbols (note there is one pad
>> bit, but it need not be transmitter) this would correct any single
>> burst up to 16 bits, and many other error patterns as well that
>> the Fire code is unable to handle.
>
> As previously noted, the fire code is simpler to process, which
> was important in 1970.
>
>> There could have been other details of the system that made an
>> RS code unworkable; no real way of telling.
>
> -- glen
>
I did some more reading...
I found a National Semiconductor App Note that states:
"Fire codes have a high miscorrection probability related to
double-burst errors (errors at two locations separated by more than the
detection span) and are not recommended by National."
http://www.ti.com/lit/an/snoa710/snoa710.pdf
The DEC operating system driver works around this limitation by
neutering the Fire Code ECC. Although the code can correct 11-bit burst
errors, there is a comment in the software that the driver reports an
uncorrectable disk error if the error length is greater than 4 bits.
I guess this goes into the "fast, easy, but really sloppy" category.
I think I see why Fire Codes have fallen into disfavor now.
Thanks everyone for the history lesson.
Rob.
Reply by Steve Pope●July 28, 20152015-07-28
Eric Jacobsen <eric.jacobsen@ieee.org> wrote:
>The notable advantages of the Fire Code seem to be simplicity and low
>latency. It could be that those were deemed good trades for the
>performance difference.
It would be lower-latency if one had an algebraic decoding method
for the Fire code.
I am only aware of the burst-trapping method, which is inherently an
operation repeated over the length (on the order of 184) of the
codeword. This is more operations than it takes to decode the
two two-error-correcting RS codes (since, one can use a root-solver
instead of a root search if t < 6).
Probably there is a way to algebraically decode the Fire code.
I just never researched it; the one time I had to design a
GSM PHY for a client I just did the burst trapping, since
it seemed to give an acceptable (to the client) result and
there were many more difficult problems to solve.
Steve
Reply by Steve Pope●July 28, 20152015-07-28
glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:
>Steve Pope <spope33@speedymail.org> wrote:
>
>(snip on disk drive error correction)
>>>Yeah, short packets are always a tricky thing to try to protect with
>>>sufficient FEC/ECC.
>
>> I looked it up and it is even shorter -- 184 bits before adding
>> Fire code parity (40 bits) and four BCC tail bits for a total
>> of 228 bits, becoming 456 bits after the BCC.
>> The Fire code can correct any 11-bit burst.
>
>https://en.wikipedia.org/wiki/History_of_IBM_magnetic_disk_drives?searchDepth=2#IBM_3330
>
>is the description of the IBM version of the drive.
>(Including mentioning the 11 bit burst correction.)
>
>Note that it was announced in 1970.
>
>> Should they have used an RS code instead?
>
>> I think the answer is yes -- Depth 2 interleaving of two RS codewords,
>> (22,18) and (23,19) with five-bit symbols (note there is one pad
>> bit, but it need not be transmitter) this would correct any single
>> burst up to 16 bits, and many other error patterns as well that
>> the Fire code is unable to handle.
>
>As previously noted, the fire code is simpler to process, which
>was important in 1970.
I was actually talking about the (*relatively* recent) GSM cellular
standard, not the much earlier disk IBM drive design.
But that they both use an 11-bit-burst-correcting Fire code is ...
not necessarily accidental. I'll have to look up whether they
use the same polynomial.
Steve
>Eric Jacobsen <eric.jacobsen@ieee.org> wrote:
>
>>On Tue, 28 Jul 2015 20:25:35 +0000 (UTC), spope33@speedymail.org
>
>>>I think a more modern design would have something more like a
>>>RS code, but the Fire Code codewords needed to be exceptionally
>>>short -- I think about 500 bits, which is getting pretty small
>>>for an RS code.
>
>>Yeah, short packets are always a tricky thing to try to protect with
>>sufficient FEC/ECC.
>
>I looked it up and it is even shorter -- 184 bits before adding
>Fire code parity (40 bits) and four BCC tail bits for a total of 228 bits,
>becoming 456 bits after the BCC. The Fire code can correct
>any 11-bit burst.
>
>Should they have used an RS code instead?
>
>I think the answer is yes -- Depth 2 interleaving of two RS codewords,
>(22,18) and (23,19) with five-bit symbols (note there is one pad
>bit, but it need not be transmitter) this would correct any single
>burst up to 16 bits, and many other error patterns as well that
>the Fire code is unable to handle.
>
>There could have been other details of the system that made an
>RS code unworkable; no real way of telling.
>
>Steve
The notable advantages of the Fire Code seem to be simplicity and low
latency. It could be that those were deemed good trades for the
performance difference.
Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com
Reply by glen herrmannsfeldt●July 28, 20152015-07-28
Steve Pope <spope33@speedymail.org> wrote:
(snip on disk drive error correction)
>>Yeah, short packets are always a tricky thing to try to protect with
>>sufficient FEC/ECC.
> I looked it up and it is even shorter -- 184 bits before adding
> Fire code parity (40 bits) and four BCC tail bits for a total
> of 228 bits, becoming 456 bits after the BCC.
> The Fire code can correct any 11-bit burst.
> I think the answer is yes -- Depth 2 interleaving of two RS codewords,
> (22,18) and (23,19) with five-bit symbols (note there is one pad
> bit, but it need not be transmitter) this would correct any single
> burst up to 16 bits, and many other error patterns as well that
> the Fire code is unable to handle.
As previously noted, the fire code is simpler to process, which
was important in 1970.
> There could have been other details of the system that made an
> RS code unworkable; no real way of telling.
>>I think a more modern design would have something more like a
>>RS code, but the Fire Code codewords needed to be exceptionally
>>short -- I think about 500 bits, which is getting pretty small
>>for an RS code.
>Yeah, short packets are always a tricky thing to try to protect with
>sufficient FEC/ECC.
I looked it up and it is even shorter -- 184 bits before adding
Fire code parity (40 bits) and four BCC tail bits for a total of 228 bits,
becoming 456 bits after the BCC. The Fire code can correct
any 11-bit burst.
Should they have used an RS code instead?
I think the answer is yes -- Depth 2 interleaving of two RS codewords,
(22,18) and (23,19) with five-bit symbols (note there is one pad
bit, but it need not be transmitter) this would correct any single
burst up to 16 bits, and many other error patterns as well that
the Fire code is unable to handle.
There could have been other details of the system that made an
RS code unworkable; no real way of telling.
Steve
>Eric Jacobsen <eric.jacobsen@ieee.org> wrote:
>
>>On Tue, 28 Jul 2015 18:17:49 +0000 (UTC), spope33@speedymail.org
>
>>>The most recent use I can recall is in GSM. There is a fire code
>>>in every GSM phone; the convolutional code and Fire code are
>>>concatenated, with the Fire code being the outer code.
>
>>>The idea, I believe, is that any errors at the output of the convolutional
>>>decoder will manifest as a short burst.
>
>>That's often true, although a lot of people have a hard time believing
>>this for some reason. It's also the reason that convolutional codes
>>are often concatenated with RS codes.
>
>>When a Viterbi (or even sequential) decoder makes an output error, if
>>the error is large enough (i.e., the soft metrics are really bad), it
>>can lose track of a whole chunk of the trellis, which means it's going
>>to barf out garbage until it finds its way back to the correct path on
>>the trellis. So usually you see two types of errors coming out of a
>>decoder for a convolutional code, the dribbly single-bit errors or
>>chunks of errors at a time.
>
>>If I understand things correctly Fire Codes trade flexibility for
>>simplicity in that they have a fairly restricted set of block errors
>>that they can fix, but they can do that with a simple solution. I
>>would guess that a properly designed interleaver, that interleaves
>>chunks of the size matched to the Fire Code, would give it a fair
>>chance of cleaning up the block errors that come ouf of a decoder for
>>a convolutional code (which is usually a Viterbi decoder).
>
>And in GSM (GMSK modes) the burst errors have another possible source,
>which is the trellis equalizer.
Yup.
>I think a more modern design would have something more like a
>RS code, but the Fire Code codewords needed to be exceptionally
>short -- I think about 500 bits, which is getting pretty small
>for an RS code.
>
>Steve
Yeah, short packets are always a tricky thing to try to protect with
sufficient FEC/ECC.
Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com
>>The most recent use I can recall is in GSM. There is a fire code
>>in every GSM phone; the convolutional code and Fire code are
>>concatenated, with the Fire code being the outer code.
>>The idea, I believe, is that any errors at the output of the convolutional
>>decoder will manifest as a short burst.
>That's often true, although a lot of people have a hard time believing
>this for some reason. It's also the reason that convolutional codes
>are often concatenated with RS codes.
>When a Viterbi (or even sequential) decoder makes an output error, if
>the error is large enough (i.e., the soft metrics are really bad), it
>can lose track of a whole chunk of the trellis, which means it's going
>to barf out garbage until it finds its way back to the correct path on
>the trellis. So usually you see two types of errors coming out of a
>decoder for a convolutional code, the dribbly single-bit errors or
>chunks of errors at a time.
>If I understand things correctly Fire Codes trade flexibility for
>simplicity in that they have a fairly restricted set of block errors
>that they can fix, but they can do that with a simple solution. I
>would guess that a properly designed interleaver, that interleaves
>chunks of the size matched to the Fire Code, would give it a fair
>chance of cleaning up the block errors that come ouf of a decoder for
>a convolutional code (which is usually a Viterbi decoder).
And in GSM (GMSK modes) the burst errors have another possible source,
which is the trellis equalizer.
I think a more modern design would have something more like a
RS code, but the Fire Code codewords needed to be exceptionally
short -- I think about 500 bits, which is getting pretty small
for an RS code.
Steve
>Steve Underwood <steveu@dis.org> wrote:
>
>>I remember Fire codes being a big thing when they were introduced. There
>>were articles about them all over the place. I think people were
>>inspired by their simplicity.
>
>The most recent use I can recall is in GSM. There is a fire code
>in every GSM phone; the convolutional code and Fire code are
>concatenated, with the Fire code being the outer code.
>
>The idea, I believe, is that any errors at the output of the convolutional
>decoder will manifest as a short burst.
That's often true, although a lot of people have a hard time believing
this for some reason. It's also the reason that convolutional codes
are often concatenated with RS codes.
When a Viterbi (or even sequential) decoder makes an output error, if
the error is large enough (i.e., the soft metrics are really bad), it
can lose track of a whole chunk of the trellis, which means it's going
to barf out garbage until it finds its way back to the correct path on
the trellis. So usually you see two types of errors coming out of a
decoder for a convolutional code, the dribbly single-bit errors or
chunks of errors at a time.
If I understand things correctly Fire Codes trade flexibility for
simplicity in that they have a fairly restricted set of block errors
that they can fix, but they can do that with a simple solution. I
would guess that a properly designed interleaver, that interleaves
chunks of the size matched to the Fire Code, would give it a fair
chance of cleaning up the block errors that come ouf of a decoder for
a convolutional code (which is usually a Viterbi decoder).
Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com