Constructions of High-Rate Minimum Storage Regenerating Codes Over Small Fields

摘要

A novel technique for construction of minimum storage regenerating (MSR) codes is presented. Based on this technique, three explicit constructions of MSR codes are given. The first two constructions provide access-optimal MSR codes, with two and three parities, respectively, which attain the sub-packetization bound for access-optimal codes. The third construction provides longer MSR codes with three parities (i.e., codes with larger number of systematic nodes). This improvement is achieved at the expense of the access-optimality and the field size. In addition to a minimum storage in a node, all three constructions allow the entire data to be recovered from a minimal number of storage nodes. That is, given storage ℓ in each node, the entire stored data can be recovered from any 2 log2 ℓ for two parity nodes, and either 3 log3 ℓ or 4 log3 ℓ for three parities. Second, in the first two constructions, a helper node accesses the minimum number of its symbols for repair of a failed node (access-optimality). The goal of this paper is to provide a construction of such optimal codes over the smallest possible finite fields. The generator matrix of these codes is based on perfect matchings of complete graphs and hypergraphs, and on a rational canonical form of matrices. For two parities, the field size is reduced by a factor of two for access-optimal codes compared to previous constructions. For three parities, in the first construction a field size of at least 6 log3 ℓ +1 (or 3 log3 ℓ +1 for fields with characteristic 2) is sufficient, and in the second construction the field size is larger, yet linear in log3 ℓ. Both constructions with three parities provide a significant improvement over previous works due to either decreased field size or lower subpacketization.