CHIEN SEARCH DEVICE, STORAGE DEVICE, AND CHIEN SEARCH METHOD

• US 20150303945A1
• Filed: 07/09/2014
• Published: 10/22/2015
• Est. Priority Date: 04/18/2014
• Status: Active Grant

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: YOSHIDA, Kenji, KONDO, Yosuke, TSUNEDA, Hidetoshi
• Granted Patent: US 9,413,391 B2
• Time in Patent Office: Days
• 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 coefficient. Further, the chien search device includes first register configured to hold operation results of the highest order operation unit, for each coefficient. Furthermore, the chien search device includes exclusive-OR operation unit configured to perform exclusive-OR operations of the operation results of the highest order operation unit, for each coefficient. Moreover, the chien search device includes second register configured to hold operation results of the exclusive-OR operation unit, for each coefficient. The respective operation units reduce the number of stages of exclusive-OR operations by using the second register values, which are obtained from the second register, and perform operations.

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 the basis of coefficients of terms of an error location polynomial calculated by an error location polynomial operation, the chien search device comprising:

for each coefficient,

n operation units configured to perform first exclusive-OR operations on the basis of an operation expression decided according to rule of Galois field;

first register configured to hold operation results of the first exclusive-OR operations corresponding to operations multiplying α

to the power of the highest order among the n operation units;

exclusive-OR operation unit configured to perform second exclusive-OR operations of the operation results of the highest order operation unit; and

second register configured to hold operation results of the exclusive-OR operation unit,

wherein the respective n operation units input first register values obtained from the first register and second register values obtained from the second register, and use the second register values in operations capable of reducing the number of stages of 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 the corresponding coefficients at the first time of the operations and holds the operation results of the highest order operation unit in the subsequent operations, 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 the second exclusive-OR operations of the operation results of the highest order operation unit in the subsequent operations.

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 operation results of 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 operation results of 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 operation results of 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 operation results of 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 the basis of a syndrome calculated on the basis of code words read from the memory unit;

a chien search unit configured to perform chien searches on the 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 the 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 coefficient,

n operation units configured to perform first exclusive-OR operations on the basis of an operation expression decided according to rule of Galois field,

first register configured to hold operation results of the first exclusive-OR operations corresponding to operations multiplying α

to the power of the highest order among the n operation units;

exclusive-OR operation unit configured to perform second exclusive-OR operations of the operation results of the highest order operation unit; and

second register configured to hold operation results of the exclusive-OR operation unit,

the respective n operation units input first register values obtained from the first register and second register values obtained from the second register, and use the second register values in operations capable of reducing the number of stages of 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 the corresponding coefficients at the first time of the operations and holds the operation results of the highest order operation unit in the subsequent operations, 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 the second exclusive-OR operations of the operation results of the highest order operation unit in the subsequent operations.

9. The storage device according to claim 7,

wherein the exclusive-OR operation unit performs the second exclusive-OR operations by using all the operation results of 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 operation results of 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 operation results of 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 operation results of 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 the basis of coefficients of terms of an error location polynomial calculated by an error location polynomial operation, the chien search method comprising:

for each coefficient,

performing first exclusive-OR operations on the basis of an operation expression decided according to rule of Galois field;

holding operation results of the first exclusive-OR operations, configured to correspond to operations multiplying α

to the power of the highest order in the n operation units, as first register values;

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

to the power of the highest order;

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

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

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

performing initialization with the corresponding coefficients at the first time of the operations and holding the operation results of multiplying α

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

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

to the power of the highest order in the subsequent operations, as the second exclusive-OR 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 operation results of multiplying α

to the power of the highest order.

16. The chien search method according to claim 14,

wherein exclusive-OR operations are performed as the second exclusive-OR operations by using the corresponding coefficients or all the operation results 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 operation results of multiplying α

to the power of the highest order.

18. The chien search method according to claim 14,

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

to the power of the highest order.