Recent studies have shown that distributed storage systems can achieve significant space savings by adapting redundancy levels to varying disk failure rates. This adaptation is performed via code conversion, wherein data encoded under an initial code are transformed to data encoded under a final code. While this process is typically resource-intensive, convertible codes are designed to enable these transformations efficiently while preserving desirable decodability constraints such as repair degree, or the number of nodes accessed during node repair. In this work, we focus on the bandwidth cost of conversion, or the total amount of data transferred during the conversion process. We study fundamental limits on the bandwidth cost of conversion between systematic optimal-distance Locally Repairable Codes (LRCs). We restrict our focus to the global merge regime, in which multiple initial codewords are combined to form a single final codeword while preserving information locality. We focus on stable convertible codes, wherein the number of unchanged nodes is maximized during conversion. We generalize an information-theoretic approach for modeling code conversion to the LRC setting, and derive the first non-trivial lower bounds on the bandwidth cost of conversion in this regime. Notably, our bounds do not rely on any linearity assumptions. Consequently, we show that the constructions of Maturana and Rashmi are bandwidth-optimal across a broad range of parameters in the global merge regime.

The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication setting in which a sender transmits a codeword and the receiver observes K independent noisy versions of this codeword. In this work, we study the problem of efficient reconstruction when each of the $K$ outputs is corrupted by a $q$-ary discrete memoryless symmetric (DMS) substitution channel with substitution probability $p$. Focusing on Reed-Solomon (RS) codes, we adapt the Koetter-Vardy soft-decision decoding algorithm to obtain an efficient reconstruction algorithm. For sufficiently large blocklength and alphabet size, we derive an explicit rate threshold, depending only on $(p, K)$, such that the transmitted codeword can be reconstructed with arbitrarily small probability of error whenever the code rate $R$ lies below this threshold.

Constructing Reed-Solomon (RS) codes that can correct insertion and deletion (ins-del) errors has been the focus of several recent studies. However, efficient decoding algorithms for such codes have received less attention and remain a significant open problem. In this work, we take a first step toward addressing this problem by designing a decoding algorithm for the case of 2-dimensional RS codes that can correct deletions up to the half- Singleton bound and is optimal in terms of field operations.

The channel output entropy of a transmitted sequence is the entropy of the possible channel outputs, and similarly, the channel input entropy of a received sequence is the entropy of all possible transmitted sequences. The goal of this work is to study these entropy values for thek-deletion andk-insertion channels, where exactlyksymbols are deleted or inserted in the transmitted sequence, respectively. If all possible sequences are transmitted with the same probability, then studying the input and output entropies becomes equivalent. For both the 1-deletion and 1-insertion channels, it is shown that among all sequences with a fixed number of runs, the input entropy is minimized for sequences with a skewed distribution of run lengths, and it is maximized for sequences with a balanced distribution of run lengths. Among our results, we establish a conjecture by Atashpendar et al., which claims that for the 1-deletion channel, the input entropy is maximized by the alternating sequences among all binary sequences. This conjecture is also verified for the 2-deletion channel, where it is proved that sequences with a single run minimize the input entropy.

The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a scenario where the sender transmits a codeword from some codebook, and the receiver obtains$N$noisy outputs of the codeword. We study the problem of efficient reconstruction using$N$outputs that are corrupted by substitutions. Specifically, for the ubiquitous Reed-Solomon codes, we adapt the Koetter-Vardy soft-decoding algorithm, presenting a reconstruction algorithm capable of correcting beyond Johnson radius. Furthermore, the algorithm uses$\mathrm{O}(nN)$field operations, where$n$is the codeword length.

This paper considers a communication system where a source sends time-sensitive information to its destination via queues in tandem. We assume that the arrival process as well as the service process (of each server) are memoryless, and each of the servers has no buffer. For this setup, we develop a recursive framework to characterize the mean peak age of information (PAoI) under preemptive and non-preemptive policies with$N$servers having different service rates. For the preemptive case, the proposed framework also allows to obtain mean age of information (AoI).

We consider the repair scheme of Guruswami-Wootters for the Reed-Solomon code and ask: can we correctly repair a failed node in the presence of erroneous nodes? Equivalently, we consider the collection of downloaded traces as a code and investigate its code-distance properties. We propose three lower bounds on its minimum distance and study methods to efficiently correct errors close to these bounds.

We study a data-driven approach to the bee identification problem for DNA strands. The bee-identification problem, introduced by Tandon et al. (2019), requires one to identify M bees, each tagged by a unique barcode, via a set of M noisy measurements. Later, Chrisnata et al. (2022) extended the model to case where one observes N noisy measurements of each bee, and applied the model to address the unordered nature of DNA storage systems.In such systems, a unique address is typically prepended to each DNA data block to form a DNA strand, but the address may possibly be corrupted. While clustering is usually used to identify the address of a DNA strand, this requires ℳ2data comparisons (when ℳ is the number of reads). In contrast, the approach of Chrisnata et al. (2022) avoids data comparisons completely. In this work, we study an intermediate, data-driven approach to this identification task.For the binary erasure channel, we first show that we can almost surely correctly identify all DNA strands under certain mild assumptions. Then we propose a data-driven pruning procedure and demonstrate that on average the procedure uses only a fraction of ℳ2data comparisons. Specifically, for ℳ = 2nand erasure probability p, the expected number of data comparisons performed by the procedure is κℳ2, where ${\left( {\frac{{1 + 2p - {p^2}}}{2}} \right)^n} \leq \kappa \leq {\left( {\frac{{1 + p}}{2}} \right)^n}$.

In our work, we study the age of information (AoI) in a multi-source system where K sources transmit updates of their time-varying processes via a common-aggregator node to a destination node through a channel with packet delivery errors. We analyze AoI for an (α,β,ϵ0, ϵ1)-Gilbert-Elliot (GE) packet erasure channel with a round-robin scheduling policy. We employ maximum distance separable (MDS) scheme at the aggregator for encoding the multi-source updates. We characterize the mean AoI for the MDS coded system. Further, for large blocklengths, we show that the optimal coding rate that achieves maximum coding gain over the uncoded system is $1 - \mathcal{P} - \mathcal{O}(1)$, where $\mathcal{P} \triangleq \frac{\beta }{{\alpha + \beta }}{ \in _0} + \frac{\alpha }{{\alpha + \beta }}{ \in _1}$, and this maximum coding gain is $1 + \mathcal{P} - \mathcal{O}(1)$.

In this paper, we study the three-node Decode-and-Forward (D&F) relay network subject to random and burst packet erasures. The source wishes to transmit an infinite stream of packets to the destination via the relay. The three-node D&F relay network is constrained by a decoding delay of T packets, i.e., the packet transmitted by the source at time i must be decoded by the destination by time i + T . For the individual channels from source to relay and relay to destination, we assume a delay-constrained sliding-window (DCSW) based packet-erasure model that can be viewed as a tractable approximation to the commonly-accepted Gilbert-Elliot channel model. Under the model, any time-window of width w contains either up to a random erasures or else erasure burst of length at most b (≥ a). Thus the source-relay and relay-destination channels are modelled as (a1, b1, w1, T1) and (a2, b2, w2, T2) DCSW channels. We first derive an upper bound on the capacity of the three-node D&F relay network. We then show that the upper bound is tight for the parameter regime: max{b1, b2} | (T − b1− b2− max {a1, a2} + 1) by constructing streaming codes achieving the bound. The code construction requires field size linear in T , and has decoding complexity equivalent to that of decoding an MDS code.

The channel output entropy of a transmitted word is the entropy of the possible channel outputs and similarly the input entropy of a received word is the entropy of all possible transmitted words. The goal of this work is to study these entropy values for the k-deletion, k-insertion channel, where exactly k symbols are deleted, inserted in the transmitted word, respectively. If all possible words are transmitted with the same probability then studying the input and output entropies is equivalent. For both the 1-insertion and 1-deletion channels, it is proved that among all words with a fixed number of runs, the input entropy is minimized for words with a skewed distribution of their run lengths and it is maximized for words with a balanced distribution of their run lengths. Among our results, we establish a conjecture by Atashpendar et al. which claims that for the binary 1-deletion, the input entropy is maximized for the alternating words. For the 2-deletion channel, it is proved that constant words with a single run minimize the input entropy.