System and method for multi-dimensional encoding and decoding

• US 8,850,297 B1
• Filed: 12/27/2013
• Issued: 09/30/2014
• Est. Priority Date: 07/01/2010
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: DensBits Technologies Ltd. (Broadcom, Inc.)
• Inventors: Steiner, Avi, Sabbag, Erez, Segal, Avigdor, Bar, Ilan, Sterin, Eli
• Primary Examiner(s): Ton, David
• Application Number:
  US14/141,671
• Time in Patent Office: 277 Days
• Field of Search: 714/762, 714/794, 714/780, 714/781, 714/782, 714/758
• US Class Current: 714/781
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• 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/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/19 Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H03M 13/2918 with error correction codes in three or more dimensions, e.g. 3-dimensional product code where the bits are arranged in a cube
• CPC Class Codes: H03M 13/2927 Decoding strategies
• CPC Class Codes: H03M 13/293 with erasure setting
• CPC Class Codes: H03M 13/2945 using at least three error correction codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2948 Iterative decoding H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding
• CPC Class Codes: H03M 13/43 Majority logic or threshold decoding
• CPC Class Codes: H03M 13/6561 Parallelized implementations

Abstract

A system and method for using a cyclic redundancy check (CRC) to evaluate error corrections. A set of data and initial CRC values associated therewith may be received. The set of data by changing a sub-set of the data may be corrected. Intermediate CRC values may be computed for the entire uncorrected set of data in parallel with said correcting. Supplemental CRC values may be computed for only the sub-set of changed data after said correcting. The intermediate and supplemental CRC values may be combined to generate CRC values for the entire corrected set of data. The validity of the corrected set of data may be evaluated by comparing the combined CRC values with the initial CRC values.

Claims

1. A method for decoding comprising:

receiving data encoded by a component codeword configured to correct up to a maximum number of errors (q) in the data;

generating an error locator polynomial (ELP) of a predetermined order (r) defining the locations in the component codeword of up to (r) errors, wherein;

if the maximum number of errors (q) that the component codeword is configured to correct is equal to the predetermined order (r), the ELP includes (r) roots corresponding to up to (r) errors to be corrected by the component codeword and if the maximum number of errors (q) that the component codeword is configured to correct is less than the predetermined order (r), the ELP includes (q) roots corresponding to up to (q) errors to be corrected by the component codeword and (r-q) virtual roots added to generate the ELP of the predetermined order (r); and

correcting up to (q) errors at locations in the component code defined by the (q) roots of the ELP.

2. The method of claim 1, wherein the (r-q) virtual roots define known locations in the component codeword, which are not corrected.

3. The method of claim 1 comprising extending the component codeword, wherein the (r-q) virtual roots define locations in the extended portion of the component codeword.

4. The method of claim 1, wherein the same decoder unit is used to solve component codes configured to correct up to different maximum numbers of errors (q).

5. The method of claim 1 comprising using the decoder unit to correct a component code predetermined to correct up to two errors (q=2) and three errors (q=3).

6. The method of claim 1 comprising using a separate decoder unit to correct a component code predetermined to correct up to a single error (q=1).

7. The method of claim 1, wherein the ELP is a cubic polynomial with a predetermined order of three (r=3).

8. The method of claim 7, wherein if the component codeword is predetermined to correct up to two errors (q=2), the ELP includes two roots corresponding to potential errors and one virtual root corresponding to no errors.

9. The method of claim 1, wherein the ELP is generated by using syndrome values of the component codeword to compute the coefficients of the ELP.

10. The method of claim 1, wherein the component codewords are BCH codes.

11. A system for decoding comprising:

a memory to store data encoded by a component codeword configured to correct up to a maximum number of errors (q) in the data; and

a decoder configured to correct up to a maximum number of errors (r) in the data, the decoder to generate an error locator polynomial (ELP) of a predetermined order (r) defining the locations in the component codeword of up to (r) errors, wherein if the maximum number of errors (q) that the component codeword is configured to correct is equal to the predetermined order (r), the ELP includes (r) roots corresponding to up to (r) errors to be corrected by the component codeword and if the maximum number of errors (q) that the component codeword is configured to correct is less than the predetermined order (r), the ELP includes (q) roots corresponding to up to (q) errors to be corrected by the component codeword and (r-q) virtual roots added to generate the ELP of the predetermined order (r), and the decoder to correct up to (q) errors at locations in the component code defined by the (q) roots of the ELP.

12. The system of claim 11, wherein the (r-q) virtual roots define known locations in the component codeword, which are not corrected.

13. The system of claim 11, wherein the decoder extends the component codeword, wherein the (r-q) virtual roots define locations in the extended portion of the component codeword.

14. The system of claim 11, wherein the decoder solves component codes configured to correct up to different maximum numbers of errors (r) and (q).

15. The system of claim 11, wherein the decoder solves a component code predetermined to correct up to two errors (q=2) and three errors (q=3).

16. The system of claim 11 comprising a separate decoder unit to correct a component code predetermined to correct up to a single error (q=1).

17. The system of claim 11, wherein the ELP is a cubic polynomial with a predetermined order of three (r=3).

18. The system of claim 17, wherein if the component codeword is predetermined to correct up to two errors (q=2), the ELP includes two roots corresponding to potential errors and one virtual root corresponding to no errors.

19. The system of claim 11, wherein the decoder generates the ELP by using syndrome values of the component codeword to compute the coefficients of the ELP.

20. The system of claim 11, wherein the component codewords are BCH codes.