Chien search device, storage device, and chien search method

• US 9,413,391 B2
• Filed: 07/09/2014
• Issued: 08/09/2016
• Est. Priority Date: 04/18/2014
• Status: Active Grant

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Kondo, Yosuke, Tsuneda, Hidetoshi, Yoshida, Kenji
• Primary Examiner(s): MCMAHON, DANIEL F
• Application Number:
  US14/326,777
• Publication Number:
  US 20150303945A1
• Time in Patent Office: 762 Days
• Field of Search: None
• US Class Current: 1/1
• 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/157 Polynomial evaluation, i.e. determination of a polynomial sum at a given value
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing

Abstract

According to one embodiment, a chien search device includes n operation units configured to perform exclusive-OR operations, for each of the coefficients. Further, the chien search device includes first register configured to hold operation results of a highest order operation unit, for each of the coefficients. Furthermore, the chien search device includes exclusive-OR operation unit configured to perform exclusive-OR operations of the results of the first exclusive-OR operations of the highest order operation unit, for each of the coefficients. Moreover, the chien search device includes second register configured to hold operation results of the exclusive-OR operation unit, for each of the coefficients. The respective operation units reduce the number of stages of exclusive-OR operations by using the second register values.

Claims

1. A chien search device configured to perform chien searches of n (n is a natural number of 2 or more) bits in parallel on a basis of coefficients of terms of an error location polynomial calculated by an error location polynomial operation, the chien search device comprising:

for each of the coefficients,

n operation units configured to perform first exclusive-OR operations on a basis of a primitive polynomial of a Galois field;

a first register configured to hold results obtained by a highest order operation unit, the highest order operation unit being among the n operation units, the highest order operation unit being configured to perform the first exclusive-OR operations, the first exclusive-OR operations corresponding to operations multiplying α

to a power of highest order;

an exclusive-OR operation unit configured to perform second exclusive-OR operations of the results of the first exclusive-OR operations, the results of the first exclusive-OR operations being obtained by the highest order operation unit; and

a second register configured to hold results obtained by the exclusive-OR operation unit,

wherein each of the n operation units inputs first register values obtained from the first register and second register values obtained from the second register, and reduces a number of stages of the first exclusive-OR operations by using the second register values.

2. The chien search device according to claim 1,

wherein the first register is initialized with corresponding coefficients at a first time of operations, and holds, in subsequent operations, the results of the first exclusive-OR operations obtained by the highest order operation unit, and

the exclusive-OR operation unit performs the second exclusive-OR operations for the corresponding coefficients at the first time of the operations, and performs, in the subsequent operations, the second exclusive-OR operations of the results of the first exclusive-OR operations obtained by the highest order operation unit.

3. The chien search device according to claim 1,

wherein the exclusive-OR operation unit performs the second exclusive-OR operations by using all the results of the first exclusive-OR operations obtained by the highest order operation unit.

4. The chien search device according to claim 2,

wherein the exclusive-OR operation unit performs the second exclusive-OR operations by using the corresponding coefficients or all the results of the first exclusive-OR operations obtained by the highest order operation unit.

5. The chien search device according to claim 1,

wherein the exclusive-OR operation unit performs the second exclusive-OR operations by using a part of the results of the first exclusive-OR operations obtained by the highest order operation unit.

6. The chien search device according to claim 2,

wherein the exclusive-OR operation unit performs the second exclusive-OR operations by using the corresponding coefficients or a part of the results the first exclusive-OR operations obtained by the highest order operation unit.

7. A storage device comprising:

a memory unit configured to store code words generated by performing error correction encoding processing;

an error location polynomial operation unit configured to perform an error location polynomial operation on a basis of a syndrome calculated on a basis of code words read from the memory unit;

a chien search unit configured to perform chien searches on a basis of coefficients of terms of an error location polynomial calculated by the error location polynomial operation; and

a decoding control unit configured to perform error correction on a basis of results of the chien searches,

wherein, when the chien searches of n (n is a natural number of 2 or more) bits are performed in parallel, the chien search unit includes

for each of the coefficients,

n operation units configured to perform first exclusive-OR operations on a basis of a primitive polynomial of a Galois field,

a first register configured to hold results obtained by a highest order operation unit, the highest order operation unit being among the n operation units, the highest order operation unit being configured to perform the first exclusive-OR operations, the first exclusive-OR operations corresponding to operations multiplying α

to a power of highest order;

an exclusive-OR operation unit configured to perform second exclusive-OR operations of the results of the first exclusive-OR operations, the results of the first exclusive-OR operations being obtained by the highest order operation unit; and

a second register configured to hold results obtained by the exclusive-OR operation unit,

wherein each of the n operation units inputs first register values obtained from the first register and second register values obtained from the second register, and reduces a number of stages of the first exclusive-OR operations by using the second register values.

8. The storage device according to claim 7,

wherein the first register is initialized with corresponding coefficients at a first time of operations, and holds, in subsequent operations, the results of the first exclusive-OR operations obtained by the highest order operation unit, and

the exclusive-OR operation unit performs the second exclusive-OR operations for the corresponding coefficients at the first time of the operations, and performs, in the subsequent operations, the second exclusive-OR operations of the results of the first exclusive-OR operations obtained by the highest order operation unit.

9. The storage device according to claim 7,

wherein the exclusive-OR operation unit performs the second exclusive-OR operations by using all the results of the first exclusive-OR operations obtained by the highest order operation unit.

10. The storage device according to claim 8,

wherein the exclusive-OR operation unit performs the second exclusive-OR operations by using the corresponding coefficients or all the results the first exclusive-OR operations obtained by the highest order operation unit.

11. The storage device according to claim 7,

wherein the exclusive-OR operation unit performs the second exclusive-OR operations by using a part of the results the first exclusive-OR operations obtained by the highest order operation unit.

12. The storage device according to claim 8,

wherein the exclusive-OR operation unit performs the second exclusive-OR operations by using the corresponding coefficients or a part of the results the first exclusive-OR operations obtained by the highest order operation unit.

13. A chien search method of a chien search device configured to perform chien searches of n (n is a natural number of 2 or more) bits in parallel on a basis of coefficients of terms of an error location polynomial calculated by an error location polynomial operation, the chien search method comprising:

for each of the coefficients,

performing first exclusive-OR operations on a basis of a primitive polynomial of a Galois field;

holding results of the first exclusive-OR operations as first register values, the first exclusive-OR operations corresponding to operations multiplying α

to a power of highest order;

performing second exclusive-OR operations of the results of the first exclusive-OR operations of multiplying α

to the power of the highest order;

holding results of the second exclusive-OR operations as second register values; and

inputting the first register values and the second register values, and reducing a number of stages of the first exclusive-OR operations by using the second register values.

14. The chien search method according to claim 13, further comprising:

performing initialization with corresponding coefficients at a first time of operations, and holding, in subsequent operations, the results of the first exclusive-OR operations of multiplying α

to the power of the highest order as the first register values; and

performing, as the second exclusive-OR operations, exclusive-OR operations for the corresponding coefficients at the first time of the operations, and performing, as the second exclusive-OR operations, exclusive-OR operations of the results of the first exclusive-OR operations of multiplying α

to the power of the highest order in the subsequent operations.

15. The chien search method according to claim 13,

wherein exclusive-OR operations are performed as the second exclusive-OR operations by using all the results of the first exclusive-OR operations of multiplying α

to the power of the highest order.

16. The chien search method according to claim 14,

wherein the exclusive-OR operations are performed as the second exclusive-OR operations by using the corresponding coefficients or all the results of the first exclusive-OR operations of multiplying α

to the power of the highest order.

17. The chien search method according to claim 13,

wherein exclusive-OR operations are performed as the second exclusive-OR operations by using a part of the results of the first exclusive-OR operations of multiplying α

to the power of the highest order.

18. The chien search method according to claim 14,

wherein the exclusive-OR operations are performed as the second exclusive-OR operations by using the corresponding coefficients or a part of the results of the first exclusive-OR operations of multiplying α

to the power of the highest order.