Error correction and detection apparatus and method

• US 4,979,174 A
• Filed: 12/29/1988
• Issued: 12/18/1990
• Est. Priority Date: 12/29/1988
• Status: Expired due to Term

• Current Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation), Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Cheng, Ying, Dravida, Subrahmanyam
• Primary Examiner(s): Atkinson, Charles E.
• Application Number:
  US07/291,900
• Time in Patent Office: 719 Days
• Field of Search: 371/38.1, 371/41, 371/40.1
• US Class Current: 714/774
• 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
• CPC Class Codes: H04L 1/004 by using forward error control H04L1/0618 takes precedence; coding, decoding or code conversion, for error detection or correction H03M13/00

Abstract

A decoder is arranged to operate as a single-bit error correction circuit (ECC) and as a multiple-bit error detection circuit (EDC). The decoder starts and remains in the ECC state as long as no errors are detected in a received data message. When an error is detected or corrected in a received data message, the decoder switches to the EDC state where it remains as long as errors are detected in the received data message. When no errors are detected in the received data message, the decoder switches back to the ECC state. In a generalized multistate decoder, switching occurs from one state to another state, each state having a different error correcting capability, in response to a predetermined number of errors corrected or detected in the received data.

Claims

1. Apparatus for receiving input digital data coded using a predetermined error correction code, said apparatus comprising

first means capable of correcting a first number of errors in the received data and capable of detecting errors in the received data at a first probability rate;

second means capable of correcting a second number of errors in the received data, which is greater than said first number of errors, and capable of detecting errors in the received data at a second probability rate less than said first probability rate;

means for deriving an error signal from said received data; and

control means for applying said received data to said first means, and subsequently in response to said error signal indicating a first predetermined number of corrected errors in said received data, which is less than or equal to said first number, thereafter applying said received data to said second means, and thereafter in response to a subsequent error signal indicating a second predetermined number of corrected errors in said received data, which is less than or equal to said second number and greater than said first number, thereafter again applying said received data to said first means.

2. The apparatus of claim 1 wherein

said first predetermined number is equal to zero.

3. The apparatus of claim 2 wherein

said second predetermined number is equal to said second number.

4. The apparatus of claim 1 wherein

said second predetermined error number is equal to said second number and

said control means does not apply said received data to said first means when the number of corrected errors is less than said second number.

5. The apparatus of claim 1 further comprising

means for interfacing the apparatus to a digital data link to receive an input signal.

6. A data communication system including a data transmitter and a data receiver connected over a data path,

said data transmitter comprising

means for generating and transmitting digital data coded using an error correcting code to said receiver;

and

said receiver comprising

means for receiving said digital data;

first means capable of correcting a first number of errors in the received data and capable of detecting errors in the received data at a first probability rate;

second means capable of correcting a second number of errors in the received data, which is greater than said first number of errors, and capable of detecting errors in the received data at a second probability rate less than said first probability rate;

means for deriving an error signal from said received data; and

control means for applying said received data to said first means, and subsequently in response to said error signal indicating a first predetermined number of corrected errors in said received data, which is less than or equal to said first number, thereafter applying said received data to said second means, and thereafter in response to a subsequent error signal indicating a second predetermined number of corrected errors in said received data, which is less than or equal to said second number and greater than said first number, thereafter again applying said received data to said first means.

7. A method of operating a data receiver for receiving input digital data coded using a predetermined error correction code, said method comprising the steps of:

(a) deriving an error signal from said received data,

(b) applying said received data to a first correcting step c,

(c) correcting a first number of errors in the receiving data and detecting errors in the received data at a first probability rate;

(d) in response to said error signal indicating a first predetermined number of corrected errors in said received data, which is less than or equal to said first number, applying subsequent-received data to a second correcting step e,

(e) correcting a second number of errors in said subsequent-received data, which is greater than said first number of errors, and detecting errors in said subsequent-received data at a second probability rate less than said first probability rate; and

(f) in response to said error signal indicating that a second predetermined number of corrected errors in said subsequent-received data, which is less than or equal to said second number and greater than said first number, applying newly received data to said first correcting step (c).

8. Apparatus for receiving input digital data coded using an error correction code, said apparatus comprising

error correcting circuit (ECC) means for detecting one or more errors and for correcting a single-bit error in the received data using said error correction code,

error detecting circuit (EDC) means for detecting one or more errors in the received data using said error correction code,

means for deriving an error signal in a predetermined manner from said received data, and

switch means responsive to the absence of an error signal received from said deriving means for switching the detecting of said received data from said EDC means to said ECC means and responsive to the presence of said error signal for switching the detecting of said received data from said ECC means to said EDC means.

9. The apparatus of claim 8 wherein

said switch means does not switch from said EDC means to said ECC means in response to an error signal derived in said predetermined manner from said received data and does not switch from said ECC means to said EDC means in response to a no-error signal derived in said predetermined manner from said received data.

10. The apparatus of claim 8 wherein

said EDC means includes a syndrome circuit for processing the received data utilizing the same process used to generate said error correction code and generating an error and a no-error signal in response to the received data.

11. The apparatus of claim 10 wherein said syndrome circuit includes means for processing groups of data bits from the received data.

12. The apparatus of claim 8 wherein

said ECC means includes a syndrome circuit for processing the received data utilizing the same process used to generate said error correction code and for generating an error and a no-error signal, said error signal representing remainder term after said processing and said no-error signal representing no remainder term after said processing,

remainder list and comparison means for comparing the remainder term with a list of predefined remainder terms to determine a bit position in the received data where an error exists, and

means responsive to a signal indicating the bit position of an error in the received data for inverting the data in said bit position.

13. The apparatus of claim 12 wherein said switch means includes

means for gating the received data for processing by a particular one of said EDC means and said ECC means depending on the existing state of said switch means and said remainder term.

14. The apparatus of claim 8 wherein said error correction code is generated using a CRC code.

15. The apparatus of claim 8 further comprising

means for interfacing the apparatus to a digital data link to receive said input digital data.

16. The apparatus of claim 8 wherein said input data includes a header and information bits and wherein said error correction code is generated for said header bits and wherein said ECC means and EDC means perform their respective operations on said header bits.

17. A data communication system including a data transmitter and a data receiver connected over a data path,

said data transmitter comprising

means for generating a data message including an error correction code and

means for transmitting said data message to said receiver, and

said receiver comprising

means for receiving said data message,

an error correcting circuit (ECC) means for detecting one or more errors and correcting a single-bit error in the received data message using said error correction code,

an error detecting circuit (EDC) means for detecting one or more errors in the received data message using said error correction code and

means for deriving an error signal in a predetermined manner from said received data, and

switch means responsive to the absence of an error signal received from said deriving means for switching the detecting of said received data from said EDC means to said ECC means and responsive to the presence of said error signal for switching the detecting of said received data message from said ECC means to said EDC means.

18. A method of operating a data receiver for receiving input digital data coded using an error correction code therein, said method comprising the steps of:

(a) detecting one or more errors and correcting a single-bit error in the received data using an error correcting circuit (ECC) and said error correction code,

(b) in response to an error correction or detection signal derived in said detecting step (a), switching said received data from said detecting step (a) to detecting step (c),

(c) detecting one or more errors in received data using an error detecting circuit (EDC) and said error correction code, and

(d) in response to an absence of an error signal in said detecting step (c), switching said received data to said detecting step (a).

19. A method of operating a data communication system including a data transmitter and a data receiver connected over a data path, said method comprising the steps of:

at said data transmitter

generating and transmitting a data message including an error correction code and at said receiver

(a) detecting one or more errors and correcting a single-bit error in the received data message using an error correcting circuit (ECC) and said error correction code,

(b) in response to an error correction or detection signal derived in said detecting step (a), switching said received data message from said detecting step (a) to detecting step (c),

(c) detecting one or more errors in received data using an error detecting circuit (EDC) and said error correction code, and

(d) in response to an absence of an error signal in said detecting step (c), switching said received data to said detecting step (a).