Error correction

• US 9,542,262 B1
• Filed: 05/29/2014
• Issued: 01/10/2017
• Est. Priority Date: 05/29/2014
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Inventors: Bar, Ilan, Weingarten, Hanan
• Primary Examiner(s): LAMARRE, GUY J
• Application Number:
  US14/290,848
• Time in Patent Office: 957 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/3738 with judging correct decoding

Abstract

A method for error correction, the method comprises receiving a codeword that comprises a payload and a redundancy section; error-correction decoding the codeword by applying a syndrome-based error correction process to provide an amended payload and an error-correction decoding success indicator; wherein the amended payload comprises an amended CRC signature and an amended payload data; calculating, using the amended payload CRC signature, a validity of the amended payload to provide a CRC validity result; estimating a number of errors in the redundancy section; and determining that the error-correction succeeded when the number of errors in the redundancy section did not exceed a threshold, the error correction success indicator indicates that the error-correction decoding failed, and the CRC validity result indicates that the amended payload is valid.

Claims

1. A method for error correction, the method comprises:

receiving a codeword that comprises a payload and a redundancy section;

error-correction decoding the codeword, by a decoder that comprises a syndrome calculator, a solver and a data correction module, by applying a syndrome-based error correction process to provide an amended payload and an error-correction decoding success indicator;

wherein the error-correction decoding success indicator is generated by the solver;

wherein the amended payload comprises an amended payload cyclic redundancy check (CRC) signature and an amended payload data;

calculating, by a CRC module and using the amended payload CRC signature, a validity of the amended payload to provide a CRC validity result;

estimating, by a decision module, a number of errors in the redundancy section; and

determining, by the decision module, that the error-correction succeeded when the number of errors in the redundancy section did not exceed a threshold, the error correction success indicator indicates that the error-correction decoding failed, and the CRC validity result indicates that the amended payload is valid.

2. The method according to claim 1, comprising receiving an original redundancy section of an original codeword;

wherein the codeword is calculated by applying at least one error-inducing process on the original codeword;

wherein the estimating of the number of errors in the redundancy section comprising calculating a redundancy difference between the redundancy section of the codeword and the original redundancy section of the original codeword.

3. The method according to claim 2 wherein the calculating of the redundancy difference comprises applying multiple Galois field operations.

4. The method according to claim 2 wherein the calculating of the redundancy difference comprises:

concatenating various terms of a syndrome to provide a first vector;

wherein the syndrome is calculated during the applying of the syndrome-based error correction process; and

performing a Galois field multiplication between the first vector and a first inverted matrix, the first inverted matrix is calculated by inverting a first matrix that comprises powers of Galois field primitive elements, to provide a second vector.

5. The method according to claim 4, comprising calculating a number of set bits in the second vector and comparing the number of set bits to the threshold.

6. The method according to claim 4, comprising:

calculating a number of set bits in the second vector and comparing the number of set bits to the threshold if a code error correction capability of the error-correction decoding exceeds one; and

calculating a number of set bits in the first vector and comparing the number of set bits to the threshold if a code error correction capability of the error-correction decoding equals one.

7. The method according to claim 4 wherein the concatenating of the various terms comprises concatenating all odd terms of the syndrome.

8. The method according to claim 1 wherein the codeword comprises multiple code components and wherein the error-correction decoding comprises error-correction decoding of all multiple code components.

9. A non-transitory computer readable medium that stores instructions that once executed by the computer cause the computer to execute the stages of:

receiving a codeword that comprises a payload and a redundancy section;

error-correction decoding the codeword, by a decoder that belongs to the computer and comprises a syndrome calculator, a solver and a data correction module and by applying a syndrome-based error correction process to provide an amended payload and an error-correction decoding success indicator;

wherein the error-correction decoding success indicator is generated by the solver;

wherein the amended payload comprises an amended payload cyclic redundancy check (CRC) signature and an amended payload data;

calculating, by a CRC module and using the amended payload CRC signature, a validity of the amended payload to provide a CRC validity result;

estimating, by a decision module, a number of errors in the redundancy section; and

determining, by the decision module, that the error-correction succeeded when the number of errors in the redundancy section did not exceed a threshold, the error correction success indicator indicates that the error-correction decoding failed, and the CRC validity result indicates that the amended payload is valid.

10. The non-transitory computer readable medium according to claim 9 wherein codeword results from applying at least one error-inducing process on an original codeword;

and

wherein the non-transitory computer readable medium stores instructions for calculating a redundancy difference between the redundancy section of the codeword and an original redundancy section of the original codeword.

11. The non-transitory computer readable medium according to claim 10 that stores instructions for calculating of the redundancy difference comprises by applying multiple Galois field operations.

12. The non-transitory computer readable medium according to claim 10 that stores instructions for calculating of the redundancy difference comprises by:

concatenating various terms of a syndrome to provide a first vector;

wherein the syndrome is calculated during the applying of the syndrome-based error correction process; and

performing a Galois field multiplication between the first vector and a first inverted matrix, the first inverted matrix is calculated by inverting a first matrix that comprises powers of Galois field primitive elements, to provide a second vector.

13. The non-transitory computer readable medium according to claim 12 that stores instructions for calculating a number of set bits in the second vector and comparing the number of set bits to the threshold.

14. The non-transitory computer readable medium according to claim 12 that stores instructions for calculating a number of set bits in the second vector and comparing the number of set bits to the threshold if a code error correction capability of the error-correction decoding exceeds one;

and calculating a number of set bits in the first vector and comparing the number of set bits to the threshold if a code error correction capability of the error-correction decoding equals one.

15. The non-transitory computer readable medium according to claim 12 that stores instructions for concatenating of the various terms by concatenating all odd terms of the syndrome.

16. The non-transitory computer readable medium according to claim 9 wherein the codeword comprises multiple code components and wherein the non-transitory computer readable medium stores instructions for error-correction decoding by error-correction decoding of the multiple code components.

17. A device for error correction, the device comprises:

a first error correction decoder that comprises a syndrome calculator, a solver and a data correction module and is arranged to;

receive a codeword that comprises a payload and a redundancy section;

error-correction decode the codeword by applying a syndrome-based error correction process to provide an amended payload and an error-correction decoding success indicator;

wherein the amended payload comprises an amended payload cyclic redundancy check (CRC) signature and an amended payload data;

wherein the error-correction decoding success indicator is generated by the solver;

a CRC module that is arranged to calculate, using the amended payload CRC signature, a validity of the amended payload to provide a CRC validity result; and

a decision module that is arranged to;

estimate a number of errors in the redundancy section; and

determine that the error-correction succeeded when the number of errors in the redundancy section did not exceed a threshold, the error correction success indicator indicates that the error-correction decoding failed, and the CRC validity result indicates that the amended payload is valid.

18. The device according to claim 17 wherein codeword results from applying at least one error-inducing process on an original codeword;

wherein the decision module is arranged to estimate of the number of errors in the redundancy section by calculating a redundancy difference between the redundancy section of the codeword and an original redundancy section of the original codeword.

19. The device according to claim 18 wherein the decision module is arranged to calculate of the redundancy difference by applying multiple Galois field operations.

20. The device according to claim 18 wherein the decision module is arranged to calculate of the redundancy difference by concatenating various terms of a syndrome to provide a first vector;

wherein the syndrome is calculated during the applying of the syndrome-based error correction process; and

performing a Galois field multiplication between the first vector and a first inverted matrix, the first inverted matrix is calculated by inverting a first matrix that comprises powers of Galois field primitive elements to provide a second vector.

21. The device according to claim 20 wherein the decision module is arranged to calculate a number of set bits in the second vector and compare the number of set bits to the threshold.

22. The device according to claim 20, wherein the decision module is arranged to calculate a number of set bits in the second vector and comparing the number of set bits to the threshold if a code error correction capability of the error-correction decoding exceeds one;

and calculate a number of set bits in the first vector and comparing the number of set bits to the threshold if a code error correction capability of the error-correction decoding equals one.

23. The device according to claim 20 wherein the decision module is arranged to concatenate the various terms by concatenating all odd terms of the syndrome.

24. The device according to claim 17 wherein the codeword comprises multiple code components and wherein the first error-correction decoder is arranged to error-correct decoding of the multiple code components.

25. The device according to claim 17 wherein the decision module comprises a syndrome processor, a matrix generator, and a Galois Field multiplier;

wherein the syndrome processor is configured to receive one or more syndromes from the solver and to generate a first vector;

wherein the matrix generator is configured to generate an inverted matrix by inverting a matrix that includes powers of Galois field primitive elements, determined from a code correction capability parameter and a Galois field size parameter; and

wherein the Galois Field multiplier is configured to multiply the inverted matrix by the first vector.