Repairing Reed-Solomon Codes via Subspace Polynomials

We propose new repair schemes for Reed-Solomon codes that use subspace polynomials and hence generalize previous works in the literature that employ trace polynomials. The Reed-Solomon codes are over mathbb {F}_{{q}{ell }} and have redundancy {{r}} = {{n}}-{{k}} geq {{q}}{{m}} , 1leq {{m}}leq ell , where {{n}} and {{k}} are the code length and dimension, respectively. In particular, for one erasure, we show that our schemes can achieve optimal repair bandwidths whenever {{n}}={{q}}ell and {{r}} = {{q}}{{m}} , for all 1 leq {{m}} leq ell . For two erasures, our schemes use the same bandwidth per erasure as the single erasure schemes, for ell /{{m}} is a power of {{q}} , and for ell ={{q}}{{a}} , {{m}}={{q}}{{b}}-1>1 ( {{a}} geq {{b}} geq 1 ), and for {{m}}geq ell /2 when ell is even and {{q}} is a power of two.