Parallel chien search with folding and a symbolized minimal polynomial combinational network (S-MPCN)

• US 9,455,747 B1
• Filed: 03/24/2014
• Issued: 09/27/2016
• Est. Priority Date: 03/27/2013
• Status: Active Grant

• Current Assignee: SK Hynix Inc.
• Original Assignee: SK Hynix Inc.
• Inventors: Lin, Yi-Min, Prabhakar, Abhiram, Zeng, Lingqi, Bellorado, Jason
• Primary Examiner(s): Bonzo, Bryce
• Assistant Examiner(s): Nguyen, Thien D
• Application Number:
  US14/223,643
• Time in Patent Office: 918 Days
• US Class Current: 1/1
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/1545 Determination of error locations, e.g. Chien search or other methods or arrangements for the determination of the roots of the error locator polynomial
• CPC Class Codes: H03M 13/1575 Direct decoding, e.g. by a direct determination of the error locator polynomial from syndromes and subsequent analysis or by matrix operations involving syndromes, e.g. for codes with a small minimum Hamming distance
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations
• CPC Class Codes: H03M 13/6561 Parallelized implementations

Abstract

A hinge path is used to determine if a first possible root is a root of an error location polynomial. A positive limb path is used to determine if a second possible root is a root of the error location polynomial, including by using a sequence of coefficients associated with the error location polynomial. The sequence of coefficients is reversed and a negative limb path is used to determine if a third possible root is a root of the error location polynomial, including by using the reversed sequence of coefficients, wherein the negative limb path is a copy of the positive limb path.

Claims

1. A system for decoding data by performing a parallel Chien search, comprising:

a syndrome calculator configured to receive encoded data and to generate one or more syndromes using the encoded data;

a key equation solver configured to generate an error location polynomial from the syndromes; and

a parallel Chien search block configured to locate a number of roots and output decoded data when the number of roots equals a degree of the error location polynomial, the parallel Chien search block including;

a hinge path configured to determine whether a first root is a root of the error location polynomial;

a positive limb path configured to determine whether a second root is a root of the error location polynomial based on a sequence of coefficients associated with the error location polynomial;

a sequence reverser configured to reverse the sequence of coefficients;

a negative limb path configured to determine whether a third root is a root of the error location polynomial based on the reversed sequence of coefficients,

a symbolized minimal polynomial combinational network configured to generate remainder polynomials;

a first symbolized basis transformer configured to evaluate a first remainder polynomial generated by the symbolized minimal polynomial combinational network; and

a second symbolized basis transformer configured to evaluate a second remainder polynomial generated by the symbolized minimal polynomial combinational network,

wherein the symbolized minimal polynomial combinational network is shared by the first symbolized basis transformer and the second symbolized basis transformer.

2. The system of claim 1, wherein the syndrome calculator is configured to generate the syndromes using BCH encoded data.

3. The system of claim 2, further comprising solid state storage, wherein the BCH encoded data is stored on the solid state storage.

4. The system of claim 1, wherein the system is configured to determine decoding of the block is successful when a number of roots located equals a degree of the error location polynomial.

5. A system for decoding data by performing a parallel Chien search, comprising:

a syndrome calculator configured to receive encoded data and to generate one or more syndromes using the encoded data;

a key equation solver configured to generate an error location polynomial from the syndromes; and

a parallel Chien search block configured to locate a number of roots and output decoded data when the number of roots equals a degree of the error location polynomial, the parallel Chien search block including;

a symbolized minimal polynomial combinational network configured to generate remainder polynomials;

a first symbolized basis transformer, associated with a first root of the error location polynomial, which is configured to evaluate a first remainder polynomial generated by the symbolized minimal polynomial combinational network at the first root of the error location polynomial; and

a second symbolized basis transformer, associated with a second root of the error location polynomial, which is configured to evaluate a second remainder polynomial generated by the symbolized minimal polynomial combinational network at the second root of the error location polynomial, wherein the first root and the second root are conjugates,

wherein the symbolized minimal polynomial combinational network is shared by the first symbolized basis transformer and the second symbolized basis transformer.

6. The system of claim 5,

wherein hinge paths use the error location polynomial to determine partial multiplication terms.

7. The system of claim 5, wherein the syndrome calculator is configured to generate the syndromes using BCH encoded data.

8. The system of claim 7, further comprising solid state storage, wherein the BCH encoded data is stored on the solid state storage.

9. A method for decoding data by performing a parallel Chien search, comprising:

receiving, with a syndrome calculator, encoded data;

generating, with the syndrome calculator, one or more syndromes using the encoded data;

generating, with a key equation solver, an error location polynomial from the generated syndromes;

determining, with a hinge path whether a first root is a root of the error location polynomial;

determining, with a positive limb path, whether a second root is a root of the error location polynomial based on a sequence of coefficients associated with the error location polynomial;

reversing, with a sequence reverser, the sequence of coefficients;

determining, with a negative limb path, whether a third root is a root of the error location polynomial based on the reversed sequence of coefficients, wherein the negative limb path is a copy of the positive limb path,

generating, with a symbolized minimal polynomial combinational network, remainder polynomials,

evaluating, with a first symbolized basis transformer, a first remainder polynomial generated by the symbolized minimal polynomial combinational network,

evaluating, with a second symbolized basis transformer, a second remainder polynomial generated by the symbolized minimal polynomial combinational network, the symbolized minimal polynomial combinational network being shared by the first and second symbolized basis transformer, and

outputting decoded data when a number of roots equals a degree of the error location polynomial.

10. The method of claim 9, wherein generating the syndromes includes using BCH encoded data.

11. The method of claim 10, wherein the BCH encoded data is stored on solid state storage.

12. A method for decoding data by performing a parallel Chien search, comprising:

receiving, with a syndrome calculator, encoded data;

generating, with the syndrome calculator, one or more syndromes using the encoded data;

generating, with a key equation solver, an error location polynomial from the generated syndromes;

generating, with a symbolized minimal polynomial combinational network, remainder polynomials;

evaluating, with a first symbolized basis transformer associated with a first root of the error location polynomial, a first remainder polynomial generated by the symbolized minimal polynomial combinational network at the first root of the error location polynomial; and

evaluating, with a second symbolized basis transformer associated with a second root of the error location polynomial, a second remainder polynomial generated by the symbolized minimal polynomial combinational network at the second root of the error location polynomial, wherein the first root and the second root are conjugates, and

outputting decoded data when a number of roots equals a degree of the error location polynomial;

wherein the symbolized minimal polynomial combinational network is shared by the first symbolized basis transformer and the second symbolized basis transformer.

13. The method of claim 12, further comprising:

generating the error location polynomial using the syndromes, wherein hinge paths use the error location polynomial to determine partial multiplication terms.

14. The method of claim 13, wherein generating the syndromes includes using BCH encoded data.

15. The method of claim 14, wherein the BCH encoded data is stored on solid state storage.