Error correction apparatus and method

• US 5,898,708 A
• Filed: 06/16/1995
• Issued: 04/27/1999
• Est. Priority Date: 06/16/1994
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Sato, Hiroaki, Aoki, Takayasu, Tateishi, Toru, Murano, Katsumi
• Primary Examiner(s): Elmore, Reba I.
• Assistant Examiner(s): Marc, McDieunel, Marc, McDieunel
• Application Number:
  US08/491,257
• Time in Patent Office: 1,411 Days
• Field of Search: 371/37.1, 371/37.5, 371/37.7, 371/37.4, 371/37.3, 371/38.1, 371/27, 371/40.1, 371/3, 371/45, 340/430, 360/32, 528/354
• US Class Current: 714/752
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials
• CPC Class Codes: H03M 13/47 Error detection, forward error correction or error protection, not provided for in groups H03M13/01 - H03M13/37

Abstract

When a receiver unit receives second data composed of check bits and first data obtained by encoding information bits indicating the communication contents by way of a first generator matrix based on a first generating polynomial, and then further encoding the first data by way of a second generator matrix of an irreducible standard form based on a second generating polynomial, an error location detector decodes the second data received by way of a second check matrix that is orthogonal to the second generator matrix so as to detect errors produced in the first data. A dummy syndrome generator generates a dummy syndrome of the error produced in the information bits based on the detected error location and on the first generating polynomial. A syndrome generator takes the product of the data obtained by excluding the check bits from the second data received by the receiver unit and the first check matrix that is orthogonal to the first generator matrix so as to generate a syndrome that indicates the error syndrome produced in the information bits. Finally, an error corrector corrects errors produced in the information bits if the dummy syndrome generated by the dummy syndrome generator is the same as the syndrome generated by the syndrome generator.

Claims

1. An error correction apparatus that receives a data train consisting of information bits indicating a communication content to which first check bits based on a first generator polynomial and second check bits based on a second generating polynomial are added, performs an error correction on the data train based on the second generating polynomial, and confirms whether the error correction is appropriate or not based on the first generator polynomial, wherein the error correction apparatus comprises:

first syndrome generation means for generating a first syndrome based on the first generator polynomial, the first syndrome being determined by an error produced in the information bits or in the first check bits;

second syndrome generation means for generating a second syndrome based on the second generator polynomial, the second syndrome being determined by an error produced in the data train;

error location detection means for detecting a location of an error produced in the data train based on the second syndrome generated by the second syndrome generation means; and

error correction means for reverse-calculating a third syndrome based on the error location detected by the error location detection means and the first generator polynomial, and correcting the error produced in the information bits when the third syndrome is identical with the first syndrome generated by the first syndrome generation means.

2. An error correction apparatus as defined in claim 1, wherein the first syndrome generation means generates the first syndrome by taking an inner product of a check polynomial which is orthogonal to the first generator polynomial and has been prepared beforehand, and the information bits and the first check bits.

3. An error correction apparatus as defined in claim 1, wherein the second syndrome generation means generates the second syndrome by taking an inner product of a check polynomial which is orthogonal to the second generator polynomial and has been prepared beforehand, and the data train.

4. An error correction apparatus as defined in claim 1, wherein the error correction means corrects the error location detected by the error location detection means into a corrected error location in which a bit at right end of the information bits and the first check bits serves as a reference location, and reverse-calculates the third syndrome based on the corrected error location and the first generator polynomial.

5. An error correction apparatus as defined in claim 1, wherein the error correction means corrects the error location detected by the error location detection means into a corrected error location in which a bit at left end of the information bits serves as a reference location, and reverse-calculates the third syndrome based on the corrected error location and the first generator polynomial.

6. An error correction system comprises:

a transmission processing unit for transmitting a data train consisting of information bits indicating a communication content to which first check bits based on a first generator polynomial and second check bits based on a second generating polynomial are added; and

a receipt processing unit for receiving the data train, performing an error correction on the data train based on the second generating polynomial, and confirming whether the error correction is appropriate or not based on the first generator polynomial,

wherein the receipt processing unit comprises;

first syndrome generation means for generating a first syndrome based on the first generator polynomial, the first syndrome being determined by an error produced in the information bits or in the first check bits;

second syndrome generation means for generating a second syndrome based on the second generator polynomial, the second syndrome being determined by an error produced in the data train;

error location detection means for detecting a location of an error produced in the data train based on the second syndrome generated by the second syndrome generation means; and

error correction means for reverse-calculating a third syndrome based on the error location detected by the error location detection means and the first generator polynomial, and correcting the error produced in the information bits when the third syndrome is identical with the first syndrome generated by the first syndrome generation means.

7. An error correction system as defined in claim 6, wherein the first syndrome generation means generates the first syndrome by taking an inner product of a check polynomial which is orthogonal to the first generator polynomial and has been prepared beforehand, and the information bits and the first check bits.

8. An error correction system as defined in claim 6, wherein the second syndrome generation means generates the second syndrome by taking an inner product of a check polynomial which is orthogonal to the second generator polynomial and has been prepared beforehand, and the data train.

9. An error correction system as defined in claim 6, wherein the error correction means corrects the error located detected by the error location detection means into a corrected error location in which a bit at right end of the information bits and the first check bits serves as a reference location, and reverse-calculates the third syndrome based on the corrected error location and the first generator polynomial.

10. An error correction system as defined in claim 6, wherein the error correction means corrects the error location detected by the error location detection means into a corrected error location in which a bit at left end of the information bits serves as a reference location, and reverse-calculates the third syndrome based on the corrected error location and the first generator polynomial.

11. An error correction method which includes the steps of receiving a data train consisting of information bits indicating a communication content to which first check bits based on a first generator polynomial and second check bits based on a second generating polynomial are added, performing an error correction on the data train based on the second generating polynomial, and confirming whether the error correction is appropriate or not based on the first generator polynomial,

characterized in that the error correction method comprises:

a first step of generating a first syndrome based on the first generator polynomial, the first syndrome being determined by an error produced in the information bits or in the first check bits, and a second syndrome based on the second generator polynomial, the second syndrome being determined by an error produced in the data train;

a second step of detecting a location of an error produced in the data train based on the second syndrome; and

a third step of reverse-calculating a third syndrome based on the error location detected in the second step and the first generator polynomial, and correcting the error produced in the information bits when the third syndrome is identical with the first syndrome.

12. An error correction method as defined in claim 11, wherein the first step generates the first syndrome by taking an inner product of a check polynomial which is orthogonal to the first generator polynomial and has been prepared beforehand, and the information bits and the first check bits, and generates the second syndrome by taking an inner product of a check polynomial which is orthogonal to the second generator polynomial and has been prepared beforehand, and the data train.

13. An error correction method as defined in claim 11, wherein the third step corrects the error location detected in the second step into a corrected error location in which a bit at right end of the information bits and the first check bits serves as a reference location, and reverse-calculates the third syndrome based on the corrected error location and the first generator polynomial.

14. An error correction method as defined in claim 11, wherein the third step corrects the error location detected in the second step into a corrected error location in which a bit at left end of the information bits serves as a reference location, and reverse-calculates the third syndrome based on the corrected error location and the first generator polynomial.