Browse Prior Art Database

Error Correcting Codes Predict for an Incrementer and Decrementer

IP.com Disclosure Number: IPCOM000115331D
Original Publication Date: 1995-Apr-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 4 page(s) / 142K

Publishing Venue

IBM

Related People

Ho, K: AUTHOR [+3]

Abstract

A method for creating Single Error Correction/Double Error Detection (SEC/DED) Error Correcting Codes (ECC) in parallel with an increment or decrement operation is disclosed. The method is called ECC prediction since it is based on the input to an increment/decrement circuit rather than the output. The idea is unique in that 1) it results in a faster and smaller implementation than ECC generation, 2) a grouping strategy is detailed which eliminates many exclusive-OR gates, and 3) provides ECC predict for decrementation at no additional cost to ECC predict for incrementation. This idea is useful for high speed fault tolerant computers with time of day clocks or interval timers protected by ECC.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 46% of the total text.

Error Correcting Codes Predict for an Incrementer and Decrementer

      A method for creating Single Error Correction/Double Error
Detection (SEC/DED) Error Correcting Codes (ECC) in parallel with an
increment or decrement operation is disclosed.  The method is called
ECC prediction since it is based on the input to an
increment/decrement circuit rather than the output.  The idea is
unique in that 1) it results in a faster and smaller implementation
than ECC generation, 2) a grouping strategy is detailed which
eliminates many exclusive-OR gates, and 3) provides ECC predict for
decrementation at no additional cost to ECC predict for
incrementation.  This idea is useful for high speed fault tolerant
computers with time of day clocks or interval timers protected by
ECC.

      A SEC/DED ECC transmission code provides a high level of fault
tolerance for transmitting data or maintaining data in memory.  An
ECC transmission code is not the best code for checking an increment
or decrement function, in this case an arithmetic or residue code
might be more appropriate since it can detect multi-bit failures.
But for an implementation of a register and a counter in which the
count operation is infrequent, it is best to protect the register
with a transmission code.  Also, these codes are useful if the data
from the counter is to be transmitted far or if the destination is a
memory array.  An example of a (72, 64) SEC/DED ECC transmission code
is shown by the parity-check matrix in Fig. 1.  64 bits of data is
protected with 8 check bits (each denoting an ECC group) for a total
of 72 bits.  A "1" indicates a bit that contributes to the ECC group.
Each row denotes an ECC group which has one check bit associated with
it.  This implies that check bit 0 ( CH(0) ) is given by the
exclusive-OR of data bits 0 to 7, 24 to 31, 32, 36, 37, 38, 40, 44,
45, 46, 48, 52, 53, 54, 56, 60, 61, and 62.  The term "group" is used
to define the contributing bits to a given ECC check bit and the term
"subgroup" will be used to define a partition of the contributing
bits of a group.

      The parity of group 0 (or equivalently check bit 0) for
incrementation is given by:
    P(S(0:63,0)) = CH(0) = P(S(0:7)) X P(S(24:31)) X P(S(32)) X
  P(S(36:38)) X P(S(40)) X P(S(44:46)) X
      P(S(48)) X P(S(52:54)) X P(S(56)) X P(S(60:62)) X 1
  where X represents an exclusive-OR, S is the sum resulting from
incrementation, and P is the parity (in this case, odd parity).

      This is the traditional method of producing check bits by ECC
generation.  Fig. 2 shows that ECC generation waits for the
incrementation to be completed prior to computing the ECC of the sum,
while ECC predict calculates it in parallel.

      For ECC predict, the check bits are expressed in terms of the
input A.  This is accomplished by expressing them first in terms of
the old check bit and the change (or reversing) of a subgroup's
parity.  Define R(k:j,m) to be 1 if the...