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

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 subpacketization 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 log₂ ℓ for two parity nodes, and either 3 log₃ℓ or 4 log₃ℓ 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 6log₃ℓ + 1 (or 3 log₃ℓ + 1 for fields with characteristic 2) is sufficient, and in the second construction the field size is larger, yet linear in log₃ℓ . Both constructions with three parities provide a significant improvement over previous works due to either decreased field size or lower subpacketization.