Repairing Reed-Solomon Codes
with Side Information

Let $q$ be a prime power, $\mathbb{F}_{q}$ be the finite field of $q$ elements and $\mathbb{F}_{q^{\ell}}$ be the extension field of degree $\ell$ of $\mathbb{F}_{q}$. We use $[n]$ to denote the set $\{1,2,\ldots,n\}$, $a\mid b$ to denote that $a$ divides $b$, and $(a,b)$ for $\gcd(a,b)$, for $a,b\in\mathbb{Z}$. For a set $U$, let $U^{*}\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}U\setminus\{0\}$, and $\bm{\gamma}U\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}\{\bm{\gamma}u\colon u\in U\}$. We use $\mathsf{span}_{\mathbb{F}_{q}}(U)$ to denote the $\mathbb{F}_{q}$-subspace of $\mathbb{F}_{q^{\ell}}$ spanned by a subset $U\subseteq\mathbb{F}_{q^{\ell}}$. We use $\dim_{\mathbb{F}_{q}}(\cdot)$ and $\mathsf{rank}_{\mathbb{F}_{q}}(\cdot)$ (or $\dim(\cdot)$ and $\mathsf{rank}(\cdot)$ for short) for the dimension of a subspace and the rank of a set of vectors over $\mathbb{F}_{q}$. The (field) trace of an element ${\bm{b}}\in\mathbb{F}_{q^{\ell}}$ over $\mathbb{F}_{q}$ is $\mathsf{Tr}_{{\mathbb{F}}_{q^{\ell}}/{\mathbb{F}}_{q}}({\bm{b}})=\sum_{i=0}^{\ell-1}{\bm{b}}^{q^{i}}$. We also write $\mathsf{Tr}(\cdot)$ instead of $\mathsf{Tr}_{{\mathbb{F}}_{q^{\ell}}/{\mathbb{F}}_{q}}(\cdot)$ for simplicity.

Let ${\mathcal{C}}$ be a linear $[n,k]$ code over $\mathbb{F}_{q^{\ell}}$. Then ${\mathcal{C}}$ is an $k$-dimensional $\mathbb{F}_{q^{\ell}}$-subspace of $\mathbb{F}_{q^{\ell}}^{n}$. A codeword of ${\mathcal{C}}$ is an element $\vec{\bm{c}}=({\bm{c}}_{1},{\bm{c}}_{2},\ldots,{\bm{c}}_{n})\in{\mathcal{C}}$ and its codeword symbols are the components ${\bm{c}}_{j}$, $j\in[n]$. The dual code of a code ${\mathcal{C}}$ is the orthogonal complement ${\mathcal{C}}^{\perp}$ of ${\mathcal{C}}$, ${\mathcal{C}}^{\perp}=\{\vec{\bm{g}}\in\mathbb{F}_{q^{\ell}}^{n}:\langle\vec{\bm{c}},\vec{\bm{g}}\rangle=0,\forall\vec{\bm{c}}\in{\mathcal{C}}\}$, where $\langle\vec{\bm{c}},\vec{\bm{g}}\rangle$ is the scalar product of $\vec{\bm{c}}$ and $\vec{\bm{g}}$. The code ${\mathcal{C}}^{\perp}$ is an $\mathbb{F}_{q^{\ell}}$-subspace of $\mathbb{F}_{q^{\ell}}^{n}$ with dimension $n-k$. The elements of ${\mathcal{C}}^{\perp}$ are called dual codewords. The number $n-k$ is called the redundancy of the code ${\mathcal{C}}$.

A generalized Reed-Solomon code, $\text{GRS}(A,k,\vec{\bm{\lambda}})$, where $\vec{\bm{\lambda}}=(\bm{\lambda}_{1},\ldots,\bm{\lambda}_{n})\in\mathbb{F}_{q^{\ell}}^{n}$, is the set of codewords $\big{(}\bm{\lambda}_{1}g(\bm{\alpha}_{1}),\ldots,\bm{\lambda}_{n}g(\bm{\alpha}_{n})\big{)}$, where $\bm{\lambda}_{j}\neq 0$ for all $j\in[n]$, $g\in\mathbb{F}_{q^{\ell}}[x],\ \deg(g)<n-k$. The dual code of a Reed-Solomon code $\text{RS}(A,k)$ is a generalized Reed-Solomon code $\text{GRS}(A,n-k,\vec{\bm{\lambda}})$, for some multiplier vector $\vec{\bm{\lambda}}$ ([1, Chap. 10]). We sometimes use the notation GRS$(n,k)$, ignoring $A$ and $\vec{\bm{\lambda}}$.

Let $f(x)$ be a polynomial corresponding to a codeword of the Reed-Solomon code ${\mathcal{C}}=\text{RS}(A,k)$, and $g(x)$ be a polynomial of degree at most $n-k-1$, which corresponds to a codeword of the dual code ${\mathcal{C}}^{\perp}$. Then $\sum_{j=1}^{n}g(\bm{\alpha}_{j})\big{(}\bm{\lambda}_{j}f(\bm{\alpha}_{j})\big{)}=0,$ and we call the polynomial $g(x)$ a check polynomial for ${\mathcal{C}}$.

Let RS$(n,k)$ be a Reed-Solomon code over $\mathbb{F}_{q^{\ell}}$ with evaluation points $A$, $\vec{\bm{c}}$  a codeword corresponding to polynomial $f(x)$, $f\in\mathbb{F}_{q^{\ell}}[x],\ \deg(f)<k$, and ${\bm{c}}_{j^{*}}=f(\bm{\alpha}^{*})$ is a codeword symbol/node of $\vec{\bm{c}}$, where $\bm{\alpha}^{*}=\bm{\alpha}_{j^{*}}\in A$. A (linear) trace repair scheme for $f(\bm{\alpha}^{*})$ corresponds to a set of $\ell$ check polynomials $\left\{g_{i}(x)\right\}_{i\in[\ell]}$, $g_{i}\in\mathbb{F}_{q^{\ell}}[x],\ \deg(g_{i})<n-k$, that satisfies the Full-Rank Condition: $\mathsf{rank}_{\mathbb{F}_{q}}\{g_{i}(\bm{\alpha}^{*})\}_{i\in[\ell]}=\ell$. The repair bandwidth of such a repair scheme (in $\mathbb{F}_{q}$-symbols) is ${\sf{bw}}=\sum_{\bm{\alpha}\in A\setminus\{\bm{\alpha}^{*}\}}\mathsf{rank}_{\mathbb{F}_{q}}(\{g_{i}(\bm{\alpha})\}_{i\in[\ell]})$. To repair all $n$ components of $\vec{\bm{c}}$, we need $n$ such repair schemes (possibly with repetition). See, e.g. [31], for a detailed explanation of why the above scheme works with an example.

Let ${\mathcal{C}}$ be an RS$(n,k)$ code over $\mathbb{F}_{q^{\ell}}$ with evaluation points $A\subseteq\mathbb{F}_{q^{\ell}}$. Suppose that the codeword symbol $f(\bm{\alpha}^{*})$ is erased and needs to be recovered, given a set of $\mathbb{F}_{q}$-linearly independent combinations of its sub-symbols (elements of $\mathbb{F}_{q}$) as side information. Note that for each vector of coefficients $\vec{{\bm{a}}}=(a_{1},\ldots,a_{\ell})\in\mathbb{F}_{q}^{\ell}$, there exists a $\bm{\beta}\in\mathbb{F}_{q^{\ell}}$ such that the equality $\sum_{i=1}^{\ell}a_{i}\xi_{i}=\mathsf{Tr}(\bm{\beta}\bm{\xi})$ holds for all $\bm{\xi}\in\mathbb{F}_{q^{\ell}}$. Therefore, we can represent the side information as a set $S=\{\bm{\beta}_{i}\}_{i=1}^{s}$, where $s=|S|$, and assume that $S$ is $\mathbb{F}_{q}$-linearly independent. We assume that the replacement/recovery node already knows $s$ traces $\{\mathsf{Tr}(\bm{\beta}_{i}f(\bm{\alpha}^{*}))\}_{i\in[s]}$, where $\{\bm{\beta}_{i}\}_{i\in[s]}\subseteq\mathbb{F}_{q^{\ell}}$ is $\mathbb{F}_{q}$-linearly independent. Equivalently, we can represent the side information as a subspace ${\mathcal{S}}\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}\mathsf{span}_{\mathbb{F}_{q}}(S)$. We call $S$ the side information set and ${\mathcal{S}}$ the side information subspace. Note that $S$ is a basis of ${\mathcal{S}}$ and $s=\dim({\mathcal{S}})$.

According to the trace-repair method, it needs to reconstruct some $\ell-s$ traces of $f(\bm{\alpha}^{*})$, namely, $\{\mathsf{Tr}(\bm{\beta}_{i}f(\bm{\alpha}^{*}))\}_{i\in[s+1,\ell]}$, referred to as target traces, where $\{\bm{\beta}_{i}\}_{i\in[\ell]}$ is an $\mathbb{F}_{q}$-basis of $\mathbb{F}_{q^{\ell}}$. We refer to $T\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}\{\bm{\beta}_{i}\}_{i\in[s+1,\ell]}$ as the target set and ${\mathcal{T}}\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}\mathsf{span}_{\mathbb{F}_{q}}(T)$ the target subspace with respect to the side information set $S$ (or the side information subspace ${\mathcal{S}}$). We capture this discussion in Proposition 1. Its proof is similar to [16, Thm. 4] and can be found in Appendix V-A.

We demonstrate below that the optimal repair bandwidth for recovering an erasure depends on $s=|S|$ but not on the specific choice of $S$. We first need an auxiliary lemma.

We provide a lower bound for the repair bandwidth with side information for one erasure in a Reed-Solomon code. The lower bound is similar to those in [15, 16, 17, 31], replacing $q^{\ell}$ by $q^{\ell-s}$ at some places. When $s=0$, it reduces to the existing bound (no side information). Its proof can be found in Appendix V-B.

In some special cases, the lower bound in Proposition 3 can be explicitly computed.

In this section we investigate the repair bandwidth incurred by the subspace-polynomial repair scheme introduced in [17, 31], which generalizes the trace-polynomial-based scheme in [15, 16], under the new assumption of side information. We show that in contrast to the standard repair problem (with no side information), the repair bandwidth of such a scheme depends on the specific choice of the subspace. In particular, we transform the problem of finding subspace-polynomial repair schemes with minimum bandwidths possible into another one on subspace intersection, which on its own is an intriguing problem.

Before presenting Theorem 1, we note that given side information set $S=\{\bm{\beta}_{i}\}_{i\in[s]}$, to construct a subspace-polynomial repair scheme, one first needs to find a target set $T=\{\bm{\beta}_{i}\}_{i\in[s+1,\ell]}$ such that $S\cup T$ forms an $\mathbb{F}_{q}$-basis of $\mathbb{F}_{q^{\ell}}$ (see Proposition 1 and the discussion preceding it). Next, given that $r=n-k\geq q^{m}$, for some $m<\ell$, one picks an $m$-dimensional subspace ${\mathcal{W}}$ of $\mathbb{F}_{q^{\ell}}$, and form the $\ell-s$ check polynomials $g_{i}(x)\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}\frac{L_{\mathcal{W}}\big{(}\bm{\beta}_{i}(x-\bm{\alpha}^{*})\big{)}}{x-\bm{\alpha}^{*}}$, $i\in[s+1,\ell]$. Note that $L_{\mathcal{W}}(x)\stackrel{{\scriptstyle\mbox{\tiny$\triangle$}}}{{=}}\prod_{\bm{\omega}\in{\mathcal{W}}}(x-\bm{\omega})$ is the subspace polynomial which is a linearly map constructed over ${\mathcal{W}}$ and $\ker(L_{\mathcal{W}})={\mathcal{W}}$. The check polynomials are then used in the trace repair scheme.

Given the side information subspace ${\mathcal{S}}$, when constructing a subspace-polynomial repair scheme, we have the freedom in selecting relevant target subspace ${\mathcal{T}}$ and ${\mathcal{W}}$. Hence, one can optimize the bandwidth over such ${\mathcal{T}}$ and ${\mathcal{W}}$. This is in stark contrast to the case of standard repair without side information, in which any subspace ${\mathcal{W}}$ would lead to the same repair bandwidth [17, 31]. Theorem 1 formalizes this fact.

Note that Theorem 1 converts the repair bandwidth with side information problem restricted to subspace-polynomial repair scheme to a pure subspace-intersection problem stated below.

(Subspace-Intersection Problem) Given $\bm{\alpha}^{*}\in A\subseteq\mathbb{F}_{q^{\ell}}$ and an $s$-dimensional subspace ${\mathcal{S}}$ of $\mathbb{F}_{q^{\ell}}$, find ${\mathcal{T}}$ and ${\mathcal{W}}$ that maximizes the sum $\sum_{\bm{\alpha}\in A\setminus\{\bm{\alpha}^{*}\}}\dim\big{(}(\bm{\alpha}-\bm{\alpha}^{*}){\mathcal{T}}\cap{\mathcal{W}}\big{)}$ among all $(\ell-s)$-dimensional subspaces ${\mathcal{T}}$ and $m$-dimensional subspaces ${\mathcal{W}}$ satisfying ${\mathcal{S}}\oplus{\mathcal{T}}=\mathbb{F}_{q^{\ell}}$.

The subspace-intersection problem can be tricky to solve, especially for general $A$. Therefore, we limit ourselves to the more tractable case when $A\equiv\mathbb{F}_{q^{\ell}}$, for which optimal repair bandwidths were known for the standard repair setting (without side information) when $q^{\ell}-k\geq q^{m}$ [17, 31]. We also assume that $(\ell-s)\mid\ell$. With these assumptions, in Corollary 2, we can replace ${\mathcal{T}}$ by $\mathbb{F}_{q^{\ell-s}}$ in the optimization problem. Note that while $\mathbb{F}_{q^{\ell-s}}$ may not be a valid ${\mathcal{T}}$ (i.e $\mathbb{F}_{q^{\ell-s}}\oplus{\mathcal{S}}\neq\mathbb{F}_{q^{\ell}}$), by Lemma 1, at least one of its cosets is. Finally, although this corollary provides an upper bound instead of an exact formulation for the bandwidth, later on, using the lower bound in Proposition 3, we can establish optimal repair bandwidths for subspace polynomial schemes in some parameter regimes.

Using Corollary 2, assuming a full-length code with $(\ell-s)\mid\ell$, we can now construct a few concrete subspace-polynomial repair schemes that achieve optimal repair bandwidths among all linear schemes. To construct the first repair scheme achieving optimal repair bandwidth, we first prove an auxiliary lemma.

The following theorem indicates the existence of optimal repair schemes for a full-length Reed-Solomon codes with side information size $s$, where $(\ell-s)|\ell$. We prove that the existing subspace repair scheme can be constructed from a subfield $\mathbb{F}_{q^{m}}$ of $\mathbb{F}_{q^{\ell}}$, where $n-k\geq q^{m}$, $\ell>m\geq 1$, $m|\ell$, and $(\ell-s,m)=1$. However, for any coset of $\mathbb{F}_{q^{m}}$, the proof is still right.

Now we consider a greedy construction that generates $m$-dimensional subspaces ${\mathcal{W}}$, $m<\ell$, that generate subspace-polynomial repair schemes with minimal repair bandwidths. Assume that $a\mid\ell$. The aim is to construct a subspace ${\mathcal{W}}$ of $\mathbb{F}_{q^{\ell}}$ satisfying $\dim(\bm{\gamma}\mathbb{F}_{q^{a}}\cap{\mathcal{W}})\in\{0,1\}$ for all $\bm{\gamma}\in\mathbb{F}_{q^{\ell}}^{*}$.