Search

Error-correcting codes resilient to synchronization errors such as insertions and deletions are known as insdel codes. Due to their important applications in DNA storage and computational biology, insdel codes have recently become a focal point of research in coding theory. In this paper, we present several new combinatorial upper and lower bounds on the maximum size of $q$-ary insdel codes. Our main upper bound is a sphere-packing bound obtained by solving a linear programming (LP) problem. It improves upon previous results for cases when the distance $d$ or the alphabet size $q$ is large. Our first lower bound is derived from a connection between insdel codes and matchings in special hypergraphs. This lower bound, together with our upper bound, shows that for fixed block length $n$ and edit distance $d$, when $q$ is sufficiently large, the maximum size of insdel codes is $ \frac{q^{n-\frac{d}{2}+1}}{{n\choose \frac{d}{2}-1}}(1 \pm o(1))$. The second lower bound refines Alon et al.'s recent logarithmic improvement on Levenshtein's GV-type bound and extends its applicability to large $q$ and $d$., Comment: 20 pages

Error-correcting codes over the real field are studied which can locate outlying computational errors when performing approximate computing of real vector--matrix multiplication on resistive crossbars. Prior work has concentrated on locating a single outlying error and, in this work, several classes of codes are presented which can handle multiple errors. It is first shown that one of the known constructions, which is based on spherical codes, can in fact handle multiple outlying errors. A second family of codes is then presented with $\zeroone$~parity-check matrices which are sparse and disjunct; such matrices have been used in other applications as well, especially in combinatorial group testing. In addition, a certain class of the codes that are obtained through this construction is shown to be efficiently decodable. As part of the study of sparse disjunct matrices, this work also contains improved lower and upper bounds on the maximum Hamming weight of the rows in such matrices.

This paper studies the problem of encoding messages into sequences which can be uniquely recovered from some noisy observations about their substrings. The observed reads comprise consecutive substrings with some given minimum overlap. This coded reconstruction problem has applications to DNA storage. We consider both single-strand reconstruction codes and multi-strand reconstruction codes, where the message is encoded into a single strand or a set of multiple strands, respectively. Various parameter regimes are studied. New codes are constructed, some of whose rates asymptotically attain the upper bounds., Comment: 35 pages

Linearized Reed-Solomon (LRS) codes are evaluation codes based on skew polynomials. They achieve the Singleton bound in the sum-rank metric and therefore are known as maximum sum-rank distance (MSRD) codes. In this work, we give necessary and sufficient conditions for the existence of MSRD codes with a support-constrained generator matrix. The conditions on the support constraints are identical to those for MDS codes and MRD codes. The required field size for an $[n,k]_{q^m}$ LRS codes with support-constrained generator matrix is $q\geq \ell+1$ and $m\geq \max_{l\in[\ell]}\{k-1+\log_qk, n_l\}$, where $\ell$ is the number of blocks and $n_l$ is the size of the $l$-th block. The special cases of the result coincide with the known results for Reed-Solomon codes and Gabidulin codes. For the support constraints that do not satisfy the necessary conditions, we derive the maximum sum-rank distance of a code whose generator matrix fulfills the constraints. Such a code can be constructed from a subcode of an LRS code with a sufficiently large field size. Moreover, as an application in network coding, the conditions can be used as constraints in an integer programming problem to design distributed LRS codes for a distributed multi-source network., Comment: 26 pages, 4 figures, 2 tables. Revision Submitted to IEEE Transaction on Information Theory

Motivated by applications to DNA-storage, flash memory, and magnetic recording, we study perfect burst-correcting codes for the limited-magnitude error channel. These codes are lattices that tile the integer grid with the appropriate error ball. We construct two classes of such perfect codes correcting a single burst of length $2$ for $(1,0)$-limited-magnitude errors, both for cyclic and non-cyclic bursts. We also present a generic construction that requires a primitive element in a finite field with specific properties. We then show that in various parameter regimes such primitive elements exist, and hence, infinitely many perfect burst-correcting codes exist., Comment: 23 pages

Motivated by applications to DNA storage, we study reconstruction and list-reconstruction schemes for integer vectors that suffer from limited-magnitude errors. We characterize the asymptotic size of the intersection of error balls in relation to the code's minimum distance. We also devise efficient reconstruction algorithms for various limited-magnitude error parameter ranges. We then extend these algorithms to the list-reconstruction scheme, and show the trade-off between the asymptotic list size and the number of required channel outputs. These results apply to all codes, without any assumptions on the code structure. Finally, we also study linear reconstruction codes with small intersection, as well as show a connection to list-reconstruction codes for the tandem-duplication channel., Comment: 22 pages

We study generalized covering radii, a fundamental property of linear codes that characterizes the trade-off between storage, latency, and access in linear data-query protocols such as PIR. We prove lower and upper bounds on the generalized covering radii of Reed-Muller codes, as well as finding their exact value in certain extreme cases. With the application to linear data-query protocols in mind, we also construct a covering algorithm that gets as input a set of points in space, and find a corresponding set of codewords from the Reed-Muller code that are jointly not farther away from the input than the upper bound on the generalized covering radius of the code. We prove that the algorithm runs in time that is polynomial in the code parameters.

Error-correcting codes over sets, with applications to DNA storage, are studied. The DNA-storage channel receives a set of sequences, and produces a corrupted version of the set, including sequence loss, symbol substitution, symbol insertion/deletion, and limited-magnitude errors in symbols. Various parameter regimes are studied. New bounds on code parameters are provided, which improve upon known bounds. New codes are constructed, at times matching the bounds up to lower-or der terms or small constant factors.

We study scalar-linear and vector-linear solutions of the generalized combination network. We derive new upper and lower bounds on the maximum number of nodes in the middle layer, depending on the network parameters and the alphabet size. These bounds improve and extend the parameter range of known bounds. Using these new bounds we present a lower bound and an upper bound on the gap in the alphabet size between optimal scalar-linear and optimal vector-linear network coding solutions. For a fixed network structure, while varying the number of middle-layer nodes $r$, the asymptotic behavior of the upper and lower bounds shows that the gap is in $\Theta(\log(r))$., Comment: extended version of arXiv:2001.04150v2; 13 pages, 5 figures, 1 table, accepted for publication in IEEE Transactions on Information Theory

We study whether an asymmetric limited-magnitude ball may tile $\mathbb{Z}^n$. This ball generalizes previously studied shapes: crosses, semi-crosses, and quasi-crosses. Such tilings act as perfect error-correcting codes in a channel which changes a transmitted integer vector in a bounded number of entries by limited-magnitude errors. A construction of lattice tilings based on perfect codes in the Hamming metric is given. Several non-existence results are proved, both for general tilings, and lattice tilings. A complete classification of lattice tilings for two certain cases is proved.

We construct integer error-correcting codes and covering codes for the limited-magnitude error channel with more than one error. The codes are lattices that pack or cover the space with the appropriate error ball. Some of the constructions attain an asymptotic packing/covering density that is constant. The results are obtained via various methods, including the use of codes in the Hamming metric, modular $B_t$-sequences, $2$-fold Sidon sets, and sets avoiding arithmetic progression.

A robust positioning pattern is a large array that allows a mobile device to locate its position by reading a possibly corrupted small window around it. In this paper, we provide constructions of binary positioning patterns, equipped with efficient locating algorithms, that are robust to a constant number of errors and have redundancy within a constant factor of optimality. Furthermore, we modify our constructions to correct rank errors and obtain binary positioning patterns robust to any errors of rank less than a constant number. Additionally, we construct $q$-ary robust positioning sequences robust to a large number of errors, some of which have length attaining the upper bound. Our construction of binary positioning sequences that are robust to a constant number of errors has the least known redundancy amongst those explicit constructions with efficient locating algorithms. On the other hand, for binary robust positioning arrays, our construction is the first explicit construction whose redundancy is within a constant factor of optimality. The locating algorithms accompanying both constructions run in time cubic in sequence length or array dimension., Comment: Extended Version of SODA 2019 Paper

To equip DNA-based data storage with random-access capabilities, Yazdi et al. (2018) prepended DNA strands with specially chosen address sequences called primers and provided certain design criteria for these primers. We provide explicit constructions of error-correcting codes that are suitable as primer addresses and equip these constructions with efficient encoding algorithms. Specifically, our constructions take cyclic or linear codes as inputs and produce sets of primers with similar error-correcting capabilities. Using certain classes of BCH codes, we obtain infinite families of primer sets of length $n$, minimum distance $d$ with $(d + 1) \log_4 n + O(1)$ redundant symbols. Our techniques involve reversible cyclic codes (1964), an encoding method of Tavares et al. (1971) and Knuth's balancing technique (1986). In our investigation, we also construct efficient and explicit binary balanced error-correcting codes and codes for DNA computing.

A class of low-power cooling (LPC) codes, to control simultaneously both the peak temperature and the average power consumption of interconnects, was introduced recently. An $(n,t,w)$-LPC code is a coding scheme over $n$ wires that (A) avoids state transitions on the $t$ hottest wires (cooling), and (B) limits the number of transitions to $w$ in each transmission (low-power). A few constructions for large LPC codes that have efficient encoding and decoding schemes, are given. In particular, when $w$ is fixed, we construct LPC codes of size $(n/w)^{w-1}$ and show that these LPC codes can be modified to correct errors efficiently. We further present a construction for large LPC codes based on a mapping from cooling codes to LPC codes. The efficiency of the encoding/decoding for the constructed LPC codes depends on the efficiency of the decoding/encoding for the related cooling codes and the ones for the mapping.

Let $K=\{k_1,k_2,\ldots,k_r\}$ and $L=\{l_1,l_2,\ldots,l_s\}$ be disjoint subsets of $\{0,1,\ldots,p-1\}$, where $p$ is a prime and $A=\{A_1,A_2,\ldots,A_m\}$ be a family of subsets of $[n]$ such that $|A_i|\pmod{p}\in K$ for all $A_i\in A$ and $|A_i\cap A_j|\pmod{p}\in L$ for $i\ne j$. In 1991, Alon, Babai and Suzuki conjectured that if $n\geq s+\max_{1\leq i\leq r} k_i$, then $|A|\leq {n\choose s}+{n\choose s-1}+\cdots+{n\choose s-r+1}$. In 2000, Qian and Ray-Chaudhuri proved the conjecture under the condition $n\geq 2s-r$. In 2015, Hwang and Kim verified the conjecture of Alon, Babai and Suzuki. In this paper, we will prove that if $n\geq 2s-2r+1$ or $n\geq s+\max_{1\leq i\leq r}k_i$, then \[ |A|\leq{n-1\choose s}+{n-1\choose s-1}+\cdots+{n-1\choose s-2r+1}. \] This result strengthens the upper bound of Alon, Babai and Suzuki's conjecture when $n\geq 2s-2$.

Given a database, the private information retrieval (PIR) protocol allows a user to make queries to several servers and retrieve a certain item of the database via the feedbacks, without revealing the privacy of the specific item to any single server. Classical models of PIR protocols require that each server stores a whole copy of the database. Recently new PIR models are proposed with coding techniques arising from distributed storage system. In these new models each server only stores a fraction $1/s$ of the whole database, where $s>1$ is a given rational number. PIR array codes are recently proposed by Fazeli, Vardy and Yaakobi to characterize the new models. Consider a PIR array code with $m$ servers and the $k$-PIR property (which indicates that these $m$ servers may emulate any efficient $k$-PIR protocol). The central problem is to design PIR array codes with optimal rate $k/m$. Our contribution to this problem is three-fold. First, for the case $12$, we derive a new upper bound on the rate of a PIR array code. Finally, for the case $s>2$, we analyze a new construction by Blackburn and Etzion and show that its rate is better than all the other existing constructions.

Multiply constant-weight codes (MCWCs) were introduced recently to improve the reliability of certain physically unclonable function response. In this paper, the bounds of MCWCs and the constructions of optimal MCWCs are studied. Firstly, we derive three different types of upper bounds which improve the Johnson-type bounds given by Chee {\sl et al.} in some parameters. The asymptotic lower bound of MCWCs is also examined. Then we obtain the asymptotic existence of two classes of optimal MCWCs, which shows that the Johnson-type bounds for MCWCs with distances $2\sum_{i=1}^mw_i-2$ or $2mw-w$ are asymptotically exact. Finally, we construct a class of optimal MCWCs with total weight four and distance six by establishing the connection between such MCWCs and a new kind of combinatorial structures. As a consequence, the maximum sizes of MCWCs with total weight less than or equal to four are determined almost completely., Comment: 34 pages