Código recuperable localmente

La construcción de Tamo-Barg utiliza buenos polinomios. ^{[ 9 ]}

• Supongamos que un${\displaystyle (r,\ell )}$-buen polinomio${\displaystyle f(x)}$encima${\displaystyle \mathbb {F} _{q}}$se da con una cubierta divisoria${\displaystyle i\in \{1,\ldots ,\ell \}}$.

• Dejar${\displaystyle s\leq \ell -1}$sea ​​un número entero positivo .

• Considere lo siguiente${\displaystyle \mathbb {F} _{q}}$- espacio vectorial de polinomios$${\displaystyle V=\left\{\sum _{i=0}^{s}g_{i}(x)f(x)^{i}:\deg(g_{i}(x))\leq \deg(f(x))-2\right\}.}$$

• Dejar${\textstyle T=\bigcup _{i=1}^{\ell }A_{i}}$.

• El código${\displaystyle \{\operatorname {ev} _{T}(g):g\in V\}}$es un${\displaystyle ((r+1)\ell ,(s+1)r,d,r)}$-código localmente cubrible óptimo, donde${\displaystyle \operatorname {ev} _{T}}$denota evaluación de${\displaystyle g}$en todos los puntos del conjunto${\displaystyle T}$.

• Longitud. La longitud es el número de puntos de evaluación. Porque los conjuntos${\displaystyle A_{i}}$son disjuntos para${\displaystyle i\in \{1,\ldots ,\ell \}}$, la longitud del código es${\displaystyle |T|=(r+1)\ell }$.

• Dimensión. La dimensión del código es${\displaystyle (s+1)r}$, para${\displaystyle s}$≤${\displaystyle \ell -1}$, como cada uno${\displaystyle g_{i}}$tiene un título como máximo${\displaystyle \deg(f(x))-2}$, cubriendo un espacio vectorial de dimensión${\displaystyle \deg(f(x))-1=r}$y mediante la construcción de${\displaystyle V}$, hay${\displaystyle s+1}$distinto${\displaystyle g_{i}}$.

• Distancia. La distancia viene dada por el hecho de que${\displaystyle V\subseteq \mathbb {F} _{q}[x]_{\leq k}}$, dónde${\displaystyle k=r+1-2+s(r+1)}$y el código obtenido es el código Reed-Solomon de grado como máximo${\displaystyle k}$, por lo que la distancia mínima es igual a${\displaystyle (r+1)\ell -((r+1)-2+s(r+1))}$.

• Localidad. Después de la eliminación del único componente, la evaluación en${\displaystyle a_{i}\in A_{i}}$, dónde${\displaystyle |A_{i}|=r+1}$, es desconocido, pero las evaluaciones para todos los demás${\displaystyle a\in A_{i}}$son conocidos, por lo que como máximo${\displaystyle r}$Se necesitan evaluaciones para determinar de forma unívoca el componente borrado, lo que nos da la localidad de${\displaystyle r}$.

Para ver esto,${\displaystyle g}$restringido a${\displaystyle A_{j}}$puede describirse mediante un polinomio${\displaystyle h}$ of degree at most ${\displaystyle \deg(f(x))-2=r+1-2=r-1}$ thanks to the form of the elements in ${\displaystyle V}$ (i.e., thanks to the fact that ${\displaystyle f}$ is constant on ${\displaystyle A_{j}}$, and the ${\displaystyle g_{i}}$'s have degree at most ${\displaystyle \deg(f(x))-2}$). On the other hand ${\displaystyle |A_{j}\backslash \{a_{j}\}|=r}$, and ${\displaystyle r}$ evaluations uniquely determine a polynomial of degree${\displaystyle r-1}$. Therefore ${\displaystyle h}$ can be constructed and evaluated at ${\displaystyle a_{j}}$ to recover ${\displaystyle g(a_{j})}$.

We will use ${\displaystyle x^{5}\in \mathbb {F} _{41}[x]}$ to construct ${\displaystyle [15,8,6,4]}$-LRC. Notice that the degree of this polynomial is 5, and it is constant on ${\displaystyle A_{i}}$ for ${\displaystyle i\in \{1,\ldots ,8\}}$, where ${\displaystyle A_{1}=\{1,10,16,18,37\}}$, ${\displaystyle A_{2}=2A_{1}}$, ${\displaystyle A_{3}=3A_{1}}$, ${\displaystyle A_{4}=4A_{1}}$, ${\displaystyle A_{5}=5A_{1}}$, ${\displaystyle A_{6}=6A_{1}}$, ${\displaystyle A_{7}=11A_{1}}$, and ${\displaystyle A_{8}=15A_{1}}$: ${\displaystyle A_{1}^{5}=\{1\}}$, ${\displaystyle A_{2}^{5}=\{32\}}$, ${\displaystyle A_{3}^{5}=\{38\}}$, ${\displaystyle A_{4}^{5}=\{40\}}$, ${\displaystyle A_{5}^{5}=\{9\}}$, ${\displaystyle A_{6}^{5}=\{27\}}$, ${\displaystyle A_{7}^{5}=\{3\}}$, ${\displaystyle A_{8}^{5}=\{14\}}$. Hence, ${\displaystyle x^{5}}$ is a ${\displaystyle (4,8)}$-good polynomial over ${\displaystyle \mathbb {F} _{41}}$ by the definition. Now, we will use this polynomial to construct a code of dimension${\displaystyle k=8}$ and length ${\displaystyle n=15}$ over ${\displaystyle \mathbb {F} _{41}}$. The locality of this code is 4, which will allow us to recover a single server failure by looking at the information contained in at most 4 other servers.

Next, let us define the encoding polynomial: ${\displaystyle f_{a}(x)=\sum _{i=0}^{r-1}f_{i}(x)x^{i}}$, where ${\displaystyle f_{i}(x)=\sum _{i=0}^{{\frac {k}{r}}-1}a_{i,j}g(x)^{j}}$. So, ${\displaystyle f_{a}(x)=}$${\displaystyle a_{0,0}+}$${\displaystyle a_{0,1}x^{5}+}$${\displaystyle a_{1,0}x+}$${\displaystyle a_{1,1}x^{6}+}$${\displaystyle a_{2,0}x^{2}+}$${\displaystyle a_{2,1}x^{7}+}$${\displaystyle a_{3,0}x^{3}+}$${\displaystyle a_{3,1}x^{8}}$.

Thus, we can use the obtained encoding polynomial if we take our data to encode as the row vector${\displaystyle a=}$${\displaystyle (a_{0,0},a_{0,1},a_{1,0},a_{1,1},a_{2,0},a_{2,1},a_{3,0},a_{3,1})}$. Encoding the vector${\displaystyle m}$ to a length 15 message vector${\displaystyle c}$ by multiplying ${\displaystyle m}$ by the generator matrix

${\displaystyle G={\begin{pmatrix}1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\1&1&1&1&1&32&32&32&32&32&38&38&38&38&38\\1&10&16&18&37&2&20&32&33&36&3&7&13&29&30\\1&10&16&18&37&23&25&40&31&4&32&20&2&36&33\\1&18&10&37&16&4&31&40&23&25&9&8&5&21&39\\1&18&10&37&16&5&8&9&39&21&14&17&26&19&6\\1&16&37&10&18&8&5&9&21&39&27&15&24&35&22\\1&16&37&10&18&10&37&1&16&18&1&37&10&18&16\end{pmatrix}}.}$

For example, the encoding of information vector${\displaystyle m=(1,1,1,1,1,1,1,1)}$ gives the codeword ${\displaystyle c=mG=(8,8,5,9,21,3,36,31,32,12,2,20,37,33,21)}$.

Observe that we constructed an optimal LRC; therefore, using the Singleton bound, we have that the distance of this code is ${\displaystyle d=n-k-\left\lceil {\frac {k}{r}}\right\rceil +2=15-8-2+2=7}$. Thus, we can recover any 6 erasures from our codeword by looking at no more than 8 other components.