公开(公告)号：US09430443B1

公开(公告)日：2016-08-30

申请号：US14707211

申请日：2015-05-08

Applicant: Norwegian University of Science and Technology

Inventor： Rune Erlend Jensen ,  Katina Kralevska ,  Danilo Gligoroski ,  Sindre Berg Stene

IPC: G06F17/16 ,  H03M13/11

CPC classification number: H03M13/1174 ,  H03M13/033 ,  H03M13/134 ,  H03M13/373 ,  H03M13/6502

Abstract: Disclosed herein is a method of generating a generator matrix for defining how to systematically code source data, the method comprising: determining source nodes for comprising a plurality of sub-stripes of source data, wherein the number of source nodes is K and the number of sub-stripes of source data comprised by each source node is S; determining redundant nodes for comprising a plurality of sub-stripes of coded data, wherein the number of redundant nodes is R and the number of sub-stripes of coded data comprised by each redundant node is S; determining values of a first generator matrix according to a systematic coding technique such that K of the rows of the generator matrix to define how to generate all of the K source nodes as comprising source data and R of the rows of the first generator matrix define how to generate all of the R redundant nodes as comprising combinations of two or more of the source nodes; generating a second generator matrix, with a first dimension (K×S) and a second dimension ((K+R)×S), in dependence on the determined first generator matrix, wherein each value of the second generator matrix defines how to generate the data comprised by a respective sub-stripe of a node defined by the first generator matrix such that the values of the second generator matrix define how to generate all of the sub-stripes of all of the nodes defined by the first generator matrix; and changing one or more of the values of the second generator matrix so that a sub-stripe of at least one of the redundant nodes is defined, by the systematic coding technique, as being dependent on a combination of two or more sub-stripes of data in the source nodes and is further defined as being dependent on one or more further sub-stripes of data, in a respective one or more source nodes, that the sub-stripe of the redundant node was not defined as being dependent on by the systematic coding technique. Advantageously, when the second generator matrix is used to generate erasure coded data in a data storage system, the amount of data that needs to be obtained to reconstruct a lost data node is less than if Reed-Solomon or other known coding techniques had been used.