P. Vijay Kumar

Streaming codes are codes designed to ensure erased packet recovery within a decoding-delay deadline. In streaming code literature, a sliding-window (SW) channel model is considered called the (a, b,w)-SW channel model. In the (a, b,w)-SW channel, within any window of w time slots, either a burst of ≤ b consecutive packets, or else ≤ a packets at random can be erased. An (a, b,w, ≤ ) streaming code is capable of recovering messages under a decoding-delay of τ time slots, from any erasure pattern produced by the (a, b,w)-SW channel. For any given (a, b,w)-SW channel, the minimum delay with which the maximum rate possible over this channel can be achieved is τ = w − 1. Rate-optimal constructions of streaming codes for parameters of the form (a, b,w, τ = w − 1) are known, and these constructions require a field size that is quadratic in w in general. In this paper, we show that is possible to construct linear field size streaming codes for all {a, b,w} parameters, by sacrificing a little on either delay or rate. Moreover, we characterize the existence of binary, rate-optimal (a, b,w, τ = w−1) streaming codes constructed via the popular technique of diagonal embedding. Further, under a less-stringent decoding-delay requirement of τ = (w+b−a−1), it is shown that binary, rate-optimal streaming codes can be constructed for certain parameters. Streaming codes for a more general class of SW channels that allow unerased packets within a burst erasure are also investigated.

Global Navigation Satellite Systems (GNSS) employ low-correlation sequences, termed as spreading codes, to distinguish between the signals transmitted by the different satellites. The spreading codes commonly employed have period that is a multiple of 1023, as the fundamental frequency associated with the navigation signals generated onboard all of these systems is 10.23 MHz, derived using highly-stable atomic clocks. The principal contribution of the paper is the construction of a family ${\mathcal{ J}}_{{\text {NAV}}}$ , of low-correlation, binary sequences having period 10230, derived by interleaving a selected set of $5 {\textstyle \mathbb {Z}_{4}}$ -Linear sequences of period 2046 followed by flipping or complementing, a subset of the interleaved sequences. Sequence selection is based on the value of an exponential sum over a Galois ring and interleaving is carried out using the Chinese Remainder Theorem. The period 10230 is of particular interest, as it is the period of the spreading codes employed by major GNSS currently in operation. The ${\mathcal{ J}}_{{\text {NAV}}}$ spreading code family turns in competitive performance when compared to existing designs including a 4.5 dB improvement in worst-case, even-correlation properties. Additional techniques are employed to ensure that Family ${\mathcal{ J}}_{{\text {NAV}}}$ has other desirable attributes of a GNSS spreading code such as low values of odd-correlation, an orthogonality property and a simple, shift-register-based implementation. The construction is shown to be a special instance of a general select, interleave and flip approach to construction that generates families of balanced, low-correlation interleaved ${\textstyle \mathbb {Z}_{4}}$ -linear sequences having period $10(2^{m}-1)$ for $m=2 \pmod {4}$ and $14(2^{m}-1)$ for $m=2,4 \pmod {6}$ . By replacing the constituent ${\textstyle \mathbb {Z}_{4}}$ -linear sequences with Family ${\mathcal{ A}}$ quaternary sequences, the same approach can be used to construct two low-correlation, interleaved quaternary sequence families having period $5(2^{m}-1)$ with $m=2 \pmod {4}$ and $7(2^{m}-1)$ with $m=2,4 \pmod {6}$ , respectively.

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.

In distributed data storage, information pertaining to a given data file is stored across multiple storage units or nodes in redundant fashion to protect against the principal concern, namely, the possibility of data loss arising from the failure of individual nodes. The simplest form of such protection is replication. The explosive growth in the amount of data generated on a daily basis brought up a second major concern, namely minimization of the overhead associated with such redundant storage. This concern led to the adoption by the storage industry of erasure-recovery codes such as Reed-Solomon (RS) codes and more generally, maximum distance separable codes, as these codes offer the lowest-possible storage overhead for a given level of reliability. In the setting of a large data center, where the amount of stored data can run into several exabytes, a third concern arises, namely the need for efficient recovery from a commonplace occurrence, the failure of a single storage unit. One measure of efficiency in node repair is how small one can make the amount of data download needed to repair a failed unit, termed the repair bandwidth. This was the subject of the seminal paper by Dimakis et al. [50] in which an entirely new class of codes called regenerating codes was introduced, that within a certain repair framework, had the minimum-possible repair bandwidth. A second measure relates to the number of helper nodes contacted for node repair, termed the repair degree. A low repair degree is desirable as this means that a smaller number of nodes are impacted by the failure of a given node. The landmark paper by Gopalan et al. [72] focuses on this second measure, leading to the development of the theory of locally recoverable codes. The two events also led to the creation of a third class of codes known as locally regenerating codes, where the aim is to simultaneously achieve reduced repair bandwidth and low repair degree. Research in a different direction led researchers to take a fresh look at the challenge of efficient RS-code repair, and led to the identification of improved repair schemes for RS codes that have significantly reduced repair bandwidth. This monograph introduces the reader to these different approaches towards efficient node repair and presents many of the fundamental bounds and code constructions that have since emerged. Several open problems are identified, and many of the sections have a notes subsection at the end that provides additional background.

In this paper, we design erasure-correcting codes for channels with burst and random erasures, when a strict decoding delay constraint is in place. We consider the sliding-windowbased packet erasure model proposed by Badr et al., where any time-window of width w contains either up to a random erasures or an erasure burst of length at most b. One needs to recover any erased packet with a strict decoding delay deadline of τ , where erasures are as per the channel model. Presently existing rate-optimal constructions in the literature require, in general, a field-size which grows exponential in τ , as long as a/τ remains a constant. In this work, we present a new rate-optimal code construction covering all channel and delay parameters, which requires an O(τ2) field-size. As a special case, when (b–a) = 1, we have a field-size linear in τ . We also present two other constructions having linear field-size, under certain constraints on channel and decoding delay parameters. As a corollary, we obtain low field-size, rate-optimal convolutional codes for any given column distance and column span. Simulations indicate that the newly proposed streaming code constructions offer lower packet-loss probabilities compared to existing schemes, for selected instances of Gilbert-Elliott and Fritchman channels.

This paper considers the natural extension of locally recoverable codes (LRC) to the case of ${t} > 1$ erased symbols. While several approaches have been proposed for the handling of multiple erasures, in the approach considered here, the t erased symbols are recovered in succession, each time contacting at most r other symbols for assistance. Under the local-recovery constraint, this sequential approach is the most general and hence offers the maximum possible code rate. We characterize the rate of an LRC with sequential recovery for any ${r} \geq 3$ and any t , by first deriving an upper bound on the code rate and then constructing a binary code achieving this optimal rate. The upper bound derived here proves an earlier conjecture. Our approach permits us to deduce the structure of the parity-check matrix of a rate-optimal LRC with sequential recovery. The derived structure of parity-check matrix leads to a graphical description of the code used in code construction. A subclass of binary codes that are both rate and block-length optimal, are shown to correspond to certain regular graphs known as Moore graphs, that have the smallest number of vertices for a given girth. A connection with Tornado codes is also made.

Codes with locality are a class of codes introduced by Gopalan et al. to efficiently repair a failed node, by minimizing the number of nodes contacted during repair. An $[n,k]$ systematic code is said to have information locality $r$ , if each message symbol can be recovered by accessing $\leq r$ other symbols. An $[n,k]$ code is said to have all-symbol locality $r$ , if each code symbol can be recovered by accessing $\leq r$ other symbols. In this paper, we consider a generalization of codes with all-symbol locality to the case of handling two erasures. We study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. We refer to these codes as sequential-recovery locally repairable codes (denoted by 2-seq LR codes). Earlier approaches to handling multiple erasures considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. We derive an upper bound on the rate of 2-seq LR codes. We provide constructions based on regular graphs which are rate-optimal with respect to the derived bound. We also characterize the structure of any rate-optimal code. By studying the Generalized Hamming Weights of the dual code, we derive a recursive upper bound on the minimum distance of 2-seq LR codes. We also provide constructions of a family of codes based on Turán graphs, that are optimal with respect to this bound. We also present explicit distance-optimal Turán graph based constructions of 2-seq LR codes for certain parameters. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case.