System for multiple error detection with single and double bit error correction

• US 4,589,112 A
• Filed: 01/26/1984
• Issued: 05/13/1986
• Est. Priority Date: 01/26/1984
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Karim, Faraydon O.
• Primary Examiner(s): Atkinson, Charles E.
• Application Number:
  US06/574,221
• Time in Patent Office: 838 Days
• Field of Search: 371/37, 371/39, 371/40
• US Class Current: 714/753
• CPC Class Codes: H03M 13/13 Linear codes

Abstract

A system for detecting multiple errors that may occur during transfer of data and for correcting up to two of these errors simultaneously. The system has a component for calculating a number of check bits associated with the data word. Also provided is a component for grouping all data bits into base groups and multiple groups, the sum of the number of base groups and multiple groups being equal to the number of check bits. Up to two weights are assigned for each data bit. The system distributes the data bits among the groups according to the weights assigned thereto. Also provided is a component for generating a check bit for each of the groups and for padding the data word with the check bits to form an appended data word. A generator creates a predetermined number of syndrome bits, the number being the number of check bits. Finally, a decoder is provided for decoding the syndrome bits to identify the erroneous bits in the data word.

Claims

1. A method for detecting multiple errors that occur during transfer of a data message having a plurality of data bits and for correcting up to two of said errors, the steps comprising:

(a) calculating a number of check bits associated with said data message;

(b) grouping all data bits in a data message into base groups and multiple layer groups, the sum of the number of base groups and the number of multiple layer groups of data bits being equal to said number of check bits;

(c) assigning up to two weights for each data bit;

(d) distributing data bits among said groups according to weights assigned thereto;

(e) generating a check bit for each of said groups the total number of generated check bits being equal to the number calculated in step (a);

(f) padding said data message with said total number of generated check bits to form an appended data message;

(g) generating a predetermined number of syndrome bits, said predetermined number being equal to said number of check bits; and

(h) decoding said syndrome bits to identify the erroneous bits in said data message.

2. The method in accordance with claim 1 wherein the number of bits b in one of said base groups is derived from the equation:

space="preserve" listing-type="equation">b=|Log.sub.2 (N)|

ps where N is the number of bits in said data message.

3. The method in accordance with claim 2 wherein the number of bits m in one of said multiple layer groups is derived from the equation:

space="preserve" listing-type="equation">m=|Log.sub.2 (N-b+1)|.

4. The method in accordance with claim 1 wherein said check bit is generated by performing an EXCLUSIVE OR operation on all of the data bits of the group corresponding thereto.

5. The method in accordance with claim 4 wherein each of said syndrome bits is generated by performing an EXCLUSIVE OR operation on a check bit and all data bits of the group corresponding thereto.