Tamo-Barg code [1]

Description

A family of \(q\)-ary polynomial evaluation codes that are optimal LRCs and for which \(q\) is comparable to \(n\).

Each length-\(k\) message \(\mu\) is encoded into a string of values of its corresponding polynomial \(f_\mu\) at points \(\alpha\) in some size-\(n\) set \(A\). This polynomial can be written as \begin{align} f_{\mu}\left(x\right)=\sum_{i=0}^{r-1}\sum_{j=0}^{k/r-1}\mu_{ij}x^{i}g(x)^{j}~,\tag*{$(1)$} \end{align}where \(\mu\) has been reorganized into an \(r \times k/r\) matrix, and where \(g(x)\) is a degree-\((r+1)\) polynomial that is constant on elements of certain partitions of \(A\) [1; Sec. III.A]. This construction assumes that \(r\) divides \(k\), but a simple extension to other parameters can be formulated.