COMBINED BLOCK-STYLE ERROR CORRECTION

• US 20150249470A1
• Filed: 10/31/2012
• Published: 09/03/2015
• Est. Priority Date: 10/31/2012
• Status: Abandoned Application

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Roth, Ron M., Vontobel, Pascal Olivier
• Application Number:
  US14/417,236
• Publication Number:
  US 20150249470A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/1525 Determination and particular use of error location polynomials
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• CPC Class Codes: H03M 13/1585 Determination of error values
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/293 with erasure setting
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations

Abstract

In a method for coding information using a coding scheme, a horizontal code is selected. Additionally, a matrix is selected. Encoding information symbols into an array based upon the selected horizontal code is performed. Moreover, encoding the columns of the array based upon the selected matrix is performed.

Claims

1. A method for encoding information symbols using a coding scheme, the method comprising:

selecting a horizontal code from a plurality of codes, wherein said horizontal code are linear codes over a field;

selecting a prescribed length and a prescribed height, wherein said matrix is selected from a plurality of matrices over said field, wherein said matrix comprises a number of rows equaling said prescribed height and a number of columns equaling said prescribed length multiplied by said prescribed height, wherein all column subsets of size less than a prescribed number within said matrix are linearly independent, and wherein a number of square sub-matrices formed by partitioning the column set of said matrix into a number of non-overlapping column subsets are invertible over said field;

encoding said information symbols into an array based upon said selected horizontal code; and

encoding said columns of said array based upon said selected matrix.

3. The method of claim 1, wherein said horizontal code has a prescribed minimum distance.

4. The method of claim 1, wherein said method for encoding information using a coding scheme is operable to correct phased burst errors and symbol errors.

2. The method of claim 2, wherein one encoding step constitutes a code which is a prescribed level of interleaving of said horizontal code and consists of arrays such that each row of said arrays belongs to said horizontal code.

5. A method for communicating information reliably, the method comprising:

transmitting a transmitted array of information symbols;

receiving a received array of encoded symbols, wherein said received array is corrupted by a first type of error, a second type of error, a third type of error, and a fourth type of error, wherein said first type of error is a block error, said second type of error is a block erasure, said third type of error is a symbol error, and said fourth type of error is a symbol erasure;

decoding said received array of encoded symbols based at least on said corrupted array.

6. A method for encoding and decoding a code, the method comprising:

selecting a horizontal code from a plurality of codes, wherein said horizontal codes are linear codes over a field;

selecting a prescribed length and a prescribed height, wherein said matrix is selected from a plurality of matrices over said field, wherein said matrix comprises a number of rows equaling said prescribed height and a number of columns equaling said prescribed length multiplied by said prescribed height, wherein all column subsets of size less than a prescribed number within said matrix are linearly independent, and wherein a number of square sub-matrices formed by partitioning the column set of said matrix into a number of non-overlapping column subsets are invertible over said field;

encoding said information symbols into an array based upon said selected horizontal code; and

encoding said columns of said array based upon said selected matrix.

7. The method of claim 6 wherein said horizontal code is a generalized Reed-Solomon code.

8. The method of claim 6, further comprising:

computing a syndrome array;

computing a modified syndrome array;

applying a decoder for said horizontal code based on at least on said syndrome array;

decoding said received array of information symbols by applying said error array to said received array of encoded symbols.

9. The method of claim 8, further comprising:

computing a row in a matrix;

applying a decoder to a horizontal array based at least on a said syndrome array and a row in said matrix; and

updating said received array and said syndrome array

10. The method of claim 6, further comprising:

computing a syndrome array;

computing a second matrix;

computing a polynomial using a Feng-Tzeng operation;

provided said Feng-Tzeng operation is successful, computing an error array; and

decoding said received array of information symbols by applying said error array to said received array of encoded symbols.

11. The method of claim 10, further comprising:

computing a greatest common divisor based at least on the left kernel of said second matrix;

computing a root sub-set and a polynomial; and

computing said second matrix.

12. The method of claim 10, further comprising:

computing a shortest linear recurrence of any nonzero column in said second matrix;

computing said root sub-set; and

updating said root sub-set.

13. The method of claim 10, further comprising:

computing a modified syndrome array;

computing a polynomial using a Feng-Tzeng operation;

provided said Feng-Tzeng operation is successful, computing an error array;

applying a decoder for said horizontal code;

provided applying said decoder to said horizontal code is successful, updating said corrupted array.