Galois field arithmetic operation circuit and memory device
AssigneeSamsung Electronics Co., Ltd.
InventorKoji Murata
Life of this patent
Estimating the term…
Abstract
A Galois field arithmetic operation circuit substituting (2^m−1) elements (m is an integer) expressed by m bits of Galois field GF(2^m) includes: a base calculation unit configured to calculate m linear independent elements out of the (2^m−1) elements; and a linear development unit configured to calculate the remaining (2^m−1−m) elements not included in the m linear independent elements by combination of the m linear independent elements respectively. The Galois field arithmetic operation circuit may be included in a memory device or other system.
Claims12
A Galois field arithmetic operation circuit substituting 2m−1 elements, where m is an integer, expressed by m bits of Galois field GF(2m) comprising:
- a base calculation circuit including m parallel arithmetic operation circuits, each of the m parallel arithmetic operation circuits configured to calculate one of m linear independent elements from the 2m−1 elements;
- and
- a linear development circuit configured to calculate a remaining 2m−1−m elements not included in the calculated m linear independent elements by respective combination of each of the m linear independent elements,
- wherein the 2m−1 elements are calculated using a first number of EXOR devices, the first number of EXOR devices being less than a second number of EXOR devices used to calculate the 2m−1 elements in another Galois field arithmetic operation circuit that includes 2m−1 parallel arithmetic operation circuits configured to calculate the same 2m−1 elements.
A memory device comprising an error correction circuit performing an error detection of data columns being input, wherein the error correction circuit comprises:
- a syndrome calculation circuit calculating a syndrome from a data column being input;
- an error coefficient calculation circuit calculating a coefficient of an error location detection polynomial from the syndrome;
- a Galois field arithmetic operation circuit performing an arithmetic operation by substituting a value representing a location of a bit of data of the data column and the coefficient into the error location detection polynomial;
- a Chien search circuit outputting an error detection signal indicating whether or not an error exists in each bit of the data column in response to a substitution result of the error location detection polynomial;
- and
- an error correction circuit correcting an error of data of a bit of the data column to output the corrected data in response to the error detection signal;
- wherein the Galois field arithmetic operation circuit is configured to substitute 2m−1 elements, where m is an integer, expressed by m bits of a Galois field GF(2m), and
- wherein the Galois field arithmetic operation circuit comprises:
- a base calculation circuit including m parallel arithmetic operation circuits, each of the m parallel arithmetic operation circuits configured to calculate one of m linear independent elements from the 2m−1 elements;
- and
- a linear development circuit configured to calculate a remaining 2m−1−m elements of the 2m−1 elements by respective combination of the m linear independent elements.
A Galois field arithmetic operation circuit, comprising:
- a base calculation circuit including a plurality of arithmetic operation circuits, each of the arithmetic operation circuits calculating a linear function corresponding to a particular factor of a polynomial, wherein a number of factors of the polynomial is greater than a number of arithmetic operation circuits in the base calculation circuit;
- and
- a linear development circuit configured to add an output of a first arithmetic operation circuit of the plurality of arithmetic operation circuits to an output of a second arithmetic operation circuit of the plurality of arithmetic operation circuits, and to separately add the output of the first arithmetic operation circuit to an output of a third arithmetic operation circuit of the plurality of arithmetic operation circuits.
Dependencies are inferred from the claim text.