Fire Codes

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

On Tue, 28 Jul 2015 23:54:53 +0000 (UTC), spope33@speedymail.org
(Steve Pope) wrote:

>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

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:

>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

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.

Rob Doyle  <radioengr@gmail.com> wrote:

>"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'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