Redundant code generation method and device, data restoration method and device, and raid storage device

A redundant code generation device for generating a redundant code data string by means of an extended Galois field operation from original data, comprising:

• an arithmetic device including at least an exclusive OR arithmetic circuit;
• a memory;
• and
• an address bus and data bus connecting said arithmetic device and said memory;
• wherein said original data are divided into a plurality of data strings;
• each of said data strings is divided into a number of bit strings that accords with the extended Galois field operation;
• and said memory includes a plurality of memory areas for storing each of said bit strings generated by the division,
• wherein said arithmetic device, taking a predetermined plural number of bits as a data unit, extracts vectors from the respective bit strings stored in said memory under address control that accords with an operational expression, executes an exclusive OR operation among said vectors to compute bit strings that make up said redundant code data string without carrying out a bit shift operation in said vectors, and stores the computed bit strings in corresponding memory areas in said memory, and
• wherein the number of bits as elements constituting each of said vectors is equal to said data unit, and the operational expression includes a companion matrix of a primitive polynomial of said extended Galois field and defines the generation of said redundant code data string.

A data restoration method for, when original data have been divided into a plurality of data strings and a redundant code data string has been generated by means of an extended Galois field operation from said original data, restoring a data string, which has become faulty among said data strings, based on normal data strings and said redundant code data string to generate a restored data string, said data restoration method comprising:

• dividing each of said normal data strings and said redundant code data string into a number of bit strings that accords with said extended Galois field operation;
• storing each of the bit strings generated by the division in a different memory area of a memory;
• and
• executing an exclusive OR operation among vectors, which are extracted from the respective bit strings stored in said memory, according to an operational expression to compute bit strings that make up said restored data string without carrying out a bit shift operation in said vectors, a predetermined plural number of bits being taken as a data unit, the number of bits as elements constituting each of said vectors being equal to said data unit, said operational expression including a companion matrix of a primitive polynomial of said extended Galois field and defining the restoration of data strings.

A data restoration device for, when original data have been divided into a plurality of data strings and a redundant code data string has been generated by means of an extended Galois field operation from said original data, restoring a data string, which has become faulty among said data strings, based on normal data strings and said redundant code data string to generate a restored data string, said data restoration device comprising:

• an arithmetic device including at least an exclusive OR arithmetic circuit;
• a memory;
• and
• an address bus and data bus connecting said arithmetic device and said memory;
• wherein each of said normal data strings and said redundant code data string is divided into a number of bit strings that accords with said extended Galois field operation;
• said memory includes a plurality of memory areas for storing each of the bit strings generated by the division,
• wherein said arithmetic device, taking a predetermined plural number of bits as a data unit, extracts vectors from the respective bit strings stored in said memory under address control that accords with an operational expression, executes an exclusive OR operation among said vectors to compute bit strings that make up said restored data string without carrying out a bit shift operation in said vectors, and stores the computed bit strings in corresponding memory areas in said memory, and
• wherein the number of bits as elements constituting each of said vectors is equal to said data unit, and the operational expression includes a companion matrix of a primitive polynomial of said extended Galois field and defines the restoration of data strings.

A RAID storage device, comprising:

• a plurality of data recording media;
• and
• an exclusive OR arithmetic circuit;
• wherein:
• original data are divided into a plurality of data strings and distributed and stored in said data recording media, and a redundant code data string found by means of an extended Galois field operation from said original data is stored in at least one of the data recording media;
• each said data string is divided into a number of bit strings that accords with said extended Galois field operation;
• said exclusive OR arithmetic circuit, taking a predetermined plural number of bits as a data unit, extracts vectors from the respective bit strings according to an operational expression which includes a companion matrix of a primitive polynomial of said extended Galois field, and executes exclusive OR operations among said vectors to carry out said extended Galois field operation without carrying out a bit shift operation in said vectors;
• and
• wherein the number of bits as elements constituting each of said vectors is equal to said data unit, and the operational expression is an operational expression for generating a redundant code data string or an operational expression for data string restoration.