Arithmetic circuit, memory system, and method of controlling nonvolatile memory

Abstract

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.