The Levenshtein sequence reconstruction problem studies the reconstruction of a transmitted sequence from multiple erroneous copies of it. A fundamental question in this field is to determine the minimum number of erroneous copies required to guarantee correct reconstruction of the original sequence. This problem is equivalent to determining the maximum possible intersection size of two error balls associated with the underlying channel. Existing research on the sequence reconstruction problem has largely focused on channels with a single type of error, such as insertions, deletions, or substitutions alone. However, relatively little is known for channels that involve a mixture of error types, for instance, channels allowing both deletions and substitutions. In this work, we study the sequence reconstruction problem for the single-deletion two-substitution channel, which allows one deletion and at most two substitutions applied to the transmitted sequence. Specifically, we prove that if two $q$-ary length-$n$ sequences have the Hamming distance $d\geq 2$, where $q\geq 2$ is any fixed integer, then the intersection size of their error balls under the single-deletion two-substitution channel is upper bounded by $(q^2-1)n^2-(3q^2+5q-5)n+O_q(1)$, where $O_q(1)$ is a constant independent from $n$ but dependent on $q$. Moreover, we show that this upper bound is tight up to an additive constant.

In this work, we study the sequence reconstruction problem for the single-deletion single-substitution channel, assuming that the transmitted sequence belongs to a$q$-ary code with minimum Hamming distance at least 2, where$q \geq 2$is any fixed integer. Specifically, we prove that for any two$q$-ary sequences of length$n$and with Hamming distance$d \geq 2$, the size of the intersection of their error balls is upper bounded by$2 q n-3 q-2-\delta_{q, 2}$, where$\delta_{i, j}$is the Kronecker delta. We also prove the tightness of this bound by constructing two sequences whose error ball intersection size achieves this bound.

In this paper, for any fixed integer$q > 2$, we construct q-ary codes correcting a burst of at most$t$deletions with redundancy$\log n+8$log log$n$+ o(log log$n) >+\gamma_{q,t}$bits and near-linear encoding/decoding complexity, where$n$is the message length and$\gamma_{q,t}$is a constant that only depends on$q$and$t$. In previous works there are constructions of such codes with redundancy$\log n+O$(log$q$log log n) bits or$\log n+O$($t$2log log n)$+O(t\log q)$. The redundancy of our new construction is independent of$q$and$t$in the second term.

In this paper, we construct non-binary, more specifically, q-ary, two-deletion correcting codes with redundancy 5 log n + O(log q log log n) bits and encoding complexity near-linear in n, where q > 2 is an even integer and n is the message length. The redundancy of our construction is log n bits higher than the best known explicit binary two-deletion codes (Guruswami et al, IEEE Trans. Inf. Theory 2021) and is the lowest in all known explicit non-binary two-deletion codes.

In this paper, we construct$q$-ary two-deletion correcting codes and burst-deletion correcting codes, where$q\geq 2$is an even integer. For two-deletion codes, our construction has redundancy$5\log n+O(\log q\log \log n)$and has encoding complexity near-linear in$n$, where$n$is the length of the message sequences. For burst-deletion codes, we first present a construction of binary codes with redundancy$\log n+9\log \log n+\gamma _{t}+o(\log \log n)$bits$(\gamma _{t}$is a constant that depends only on$t$) and capable of correcting a burst of at most$t$deletions, which improves the Lenz-Polyanskii Construction (ISIT 2020). Then we give a construction of$q$-ary codes with redundancy$\log n+(8\log q+9)\log \log n+\gamma _{t}+o(\log \log n)$bits and capable of correcting a burst of at most$t$deletions.

Advances in synthesis and sequencing technologies have made DNA macromolecules an attractive medium for digital information storage. Compared with the ex vivo method that stores data in a non-biological environment, there have been considerations and attempts to store data in living organisms, also known as the in vivo method or live DNA due to several magnificent advantages. Data stored in this medium is prone to errors arising from various mutations such as point mutations (when there is a change in a single nucleotide in DNA, i.e. deletion, insertion, or substitution) or chromosomal alterations (that change the structure of a segment of DNA, i.e. tandem duplication, inversion).In this paper, we provide error-correcting codes for errors caused by inversions, that reverse the order of a segment of DNA. In particular, we construct families of codes for correcting single inversion of a fixed length or variable length up to a given constant k with at most log n+Θ(1) redundant bits, where the redundancy matches the optimal value up to only a constant additive term. Moreover, our codes remain order-optimal, i.e. the redundancy is at most log n + o(log n), when k = o(log n). The redundancy can be further reduced when k ≪ 3.

In this paper, we present an explicit construction of list-decodable codes for single-deletion and single-substitution with list size two and redundancy 3log n+4, where n is the block length of the code. Our construction has lower redundancy than the best known explicit construction by Gabrys et al. (arXiv 2021), whose redundancy is 4log n + O(1).

We consider construction of deletion and substitution correcting codes with low redundancy and efficient encoding/ decoding. First, by simplifying the method of Simaet 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 Smagloyet 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.

In this paper, by applying the precoding technique in conjunction with the syndrome compression approach, we construct systematic$t$-deletion$s$-substitution correcting codes, where$t$and$s$are fixed positive integers. The redundancy of our construction is$(4t+3s)\log n+o(\log n)$for the binary case and$(4t+4s-1- \mathrm{L}\frac{2s-1}{q}\rfloor)\bar{\mathrm{l}}\text{og}_{q}n+o(\bar{\mathrm{l}}\text{og}_{q}n)$for the$q$-ary case, where$n$is the length of the codes and$q> 2$is a fixed prime power.11If$x$is a positive real number, then$\log_{q}\alpha$is the logarithm of$x$with base$q$; if$q=2$, we simply denote$\log x=\text{lo}\bar{\mathrm{g}}_{q}x$. We also construct binary t-deletion correcting codes (i.e.,$s=0$) with redundancy$(4t-1)\log n+o(\log n)$. The encoding/decoding complexities of all constructions are polynomial in$n$.

In this article, under a general cost function C, we present a dynamic programming (DP) method to obtain an optimal sequential deterministic quantizer (SDQ) for q-ary input discrete memoryless channel (DMC). The DP method has complexity O(q (N-M)2M), where N and M are the alphabet sizes of the DMC output and quantizer output, respectively. Then, starting from the quadrangle inequality, two techniques are applied to reduce the DP method's complexity. One technique makes use of the Shor-Moran-Aggarwal-Wilber-Klawe (SMAWK) algorithm and achieves complexity O(q (N-M) M). The other technique is much easier to be implemented and achieves complexity O(q (N2- M2)). We further derive a sufficient condition under which the optimal SDQ is optimal among all quantizers and the two techniques are applicable. This generalizes the results in the literature for binary-input DMC. Next, we show that the cost function of α-mutual information ( α-MI)-maximizing quantizer belongs to the category of C. We further prove that under a weaker condition than the sufficient condition we derived, the aforementioned two techniques are applicable to the design of α-MI-maximizing quantizer. Finally, we illustrate the particular application of our design method to practical pulse-amplitude modulation systems.

We design p-reconstructible μ-secure [n, k] erasure coding schemes (0 ≤ μ3/4.

The process of DNA-based data storage (DNA storage for short) can be mathematically modelled as a communication channel, termed DNA storage channel, whose inputs and outputs are sets of unordered sequences. To design error correcting codes for DNA storage channel, a new metric, termed the sequence-subset distance, is introduced, which generalizes the Hamming distance to a distance function defined between any two sets of unordered vectors and helps to establish a uniform framework to design error correcting codes for DNA storage channel. We further introduce a family of error correcting codes, referred to as sequence-subset codes, for DNA storage and show that the error-correcting ability of such codes is completely determined by their minimum distance. We derive some upper bounds on the size of the sequence-subset codes including a tight bound for a special case, a Singleton-like bound and a Plotkin-like bound. We also propose some constructions, including an optimal construction for that special case, which imply lower bounds on the size of such codes.

In this paper, we present a general framework of applying dynamic programming (DP) to the sequential deterministic quantization for discrete memoryless channels (DMCs) with pre-labelled outputs. The DP has complexity O(q(N -M)2M), where q, N, and M are alphabet sizes of the DMC input, DMC output, and the quantizer output, respectively. Then, starting from the quadrangle inequality (QI), we apply two techniques to reduce the DP's complexity. One technique makes use of the SMAWK algorithm with complexity O(q(N - M)M), while the other technique is much easier to be implemented and has complexity O(q(N2- M2)). Moreover, we give a sufficient condition on the channel transition probability, under which the two low-complexity techniques can be applied for designing quantizers that maximize the α-mutual information, which is a generalized objective function for channel quantization. This condition works for the general q-ary input case, including the previous work for q = 2 as a subcase.

We introduce a new metric, termed sequence-subset distance, and a new family of codes with respect to this new metric, termed sequence-subset codes, on the power set of the set of all sequences of the same length over a finite alphabet. This new metric and family of codes are motivated by the problem of designing error correcting codes for DNA-based data storage, which can be mathematically modelled as a communication channel whose inputs and outputs are sets of unordered sequences. We derive some upper bounds on the size of the sequence-subset codes including a tight bound for a special case and a Singleton-like bound, and present some constructions of such codes.

We prove that for any positive integers n and k such that n ≥ k ≥ 1, there exists an [n, k] generalized Reed-Solomon (GRS) code that has a sparsest and balanced generator matrix (SBGM) over any finite field of size q ≥ n+[(k(k-1))/n], where sparsest means that each row of the generator matrix has the least possible number of nonzeros, while balanced means that the number of nonzeros in any two columns differ by at most one. Previous work by Dau et al (ISIT'13) showed that there always exists an MDS code that has an SBGM over any finite field of size q ≥ \binomn-1k-1 I, and Halbawi et al (ISIT'16, ITW'16) showed that there exists a cyclic Reed-Solomon code (i.e., n=q-1) with an SBGM for any prime power q. Hence, this work extends both of the previous results.

Codes with locality, also known as locally repairable codes (LRC), are designed for distributed storage systems (DSS) to reduce the disk I/O complexity for node repair. A linear code is said to have (r, δ)-locality if each code symbol is contained in a local code of length ≤ r + δ - 1 and minimum distance ≥ δ. For such codes, a generalized Singleton bound of the minimum distance was proven by Prakash et al (ISIT'12).In this paper, we consider the problem of constructing optimal codes with (r, δ)-locality. Specifically, we present three classes of linear codes that have (r, δ)-locality and whose minimum distance achieves the generalized Singleton bound. For δ = 2, we provide a combinatorial description of the largest possible d such that there exists a linear code with (r, δ)-locality and minimum distance d.

We consider the locally repairable codes (LRCs), aiming at sequentially recovering multiple erasures; in particular, we propose and study the so-called (n, k, r, t)-sequential LRCs (SLRC) as an [n, k] linear code, where any t' (≤ t) erasures can be sequentially recovered, each by r (2 ≤ r <; k) other code symbols. Here, sequential recovering means that the erased symbols are recovered one by one, and an already recovered symbol can be used to recover the remaining erased symbols. This important recovering method, in contrast with the extensively studied parallel recovering, is currently far from being thoroughly understood; more specifically, there are to date no codes constructed for arbitrary t ≥ 3 erasures and bounds to evaluate the performance of such codes. We first derive a tight upper bound on the code rate of the (n, k, r, t)-SLRC for t = 3 and r ≥ 2. We then propose two constructions of binary (n, k, r, t)-SLRCs for general r, t ≥ 2 (existing constructions only deal with t ≤7 erasures). The first construction generalizes the method of direct product construction. The second construction is based on the resolvable configurations and yields SLRCs for any r ≥ 2 odd t ≥ 3. For both constructions, the rates are optimal for t ∈ {2, 3} and are higher than most of the existing LRC families for arbitrary t ≥ 4.

Locally repairable codes (LRC) for distributed storage allow two approaches to locally repair multiple failed nodes: 1) parallel approach, by which each newcomer access a set of r live nodes (r is the repair locality) to download data and recover the lost packet; and 2) sequential approach, by which the newcomers are properly ordered and each newcomer access a set of r other nodes, which can be either a live node or a newcomer ordered before it. An [n, k] linear code with locality r that allows local repair for up to t failed nodes by sequential approach is called an (n, k, r, t)-exact locally repairable code (ELRC). In this paper, we present a family of binary codes which is equivalent to the direct product of m copies of the [r+1, r] singleparity-check code. We prove that such codes are (n, k, r, t)-ELRC with n = (r + 1)m, k = rmand t = 2m- 1, which implies that they permit local repair for up to 2m- 1 erasures by sequential approach. Our result shows that the sequential approach has much bigger advantage than parallel approach.

We consider the locality of encoding and decoding operations in distributed storage systems (DSS), and propose a new class of codes, called locally encodable and decodable codes (LEDC), that provides a higher degree of operational locality compared to currently known codes. For a given locality structure, we derive an upper bound on the global distance and demonstrate the existence of an optimal LEDC for sufficiently large field size. In addition, we also construct two families of optimal LEDC for fields with size linear in code length.

The MDS property (aka the k-out-of-n property) requires that if a file is split into several symbols and subsequently encoded into n coded symbols, each being stored in one storage node of a distributed storage system (DSS), then an user can recover the file by accessing any k nodes. We study the so-called p-decodable μ-secure erasure coding scheme (1 ≤ p ≤ k - μ, 0 ≤ μ <; k, p|(k - μ)), which satisfies the MDS property and the following additional properties: (P1) strongly secure up to a threshold: an adversary which eavesdrops at most μ storage nodes gains no information (in Shannon's sense) about the stored file, (P2) partially decodable: a legitimate user can recover a subset of p file symbols by accessing some μ + p storage nodes. (P2) partially decodable: a legitimate user can recover a subset of p file symbols by accessing some μ + p storage nodes. The scheme is perfectly p-decodable μ-secure if it satisfies the following additional property: (P3) weakly secure up to a threshold: an adversary which eavesdrops more than μ but less than μ + p storage nodes cannot reconstruct any part of the file. Most of the related work in the literature only focused on the case p = k - μ. In other words, no partial decodability is provided: an user cannot retrieve any part of the file by accessing less than k nodes. For our more general code, Property (P2) guarantees partial decodability: once the user accesses p more nodes than the strong security threshold μ, it can start to decode some subset of p file symbols. We provide an explicit construction of p-decodable μ-secure coding schemes over small fields for all μ and p. That construction also produces perfect p-decodable μ-secure schemes over small fields when p = 1 (for every μ), and when μ = 0, 1 (for every p). We establish that perfect schemes exist over sufficiently large fields for almost all μ and p.

We consider a simple multiple access network (SMAN), where k sources of unit rates transmit their data to a common sink via n relays. Each relay is connected to the sink and to certain sources. A coding scheme (for the relays) is weakly secure if a passive adversary who eavesdrops on less than k relay-sink links cannot reconstruct the data from each source. We show that there exists a weakly secure maximum distance separable (MDS) coding scheme for the relays if and only if every subset of ℓ relays must be collectively connected to at least ℓ+1 sources, for all 0 <; ℓ <; k. Moreover, we prove that this condition can be verified in polynomial time in n and k. Finally, given a SMAN satisfying the aforementioned condition, we provide another polynomial time algorithm to trim the network until it has a sparsest set of source-relay links that still supports a weakly secure MDS coding scheme.

We investigate a simple multiple access network (SMAN) where k independent sources of unit rates multicast their information to a set of sinks, via n commonly shared relays. All links are assumed to have unit capacity. Given such a SMAN, a coding scheme for the relays is called optimal if each sink can retrieve all information from the sources under at most ⌊n-k+1/2⌋ node/link errors. We study the problem of designing the sparsest SMAN, i.e., the SMAN that has the least number of edges, that supports an optimal coding scheme for the relays. Additionally, the SMAN must satisfy either of the following constraints: 1) Connection Constraint: Each relay can be connected only to a given subset of sources or 2) Balance Constraint: Each relay must be connected to approximately the same number of sources. We provide two polynomial time algorithms to identify the cases where such a SMAN exists together with its optimal coding scheme designed over sufficiently large fields. One algorithm is based on a nontrivial modification of the well-known Gale-Ryser algorithm, whereas the other is based on a novel generalization of the famous Hall's marriage theorem. We also propose a combinatorial approach to construct optimal coding schemes over small fields and settle the problem for a special case.

In wireless networks, getting the global knowledge of channel state information (CSI, e.g., channel gain or link loss probability) is always beneficial for the nodes to optimize the network design. However, the node usually only has the local CSI between itself and other nodes, and lacks the CSI between any pair of other nodes. To enable all the nodes to get the global CSI, in this paper, we propose a network-coded third-party information exchange scheme, with an emphasis on minimizing the total transmission cost for ( ) exchanging the CSI among the nodes. We show that for a network of N nodes, if and only if any k nodes (1 ≤ k <; N) send at least (2 : k) packets, a feasible solution exists for third-party information exchange. Formulating the problem of feasible and optimal solutions as an integer linear programming (ILP) problem, we compute the optimal number of packets that must be transmitted by every node. Guided by the necessary and sufficient condition, we construct two practical transmission schemes: fair load (FL) scheme and proportional load (PL) scheme. A deterministic encoding strategy based on XORs coding over GF(2) is further designed to guarantee that with FL or PL scheme, each node finally can decode the complete packets. It is shown that in two specific networks, these two schemes are optimal, achieving the minimum transmission cost. In more general networks, simulation results show that PL is still close to optimal with a high probability. Finally, a distributed transmission protocol is developed, which allows FL and PL schemes to be operated in a distributed and hence scalable manner.

We study the existence over small fields of Maximum Distance Separable (MDS) codes with generator matrices having specified supports (i.e. having specified locations of zero entries). This problem unifies and simplifies the problems posed in recent works of Yan and Sprintson (NetCod'13) on weakly secure cooperative data exchange, of Halbawi et al. (arxiv'13) on distributed Reed-Solomon codes for simple multiple access networks, and of Dau et al. (ISIT'13) on MDS codes with balanced and sparse generator matrices.We conjecture that there exist such [n, k]qMDS codes as long as q ≥ n + k - 1, if the specified supports of the generator matrices satisfy the so-called MDS condition, which can be verified in polynomial time. We propose a combinatorial approach to tackle the conjecture, and prove that the conjecture holds for a special case when the sets of zero coordinates of rows of the generator matrix share with each other (pairwise) at most one common element. Based on our numerical result, the conjecture is also verified for all k ≤ 7. Our approach is based on a novel generalization of the well-known Hall's marriage theorem, which allows (overlapping) multiple representatives instead of a single representative for each subset.

A passive adversary can eavesdrop stored content or downloaded content of some storage nodes, in order to learn illegally about the file stored across a distributed storage system (DSS). Previous work in the literature focuses on code constructions that trade storage capacity for perfect security. In other words, by decreasing the amount of original data that it can store, the system can guarantee that the adversary, which eavesdrops up to a certain number of storage nodes, obtains no information (in Shannon's sense) about the original data. In this work we introduce the concept of block security for DSS and investigate minimum bandwidth regenerating (MBR) codes that are block secure against adversaries of varied eavesdropping strengths. Such MBR codes guarantee that no information about any group of original data units up to a certain size is revealed, without sacrificing the storage capacity of the system. The size of such secure groups varies according to the number of nodes that the adversary can eavesdrop. We show that code constructions based on Cauchy matrices provide block security. The opposite conclusion is drawn for codes based on Vandermonde matrices.

Linear erasure codes with local repairability are desirable for distributed data storage systems. An [n, k, d] linear code having all-symbol (r, δ)-locality, denoted as (r, δ)a, is considered optimal if it has the actual highest minimum distance of any code of the given parameters n, k, r and δ. A minimum distance bound is given in [10]. The existing results on the existence and the construction of optimal (r, δ)alinear codes are limited to only two small regions within this special case, namely, i) m = 0 and ii) m ≥ (v+δ-1) > (δ-1) and δ = 2, where m = n mod (r+δ-1) and v = k mod r. This paper investigates the properties and existence conditions for optimal (r, δ)alinear codes with general r and δ. First, a structure theorem is derived for general optimal (r, δ)acodes which helps illuminate some of their structure properties. Next, the entire problem space with arbitrary n, k, r and δ is divided into eight different cases (regions) with regard to the specific relations of these parameters. For two cases, it is rigorously proved that no (r, δ)alinear code can achieve the minimum distance bound in [10]. For four other cases the optimal (r, δ)acodes are shown to exist over a field of size q ≥ (k-1n), deterministic constructions are proposed. Our new constructive algorithms not only cover more cases, but for the same cases where previous algorithms exist, the new constructions require a smaller field, which translates to potentially lower computational complexity. Our findings substantially enriches the knowledge on optimal (r, δ)alinear codes, leaving only two cases in which the construction of optimal codes are not yet known.

We show that given n and k, for q sufficiently large, there always exists an [n, k]qMDS code that has a generator matrix G satisfying the following two conditions: (C1) Sparsest: each row of G has Hamming weight n - k + 1; (C2) Balanced: Hamming weights of the columns of G differ from each other by at most one.

The encoding complexity of network coding for single multicast networks has been intensively studied from several aspects: e.g., the time complexity, the required number of encoding links, and the required field size for a linear code solution. However, these issues as well as the solvability are less understood for networks with multiple multicast sessions. Recently, Wang and Shroff showed that the solvability of networks with two unit-rate multicast sessions (2-URMS) can be decided in polynomial time . In this paper, we prove that for the 2-URMS networks: 1) the solvability can be determined with time O(|E|); 2) a solution can be constructed with time O(|E|); 3) an optimal solution can be obtained in polynomial time; 4) the number of encoding links required to achieve a solution is upper-bounded by max{3,2N - 2}; and 5) the field size required to achieve a linear solution is upper-bounded by max{2, ⌊√{2N-7/4}+1/2⌋}, where |E| is the number of links and N is the number of sinks of the underlying network. Both bounds are shown to be tight.

In this paper, we consider the problem of minimizing the total transmission cost for exchanging channel state information. We proposed a network coded cooperative data exchange scheme, such that the total transmission cost is minimized while each client can decode all the channel information held by all other clients. In this paper, we first derive a necessary and sufficient condition for a feasible transmission. Based on the derived condition, there exists a feasible code design to guarantee that each client can decode the complete information. We further formulate the problem of minimizing the total transmission cost as an integer linear programming. Finally, we discuss the probability that each client can decode the complete information with distributed random linear network coding.

We consider a directed acyclic network with two source-sink pairs {s1, t1} and {s2, t2}. The source s1wishes to communicate a message X1to the sink t1and the source s2wishes to communicate two messages X2and X3to the sink t2, where Xi, i = 1,2,3, are independent random variables of unit rate. We give a simple characterization for linear solvability of such networks under the condition that the minimum cut from {s1, s2} to t2equals 3. We develop a region decomposition method for proving this result, which we believe can be an effective approach for non-multicast network coding problem.