In large-scale distributed storage systems, erasure coding is employed to ensure reliability against disk failures. Recent work by Kadekodi et al. demonstrates that adapting code parameters to varying disk failure rates can lead to significant storage savings without compromising reliability. Such adaptations, known ascode conversions, motivate the design ofconvertible codes, which enable efficient transformations between codes of different parameters. In this work, we study the setting in which λ codewords of an initial [nI=kI+rI,kI] MDS code are merged into a single codeword of a final [nF= λkI+rF,kF= λkI] MDS code. We begin by presenting three constructions that achieve optimalaccess cost, defined as the total number of disks accessed during the conversion process. The first two constructions apply when λ ≤rIand impose specific divisibility conditions onrIand the field sizeq. These schemes minimize both the per-symbol and the overall access cost. The third construction, which builds on a prior scheme by Kong, achieves minimal access cost while supporting arbitrary parameter regimes. All three constructions require field sizes that are linear in the final code length, and notably, the third construction achieves a field size that matches the lower bound implied by the MDS conjecture in almost all cases. In addition, we propose a construction that optimizes thebandwidth cost, defined as the total number of symbols transmitted during conversion. This scheme is a refinement of Maturana and Rashmi’s bandwidth-optimal construction based on the piggybacking framework, and achieves reduced sub-packetization.The code will be available at https://github.com/ZhilongNiu/SDMoMFE.

In large-scale distributed storage systems, erasure coding provides reliability against disk failures. Recent work by Kadekodi et al. demonstrates that adapting code parameters to varying disk failure rates can lead to storage savings, without compromising reliability. During such adaptations (also called code conversions), data encoded with multiple codewords of an initial [$n^{I}, k^{I}$] code are transformed into multiple codewords of a final$\left[n^{F}, k^{F}\right]$code. The convertible codes framework aims to design initial and final codes to enable resource-efficient conversions. In this paper, we study the scenario where$\lambda \geq 2$codewords of an initial$\left[n^{I}=k^{I}+r^{I}, k^{I}\right]$MDS code are merged into a single codeword of a final$\left[n^{F}=\lambda k^{I}+r^{F}, k^{F}=\lambda k^{I}\right]$MDS code. Some initial code symbols are retained in the final codeword, while others are newly generated. The access cost is the total number of symbols read or written during the conversion procedure to produce new symbols. In this paper, we present three convertible code constructions. The first two require$\lambda \leq r^{I}$and impose certain divisibility conditions on$r^{I}$and the field size$q$. However, they minimize the access cost incurred for generating each new symbol individually and for all symbols cumulatively. The third construction, a modification of an earlier construction by Kong, minimizes the cumulative access cost and works for all parameters. All the code constructions require field sizes linear in the block length of the final code and achieve the smallest known field sizes across MDS convertible codes in the literature.

Streaming codes are packet-level codes designed to ensure the timely recovery of lost packets. This paper focuses on streaming codes for multi-hop relay networks that guarantee the recovery of message packets within a delay of$\tau$time slots, even when a burst erasure affecting at most$b$packets occurs on each link. We first present a straightforward upper bound on the rate of burst-erasure-correcting streaming codes for multi-hop relay networks. The main contribution of this paper is a coding scheme that achieves rates arbitrarily close to this rate upper bound as the message size increases.

We study burst erasure correcting streaming codes for three-node relay networks, where there is a source-relay link and a relay-destination link. These codes guarantee that all message packets are recovered within a delay of$\tau $time slots, given that a single burst erasure of length at most b packets occurs in both links. Leveraging previously known techniques in the streaming code literature, we first provide a simple upper bound on the rate of burst erasure correcting streaming codes for three-node relay networks. Our main result is a coding scheme that achieves rates arbitrarily close to the rate upper bound, as message size increases.

We study burst erasure correcting streaming codes for three-node relay networks, where there is a source-relay link and a relay-destination link. These codes guarantee that all message packets are recovered within a delay of$\tau$time slots, given that a single burst erasure of length at most$b$packets occurs in both links. Leveraging previously known techniques in the streaming code literature, we first provide a simple upper bound on the rate of burst erasure correcting streaming codes for three-node relay networks. Our main result is a coding scheme that achieves rates arbitrarily close to the rate upper bound as message size increases.

Streaming codes are a class of packet-level erasure codes that ensure packet recovery over a sliding window channel which allows either a burst erasure of size$b$or$a$random erasures within any window of size$(\tau +1)$time units, under a strict decoding-delay constraint$\tau $. The field size over which streaming codes are constructed is an important factor in determining the implementation complexity. The best-known explicit rate-optimal streaming code, which covers all$\{a,b,\tau \}$parameter choices, requires a field size of$q^{2}$, where$q \ge \tau +b-a$is a prime power. In this work, we present an explicit rate-optimal streaming code over a field of size$q^{2}$, for prime power$q \ge \tau $. This is the smallest known field size for an explicit rate-optimal construction that takes into account all$\{a,b,\tau \}$parameters. We achieve this by modifying the non-explicit code construction due to Krishnan et al., without changing the field size. We also present a generalization of our construction, which results in streaming codes over further smaller fields by trading off code rate.

For a convolutional code in the presence of a symbol erasure channel, the information debt I(t) at time t provides a measure of the number of additional code symbols required to recover all message symbols up to time t. Information-debt-optimal streaming (iDOS) codes are convolutional codes which allow for the recovery of all message symbols up to t whenever I(t) turns zero under the following conditions; (i) information debt can be non-zero for at most τ consecutive time slots and (ii) information debt never increases beyond a particular threshold. The existence of periodically-time-varying iDOS codes are known for all parameters. In this paper, we address the problem of constructing explicit, time-invariant iDOS codes. We present an explicit time-invariant construction of iDOS codes for the unit memory (m = 1) case. It is also shown that a construction method for convolutional codes due to Almeida et al. leads to explicit time-invariant iDOS codes for all parameters. However, this general construction requires a larger field size than the first construction for the m = 1 case.

This paper presents an explicit construction of a class of optimal-access, minimum storage regenerating (MSR) codes, for small values of the number$d$of helper nodes. The construction is valid for any parameter set$(n,k,d)$with$d \in \{k+1, k+2, k+3\}$and employs a finite field$\mathbb {F}_{q}$of size$q=O(n)$. We will refer to the constructed codes as$\text {Small-}\mathsf {d}$MSR codes. The sub-packetization level$\alpha $is given by$\alpha = s^{{\lceil \frac {n}{s}\rceil }}$, where$s=d-k+1$. By an earlier result on the sub-packetization level for optimal-access MSR codes, this is the smallest value possible.

In the context of an (n,k,m) convolutional code where k is the number of message symbols, n the number of code symbols and m the memory, Martinian [1] introduced the concept of information debt whose value at time t is the number of additional coded symbols needed to decode all prior message symbols. The same paper shows the existence of (n,k,m) convolutional codes that can recover all prior message symbols whenever the symbol-erasure pattern is such that the maximum time interval τ between successive returns to zero of the information debt function is at most m. The parameter τ also represents the worst-case delay in decoding a message symbol. In the present paper, we study (n,k,m) convolutional codes that possess the analogous property for the case τ > m whenever it is possible to do so. We will refer to such codes as information-debt-optimal streaming (iDOS) codes. We prove the existence of periodically time-varying iDOS codes for all possible {n,k,m,τ} parameters. We also show that m-MDS codes and Maximum Distance Profile convolutional codes are iDOS codes for certain parameter ranges. As a by-product of our existence result, the minimum memory needed for a particular class of streaming codes studied earlier in the literature, is determined.

We present two lower bounds on sub-packetization level$\alpha $of MSR codes with parameters$(n, k, d=n-1, \alpha )$where$n$is the block length,$d$is the number of helper nodes contacted during single-node repair,$\alpha $the sub-packetization level and$k\alpha $the scalar dimension. The first bound we present is for any MSR code and is given by$\alpha \ge e^{\frac {(k-1)(r-1)}{2r^{2}}}$. The second bound we present is for the case of optimal-access MSR codes and the bound is given by$\alpha \ge \min \left\{{ r^{\frac {n-1}{r}}, r^{k-1} }\right\}$. There exist optimal-access MSR constructions that achieve the second sub-packetization level bound with an equality making this bound tight. We also prove that for an optimal-access MSR code to have optimal sub-packetization level under the constraint that the$\beta $scalar symbol indices we access from a given helper node is dependent only on the index of the failed node, it is necessary that the support of the parity-check matrix be the same as the support structure of the existing MSR constructions in literature such as the Clay code.

Streaming codes represent a packet-level FEC scheme for achieving reliable, low-latency communication. In the literature on streaming codes, the commonly-assumed Gilbert-Elliott channel model, is replaced by a more tractable, delay-constrained, sliding-window (DCSW) channel model that can introduce either random or burst erasures. The known streaming codes that are rate optimal over the DCSW channel model are constructed by diagonally embedding a scalar block code across successive packets. These code constructions have field size that is quadratic in the delay parameter$\tau$and have a somewhat complex structure with an involved decoding procedure. This led to the introduction of simple streaming (SS) codes in which diagonal embedding is replaced by staggered-diagonal embedding (SDE). The SDE approach reduces the impact of a burst of erasures and makes it possible to construct near-rate-optimal streaming codes using Maximum Distance Separable (MDS) code having linear field size. The present paper takes this development one step further, by retaining the staggered-diagonal feature, but permitting the placement of more than one code symbol from a given scalar codeword within each packet. These generalized, simple streaming codes allow us to improve upon the rate of SS codes, while retaining the simplicity of working with MDS codes. We characterize the maximum code rate of streaming codes under a constraint on the number of contiguous packets over which symbols of the underlying scalar code are dispersed. Such a constraint leads to simplified code construction and reduced-complexity decoding.

Streaming codes are a class of packet-level erasure codes that ensure packet recovery over a sliding window channel which allows either a burst erasure of size$b$or$a$random erasures within any window of size ($\tau+1$) time units, under a strict decoding-delay constraint$\tau$. The field size over which streaming codes are constructed is an important factor determining the complexity of implementation. The best known explicit rate-optimal streaming code requires a field size of$q^{2}$where$q\geq\tau+b-a$is a prime power. In this work, we present an explicit rate-optimal streaming code, for all possible$\{a, b,\tau\}$parameters, over a field of size$q^{2}$for prime power$q\geq \tau$. This is the smallest-known field size of a general explicit rate-optimal construction that covers all$\{a, b, \tau\}$parameter sets. We achieve this by modifying the non-explicit code construction due to Krishnan et al. to make it explicit, without change in field size.

Streaming codes are a class of packet-level erasure codes that are designed with the goal of ensuring recovery in low-latency fashion, of erased packets over a communication network. It is well-known in the streaming code literature, that diagonally embedding codewords of a $[{\tau}+1, {\tau}+1-{a}]$ Maximum Distance Separable (MDS) code within the packet stream, leads to rate-optimal streaming codes capable of recovering from a arbitrary packet erasures, under a strict decoding delay constraint ${\tau}$. Thus MDS codes are geared towards the efficient handling of the worst-case scenario corresponding to the occurrence of a erasures. In the present paper, we have an increased focus on the efficient handling of the most-frequent erasure patterns. We study streaming codes which in addition to recovering from ${a}\gt 1$ arbitrary packet erasures under a decoding delay ${\tau}$, have the ability to handle the more common occurrence of a single-packet erasure, while incurring smaller delay ${r}\lt {\tau}$. We term these codes as $({a},{\tau},{r})$ locally recoverable streaming codes (LRSCs), since our single-erasure recovery requirement is similar to the requirement of locality in a coded distributed storage system. We characterize the maximum possible rate of an LRSC by presenting rate-optimal constructions for all possible parameters $\{{a},{\tau},{r}\}$. Although the rate-optimal LRSC construction provided in this paper requires large field size, the construction is explicit. It is also shown that our (${a},{\tau}={a}({r}+1)-1,{r})$ LRSC construction provides the additional guarantee of recovery from the erasure of ${h}, 1\leq {h}\leq {a}$, packets, with delay ${h}({r}+1)-1$. The construction thus offers graceful degradation in decoding delay with increasing number of erasures. A full version of this paper is accessible at [1].

The Gilbert-Elliot (GE) channel is a commonlyaccepted model for packet erasures in networks. Streaming codes are a class of packet-level erasure codes designed to provide reliable communication over the GE channel. The design of a streaming code may be viewed as a two-step process. In the first, a more tractable, delay-constrained sliding window (DCSW) channel model is considered as a proxy to the GE channel. The streaming code is then designed to reliably recover from all erasures introduced by the DCSW channel model. Simulation is typically used to evaluate the performance of the streaming code over the original GE channel, as analytic performance evaluation is challenging. In the present paper, we take an important first step towards analytical performance evaluation. Recognizing that most, efficient constructions of a streaming code are based on the diagonal embedding or horizontal embedding of scalar block codes within a packet stream, this paper provides upper and lower bounds on the block-erasure probability of the underlying scalar block code when operated over the GE channel.A full version of this paper is accessible at [1].

An (a, b, τ) streaming code is a packet-level erasure code that can recover under a strict delay constraint of τ time units, from either a burst of b erasures or else of a random erasures, occurring within a sliding window of time duration w. While rate-optimal constructions of such streaming codes are available for all parameters {a, b, τ, w} in the literature, they require in most instances, a quadratic, O(τ2) field size. In this work, we make further progress towards field size reduction and present rate-optimal O(τ) field size streaming codes for two regimes: (i) gcd(b, τ + 1 - a) ≥ a (ii) τ + 1 a + b and b mod a ϵ 0, a - 1.

In [1], Arıkan introduced polar codes and proved that they are capacity achieving over symmetric binary memoryless channels under successive cancellation decoding (SCD). However, the metric used in the SCD algorithm does not incorporate knowledge of future frozen bits. In this paper we take a fresh look at the SCD algorithm and propose two decoding algorithms a) successive cancellation with back-tracking (SC-BT) and successive cancellation with look ahead (SC-LA). Both algorithms try to improve the performance using a memory of size O(N). We also extend the SC-LA algorithm to work with successive cancellation list decoding (SCLD).

This paper presents the construction of an explicit, optimal-access, high-rate MSR code for any (n, k, d=k+ 1, k+2, k+3) parameters over the finite field \mathbbFQ having sub-packetization α = q[n/(q)], where q=d-k+1 and Q=O(n). The sub-packetization of the current construction meets the lower bound proven in a recent work by Balaji et al. in [1]. To our understanding the codes presented in this paper are the first explicit constructions of MSR codes with having optimal sub-packetization, optimal access and small field size.

This paper presents an explicit construction for an ((n = 2qt, k = 2q{t-1), d = n - (q + 1)), (α = q(2q)t-1,β = α/q)) regenerating code over a field Fqoperating at the Minimum Storage Regeneration (MSR) point. The MSR code can be constructed to have rate k/n as close to 1 as desired, sub-packetization level α ≤ rn/rfor r = (n - k), field size Q no larger than n and where all code symbols can be repaired with the same minimum data download. This is the first-known construction of such an MSR code for d <; (n - 1).

The notion of a Private Information Retrieval (PIR) code was recently introduced by Fazeli, Vardy and Yaakobi [1] who showed that this class of codes permit PIR at reduced levels of storage overhead in comparison with rephcated-server PIR. In the present paper, the construction of an (n, k) τ-server binary linear PIR code having parameters n =ℓΣi=0(mi), k = (mi) and τ = 2ℓfor any integer m ≥ ℓ ≥ 0 is presented. These codes are obtained through homogeneous-polynomial evaluation and correspond to the binary. Projective Reed Muller (PRM) code. The construction can be extended to yield PIR codes for any τ = ∊ {2ℓ, 2ℓ− 1 | ℓ ∊ Z, ℓ ≥ 0} and any value of k, through a combination of single-symbol puncturing and shortening of the PRM code. Each of these code constructions above, have smaller storage overhead in comparison with known short block length codes in [1]. For the particular case of τ = 3,4, we show that the codes constructed here are optimal, systematic PIR codes by providing an improved lower bound on the block length n{k, τ) of a systematic PIR code. It follows from a result by Vardy and Yaakobi [2], that these codes also yield optimal, systematic primitive multi-set {n, k, τ)Bbatch codes for τ = 3,4. The PIR code constructions presented here also yield upper bounds on the generahzed Hamming weights of binary PRM codes.