Back to results
US 10,097,207 B2Granted
ECC circuit, storage device and memory system
AssigneeToshiba Memory Corporation
InventorKosuke Hatsuda
Life of this patent
Estimating the term…
Abstract
A syndrome calculation circuit receives input data r(x) including data and a parity bit and having a code length n of (2m−1) bits at maximum which is represented by a Galois field GF(2m), and performs syndrome calculation so as to meet s≡αi+αj z≡(αi+β)−1+β−1+(αj+β)−1+β1 (A) thereby calculating syndromes s and z. An error position polynomial coefficient calculation circuit calculates the coefficient of an error position polynomial to obtain s×z by multiplying s and z by one multiplier. After that, 2-bit error data positions i and j are specified. Errors at the error data positions i and j of the input data are corrected.
Claims6
An error check and correction (ECC) circuit comprising:
- a syndrome calculation circuit configured to receive input data r(x) including data and a parity bit and having a code length n of (2m−1) bits at maximum which is represented by a Galois field GF(2m), and calculate a syndrome including a term (p+β)−1 based on the received input data r(x);
- and
- an error position polynomial coefficient calculation circuit configured to calculate a coefficient of an error position polynomial based on the calculated syndrome,
- where n, m:
- positive integers
- r(x):
- a polynomial representing the input data
- p:
- an indicator representing an error position
- β:
- an arbitrary constant of GF(2m) that is not 0,
- wherein the syndrome calculation circuit calculates syndromes s and z based on the received input data r(x) by performing syndrome calculation to meet
- s≡αi+αj
- z≡(αi+β)−1+β−1+(αj+β)−1+β−1 (A)
- where:
- α:
- an nth root of unity that is an element of the Galois field GF(2m)
- i, j:
- positions where errors of e(x) exist
- e(x):
- a polynomial representing an error position,
- wherein the error position polynomial coefficient calculation circuit calculates the coefficient of the error position polynomial to obtain s×z by multiplying s and z by one multiplier based on the calculated syndromes s and z,
- wherein the ECC circuit further comprises:
- an error position polynomial solution calculation circuit configured to calculate solutions x1 and x2 to the error position polynomial based on the syndrome s and s×z;
- a decoding circuit configured to specify 2-bit error data positions i and j of the input data based on the solutions x1 and x2;
- and
- an error bit correction circuit configured to correct errors at the error data positions i and j of the input data based on the specified 2-bit error data positions i and j, and
- wherein the syndrome calculation circuit calculates the syndromes s and z using a table storing a relationship between the input data r(x), the 2-bit error data positions i and j, and the syndromes s and z.
25 more elements
A storage device comprising:
- a memory;
- and
- an error check and correction (ECC) circuit configured to receive input data r(x) read from the memory, perform error correction of the received input data, and output, as output data, the input data that has undergone the error correction,
- wherein the input data r(x) includes data and a parity bit and has a code length n of (2m−1) bits at maximum which is represented by a Galois field GF(2m),
- wherein the ECC circuit comprises:
- a syndrome calculation circuit configured to calculate a syndrome including a term (p+β)−1 based on the received input data r(x);
- and
- an error position polynomial coefficient calculation circuit configured to calculate a coefficient of an error position polynomial based on the calculated syndrome, where n, m:
- positive integers
- r(x):
- a polynomial representing the input data
- p:
- an indicator representing an error position
- β:
- an arbitrary constant of GF(2m) that is not 0,
- wherein the syndrome calculation circuit calculates syndromes s and z based on the received input data r(x) by performing syndrome calculation to meet
- s≡αi+αj
- z≡(αi+β)−1+β−1+(αj+β)−1+β−1 (A)
- where:
- α:
- an nth root of unity that is an element of the Galois field GF(2m)
- i, j:
- positions where errors of e(x) exist
- e(x):
- a polynomial representing an error position,
- wherein the error position polynomial coefficient calculation circuit calculates the coefficient of the error position polynomial to obtain s×z by multiplying s and z by one multiplier based on the calculated syndromes s and z,
- wherein the ECC circuit further comprises:
- an error position polynomial solution calculation circuit configured to calculate solutions x1 and x2 to the error position polynomial based on the syndrome s and s×z;
- a decoding circuit configured to specify 2-bit error data positions i and j of the input data based on the solutions x1 and x2;
- and
- an error bit correction circuit configured to correct errors at the error data positions i and j of the input data based on the specified 2-bit error data positions i and j, and
- wherein the syndrome calculation circuit calculates the syndromes s and z using a table storing a relationship between the input data r(x), the 2-bit error data positions i and j, and the syndromes s and z.
29 more elements
A memory system comprising:
- a memory;
- and
- a memory controller including an error check and correction (ECC) circuit configured to receive input data r(x) read from the memory, perform error correction of the received input data, and output, as output data, the input data that has undergone the error correction,
- wherein the input data r(x) includes data and a parity bit and has a code length n of (2m−1) bits at maximum which is represented by a Galois field GF(2m),
- wherein the ECC circuit comprises:
- a syndrome calculation circuit configured to calculate a syndrome including a term (p+β)−1 based on the received input data r(x);
- and
- an error position polynomial coefficient calculation circuit configured to calculate a coefficient of an error position polynomial based on the calculated syndrome,
- where n, m:
- positive integers
- r(x):
- a polynomial representing the input data
- p:
- an indicator representing an error position
- β:
- an arbitrary constant of GF(2m) that is not 0,
- wherein the syndrome calculation circuit calculates syndromes s and z based on the received input data r(x) by performing syndrome calculation to meet
- s≡αi+αj
- z≡(αi+β)−1+β−1+(αj+β)−1+β−1 (A)
- where:
- α:
- an nth root of unity that is an element of the Galois field GF(2m)
- i, j:
- positions where errors of e(x) exist
- e(x):
- a polynomial representing an error position,
- wherein the error position polynomial coefficient calculation circuit calculates the coefficient of the error position polynomial to obtain s×z by multiplying s and z by one multiplier based on the calculated syndromes s and z, and
- wherein the ECC circuit further comprises:
- an error position polynomial solution calculation circuit configured to calculate solutions x1 and x2 to the error position polynomial based on the syndrome s and s×z;
- a decoding circuit configured to specify 2-bit error data positions i and j of the input data based on the solutions x1 and x2;
- and
- an error bit correction circuit configured to correct errors at the error data positions i and j of the input data based on the specified 2-bit error data positions i and j, and
- wherein the syndrome calculation circuit calculates the syndromes s and z using a table storing a relationship between the input data r(x), the 2-bit error data positions i and j, and the syndromes s and z.
30 more elements
Dependencies are inferred from the claim text.