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

This paper presents a new construction of high-rate minimum storage regenerating codes. In addition to a minimum storage in a node, these codes have the following two important properties: first, given storage l in each node, the entire stored data can be recovered from any 2 log(2) l (any 3 log(3) (l)) nodes for two parities (for three parities, respectively); second, a helper node accesses the minimum number of its symbols for repair of a failed systematic 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, the field size is 6 log(3) l + 1 (or 3 log(3) l + 1 for fields with characteristic 2), where only non-explicit constructions with exponential field size (in log(3) l) were known so far.