Error correction for digital systems

• US 8,090,976 B2
• Filed: 06/29/2007
• Issued: 01/03/2012
• Est. Priority Date: 06/29/2006
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Maciver, Mark Alasdair, MacKenzie, James Keith
• Primary Examiner(s): BAKER, STEPHEN M
• Application Number:
  US11/771,243
• Publication Number:
  US 20080022193A1
• Time in Patent Office: 1,649 Days
• Field of Search: 714/7, 714/43, 714/708, 714/4.11
• US Class Current: 714/4.11
• CPC Class Codes: G06F 11/2007 using redundant communication media
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H04L 1/0061 Error detection codes
• CPC Class Codes: H04L 1/22 using redundant apparatus to increase reliability

Abstract

An interface system is provided between a source component (210) and a destination component (220) having multiple parallel lines for transmitting data or parity bits (231-234, 251-253) and one or more spare lines (241-243). An error detection means (222) identifies one or more faulty lines. A mapping means (228) re-routes data or parity from a faulty line to a spare line. A communication link (208) is provided for communicating the re-routing between the source component (210) and the destination component (220). The error detection and mapping can be repeated to detect and re-route sequential multiple-bit line errors using additional spare lines (241-243).

Claims

1. A method for error correction across multiple parallel lines, comprising:

receiving data bits and parity bits across parallel lines;

performing error detection and location to identify one or more faulty lines;

disabling a faulty line and enabling a spare line;

re-routing data from the faulty line to the spare line;

mapping parity for subsequent error detection;

correcting the data on a faulty line and outputting the corrected data; and

tracking line errors and disabling a faulty line after a predetermined number of errors in a given time period.

2. The method according to claim 1, wherein error detection and location comprises a single-bit error correction algorithm, a double-bit error correction algorithm, or a multiple-bit error correction algorithm, with an associated required number of parity bits.

3. The method according to claim 2, wherein a faulty line can be a line transmitting data bits or parity bits.

4. The method according to claim 3, wherein an error detection step and subsequent re-routing of sequential multiple-bit line errors using additional spare lines is performed iteratively.

5. The method according to claim 4, wherein data on a faulty line is corrected if no more spare lines are available.

6. The method according to claim 5, wherein the error detection algorithm uses a Hamming code.

7. A computer program product stored on a computer readable storage medium, comprising computer readable program code means for performing the steps of:

receiving data bits and parity bits across parallel lines;

performing error detection and location to identify one or more faulty lines;

disabling a faulty line and enabling a spare line;

re-routing data from the faulty line to the spare line;

mapping parity for subsequent error detection;

correcting the data on a faulty line and outputting the corrected data; and

tracking line errors and disabling a faulty line after a predetermined number of errors in a given time period.

8. An interface system between a source component and a destination component, comprising:

multiple parallel lines for transmitting data bits or parity bits wherein the data bits comprise signal, control, clock, status, or address information;

one or more spare lines;

an error detection and location element for identifying one or more faulty lines;

a mapping logic element for re-routing data bits or parity bits from a faulty line to a spare line; and

a communication link for communicating the re-routing between the source component and the destination component.

9. The interface system according to claim 8, wherein the parallel lines comprise one or more parallel busses.

10. The interface system according to claim 8, wherein the parallel lines comprise independent interconnections on separate lines.

11. The interface system according to claim 8, wherein the parallel lines are a combination of one or more parallel buses and one or more independent interconnections.

12. The interface system according to claim 11, wherein the error detection and location element includes logic for correcting the data on a faulty line and outputting the corrected data.

13. The interface system according to claim 12, further comprising:

a history table for tracking line errors and control logic to disable a faulty line after a predetermined number of errors in a given period.

14. The interface system according to claim 13, wherein a faulty line comprises a line transmitting data bits or a line transmitting parity bits.

15. The interface system according to claim 14, wherein the communications link is a protected communication link incorporating the error detection and correction and redundancy techniques as recited in claim 8.