Fire Codes

I was studying the schematic of a 1970's era washing machine sized disk
drive [1] wondering how it performed ECC. Everything was built out of
simple SSI TTL circuitry.

The disk controller had a 13-bit register that provided the "Error
Position" and another 12-bit register that provided the "Error Pattern".
I couldn't find any explanation for how this circuit worked in any of
the disk drive documentation although the other circuitry had an
excellent circuit description.

I found a circuit that looked like a 32-bit CRC but it was wrapped other
stuff like a zero detector and some counters and comparators. I wanted
to understand how something so simple could perform error detection and
correction.

I finally extracted the polynomial from the schematic did a Google
search on the polynomial. One reference mentioned that this polynomial
was a "Fire Code" after P. Fire. This particular implementation could
correct 11-bit burst errors so all of the register sizes made sense.

I've never heard of Fire Codes.

So - my question... Are there any modern uses of Fire Codes or has it
gone the way of the Dodo bird?

Thanks -
Rob

[1] DEC RP06 disk drive.

Rob Doyle  <radioengr@gmail.com> wrote:

>I was studying the schematic of a 1970's era washing machine sized disk
>drive [1] wondering how it performed ECC. Everything was built out of
>simple SSI TTL circuitry.

>The disk controller had a 13-bit register that provided the "Error
>Position" and another 12-bit register that provided the "Error Pattern".
>I couldn't find any explanation for how this circuit worked in any of
>the disk drive documentation although the other circuitry had an
>excellent circuit description.
>
>I found a circuit that looked like a 32-bit CRC but it was wrapped other
>stuff like a zero detector and some counters and comparators. I wanted
>to understand how something so simple could perform error detection and
>correction.
>
>I finally extracted the polynomial from the schematic did a Google
>search on the polynomial. One reference mentioned that this polynomial
>was a "Fire Code" after P. Fire. This particular implementation could
>correct 11-bit burst errors so all of the register sizes made sense.
>
>I've never heard of Fire Codes.
>
>So - my question... Are there any modern uses of Fire Codes or has it
>gone the way of the Dodo bird?

Yes, they are still used.  The decoders are diabolically simple --
first, you use a FSR to create a residue, then you shift the
register backwards until it contains a short enough string of
one's such that you know you've found the error pattern.  In your
example, when after back-shifting the 32 bit register exhibits all 
zero's except in any 11 consecutive bits, you are done and that is 
your burst error pattern.

Steve

On 07/28/2015 10:48 PM, Rob Doyle wrote:
> I was studying the schematic of a 1970's era washing machine sized disk
> drive [1] wondering how it performed ECC. Everything was built out of
> simple SSI TTL circuitry.
>
> The disk controller had a 13-bit register that provided the "Error
> Position" and another 12-bit register that provided the "Error Pattern".
> I couldn't find any explanation for how this circuit worked in any of
> the disk drive documentation although the other circuitry had an
> excellent circuit description.
>
> I found a circuit that looked like a 32-bit CRC but it was wrapped other
> stuff like a zero detector and some counters and comparators. I wanted
> to understand how something so simple could perform error detection and
> correction.
>
> I finally extracted the polynomial from the schematic did a Google
> search on the polynomial. One reference mentioned that this polynomial
> was a "Fire Code" after P. Fire. This particular implementation could
> correct 11-bit burst errors so all of the register sizes made sense.
>
> I've never heard of Fire Codes.
>
> So - my question... Are there any modern uses of Fire Codes or has it
> gone the way of the Dodo bird?
>
> Thanks -
> Rob
>
> [1] DEC RP06 disk drive.

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.

Steve

Rob Doyle <radioengr@gmail.com> wrote:
> I was studying the schematic of a 1970's era washing machine sized disk
> drive [1] wondering how it performed ECC. Everything was built out of
> simple SSI TTL circuitry.
 
> The disk controller had a 13-bit register that provided the "Error
> Position" and another 12-bit register that provided the "Error Pattern".
> I couldn't find any explanation for how this circuit worked in any of
> the disk drive documentation although the other circuitry had an
> excellent circuit description.
 
(snip) 
> [1] DEC RP06 disk drive.

The RP06 is the same as an IBM 3330-11, with different control
logic. As far as I know, the data formatting such as ECC is the
same.  

Not so long ago, the question came up about reading RP06 disks
on 3330-11 drives with the 3830 controller/formatter. 

And yes, all that was available at the time was very simple logic.

-- glen

On 7/28/15 10:48 AM, Rob Doyle wrote:
>
> I've never heard of Fire Codes.
>

i thought those were the codes that require smoke detectors in some 
American cities to be both AC and DC powered.

:-)


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

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.


Steve

On Tue, 28 Jul 2015 18:17:49 +0000 (UTC), spope33@speedymail.org
(Steve Pope) wrote:

>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

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.

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

On Tue, 28 Jul 2015 20:25:35 +0000 (UTC), spope33@speedymail.org
(Steve Pope) wrote:

>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

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