Error correcting scheme

• US 4,564,944 A
• Filed: 12/30/1983
• Issued: 01/14/1986
• Est. Priority Date: 12/30/1983
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Seigler, Adrian E., Coppersmith, Don, Cocke, John, Strait, Gary E., Arnold, Richard F.
• Primary Examiner(s): Atkinson, Charles E.
• Application Number:
  US06/567,212
• Time in Patent Office: 746 Days
• Field of Search: 371/37, 371/38, 371/39, 371/40, 371/43, 364/200, 364/900
• US Class Current: 714/759
• CPC Class Codes: H03M 13/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence

Abstract

A method and an apparatus are disclosed for converting error syndromes of an error-correcting code to pointers which identify the positions of the erroneous bits. Each syndrome is converted by a plurality of hashing functions into a plurality of hash words, which in turn are used to address a plurality of read-only stores. The outputs of the read-only stores are logically combined to obtain the respective error pointer. A preferred embodiment uses three hashing functions (41, 43, 45) and three read-only stores (53, 55, 57) and combines their outputs by an Exclusive-Or function (59). The storage capacity and the processing time required for syndrome-to-error pointer conversion are reduced by the disclosed scheme.

Claims

1. A method for generating error position indications for use with an error detection and correction scheme in which error syndromes are produced, characterized by hashing each error syndrome by a plurality of hashing functions, using the respective hash outputs to address a plurality of lookup tables, and logically combining the table outputs to generate an error pointer.

2. A method in accordance with claim 1, characterized in that each error syndrome is converted simultaneously by three hashing functions into three different hash outputs for addressing three lookup tables, and that the three table outputs are combined bitwise by an EXCLUSIVE-OR operation.

3. A method in accordance with claim 1 or 2, characterized in that by each of the individual hashing functions, a plurality of different vectors is generated each by arranging selected binary digits of the respective syndrome in a predetermined order, and that the resulting vectors are combined bitwise in a plurality of different logical operations.

4. A method in accordance with claim 1 or 2, characterized in that each syndrome, besides being subjected to a plurality of hashing operations, is used as an address for a lookup table in which for each possible syndrome a binary indication is stored, and that the respective binary table output indicates whether the syndrome represented a correctable or a non-correctable error.

5. A method in accordance with claim 3, characterized in that for at least one of the hashing functions three different vectors are generated of which two are combined by a logical AND or OR operation, the intermediate result being combined with the third vector by an EXCLUSIVE-OR operation.

6. A method in accordance with claim 3, characterized in that for at least one of the hashing functions, four different vectors are generated of which two are combined by a logical AND or OR operation, the respective first intermediate result being combined with a third one of the vectors by a logical OR or AND operation, and the second intermediate result being combined with the fourth vector by an EXCLUSIVE-OR operation.

7. A method in accordance with claim 1, characterized in that each of the error pointers generated by logically combining the plurality of table outputs comprises, apart from up to two coded error position representations, in predetermined bit positions a coded indication of the number of correctable errors and of the type of bit (data, ECC) that is corrected, or of the fact that at least one uncorrectable error is present.

8. A method in accordance with claim 1, characterized in that in the case of multiple errors within any one compact bit group of a plurality of such bit groups, an error pointer is generated which comprises in predetermined bit positions (a) an identification of the bit group in which a plurality of bits is to be corrected, (b) a bit mask indicating which bit positions in the identified group comprise an erroneous bit to be inverted, and (c) an indication that a multiple correctable error is present within one bit group.

9. Double error correcting apparatus including means for generating an error syndrome, characterized in that it comprises

multiple hashing means connected to the syndrome generator for converting each syndrome to n different hash words,

read-only storage means connected to the output of said multiple hashing means to provide n auxiliary words in response to n hash words, and

EXCLUSIVE-OR means for logically combining said n auxiliary words into one error pointer.

10. Apparatus in accordance with claim 9, characterized in that second read-only storage means are provided which are connected to be addressable by the output of the syndrome generating means, and in which each addressable location is a single bit position whose contents indicates whether the addressing syndrome represents a correctable error condition or not.

11. Apparatus in accordance with claim 9, characterized in that decoding means are connected to receive the error pointer from said EXCLUSIVE-OR means, for decoding two separate fields of said error pointer into a direct position representation of erroneous bits to be inverted, and for decoding the remaining bit combination of said error pointer into an indication of the number of errors corrected.

12. Apparatus in accordance with claim 11, characterized in that said decoding means decodes the remaining bit combination of the error pointer into an indication that three or four correctable errors are present in one of plural 4-bit groups of the total information block, that it decodes one of the two fields of the error pointer as an identification of one of the 4-bit groups, and the second field as a mask indicating the three or four bits which are in error in the respective 4-bit group.

13. A method of converting names N_i of a given list of names into associated values V_i of a given list of values, characterized by

converting a selected name by H different hashing functions into H different hash words,

converting each of said H hash words by table lookup into an associated auxiliary value, and

combining the resulting H auxiliary values by a given logical operation into the single value associated to said selected name.