Back to results
US 2008/0177815 A1Published application
Raid system and galois field product computation method
AssigneeFujitsu Limited
InventorToshio Ito
Life of this patent
Estimating the term…
Abstract
Described is an apparatus for performing a Galois field product computation on data. A first symbol data includes a plurality of symbols each being a bit sequence on which a product operation by a factor α is to be performed in a Galois field, where α is a primitive element of the Galois field, is acquired. A factor α computation is performed on the first symbol data by performing a bit shift operation on the first symbol data toward high-order bit position, generating first mask data from the first symbol data, generating first correction data by computing a logical AND of the first mask data and a first symbol correction value, generating a factor α computation result by computing a XOR of the second symbol data and the first correction data.
Claims11
An apparatus for storing data, comprising:
- N data storages each storing a partial data block which is one of N partial data blocks generated by dividing the data where N is a natural number greater than 1;
- a parity storage for storing a first parity data and a second parity data, the first parity data being generated by combining the N partial data blocks, the second parity data being generated by performing on the N partial data blocks a Galois field product computation;
- a controller for dividing the data into the N partial data blocks, generating the first parity data by combining the N partial data blocks, generating the second parity data by performing on the N partial data blocks the Galois field product computation, and storing the generated first and second parity data into the parity storage, wherein the controller performs the Galois field product computation comprising:
- acquiring, from one of the N partial data blocks, a first symbol data including a plurality of symbols each being a bit sequence on which a product operation by a factor α is to be performed in a Galois field, where α is a primitive element of the Galois field;
- performing a factor α computation comprising:
- generating a second symbol data by performing a bit shift operation on the first symbol data toward high-order bit position,
- generating first mask data from the first symbol data, by substituting 1 into all the bits of a symbol thereof having a carry bit to be generated by the bit shift operation and by substituting 0 into all the bits of the other symbols thereof,
- generating first correction data by computing a logical AND of the first mask data and a first symbol correction value which is determined on the basis of a primitive polynomial for the Galois field,
- generating a factor α computation result by computing a XOR of the second symbol data and the first correction data, the factor α computation result including the plurality of symbols each including a result of a product operation of the factor α and the corresponding symbol included in the first symbol data in the Galois field, and
- storing the factor α computation result into the first symbol data as a new first symbol data;
- and
- repeating the factor α computation a repetition number M times on the first symbol data where M is an integer greater than or equal to 0, so as to weight each symbol included in the first symbol data with a waiting value of a factor αM.
9 more elements
A method for performing a Galois field product computation on data, comprising:
- acquiring a first symbol data including a plurality of symbols each being a bit sequence on which a product operation by a factor α is to be performed in a Galois field, where α is a primitive element of the Galois field;
- performing a factor α computation comprising:
- generating a second symbol data by performing a bit shift operation on the first symbol data toward high-order bit position,
- generating first mask data from the first symbol data, by substituting 1 into all the bits of a symbol thereof having a carry bit to be generated by the bit shift operation thereon and by substituting 0 into all the bits of the other symbols thereof,
- generating first correction data by computing a logical AND of the first mask data and a first symbol correction value which is determined on the basis of a primitive polynomial for the Galois field,
- generating a factor α computation result by computing a XOR of the second symbol data and the first correction data, the factor α computation result including the plurality of symbols each including a result of a product operation of the factor α and the corresponding symbol included in the first symbol data in the Galois field, and
- storing the factor α computation result into the first symbol data as a new first symbol data;
- and
- repeating the factor α computation a repetition number M times on the first symbol data where M is an integer greater than or equal to 0, so as to weight each symbol included in the first symbol data with a weighting value of a factor αM.
6 more elements
Dependencies are inferred from the claim text.