Error-correcting codes resilient to synchronization errors such as insertions and deletions are known as insdel codes. In this paper, we present several new combinatorial upper and lower bounds on the maximum size ofq-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 distancedor the alphabet sizeqis 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 lengthnand edit distanced, whenqis sufficiently large, the maximum size of insdel codes is$ \frac {q^{n-\frac {d}{2}+1}}{\binom {n}{\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 largeqandd.

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 _{q}k, 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.

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 0–1 paritycheck 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.

We study network maximum distance separable (MDS) codes, which are a class of network error-correcting codes whose distance attains the Singleton-type bound. The minimum field size of a network MDS code is of particular interest, since it impacts the computing complexity at the network nodes. Previous constructions of network MDS codes, which are applicable to general single-source multicast networks, require large field sizes. In this paper, for two specific classes of network topologies, we derive upper and lower bounds on the minimum field size of the corresponding network MDS codes and present explicit constructions. The proposed upper bounds significantly improve upon the previous ones and differ from the lower bounds only by a small factor, which is asymptotically no more than 2. Additionally, we extend the concept of linear network error-correction coding from the scalar case to the vector case, and demonstrate a class of networks in which the minimum field size of the vector network MDS code is substantially smaller than that of the scalar case.

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 in 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.

Linearized Reed-Solomon (LRS) codes are a class of 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 on the existence of MSRD codes with support-constrained generator matrix. These conditions are identical to those for MDS codes and MRD codes. Moreover, the required field size for an ${\left[ {n,k} \right]_{{q^m}}}$ LRS codes with support-constrained generator matrix is q⩾ ℓ + 1 and m ⩾ maxl∈[ℓ]{k−1+logqk,nl}, where ℓ is the number of blocks and nlis 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.

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, where each error affects the corresponding position by increasing it by one, 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.

We consider the following robust computing problem in a directed acyclic network. A sink node is required to compute with zero error a target function of source messages which are generated at multiple source nodes, whereas the communication links might be corrupted by errors. The nodes in this network may perform network coding to combat the errors. Given an integer$\tau $, the robust computing rate of a network code against$\tau $errors is the average number of times that the target function can be computed with zero error for one use of the network with at most$\tau $links being corrupted by errors. We derive two cut-set bounds on the robust computing capacity and show that these bounds can be achieved in a multi-edge tree network for computing any target function. Furthermore, we consider linear network codes for computing linear target functions. Given a computing rate, we define a minimum distance to measure the error-tolerant capability of the linear network function computing codes. We propose a Singleton-like bound on this minimum distance and show that this bound is tight in two classes of networks for computing the sum of source messages.

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 find the exact value of the generalized covering radii of Reed-Muller codes in certain extreme cases, as well as proving lower and upper bounds in various scenarios.

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.

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.

A robust positioning pattern is a large array in which the contents of any subarray of given dimension can determine the subarray’s position, even if they are corrupted by errors. In this paper, we propose new explicit constructions and efficient locating algorithms for robust positioning patterns, which improve upon the previous results in two parameter regimes. For robustness against a constantfractionof errors, we construct the first infinite family of$q$-ary robust positioning patterns whose rate asymptotically achieves the Singleton bound. For robustness against a constantnumberof errors, we present the first infinite family of binary robust positioning patterns where the gap between the redundancy and the lower bound is logarithmic in the subarray size and independent of the number of errors. Along with these explicit constructions, we also give efficient locating algorithms with time complexity quartic or cubic in the subarray size.

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-order terms or small constant factors.

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.

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 Θ(log(r)).

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 Bt-sequences, 2-fold Sidon sets, and sets avoiding arithmetic progression.

An (n,d)-robust positioning sequence (RPS) is a binary sequence where every pair of length-n subwords is distance d apart. In this paper, we study the quantity P(n,d), which denotes maximum length of an (n,d)-RPS, and provide tight estimates in the range n/2 < d ≤ n. First, we show that the usual Plotkin bound cannot be attained when certain divisibility conditions hold. Next, using the concept of differences, we construct an infinite family of RPSs that attain a modified Plotkin bound. Finally, except for 16 cases, we determine the exact values of P(n,d) for δ(n) ≤ d ≤ n ≤ 50, where δ(n) = ⌈n/2⌉ if n ≢ 0(mod 4) and δ(n) = (n +2)/2 if n ≡ 0(mod 4).

We study scalar-linear and vector-linear solutions to 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. These bounds improve and extend the parameter range of known bounds. Using these new bounds we present a general lower bound on the gap in the alphabet size between scalar-linear and vector-linear solutions.

We study whether an asymmetric limited-magnitude ball may tile Zn. 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.

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 among 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.

In a bus with n wires, each wire has two states, `0' or `1', representing one bit of information. Whenever the state transitions from `0' to `1', or `1' to `0', joule heating causes the temperature to rise, and high temperatures have adverse effects on on-chip bus performance. Recently, the class of low-power cooling (LPC) codes was proposed to control such state transitions during each transmission. As suggested in earlier work, LPC codes may be used to control simultaneously both the peak temperature and the average power consumption of on-chip buses. Specifically, an (n, t, w)-LPC code is a coding scheme over n wires that (i) avoids state transitions on the t hottest wires (thus preventing the peak temperature from rising); and (ii) allows at most w state transitions in each transmission (thus reducing average power consumption). In this paper, for any fixed value of w, several constructions are presented for large LPC codes that can be encoded and decoded in time O(n log2(n/w)) along with the corresponding encoding/decoding schemes. In particular, we construct LPC codes of size (n/w)w-1, which are asymptotically optimal. We then modify these LPC codes to also correct errors in time O(n3). For the case where w is proportional to n, we further present a different construction of large LPC codes, based on a mapping from cooling codes to LPC codes. Using this construction, we obtain two families of LPC codes whose encoding and decoding complexities are O(n3).

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) log4n + 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.

Permutation codes and multipermutation codes are widely studied due to various applications in information theory. Designing codes correcting deletion errors has been the main subject of works in the literature and to the best of our knowledge, there exist only optimal codes capable of correcting a single deletion in a permutation. In this paper, we construct several classes of permutation and multipermutation codes that are capable of correcting a burst deletion of length s ≥ 2, for both stable and unstable models. Efficient error decoders are provided to show the correctness of our constructions.

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) log4n + 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.

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. This paper provides 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. Our construction of binary robust positioning sequences 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 our constructions run in time cubic in sequence length or array dimensions.

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 identity of the specific item to any single server. Classic k-server PIR protocols work on replicated databases, i.e., each of the k servers stores a whole copy of the database. Recently, new PIR models were proposed with coding techniques arising from the distributed storage system. In these new models, each server only stores a fraction 1/s of the whole database, where s > 1 is the given rational number. The PIR array codes are recently proposed by Fazeli, Vardy, and Yaakobi to characterize the new models. The central problem in designing a PIR array code with m servers and the k-PIR property (which indicates that these m servers may emulate a classic k-server PIR protocol) is to maximize k/m, known as the virtual server rate. Our main contribution to this problem is twofold. First, for the case 12, a new upper bound on the rate of a PIR array code is presented. Besides, we also have some discussions on an asymptotically optimal construction by Blackburn and Etzion.

A class of low-power cooling (LPC) codes, to control simultaneously both the peak temperature and the average power consumption of interconnects, were 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) limit 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-1and 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 class of geometric orthogonal codes (GOCs) was introduced by Doty and Winslow (2016) for more robust macrobonding in DNA origami. They observed that GOCs are closely related to optical orthogonal codes (OOCs). It is possible for GOCs to have size greater than OOCs of corresponding parameters due to slightly more relaxed constraints on correlations. However, the existence of GOCs exceeding the size of optimal OOCs of corresponding parameters has never been demonstrated. This paper gives the first infinite family of GOCs of size greater than optimal OOCs.

The class of geometric orthogonal codes (GOCs) were introduced by Doty and Winslow (2016) for more robust macro-bonding in DNA origami. They observed that GOCs are closely related to optical orthogonal codes (OOCs). It is possible for GOCs to have size greater than OOCs of corresponding parameters due to slightly more relaxed constraints on correlations. However, the existence of GOCs exceeding the size of optimal OOCs of corresponding parameters have never been demonstrated. This paper gives the first infinite family of GOCs of size greater than optimal OOCs.

We construct permutation codes capable of correcting bursts of stable deletions. For correcting a single burst of exactly s stable deletions, our code has size sn!/((2s)!n)2, while the upper bound n!/s!(n - s + 1). We also construct permutation codes for the cases of single burst of up to s stable deletions, and up to b bursts of at most s stable deletions each.

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. First, we derive three different types of upper bounds which improve the Johnson-type bounds given by Cheeet al.for 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}^{m}w_{i}-2$or$2mw-2w$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.