Redundancy transitioning enables erasure-coded storage to adapt to varying performance and reliability requirements by re-encoding data with new coding parameters on-the-fly. Existing studies focus on bandwidth-driven redundancy transitioning that reduces the transitioning bandwidth across storage nodes, yet the actual redundancy transitioning performance remains bottlenecked by the most loaded node. We present BART, a load-balanced redundancy transitioning scheme that aims to reduce the redundancy transitioning time via carefully scheduled parallelization. We show that finding an optimal load-balanced solution is difficult due to the large solution space. Given this challenge, BART decomposes the redundancy transitioning problem into multiple sub-problems and solves the sub-problems via efficient heuristics. We evaluate BART using both simulations for large-scale storage and HDFS prototype experiments on Alibaba Cloud. We show that BART significantly reduces the redundancy transitioning time compared with the bandwidth-driven approach.

A locally repairable code is called Singleton-optimal if it achieves the Singleton-type bound. Such codes are of great theoretic interest in the study of locally repairable codes. One of the major problems in this topic is to determine the maximum length of aq-ary Singleton-optimal locally repairable code with fixed locality and minimum distance. Unlike classical MDS codes, the maximum length of Singleton-optimal locally repairable codes is very sensitive to the minimum distance and locality. Thus, determining the maximum length of the Singleton-optimal locally repairable codes is more challenging and complicated. In literature, many efforts are paid to solve this problem especially for small distance and locality regime. Moreover, most of works also requires that (r+ 1)|nand the recovery sets are disjoint so as to simplify the argument,whereris locality andnis the code length. In this paper, we derive some upper bounds on the maximum length of Singleton-optimal locally repairable codes with minimum distance 5, 6 and 7 without the constraint that (r+ 1)|nand the recovery sets are disjoint.It turns out that even without this constraint we still obtain better upper bounds for codes with small locality and distance compared to known results. Furthermore, based on our upper bounds for codes with small distance and locality, we propose the propagation rule to derive some upper bounds for codes with relatively large distance and locality assuming that (r+1)|nand recovery sets are disjoint.

Real-world distributed storage systems (DSSs) are heterogeneous because storage nodes may have unequal per-symbol storage costs, and network links may have unequal per-symbol transmission costs. For some general classes of heterogeneous DSSs, the optimal tradeoff between storage and repair costs achievable by functional repair codes is known (at least numerically). However, it is unclear whether exact-repair codes can achieve any point of such an optimal storage-repair tradeoff curve, especially at the point of the minimum storage cost. In this paper, we provide an affirmative answer to the question by constructing the so-called heterogeneous minimum storage repair (HMSR) codes for both the average and worst-case repair costs. To optimize storage and repair costs, a heterogeneous DSS may need to adopt irregular array codes and repair a node by downloading unequal numbers of symbols from helper nodes. However, our results show that for almost all heterogeneous DSSs, exact-repair HMSR codes are regular array codes covering an adequately chosen set of nodes. Specifically, exact-repair HMSR codes are designed by stacking conventional MSR codes and applying different repair schemes to different layers. Still, this does not work for every heterogeneous DSS. It is proven that using regular or linear irregular array codes for constructing exact-repair HMSR codes is insufficient in some cases.

In an erasure-coded distributed storage system (DSS), requesting a file requires downloading information from multiple storage nodes, called servers, which leads to cross-server network traffic. The cross-server transmission cost can be reduced if these servers are equipped with extra memory to cache some information about the files. This paper considers the so-called cache-aided DSS (CADSS), where each server is connected to several caching proxies through a shared link, and studies the transmission cost incurred by file requests. For simplicity, we focus on a CADSS in which the servers are connected via a one-hop link, and each server is connected to the same number of caching proxies. When the caching proxies receive file requests, a server first downloads some symbols from the other servers, called the helper servers, and then broadcasts some symbols to the caching proxies. For a single server, the maximum number of symbols downloaded from the helper nodes (respectively broadcast to its caching proxies) normalized by the file size is called the cross-server (respectively local) reads. This paper first optimizes the cross-server and local reads separately. Whether from the perspective of optimizing cross-server or local reads, a CADSS can be interpreted as an equivalent single-server caching system but with different system parameters. This paper analyzes the optimal tradeoff between the cross-server and local reads. It is shown that the optimal cross-server and local reads can be achieved simultaneously for some parameters, while a tradeoff exists for some other parameters. We characterize the two extreme points of the optimal tradeoff curve and derive the optimal tradeoff for some specific parameters.

This paper considers the parity-check matrix of a maximum distance separable (MDS) array code as a superposition of two matrices, block diagonal matrix A and side matrix S. By matching their entries, the syndrome calculation of the matrix A can share computations with that of the side matrix S. Then, a low-complexity encoding, referred to as side encoding, is proposed to encode matched MDS array codes efficiently. Moreover, it can combine with the Reed-Muller transform-based (RMTB) Reed-Solomon encoding algorithm to reduce the encoding complexity further. The analysis indicates that for the MDS array code [1] with four parity nodes, the number of multiplications is reduced by 85.4% and 52.6% compared to the traditional encoding and only RMTB encoding, respectively.

This paper proposes the re-encoding transformed (ReT) based list decoding using the module basis reduction (BR) interpolation for algebraic geometric (AG) codes on Cabcurves. The two ReT approaches are introduced to facilitate the BR interpolation. One is realized by the bivariate Lagrange polynomial. The other is conducted by the ReT of Reed-Solomon (RS) codes based on the mathematical structure of AG codes. The ReT based BR interpolation (ReT-BR) algorithm for decoding the AG codes is further introduced. Finally, complexity of the proposed algorithm is analyzed and validated by the simulation results, demonstrating its complexity advantage over the non-ReT counterpart.

Sparse regression codes (SPARCs) are a promising coding scheme that can approach the Shannon limit over Additive White Gaussian Noise (AWGN) channels. Previous works have proven the capacity-achieving property of SPARCs with Gaussian design matrices. We generalize these results to right orthogonally invariant ensembles that allow for more structured design matrices. With the Vector Approximate Message Passing (VAMP) decoder, we rigorously demonstrate the exponentially decaying error probability for design matrices that satisfy a certain criterion with the exponentially decaying power allocation. For other spectra, we design a new power allocation scheme to show that the information theoretical threshold is achievable.

In classical coding theory, it is common to construct new codes via propagation rules. There are various propagation rules to construct classical block codes. However, propagation rules have not been extensively explored for locally repairable codes. In this paper, we systematically study some of propagation rules to construct optimal and asymptotically good locally repairable codes. To our surprise, these simple propagation rules produce interesting results. Firstly, by a lengthening propagation rule that adds some rows and columns to a parity-check matrix of a given linear code, we are able to convert a classical maximum distance separable (MDS) code into a Singleton-optimal locally repairable code and provide a simplified proof of the asymptotic Tafasman-Vlăduţ-Zink bound which exceeds the asymptotic Gilbert-Varshamov bound of locally repairable codes. Secondly, by concatenating a locally repairable code as an inner code with a classical block code as an outer code, we obtain a family of dimension-optimal locally repairable codes. Thirdly, we can make use of the shortening technique to produce more dimension-optimal locally repairable codes. Finally, one of phenomena that we observe in this paper is that some trivial propagation rules in classical block codes do not hold anymore for locally repairable codes.

In coding theory, constructing codes with good parameters is one of the most important and fundamental problems. A great many good codes have been constructed over alphabets of sizes equal to prime powers, however, good block codes over other alphabet sizes are rare. In this paper, we provide a new explicit construction of$(q+1)$-ary nonlinear codes via algebraic function fields, where$q$is a prime power. Our codes are constructed by evaluating rational functions at all rational places of an algebraic function field. Compared with algebraic geometry codes, the main difference is that we allow rational functions to be evaluated at pole places. After evaluating rational functions from a union of Riemann-Roch spaces, we obtain a family of nonlinear codes over the alphabet$\mathbb {F}_{q}\cup \{\infty \}$. It turns out that our codes have better parameters than those obtained from MDS codes or good algebraic geometry codes via code alphabet extension and restriction.

In this paper, the problem of designing the maximum-distance-separable (MDS) array codes for repairing a single node failure in a distributed storage system (DSS) is addressed. We consider the class of heterogeneous DSSs which can be represented as a fully connected storage network consisting of links having possibly different per-symbol transmission costs and assume that the repair process only allows a single-hop transmission from any helper node to a failed node. First, we consider the repair cost of a failed node to be the total transmission cost from all helper nodes incurred by the repair process. For a storage network represented by a complete weighted graph with the weights being the persymbol transmission costs, we derive a repair cost lower bound of every node. Somewhat surprisingly, even for a storage network represented by a complete weighted graph with time-varying weights, we can also construct a single optimal-repair-cost MDS array code that can achieve the repair cost lower bounds of all nodes. Next, we consider the repair cost of a failed node to be the worst-case transmission cost over all helper nodes incurred by the repair process. For a storage network represented by a static complete weighted graph, we derive a lower bound on the repair cost of every node and construct a single optimal-repair-cost MDS array code that can achieve the repair cost lower bounds of all nodes.

In this paper, we consider two rack-aware storage systems. First, large-scale rack-aware storage system, which is very common in large-scale storage system, is a rack-aware storage system where all sizes of racks are at least the number of redundant nodes. For such storage system, we prove that any Maximum Distance Separable (MDS) codes can have optimal inter-rack repair bandwidth and give a closed-form representation of all repair schemes with optimal inter-rack repair bandwidth. Furthermore, we show that the optimal repair access and optimal inter-rack repair bandwidth can be attained simultaneously for such storage system. Second, we investigate the rack-aware storage system of all racks with the same size, which is called uniform rack-aware storage system. We prove that, except the trivial cases, we cannot attain optimal inter-rack repair bandwidth and optimal repair access for such storage system at the same time. Specifically, we establish the lower bound of repair access for a repair scheme with optimal interrack repair bandwidth, which is tight for some parameters, and also the tight lower bound of inter-rack repair bandwidth for a repair scheme with optimal repair access.

Regenerating codes are designed to reduce the repair bandwidth (access bandwidth) for rebuilding a fail node in an erasure-coded storage system. In practical systems, the fail node is not rebuilt immediately. Before its rebuilding, the data originally stored in the failed node might be accessed by the system. Hence, accessing the data in the failed disk (degraded read) with low latency is crucial for any practical storage system. In this work, to solve this problem, a new class of the regenerating codes based on the maximum distance separable (MDS) array codes is defined, named the MDS array code with the property of degraded read friendly (DRF). For the DRF MDS array codes with 2 redundant nodes and the sub-packetization level of 2, the lower bound of their access bandwidth is derived. A class of the DRF MDS array codes that achieves the derived bound is given to solidify the achievability of the proposed lower bound.

Constrained coding is used widely in digital communication and storage systems. In this article, we study a generalized sliding window constraint called the skip-sliding window. A skip-sliding window (SSW) code is defined in terms of the length L of a sliding window, skip length J, and cost constraint E in each sliding window. Each valid codeword of length L + kJ is determined by k+1 windows of length L where window i starts at (iJ + 1)th symbol for all non-negative integers i such that i ≤ k; and the cost constraint E in each window must be satisfied. SSW coding constraints naturally arise in applications such as simultaneous energy and information transfer, and SSW codes are also potential candidates for visible light communications. In this work, two methods are given to enumerate the size of SSW codes and further refinements are made to reduce the enumeration complexity. Using the proposed enumeration methods, the noiseless capacity of binary SSW codes is determined and some useful observations are made, such as the fact that SSW codes provide greater capacity than certain related classes of constrained codes. Moreover, we provide noisy capacity bounds for SSW codes.

Based on the notion of supercodes, we propose a two-phase maximum-likelihood (ML) soft-decision decoding (tpMLSD) algorithm for binary linear block codes in this work. The first phase applies the priority-first search algorithm backwardly to a trellis derived from the parity-check matrix of the supercode of the linear block code. Using the information retained from the first phase, the second phase employs the priority-first search algorithm to the trellis corresponding to the linear block code itself, which guarantees to find the ML decision with a constant complexity per information bit at high signal-to-noise ratios (SNRs). Simulations on the extended BCH code of n = 64 and k = 24 show that the proposed two-phase scheme is an order of magnitude more efficient in average decoding complexity than the recursive ML decoding [1] when the SNR per information bit is 8 dB.

Communication systems for multicasting information and energy simultaneously to more than one user are investigated. In the system under study, a transmitter sends the same message and signal to multiple receivers over distinct and independent channels. The fundamental communication limit under a received energy constraint, called the multicast capacity-energy function, is studied and a single-letter expression is derived. This is based on coding theorems for compound channels. The problem of receiver segmentation, where receivers are divided into related groups, is also considered.

We consider binary skip-sliding window (SSW) codes which satisfy certain weight constraints over a skip-sliding window. When on-off keying is employed, these weight constraints ensure real-time energy content in the transmitted signal. For a given energy requirement and battery size at an energy harvesting receiver, we investigate the maximum achievable rate using SSW codes which avoid energy outage at the receiver. The SSW codes generalize sliding window constrained (SWC) codes and subblock energy constrained (SEC) codes; we show that SSW codes with window length equal to twice the skip-length can outperform both SWC and SEC codes in terms of outage-constrained rate.

This paper investigates the fundamental limits of communication over a noisy discrete memoryless channel that wears out, in the sense of signal-dependent catastrophic failure. In particular, we consider a channel that starts as a memoryless binary-input channel and when the number of transmitted ones causes a sufficient amount of damage, the channel ceases to convey signals. Constant composition codes are adopted to obtain an achievability bound, and the left-concave right-convex inequality is then refined to obtain a converse bound on the log-volume throughput for channels that wear out. Since infinite blocklength codes will always wear out the channel for any finite threshold of failure, and therefore cannot convey information at positive rates, we analyze the performance of finite blocklength codes to determine the maximum expected transmission volume at a given level of average error probability. We show that this maximization problem has a recursive form and can be solved by dynamic programming. Numerical results demonstrate that a sequence of block codes is preferred to a single block code for streaming sources.

Constrained coding is used widely in digital communication and storage systems. In this paper, we study a generalized sliding window constraint called the skip-sliding window constraint. A skip-sliding window (SSW) code is defined in terms of the length L of a sliding window, skip length J, and cost constraint E in each sliding window. Each valid codeword of length L+kJ is determined by k+1 windows of length L where window i starts at (iJ+1)th symbol for all non-negative integers i such that i ≤ k; and the cost constraint E in each window must be satisfied. In this work, two methods are given to enumerate the size of SSW codes. Using the proposed enumeration methods, the noiseless capacity of binary SSW codes is determined and observations such as greater capacity than other classes of codes are made. Moreover, some noisy capacity bounds are given. SSW coding constraints arise in various applications including simultaneous energy and information transfer.

Due to the growing interest in applying tail-biting convolutional coding techniques in real-time communication systems, fast decoding of tail-biting convolutional codes has become an important research direction. In this paper, a new maximum-likelihood decoder for tail-biting convolutional codes is proposed. It is named bidirectional priority-first search algorithm (BiPFSA) because priority-first search algorithm has been used both in forward and backward directions during decoding. Simulations involving the antipodal transmission of (2, 1, 6) and (2, 1, 12) tail-biting convolutional codes over additive white Gaussian noise channels shows that BiPFSA not only has the least average decoding complexity among the state-of-the-art decoding algorithms for tail-biting convolutional codes but can also provide a highly stable decoding complexity with respect to growing information length and code constraint length. More strikingly, at high SNR, its average decoding complexity can even approach the ideal benchmark complexity, obtained under a perfect noise-free scenario by any sequential-type decoding. This demonstrates the superiority of BiPFSA in terms of decoding efficiency.

This work investigates the limits of communication over a noisy channel that wears out, in the sense of signal-dependent catastrophic failure. In particular, we consider a channel that starts as a memoryless binary-input channel and when the number of transmitted ones causes a sufficient amount of damage, the channel ceases to convey signals. We restrict attention to constant composition codes. Since infinite blocklength codes will always wear out the channel for any finite threshold of failure and therefore convey no information, we analyze the performance of finite blocklength codes to determine the maximum expected transmission volume at a given level of average error probability. We show that this maximization problem has a recursive form and can be solved by dynamic programming. A discussion of damage state feedback in channels that wear out is also provided. Numerical results show that a sequence of block codes is preferred to a single block code for streaming sources.

A joint source-channel coding problem that combines the efficient compression of discrete memoryless sources with their reliable communication over memoryless channels via binary prefix-free variable-length error-correcting codes (VLECs) is considered. Under a fixed free distance constraint, a priority-first search algorithm is devised for finding an optimal VLEC with minimal average codeword length. Two variations of the priority-first-search-based code construction algorithm are also provided. The first one improves the resilience of the developed codes against channel noise by additionally considering a performance parameter Bdfreewithout sacrificing optimality in average codeword length. In the second variation, to accommodate a large free distance constraint as well as a large source alphabet such as the 26-symbol English data source, the VLEC construction algorithm is modified with the objective of significantly reducing its search complexity while still yielding near-optimal codes. A low-complexity sequence maximum a posteriori (MAP) decoder for all VLECs (including our constructed optimal code) is then proposed under the premise that the receiver knows the number of codewords being transmitted. Simulations show that the realized optimal and suboptimal VLECs compare favorably with existing codes in the literature in terms of coding efficiency, search complexity and error rate performance.

In this paper, we present a novel algorithm that guarantees of finding a variable-length error-correcting code (VLEC) with minimal average codeword length for a fixed free distance dfree. We also propose a low complexity maximum a posterior (MAP) decoding algorithm for our codes under the premise that the receiver knows the number of codewords being transmitted. The resulting VLEC provides significant gains over other codes from the literature. When compared with separate source-channel tandem codes with identical dfree, such as a tandem code consisting of a Huffman source code concatenated with a (2, 1, 4) tail-biting convolutional channel code, our system has only a 0.3 dB performance loss at a bit error rate of 10-5while requiring significantly less decoding complexity.

In this work, we proposed a reliability-based enhancement for the decoding of convolutional tail-biting codes (CTBC) from the observations that the decoding does not have to start from the beginning of the received vector, and that the reliability of the received vector can be used to determine a good starting position of the decoding process. Simulations show that our reliability-based enhancement can be used together with existing decoding algorithms of the CTBC to improve either their error rate or complexity.

Variable length codes (VLCs) are widely adopted in many compression standards due to their good coding efficiency on average codeword length. However, an inherent problem with a VLC is that an error of even one bit can cause serious error propagation and thus loss of synchronization at the receiver, which would lead to a series of non-correctly decoded symbols. Reversible variable length codes (RVLCs) were introduced to significantly mitigate this phenomenon. In this work, a method to find an optimal RVLC in terms of the minimum average codeword length is first formulated as a tree-searching problem, and then, instead of performing an exhaustive search, an A*-based construction algorithm is proposed to find an optimal RVLC. The proposed algorithm has been applied to several benchmarks for sources and has found respective optimal symmetric and asymmetric RVLCs.

In order to release the growing demand for computational complexity with respect to increasing information sequence length in the priority-first search decoding algorithm, a path elimination modification is proposed and also analyzed in this work. Specifically, we propose to directly eliminate all paths whose end nodes are Δ-level prior to the farthest node among those that have been visited thus far by the priority-first search. Following the argument on random coding, we then analyze the path elimination window Δ that results in a larger exponent for additional decoding error caused by path elimination than the exponent of the maximum-likelihood error performance, and hence guarantees exponentially negligible performance degradation. Our analytical results indicate that under additive white Gaussian noise (AWGN) channels, the path elimination window required for exponentially negligible performance degradation is just three times the code constraint length for rate one-half convolutional codes. It can be further reduced to 1.7-fold of the code constraint length when rate one-third convolutional codes are considered instead. Simulation results confirm these analytical window sizes. As a consequence, the priority-first search decoding algorithm can considerably reduce its computation burden and memory consumption by directly eliminating a large number of paths with nearly no performance degradation. This makes the priority-first search decoding algorithm with path elimination suitable for applications that demand low-complexity software implementation with near optimal performance.