Error correction system for single-error correction, related-double-error correction and unrelated-double-error detection

Claim 2

In a data processing system, means for storing data bit sequences, each sequence consisting of a predetermined number of pairs of related information bits and check bits; means for receiving said information bits; and means responsive to each sequence of data bits for selectively transferring said information bits from said storing means to said receiving means, said transferring means including means responsive to each data bit sequence for uniquely detecting and correcting all single data bit errors, uniquely detecting and correcting all related double data bit errors or detecting all non-related double data bit errors.

Claim 3

A data processing system as in claim 1 wherein said transfErring means comprises: means receptive of a data bit sequence from said storage means for generating syndrome patterns indicative of data bit errors; means for decoding said patterns to uniquely locate all single errors and errors in a pair of related bits and to detect all double errors in unrelated bits.

Claim 4

A data processing system as in claim 2 wherein said check bits form three code groups, the first group representative of a first code having a capability of detecting single errors in said data bit sequence; the second group in combination with said first group representative of a second code having a capability of locating errors in a pair of related bits and of locating single errors detected by said first code; and the third group containing an odd-weight-column parity bit to detect errors in two unrelated bits.

Claim 5

A system as in claim 3 wherein said syndrome pattern generating means comprises: first and second syndrome check bit means for encoding the information bits transmitted from said storage means with said first and second codes thereby generating syndrome check bits, and for comparing each syndrome check bit with the corresponding check bits of said first and second code groups transmitted from said storage means; third syndrome check bit means for encoding the information bits transmitted from said storage means with an overall parity check bit generated over all of the elements in said transmitted data bit sequence and for comparing the overall parity check bit with said odd-weight-column parity bit transmitted from said storage means; whereby the comparison of each transmitted check bits with its corresponding syndrome check bits yield signals representative of syndrome error patterns.

Claim 6

A system as in claim 4 wherein said decoding means comprises: means responsive to said signals representative of syndrome error patterns for transmitting individual signals indicative of a single error or a pair of related errors; means responsive to said individual signals for generating an indication of which data bit or bits are in error.

Claim 7

A system as in claim 5 further comprising means responsive to said decoding means for correcting the data bit or bits in error.

Claim 8

A system as in claim 5 further comprising error indication means responsive to said signals representative of syndrome error patterns and said decoding means for signalling whether there is no error, a correctable single error, a correctable related double error or a non-correctable error in a data sequence.

Claim 9

A system as in claim 3 wherein: said first code is a single error correction code devised over the first bit locations in each said pair and replicated over the second bit location in each said pair; said second code includes minimum-3-weight-column, single error correction code devised over the first bit location in each said pair and spread over the second bit location in each said pair; and the code sequence generated by said first and second codes comprises a plurality of pairs of related check bit locations.

Claim 10

In combination in a data storage system including a source of information sequences, each said sequence comprising a plurality of pairs of related data bit locations, first parity check bit means responsive to an information sequence from said source for encoding said sequence with a first code having a capability of detecting single errors in said sequence; second parity check bit means responsive to said information sequence from said source for encoding said sequence with a second code, the first and second code in combination having a capability of locating errors in a pair of related bits and of locating single errors detected by said first code; and third parity check bit means responsive to said information sequence from said source for encoding said sequence with an odd-weight-column parity bit to detect errors in two unrelated bits.

Claim 11

In combination in a data storage system including a source of information sequences, each said sequence comprising a plurality of pairs of related data bit locations, first parity check bit means responsive to an information sequence from said source for encoding said sequence with a first code having a capability of detecting single errors in said sequence; second parity check bit means responsive to said information sequence from said source for encoding said sequence with a second code, the first and second code in combination having a capability of locating errors in a pair of related bits and of locating single errors detected by said first code; and third parity check bit means responsive to said information sequence from said source for encoding said sequence with an odd-weight-column parity bit to detect errors in two unrelated bits.

Claim 12

A combination as in cLaim 9 wherein said first code is a single error correction code devised over the first bit locations in each said pair and replicated over the second bit location in each said pair, and said second code is a minimum-3-weight-column, single error correction code devised over the first bit location in each said pair and spread over the second bit location in each said pair; and the code sequence generated by said first and second codes comprises a plurality of pairs of related check bit locations, the combination of said data bits and check bits being an encoded information sequence.

Claim 13

A combination as in claim 10 further comprising error-prone means for storing said encoded information sequences.

Claim 14

A combination as in claim 11 wherein said storage means comprises: a first set of basic operational modules, each module containing a pair of related bit locations for each encoded information sequence; another basic operational module, for storing said odd-weight-column parity bit for each encoded information sequence.

Claim 15

A combination as in claim 11 further comprising: means receptive of an encoded information sequence transmitted from said error-prone storage means for generating syndrome patterns indicative of errors in said transmitted encoded sequence; and means for decoding said patterns to locate a single error and errors in a pair of related bits and to detect errors in unrelated bits.

Claim 16

A combination as in claim 13 wherein said syndrome pattern generating means comprises: first and second syndrome check bit means for encoding the data bits transmitted from said storage means with said first and second codes thereby generating syndrome check bits and for comparing each syndrome check bit with the corresponding check bits encoded by said first and second parity check bit encoding means and transmitted from said storage means; third syndrome check bit means for encoding the data bits transmitted from said error-prone storage means with an overall parity check bit generated over all of the elements in said transmitted encoded information sequence and for comparing the overall parity check bit with said odd-weight-column parity bit transmitted from said storage means; whereby the comparison of each transmitted check bit with its corresponding syndrome check bit yield signals representative of syndrome error patterns.

Claim 17

A combination as in claim 14 wherein said decoding means comprises: means responsive to said signals representative of syndrome error patterns for transmitting individual signals indicative of a single error or a pair or related errors; means responsive to said individual signals for generating an indication of which data bit or bits are in error.

Claim 18

A combination as in claim 15 further comprising means responsive to said decoding means for correcting the data bit or bits in error.

Claim 19

A combination as in claim 15 further comprising error indication means responsive to said signals representative of syndrome error patterns and said decoding means for signalling whether there is no error, a correctable error or a non-correctable error in an encoded sequence.

Claim 20

In an error correction system operable to locate single errors and related double errors and to detect unrelated double errors in a codeword including an information sequence and parity check digits having first and second sets of data bit and check bit locations, respectively, each location in the first set related to a corresponding location in the second set, comprising: means for providing an information sequence, means responsive to said information sequence for generating a first group of parity check bits in accordance with a first single error correcting code devised for said first set of data bits, the element values in each data location in said first set being replicated in the corresponding location in said second set; means responsive to said information sequence for generating a second group of parity check bits in accordance with a second single error correcting code having a minimum-column-weight of three devised over the element values of said first set of data bits, the element values in each data location in said first set being spread into the data locations in said first and second sets; the column vectors of said related data bits formed by said second group of parity check bits being different in at least one position; means responsive to said information sequence for generating a parity check bit in accordance with an odd-weight-column code devised over the element values of each data bit location in said first and second parity bit groups; means for applying said information sequence and parity bits to an error-prone storage system; means receptive of said information sequence and parity bits from said storage system for encoding syndrome bits from said received information sequence and parity bits; and means for decoding said bits to identify a correctable single error, a related double error and an uncorrectable unrelated double error.

Claim 21

In an error correction system operable to locate single errors and related double errors and to detect unrelated double errors in a codeword including an information sequence and parity check digits having first and second sets of data bit and check bit locations, respectively, each location in the first set related to a corresponding location in the second set, comprising: means for providing an information sequence, means responsive to said information sequence for generating a first group of parity check bits in accordance with a first single error correcting code devised for said first set of data bits, the element values in each data location in said first set being replicated in the corresponding location in said second set; means responsive to said information sequence for generating a second group of parity check bits in accordance with a second single error correcting code having a minimum-column-weight of three devised over the element values of said first set of data bits, the element values in each data location in said first set being spread into the data locations in said first and second sets; the column vectors of said related data bits formed by said second group of parity check bits being different in at least one position; means responsive to said information sequence for generating a parity check bit in accordance with an odd-weight-column code devised over the element values of each data bit location in said first and second parity bit groups; means for applying said information sequence and parity bits to an error-prone storage system; means receptive of said information sequence and parity bits from said storage system for encoding syndrome bits from said received information sequence and parity bits; and means for decoding said bits to identify a correctable single error, a related double error and an uncorrectable unrelated double error.

Claim 22

A system as in claim 18 wherein said decoding means comprises: means providing intermediate outputs according to logical combinations of selected syndrome bits, means for providing logical combinations of all of said syndrome bits to form syndrome error vectors indicative of single and related errors in the information and parity check sequence.

Claim 23

A system as in claim 18 further including error location indication means responsive to a signal from said decoding means for generating an indication of the data location or locations in error.

Claim 24

A system as in claim 20 further including means responsive to said error location indication means for correcting the bits in said erroneous data location or locations.

Claim 25

A system as in claim 21 wherein said data bit correcting means comprises a set of EXCLUSIVE-OR circuits, one for each data position, each one having a first input connection from a corresponding data bit location in said error prone storage system and a second input connection from a corresponding error location indication means, thereby providing a corrected data signal at its output.

Claim 26

In a data processing system: means for storing a data bit sequence consisting of a predetermined number of pairs of related information bits and first check bits, means responsive to said information bits for generating a predetermined number of second check bits corresponding to said first check bits, means for comparing corresponding ones of said first and second check bits to generate a unique syndrome bit pattern, means responsive to said unique syndrome bit pattern for producing a signal identifying a single information bit error or a related double information bit error, and means responsive to said information bits and said signal identifying means for correcting said single information bit error or said related double information bit error.

Claim 27

In a data processing system: means for storing a data bit sequence consisting of a predetermined number of pairs of related information bits and first check bits, means responsive to said information bits for generating a predetermined number of second check bits corresponding to said first check bits, means for comparing corresponding ones of said first and second check bits to generate a unique syndrome bit pattern, means responsive to said unique syndrome bit pattern for producing a signal identifying a single information bit error or a related double information bit error, and means responsive to said information bits and said signal identifying means for correcting said single information bit error or said related double information bit error.

Claim 28

A data processing system as in claim 23 wherein said first check bits form two code groups, the first group representative of a first code having a capability of detecting single errors in said data bit sequence, and the second group in combination with said first group representative of a second code having a capability of uniquely locating errors in a pair of related bits and of locating single errors detected by said first code.

Claim 29

A system as in claim 24 further comprising error indication means responsive to said syndrome bit pattern and said signal identifying means for signalling whether there is no error, a correctable single error or a correctable related double error.

Claim 30

A system as in claim 24 wherein: said first code is a single error correction code devised over the first bit locations in each said pair and replicated over the second bit locations in each said pair; said second code is a minimum-3-weight-column, single error correction code devised over the first bit location in each said pair and spread over the second bit location in each said pair; and the code sequence generated by said first and second codes comprises a plurality of pairs of related check bit locations.

Claim 31

In combination in a data storage system including a source of information sequences, each said sequence comprising a plurality of pairs of related data bit locations, first parity check bit means for encoding said sequence with a first code having a capability of detecting single errors in said sequence; and second parity check bit means for encoding said sequence with a second code, the first and second code in combination having a capability of locating errors in a pair or related bits and of locating single errors detected by said first code.

Claim 32

In combination in a data storage system including a source of information sequences, each said sequence comprising a plurality of pairs of related data bit locations, first parity check bit means for encoding said sequence with a first code having a capability of detecting single errors in said sequence; and second parity check bit means for encoding said sequence with a second code, the first and second code in combination having a capability of locating errors in a pair or related bits and of locating single errors detected by said first code.

Claim 33

A combination as in claim 27 wherein said first code is a single error correction code devised over the first bit locations in each said pair and replicated over the second bit location in each said pair, and said second code is a minimum-3-weight-column, single error correction code devised over the first bit location in each said pair and spread over the second bit location in each said pair; and the code sequence generated by said first and second codes comprises a plurality of pairs of related check bit locations, the combination of said data bits and check bits being an encoded information sequence.

Claim 34

A combination as in claim 28 further comprising error-prone storage means responsive to said source of information sequences and said first and second parity check circuits for storing said encoded information sequences.

Claim 35

A combination as in claim 29 wherein said storage means comprises a set of basic operational modules, each module containing a pair of related bit locations for storing said encoded information sequence.

Claim 36

A combination as in claim 29 further comprising: means receptive of an encoded information sequence transmitted from said error-prone storage means for generating syndrome patterns indicative of errors in said transmitted encoded sequence; and means for decoding said patterns to locate a single error and errors in a pair of related bits.

Claim 37

A combination as in claim 31 wherein said syndrome pattern generating means comprises: first and second syndrome check bit means for encoding the data bits transmitted from said storage means with said first and second codes thereby generating syndrome check bits and for comparing each syndrome check bit with the corresponding check bits encoded by said first and second parity check bit encoding means and transmitted from said storage means; whereby the comparison of each transmitted check bit with its corresponding syndrome check bit yields signals representative of syndrome error patterns.

Claim 38

A combination as in claim 32 wherein said decoding means comprises: means responsive to said signals representative of syndrome error patterns for transmitting individual signals indicative of a single error or a pair of related errors; means responsive to said individual signals for generating an indication of which data bit or bits are in error.

Claim 39

A combination as in claim 33 further comprising means responsive to said decoding means for correcting the data bit or bits in error.

Claim 40

A combination as in claim 33 further comprising error indication means responsive to said signals representative of syndrome error patterns and said decoding means for signalling whether there is no error or a correctable error in an encoded sequence.

Claim 41

In an error correction system operable to locate single errors and related double errors in a codeword including an information sequence and parity check digits having first and second sets of data bit and check bit locations, respectively, each location in the first set related to a corresponding location in the second set, comprising: means for providing an information sequence, means responsive to said information sequence for generating a first group of parity check bits in accordance with a first single error correcting code devised for said first set of data bits, the element values in each data location in said first set being replicated in the corresponding location in said second set; means responsive to said information sequence for generating a second group of parity check bits in accordance with a second single error correcting code having a minimum-column-weight of three devised over the element values of said first set of data bits, the element values in each data location in said first set being spread into the data locations in said first and second sets; the column vectors of said related data bits formed by said second group of parity check bits being different in at least one position; means for applying said information sequence and parity bits to an error-prone storage system; means receptive of said information sequence and parity bits from said storage system for encoding syndrome bits from said received information sequence and parity bits; and means for decoding said bits to identify a correctable single error or a related double error.

Claim 42

In an error correction system operable to locate single errors and related double errors in a codeword including an information sequence and parity check digits having first and second sets of data bit and check bit locations, respectively, each location in the first set related to a corresponding location in the second set, comprising: means for providing an information sequence, means responsive to said information sequence for generating a first group of parity check bits in accordance with a first single error correcting code devised for said first set of data bits, the element values in each data location in said first set being replicated in the corresponding location in said second set; means responsive to said information sequence for generating a second group of parity check bits in accordance with a second single error correcting code having a minimum-column-weight of three devised over the element values of said first set of data bits, the element values in each data location in said first set being spread into the data locations in said first and second sets; the column vectors of said related data bits formed by said second group of parity check bits being different in at least one position; means for applying said information sequence and parity bits to an error-prone storage system; means receptive of said information sequence and parity bits from said storage system for encoding syndrome bits from said received information sequence and parity bits; and means for decoding said bits to identify a correctable single error or a related double error.

Claim 43

A system as in claim 36 wherein said decoding means comprises: means providing intermediate outputs according to logical combinations of selected syndrome bits; and means for providing logical combinations of all of said syndrome bits to form syndrome error vectors indicative of single and related errors in the information and parity check sequence.

Claim 44

A system as in claim 36 further including error location indication means responsive to a signal from said decoding means for generating an indication of the data location or locations in error.

Claim 45

A system as in claim 38 further including means responsive to said error location indication means for correcting the bits in said erroneous data location or locations.

Claim 46

A system as in claim 39 wherein said data bit correcting means comprises a set of EXCLUSIVE-OR circuits, one for each data position, each one having a first input connection from a corresponding data bit location in said error prone storage system and a second input connection from a corresponding error location indication means, thereby providing a corrected data signal at its output.

Claim 47

In a data processing system, means for storing a data bit sequence consisting of a predetermined number of pairs of related information bits and first check bits; means responsive to said information bits for generating a predetermined number of second check bits corresponding to said first check bits; means for comparing corresponding ones of said first and second check bits to generate a syndrome bit pattern; said syndrome bit pattern having a first unique configuration for indicating the absence of data bit errors, second unique configurations for indicating the presence of correctable single data bit errors, third unique configurations for indicating the presence of correctable related double bit errors or fourth configurations for indicating the presence of non-correctable double data bit errors, the fourth configurations being different from any of said third unique configurations; and means responsive to said syndrome bit pattern for producing a signal indicating the absence of data bit errors, the presence of a correctable single data bit error, the presence of correctable related double data bit errors or the presence of non-correctable double data bit errors.

Claim 48

In a data processing system, means for storing a data bit sequence consisting of a predetermined number of pairs of related information bits and first check bits; means responsive to said information bits for generating a predetermined number of second check bits corresponding to said first check bits; means for comparing corresponding ones of said first and second check bits to generate a syndrome bit pattern; said syndrome bit pattern having a first unique configuration for indicating the absence of data bit errors, second unique configurations for indicating the presence of correctable single data bit errors, third unique configurations for indicating the presence of correctable related double bit errors or fourth configurations for indicating the presence of non-correctable double data bit errors, the fourth configurations being different from any of said third unique configurations; and means responsive to said syndrome bit pattern for producing a signal indicating the absence of data bit errors, the presence of a correctable single data bit error, the presence of correctable related double data bit errors or the presence of non-correctable double data bit errors.