Method for constructing erasure correcting codes whose implementation requires only exclusive ORs
AssigneeInternational Business Machines Corporation
InventorsShmuel Winograd, Barry Marshall Trager
Life of this patent
Estimating the term…
Abstract
Error correcting codes of any distance (including codes of distance greater than four) use only exclusive OR (XOR) operations. Any code over a finite field of characteristic two are converted into a code whose encoding and correcting algorithms involve only XORs of words (and loading and storing of the data). Thus, the implementation of the encoding and correcting algorithms is more efficient, since it uses only XORs of words—an operation which is available on almost all microprocessors. An important code, the (3, 3) code of distance four, is also described.
Claims12
A computer implemented method for encoding and correcting erasure errors comprising the steps of:
- transforming encoding and decoding matrices of GF(2n ), the Galois Field of 2n elements for n greater than one, and wherein a converted code is a (3, 3) code of distance four;
- and
- encoding data and correcting erasure errors using only exclusive OR operations on complete data words for error correcting codes with four or more check symbols which can correct as many errors as there are check symbols.
A computer implemented method for encoding data and correcting erasure errors comprising the steps of:
- converting a code over a finite field of characteristic two which can correct up to e erasure errors into a code which can correct up to e erasure errors in words;
- encoding data using the converted code;
- reading the encoded data and correcting up to e erasure errors in words, wherein the converted code is a (3, 3) code, wherein even if all the information in any three of the words w1 is erased, the data can be recovered.
A computer implemented method for encoding and correcting erasure errors comprising the steps of:
- transforming encoding and decoding matrices of GF(2n), the Galois Field of 2n elements for n greater than one, and
- encoding data and correcting erasure errors using only exclusive OR operations on complete data words.
A computer implemented method for encoding and correcting four or more erasure errors in data whose locations are known, comprising the steps of:
- converting a code over a finite field of characteristic two into a code whose encoding and correcting algorithms involve only exclusive OR (XOR) operations of complete data words;
- reading data from main volatile memory and encoding the data using only XOR operations to generate a correcting code;
- storing data and correcting code in an auxiliary array of non-volatile storage devices;
- reading the data from the auxiliary array of non-volatile storage devices;
- and
- reconstructing erasure errors in the data read from the auxiliary array of non-volatile storage devices using only XOR operations to generate reconstructed data.
A computer system for correcting four or more erasure errors whose locations are known, comprising:
- a main volatile memory and an auxiliary array of non-volatile storage devices connected for transferring data therebetween;
- an encoding means for converting a code over a finite field of characteristic two into a code whose encoding and correcting algorithms involve only exclusive OR (XOR) operations of complete data words, data read from said main volatile memory being encoded by said encoding means using only XOR operations to generate a correcting code and stored with the correcting code in said auxiliary array of non-volatile storage devices;
- and
- data reconstructing means which, when data is read from the auxiliary array of non-volatile storage devices, reconstructs erasure errors in the data read from the auxiliary array of non-volatile storage devices using only XOR operations to generate reconstructed data.
A computer implemented method for encoding and correcting erasure errors comprising the steps of:
- encoding data transferred from a memory to a storage device using only XOR operations on complete data words;
- and
- reconstructing data stored in said storage device using only XOR operations on complete data words.
Dependencies are inferred from the claim text.