Self-checking error correcting encoder/decoder

Claim 2

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.

Claim 3

Encoding apparatus according to claim 1 further comprising means for combining said first and second data bit groups and said appended parity check signals to form a data word for transmission or storage.

Claim 4

Encoding apparatus according to claim 1 wherein said first stage syndrome generator circuit is responsive to said data bits for generating a plurality of true intermediate syndrome signals, a plurality of complemented intermediate syndrome signals and a plurality of nyble parity relationships.

Claim 5

Encoding apparatus according to claim 3 wherein said second stage syndrome generator circuit comprises means responsive to said true intermediate syndrome signals, said complemented intermediate syndrome signals and to said nyble parity signals generated by the other syndrome generator circuit for generating complemented parity signals.

Claim 6

Encoding apparatus according to claim 4 wherein said second stage syndrome generator circuit comprises two identical half circuits, a first half circuit being responsive to said true intermediate syndrome signals and to said nyble parity signals generated by the other syndrome generator circuit for generating true parity signals and a second half circuit being responsive to said complemented intermediate syndrome signals and to said nyble parity signals generated by the other syndrome generator circuit for generating complemented parity signals.

Claim 7

Encoding apparatus according to claim 5 wherein said second stage syndrome generator circuit further comprises an encoder circuit responsive to said true parity signals and to said complemented parity signals for generating parity check signals.

Claim 8

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 one-half of the total number of data bits, a first encoder half circuit responsive to the data bits in said first bit group for generating a first set of parity relationships from the values of the data bits in said first group, a second encoder half circuit responsive to the data bits in said second bit group for generating a second set of parity relationships from the values of the data bits in said second group, parity generator means for deriving parity check signals from selected ones of said first and second sets, and means for appending said parity check signals to said first and second data bit groups.

Claim 9

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 one-half of the total number of data bits, a first encoder half circuit responsive to the data bits in said first bit group for generating a first set of parity relationships from the values of the data bits in said first group, a second encoder half circuit responsive to the data bits in said second bit group for generating a second set of parity relationships from the values of the data bits in said second group, parity generator means for deriving parity check signals from selected ones of said first and second sets, and means for appending said parity check signals to said first and second data bit groups.

Claim 10

Encoding apparatus according to claim 7 further comprising means for combining said first and second data bit groups and said appended parity check signals to form a data word for transmission or storage.

Claim 11

Encoding apparatus according to claim 7 wherein said first encoder half circuit and said second encoder half circuit are comprised of identical circuitry.

Claim 12

Encoding apparatus according to claim 7 wherein said first parity relationship set comprises a third subset of parity relations and a fourth subset of parity relations and said second parity relationship set comprises a fifth subset of parity relations and a sixth subset of parity relations.

Claim 13

Encoding apparatus according to claim 10 wherein said third subset and said fifth subset are derived using identical parity equations and said fourth subset and said sixth subset are derived using identical parity equations.

Claim 14

Encoding apparatus according to claim 11 wherein said parity generator means comprises two identical syndrome generator circuits, a first syndrome generator circuit generating a first set of syndrome signals and a second syndrome generator circuit generating a second set of syndrome signals.

Claim 15

Encoding apparatus according to claim 12 wherein said first set of syndrome signals are derived from said third and sixth subsets and said second set of syndrome signals are derived from said fourth and fifth subsets.

Claim 16

Encoding apparatus according to claim 13 wherein said first set of parity relationships comprises a plurality of true parity relationships and a plurality of complemented parity relationships and wherein said first syndrome generator circuit comprises two identical half circuits, a first half circuit being responsive to said true parity relationships for generating true syndrome signals.

Claim 17

Encoding apparatus according to claim 14 wherein said first syndrome generator circuit comprises a second half circuit being responsive to said complemented parity relationships for generating complemented syndrome signals.

Claim 18

Encoding apparatus according to claim 15 wherein said parity generator means further comprises encoder means responsive to said true syndrome signals and said complemented syndrome signals for generating said parity check signals.

Claim 19

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 a poriton 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 a portion of the total number of parity check bits, syndrome generator means comprising two identical generator half circuits, each of said generator half circuits comprising means responsive to said data bits in one of said groups and to said parity check bits in one of said groups for deriving parity check signals, syndrome decoder means comprising two identical decoder half circuits, each of said half circuits comprising a first stage decoder circuit responsive to selected parity check signals for generating intermediate data correction signals, and a second stage decoder responsive to intermediate data correction signals generated by the first stage decoder circuits in each decoder half circuit for generating erroneous bit pointers, and data correction means responsive to said data bits in said data word and to said erroreous bit pointers for generating corrected data bits.

Claim 20

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 a poriton 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 a portion of the total number of parity check bits, syndrome generator means comprising two identical generator half circuits, each of said generator half circuits comprising means responsive to said data bits in one of said groups and to said parity check bits in one of said groups for deriving parity check signals, syndrome decoder means comprising two identical decoder half circuits, each of said half circuits comprising a first stage decoder circuit responsive to selected parity check signals for generating intermediate data correction signals, and a second stage decoder responsive to intermediate data correction signals generated by the first stage decoder circuits in each decoder half circuit for generating erroneous bit pointers, and data correction means responsive to said data bits in said data word and to said erroreous bit pointers for generating corrected data bits.

Claim 21

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.

Claim 22

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.

Claim 23

Decoding apparatus according to claim 18 wherein said first decoder half circuit and said second decoder half circuit are comprised of identical circuitry.

Claim 24

Decoding apparatus according to claim 19 wherein said first parity relationship set comprises a third subset of parity relations and a fourth subset of parity relations and said second parity relationship set comprises a fifth subset of parity relations and a sixth subset of parity relations.

Claim 25

Decoding apparatus according to claim 20 wherein said third subset and said fifth subset are derived using identical parity equations and said fourth subset and said sixth subset are derived using identical parity equations.

Claim 26

Decoding apparatus according to claim 21 wherein said syndrome generator means comprises two identical syndrome generator circuits, a first syndrome generator circuit generating a first set of syndrome signals and a second syndrome generator circuit generating a second set of syndrome signals.

Claim 27

Decoding apparatus according to claim 22 wherein said first set of syndrome signals are derived from said third and sixth subsets and said second set of syndrome signals are derived from said fourth and fifth subsets.

Claim 28

Decoding apparatus according to claim 23 wherein said first set of parity relationships comprises a plurality of true parity relationships and a plurality of complemented parity relationships and wherein said first syndrome generator circuit comprises two identical half circuits, a first half circuit being responsive to said true parity relationships for generating true syndrome signals.

Claim 29

Decoding apparatus according to claim 24 wherein said first syndrome generator circuit comprises a second half circuit being responsive to said complemented parity relationships for generating complemented syndrome signals.

Claim 30

Decoding apparatus according to claim 25 wherein said syndrome decoder means comprises two identical half decoders, each of said half decoder circuits being responsive to one half of said parity check bits for generating one half of said data correction signals.

Claim 31

Decoding apparatus according to claim 26 wherein each of said half decoder circuits is comprised of a first stage syndrome decoder and a second stage syndrome decoder, said first stage syndrome decoder being responsive to one half of said parity check bits for generating a set of intermediate syndrome signals, and said second stage syndrome decoder being responsive to intermediate syndrome signals generated by first stage syndrome generators in both of said half decoder circuits for generating one half of said data correction signals.

Claim 32

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, means for dividing the bits of said first bit group into a first plurality of nybles, each of said first plurality of nybles consisting of a portion of the bits in said bit group, means for dividing the bits of said second bit group into a second plurality of nybles, each of said second plurality of nybles consisting of a portion of the bits in said bit group, nyble parity encoder means comprising two identical nyble parity circuits, one of said nyble parity circuits responsive to nyble bits in said first plurality of nybles for generating a set of nyble parities from said nyble bits, the other of said nyble parity circuits being responsive to nyble bits in said second plurality of nybles for generating a set of nyble parities from said nyble bits, byte parity encoder means responsive to selected ones of said nyble parities for generating a plurality of byte parity bits, and means for appending said byte parity bits to said first and second data bit groups.

Claim 33

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, means for dividing the bits of said first bit group into a first plurality of nybles, each of said first plurality of nybles consisting of a portion of the bits in said bit group, means for dividing the bits of said second bit group into a second plurality of nybles, each of said second plurality of nybles consisting of a portion of the bits in said bit group, nyble parity encoder means comprising two identical nyble parity circuits, one of said nyble parity circuits responsive to nyble bits in said first plurality of nybles for generating a set of nyble parities from said nyble bits, the other of said nyble parity circuits being responsive to nyble bits in said second plurality of nybles for generating a set of nyble parities from said nyble bits, byte parity encoder means responsive to selected ones of said nyble parities for generating a plurality of byte parity bits, and means for appending said byte parity bits to said first and second data bit groups.