Arithmetic circuit, memory system, and method of controlling nonvolatile memory
In an arithmetic circuit, a first substitution circuit calculates p/2 first evaluation values by using a first input polynomial having first-order to s-th-order coefficients of the error locator polynomial. When the number of errors is t/2 or less, the arithmetic circuit outputs p pieces of information including: error position information calculated from the first evaluation values obtained by substituting p/2 first check values, and error position information calculated from a second evaluation values obtained by substituting the first check values into a second input polynomial having coefficients obtained by converting coefficients of the first input polynomial. When the number of errors is larger than t/2, the arithmetic circuit outputs p/2 pieces of error position information based on the first evaluation values and third evaluation values obtained by converting the second evaluation values obtained by a third polynomial having (s+1)-th-order to t-th-order coefficients of the error locator polynomial.
1 . An arithmetic circuit comprising:
a first substitution circuit configured to calculate p/2 first evaluation values by substituting p/2 check values into a first input polynomial, p being an even integer satisfying 2≤p<n, n being an integer of 2 or more, the first input polynomial being represented by first-order to s-th-order coefficients of an error locator polynomial for an error correction code, s being the minimum integer greater than or equal to t/2 or the maximum integer less than or equal to t/2, t being an integer of 2 or more, the error correction code having a code length of n bits to correct an error of t bits or less; and
a second substitution circuit configured to calculate p/2 second evaluation values,
wherein the arithmetic circuit is configured to, when the number of errors is t/2 or less, output p pieces of error position information including
p/2 pieces of error position information calculated based on the first evaluation values calculated by the first substitution circuit by substituting p/2 first check values from the first to the p/2-th among the p check values, and
p/2 pieces of error position information calculated based on the second evaluation values calculated by the second substitution circuit by substituting the first check values into a second input polynomial, the second input polynomial being represented by coefficients obtained by converting the coefficients of the first input polynomial, and
wherein the arithmetic circuit is configured to, when the number of errors is larger than t/2,
convert the second evaluation values into third evaluation values, the second evaluation values being calculated by the second substitution circuit by substituting the first check values into a third input polynomial represented by (s+1)-th-order to t-th-order coefficients of the error locator polynomial, and
output p/2 pieces of error position information calculated based on the first evaluation values, the first evaluation values being calculated by the first substitution circuit by substituting the first check values and the third evaluation values.
2 . The arithmetic circuit according to claim 1 , wherein the arithmetic circuit is configured to, when the number of errors is t/2 or less, obtain the coefficients of the second input polynomial by multiplying the k-th-order coefficient of the first input polynomial by a primitive element α to the power of (kp/2), k being an integer satisfying 1≤k≤t/2.
3 . The arithmetic circuit according to claim 1 , wherein the arithmetic circuit is configured to, when the number of errors is larger than t/2, calculate the third evaluation values by multiplying the p/2 second evaluation values by predetermined p/2 multiplication values, respectively.
4 . The arithmetic circuit according to claim 1 , wherein
the first substitution circuit is configured to substitute p/2 check values in parallel into the first input polynomial to calculate the p/2 first evaluation values, and
the second substitution circuit is configured to substitute p/2 check values in parallel into the second input polynomial or the third input polynomial to calculate the p/2 second evaluation values.
5 . The arithmetic circuit according to claim 1 , wherein the arithmetic circuit is configured to
calculate p/2 fourth evaluation values by adding the first evaluation values calculated by the first substitution circuit and the third evaluation values, and
calculate the p/2 pieces of error position information by using the fourth evaluation values.
6 . The arithmetic circuit according to claim 1 , wherein the error correction code is a Bose-Chaudhuri-Hocquenghem (BCH) code or a Reed-Solomon (RS) code.