Shaping codes are used to generate code sequences in which the symbols obey a prescribed probability distribution. They arise naturally in the context of source coding for noiseless channels with unequal symbol costs. Recently, shaping codes have been proposed to extend the lifetime of flash memory and reduce DNA synthesis time. In this paper, we study a general class of shaping codes for noiseless finite-state channels with cost and i.i.d. sources. We establish a relationship between the code rate and minimum average symbol cost. We then determine the rate that minimizes the average cost per source symbol (total cost). An equivalence is established between codes minimizing average symbol cost and codes minimizing total cost, and a separation theorem is proved, showing that optimal shaping can be achieved by a concatenation of optimal compression and optimal shaping for a uniform i.i.d. source.

Shaping codes are used to encode information for use on channels with cost constraints. Applications include data transmission with a power constraint and, more recently, data storage on flash memories with a constraint on memory cell wear. In the latter application, system requirements often impose a rate constraint. In this paper, we study rate-constrained fixed-to-variable length shaping codes for noiseless, memoryless costly channels and general i.i.d. sources. The analysis relies on the theory of word-valued sources. We establish a relationship between the code expansion factor - the ratio of the expected codeword length to the length of the input source word - and the minimum average symbol cost. We then determine the expansion factor that minimizes the average cost per source symbol (total cost), corresponding to a conventional optimal source code with cost. An equivalence is established between codes minimizing average symbol cost and codes minimizing total cost, and a separation theorem is proved, showing that optimal shaping can be achieved by a concatenation of optimal compression and optimal shaping for a uniform i.i.d. source. Shaping codes often incorporate, either explicitly or implicitly, some form of non-equiprobable signaling. We use our results to further explore the connections between shaping codes and codes that map a sequence of i.i.d. source symbols into an output sequence of symbols that are approximately independent and distributed according to a specified target distribution, such as distribution matching (DM) codes. Optimal DM codes are characterized in terms of a new performance measure - generalized expansion factor (GEF) - motivated by the costly channel perspective. The GEF is used to study DM codes that minimize informational divergence and normalized informational divergence.

Rate-compatible error-correcting codes (ECCs), which consist of a set of extended codes, are of practical interest in both wireless communications and data storage. In this work, we first study the lower bounds for rate-compatible ECCs, thus proving the existence of good rate-compatible codes. Then, we propose a general framework for constructing rate-compatible ECCs based on cosets and syndromes of a set of nested linear codes. We evaluate our construction from two points of view. From a combinatorial perspective, we show that we can construct rate-compatible codes with increasing minimum distances, and we discuss decoding algorithms and correctable patterns of errors and erasures. From a probabilistic point of view, we prove that we are able to construct capacity-achieving rate-compatible codes, generalizing a recent construction of capacity-achieving rate-compatible polar codes. Applications of rate-compatible codes to data storage are considered. We design two-level rate-compatible codes based on Bose-Chaudhuri-Hocquenghem (BCH) and low-density parity-check (LDPC) codes which are two popular codes widely used in the data storage industry, and then we evaluate the performance of these codes in multi-level cell (MLC) flash memories. We also examine code performance on binary and $q$ -ary symmetric channels. Finally, we briefly discuss two variations of our main construction and their relative performance.

Erasure codes play an important role in storage systems to prevent data loss. In this work, we study a class of erasure codes called Multi-Erasure Locally Recoverable Codes (ME-LRCs) for storage arrays. Compared to previous related works, we focus on the construction of ME-LRCs over small fields. Our main contribution is a general construction of ME-LRCs based on generalized tensor product codes, and an analysis of their erasure-correcting properties. A decoding algorithm tailored for erasure recovery is given, and correctable erasure patterns are identified. We then prove that our construction yields optimal ME-LRCs with a wide range of code parameters, and present some explicit ME-LRCs over small fields. Next, we show that generalized integrated interleaving (GII) codes can be treated as a subclass of generalized tensor product codes, thus defining the exact relation between these codes. Finally, ME-LRCs are investigated in a probabilistic setting. We prove that ME-LRCs based upon a generalized tensor product construction can achieve the capacity of a compound erasure channel consisting of a family of erasure product channels.

Error-correcting codes play an important role in storage systems to maintain data integrity. In this work, we propose a new class of linear error- correcting codes, called ladder codes, whose codeword structure consists of multiple codewords of certain component codes and also their shared redundancy. First, we give a general construction for an m-level ladder code, determine the code length and dimension, and also derive a lower bound d*Lon the minimum distance. Some examples of ladder codes are presented. Then, we study correctable error-erasure patterns of ladder codes and give a corresponding decoding algorithm. Finally, we compare a two-level ladder code with a concatenated code, and show that the former can outperform the latter in many cases. Ladder codes have potential to be used for data protection in flash memories where only a few pages may suffer from severe errors in a block.

Data shaping is a coding technique that has been proposed to increase the lifetime of flash memory devices. Several data shaping codes have been described in recent work, including endurance codes [2] and direct shaping codes for structured data [8], [4], [5]. In this paper, we study information-theoretic properties of a general class of data shaping codes and prove a separation theorem stating that optimal data shaping can be achieved by the concatenation of optimal lossless compression with optimal endurance coding. We also determine the expansion factor that minimizes the total wear cost. Finally, we analyze the performance of direct shaping codes and establish a condition for their optimality.

Rate-compatible error-correcting codes (ECCs), which consist of a set of extended codes, are of practical interest in both wireless communications and data storage. In this work, we first study the lower bounds for rate-compatible ECCs, thus proving the existence of good rate-compatible codes. Then, we propose a general framework for constructing rate-compatible ECCs based on cosets and syndromes of a set of nested linear codes. We evaluate our construction from two points of view. From a combinatorial perspective, we show that we can construct rate-compatible codes with increasing minimum distances. From a probabilistic point of view, we prove that we are able to construct capacity-achieving rate-compatible codes.

In this work, we study the performance of different decoding schemes for multilevel flash memories where each page in every block is encoded independently. We focus on the multi-level cell (MLC) flash memory, which is modeled as a two-user multiple access channel suffering from asymmetric noise. The uniform rate regions and sum rates of Treating Interference as Noise (TIN) decoding and Successive Cancelation (SC) decoding are investigated for a Program/Erase (P/E) cycling model and a data retention model. We examine the effect of different binary labelings of the cell levels, as well as the impact of further quantization of the memory output (i.e., additional read thresholds). Finally, we extend our analysis to the three-level cell (TLC) flash memory.

In this paper, we study the performance of different decoding schemes for multilevel flash memories where each page in every block is encoded independently. We focus on multi-level cell flash memory, which is modeled as a two-user multiple-access channel suffering from asymmetric noise. The uniform rate regions and sum rates of treating interference as noise decoding and successive cancelation decoding are investigated for a program/erase cycling model and a data retention model. We examine the effect of different binary labelings of the cell levels, as well as the impact of further quantization of the memory output (i.e., additional read thresholds). Finally, we extend our analysis to the three-level cell flash memory.

Locally repairable codes (LRCs) are a class of codes designed for the local correction of erasures. They have received considerable attention in recent years due to their applications in distributed storage. Most existing results on LRCs do not explicitly take into consideration the field size q, i.e., the size of the code alphabet. In particular, for the binary case, only a few results are known. In this paper, we present an upper bound on the minimum distance d of linear LRCs with availability, based on the work of Cadambe and Mazumdar. The bound takes into account the code length n, dimension k, locality r, availability t, and field size q. Then, we study the binary linear LRCs in three aspects. First, we focus on analyzing the locality of some classical codes, i.e., cyclic codes and Reed-Muller codes, and their modified versions, which are obtained by applying the operations of extend, shorten, expurgate, augment, and lengthen. Next, we construct LRCs using phantom parity-check symbols and multi-level tensor product structure, respectively. Compared with other previous constructions of binary LRCs with fixed locality or minimum distance, our construction is much more flexible in terms of code parameters, and gives various families of high-rate LRCs, some of which are shown to be optimal with respect to their minimum distance. Finally, the availability of LRCs is studied. We investigate the locality and availability properties of several classes of one-step majority-logic decodable codes, including cyclic simplex codes, cyclic difference-set codes, and 4-cycle free regular low-density parity-check codes. We also show the construction of a long LRC with availability from a short one-step majority-logic decodable code.

In this work, we present a new upper bound on the minimum distance d of linear locally repairable codes (LRCs) with information locality and availability. The bound takes into account the code length n, dimension k, locality r, availability t, and field size q. We use tensor product codes to construct several families of LRCs with information locality, and then we extend the construction to design LRCs with information locality and availability. Some of these codes are shown to be optimal with respect to their minimum distance, achieving the new bound. Finally, we study the all-symbol locality and availability properties of several classes of one-step majority-logic decodable codes, including cyclic simplex codes, cyclic difference-set codes, and 4-cycle free regular low-density parity-check (LDPC) codes. We also investigate their optimality using the new bound.

Locally repairable codes (LRCs) are a class of codes designed for the local correction of erasures. They have received considerable attention in recent years due to their applications in distributed storage. Most existing results on LRCs do not explicitly take into consideration the field size q, i.e., the size of the code alphabet. In particular, for the binary case, only a few specific results are known by Goparaju and Calderbank. Recently, however, an upper bound on the dimension k of LRCs was presented by Cadambe and Mazumdar. The bound takes into account the length n, minimum distance d, locality r, and field size q, and it is applicable to both non-linear and linear codes. In this work, we first develop an improved version of the bound mentioned above for linear codes. We then focus on cyclic linear binary codes. By leveraging the cyclic structure, we notice that the locality of such a code is determined by the minimum distance of its dual code. Using this result, we investigate the locality of a variety of well known cyclic linear binary codes, e.g., Hamming codes and Simplex codes, and also prove their optimality with our improved bound for linear codes. We also discuss the locality of codes which are obtained by applying the operations of Extend, Shorten, Expurgate, Augment, and Lengthen to cyclic linear binary codes. Several families of such modified codes are considered and their optimality is addressed. Finally, we investigate the locality of Reed-Muller codes. Even though they are not cyclic, it is shown that some of the locality results for cyclic codes still apply.