Search

We consider construction of deletion and substitution correcting codes with low redundancy and efficient encoding/ decoding. First, by simplifying the method of Sima et al. (ISIT 2020), we construct a family of binary single-deletion $s$ -substitution correcting codes with redundancy $(s+1) (2s+1)\log _{2} n+o(\log _{2} n)$ and encoding complexity $O(n^{2})$ , where $n$ is the blocklength of the code and $s\geq 1$. The construction can be viewed as a generalization of Smagloy et al.’s construction (ISIT 2020), and for the special case of $s=1$ , our construction is a slight improvement in redundancy of the existing works. Further, we modify the syndrome compression technique by combining a precoding process and construct a family of systematic $t$ -deletion $s$ -substitution correcting codes with polynomial time encoding/decoding algorithms for both binary and nonbinary alphabets, where $t\geq 1$ and $s\geq 1$. Specifically, our binary $t$ -deletion $s$ -substitution correcting codes of length $n$ have redundancy $(4t+3s)\log _{2}n+o(\log _{2}n)$ , whereas, for $q$ being a prime power, the redundancy of $q$ -ary $t$ -deletion $s$ -substitution codes is asymptotically $\left({4t+4s-1-\lfloor \frac {2s-1}{q}\rfloor }\right)\vphantom {{\lfloor \frac {2s-1}{q}\rfloor }_{j}}\log _{q} n + o(\log _{q}n)$ as $n\to \infty $. We also construct a family of binary systematic $t$ -deletion correcting codes (i.e., $s=0$) with redundancy $(4t-1)\log _{2} n+o(\log _{2} n)$. The proposed constructions improve upon the redundancy of the state-of-the-art constructions. [ABSTRACT FROM AUTHOR]

Lifted Reed-Solomon and multiplicity codes are classes of codes, constructed from specific sets of $m$ -variate polynomials. These codes allow for the design of high-rate codes that can recover every codeword or information symbol from many disjoint sets. Recently, the underlying approaches have been combined for the bi-variate case to construct lifted multiplicity codes, a generalization of lifted codes that can offer further rate improvements. We continue the study of these codes by first establishing new lower bounds on the rate of lifted Reed-Solomon codes for any number of variables $m$ , which improve upon the known bounds for any $m\ge 4$. Next, we use these results to provide lower bounds on the rate and distance of lifted multiplicity codes obtained from polynomials in an arbitrary number of variables, which improve upon the known results for any $m\ge 3$. Specifically, we investigate a subcode of a lifted multiplicity code formed by the linear span of $m$ -variate monomials whose restriction to an arbitrary line in ${\mathbb {F}}_{q}^{m}$ is equivalent to a low-degree univariate polynomial. We find the tight asymptotic behavior of the fraction of such monomials when the number of variables $m$ is fixed and the alphabet size $q=2^\ell $ is large. Using these results, we give a new explicit construction of batch codes utilizing lifted Reed-Solomon codes. For some parameter regimes, these codes have a better trade-off between parameters than previously known batch codes. Further, we show that lifted multiplicity codes have a better trade-off between redundancy and the number of disjoint recovering sets for every codeword or information symbol than previously known constructions, thereby providing the best known PIR codes for some parameter regimes. Additionally, we present a new local self-correction algorithm for lifted multiplicity codes. [ABSTRACT FROM AUTHOR]