US 4,736,376 A · Self-checking error correcting encoder/decoder

Abstract

Encoding/decoding circuitry which processes data and both corrects single errors and detects multiple errors is disclosed. The circuitry is both fail-safe and self-checking in that no internal device failure can alter data without producing improperly encoded outputs and all failures quickly reveal themselves through normal usage even if they do not actually cause any data to be modified. The circuitry can be configured in two identical halves with each half operating on one half of the data so that the circuitry can be advantageously constructed with large scale integrated circuits. Error-detecting information in the form of a syndrome produced by each circuit half is combined with similar syndrome information produced by the other circuit half. The combined syndrome information is then decoded to generate error correction information which is used to modify the data bit outputs to correct detected errors. A failure in either circuit half modifies the combined syndrome information in such a way that the modification can either be detected or else causes no erroneous data bit modification.

Claims28

Dependent claims

Apparatus for encoding digital data for storage or transmission, said data being comprised of at least one data word having a plurality of bits, said apparatus comprising,

means for dividing the bits of said data word into a first bit group and a second bit group, each group consisting of a portion of the total number of data bits,
syndrome generator means comprising two identical syndrome generator circuits, each of said syndrome generator circuits comprising a first stage syndrome generator circuit responsive to data bits in one of said bit groups for generating an intermediate syndrome signal, and a second stage syndrome generator circuit responsive to the intermediate syndrome signals from the first stage syndrome generator circuits in both of said syndrome generator circuits for generating a set of parity check signals, and
means for appending said parity check signals to said first and second data bit groups.

Apparatus for decoding digital data after retrieval from storage or after transmission, said data being comprised of at least one data word having a plurality of data bits and a plurality of parity check bits appended to said data bits, said apparatus comprising,

means for dividing the bits of said data word into a first bit group and a second bit group, each group consisting of one-half of the total number of data bits,
means for dividing the parity check bits of said data word into a first parity check bit group and a second parity check bit group, each parity check bit group consisting of one-half of the total number of parity check bits,
a first decoder half circuit responsive to the data bits in said first data bit group and to the parity check bits in said first parity check bit group for generating a first set of parity relationships from the values of the data bits in said first data bit group and the values of said parity check bits in said first parity check bit group,
a second decoder half circuit responsive to the data bits in said second data bit group and to the parity check bits in said second parity check bit group for generating a second set of parity relationships from the values of the data bits in said second data bit group and the values of said parity check bits in said second parity check bit group,
syndrome generator means for deriving parity check signals from selected ones of said first and second sets,
syndrome decoder means responsive to said parity check signals for generating data correction signals, and
data correction means responsive to said said data bits in said data word and to said data correction signals for generating corrected data bits.

4 more elements

Dependencies are inferred from the claim text.

Self-checking error correcting encoder/decoder

Life of this patent

Self-checking error correcting encoder/decoder

Life of this patent

Abstract

Claims28