Finding the error locator polynomial for decoding is achieved by several algorithms, such as the Peterson-Gorenstein-Zierler (PGZ) algorithm and the Berlekamp-Massey (BM) algorithm. This paper presents a two-stage decoding method for BCH codes using both algorithms. First, we run the first-stage PGZ algorithm implemented in parallel for fast decoding. Since the PGZ algorithm is not feasible for large numbers of errors, the correction capability of the first stage is limited. When such errors occur, the computation of the previous PGZ algorithm is recycled for the second-stage BM algorithm. In other words, we study a relay method to convert failed results of the PGZ algorithm to parameters of the subsequent BM algorithm. Our relay method using the PGZ algorithm is easier to select the relayed parameters than an unfolding of the BM algorithm using a binary decision tree. Using the relayed parameters removes several iterative updates of the subsequent BM algorithm, so that our relay algorithm can be a quick and simple start for fast decoding.

Flash memory is gaining attention for achieving large-capacity and high-speed storage devices. In particular, multi-level flash memory is widely used for increasing storage capacity. However, it faces slower access speeds as the number of read thresholds increases. Sharon et al. proposed the random input-output (RIO) code, which reduces the number of read thresholds to one for multi-level flash memory. However, the RIO code offers lower storage capacity than conventional uncoded multi-level flash memory. We propose SHare Coding (SHC), which maintains storage capacity and achieves higher speeds with fewer read thresholds than conventional uncoded methods.

Mismatch between the true channel and the channel assumed in the design of a communication system can degrade system performance. Joint channel estimation and data recovery via the Expectation-Maximization (EM) algorithm can overcome this problem. Though stable, the EM algorithm can be complex to implement and can exhibit slow convergence. We present approximations of the EM algorithm that reduce computational complexity and accelerate convergence for LDPC-coded discrete memoryless channels. In place of the exact bit-wise maximum a posteriori probability decoder in the E step of the EM algorithm, we use the sum-product decoder and min-sum decoder. In the M step, we use hard information instead of soft information to estimate the channel parameter. In order to evaluate the approximations in a practical channel mismatch scenario, we use a flash memory channel described by a quantized Normal-Laplace mixture model. The simulation results demonstrate that the approximations in the E step can estimate the true channel with low-complexity decoding and those in the M step can accelerate the convergence with reduced measurement precision.

The circuit of parallel Chien search is the largest in the decoder for long Bose-Chaudhuri-Hocquenghem (BCH) codes with strong correction capability. It can be decomposed into two functional blocks. One is the shift block which stores and transforms an error locator polynomial. The rest consists of substitution circuits which substitute finite field values into the polynomial to find its roots, which indicate error locations. For circuit-size reduction of the substitution, an error locator polynomial is divided by a product of minimal polynomials. If there are common roots between a dividend and divisor, the remainder inherits the common roots. Hence, error locations can be found by testing the remainder with the lower degree than that of the error locator polynomial. Our new architecture needs additional operations, such as the division. However, for 122-error-correcting BCH codes over GF(215), our new architecture can reduce the circuit size of the 16-parallel Chien search by 17% compared with an optimized conventional architecture.

Graph codes are constructed from undirected graphs where the code symbols correspond to the edges and component codes are associated with the vertices. We investigate graph codes on multigraphs whereas previous work has mainly studied them on simple graphs. This paper proposes graph codes constructed from complete multipartite graphs as generalizations of block-wise product codes. The graph codes show better error-correcting performance in error-floor region compared with block-wise product codes. This paper also shows an efficient encoding method for the graph codes by employing Richardson and Urbanke's encoding algorithm for LDPC codes.

In order to suppress error floors of low density parity check (LDPC) codes, we study a parallel concatenation scheme with an intermediate single parity check (SPC) code and interleavers. The interleavers of the concatenation play an important role to lower error floors, because it is highly possible that interleaved bits in a trapping set are not to be in error even if the bits in the trapping set are originally in error. For quasi-cyclic LDPC codes, our simulation results confirm that the integrated parallel interleaved concatenation with circulant-size cyclic-shift interleavers improves error-floor performance, and it is better than serial concatenation schemes with BCH codes. If a decoder can afford to accommodate higher-hardware complexity, the decoding performance of our scheme improves so that the error floor can be lowered further.

The beta-binomial (BBM) channel model was recently proposed to model the overdispersed statistics of empirically observed bit errors in multi-level cell (MLC) flash memories. In this paper, we study the capacity of the BBM channel model for MLC flash memories. Using the compound channel approach, we first show that the BBM channel model capacity is zero. However, through empirical observation, this appears to be a very pessimistic estimate of the flash memory channel capacity. We propose a refined channel model called the truncated-support BBM (TS-BBM) channel model and derive its capacity. Using empirical error statistics from 1X-nm and 2Y-nm MLC flash memories, we numerically estimate the TS-BBM channel model capacity as a function of the program/erase cycling stress. The capacity of the 2-TS-BBM channel model provides an upper bound on the coding rates for the flash memory chip assuming a single binary error correction code is used.

We propose binary discrete parametric channel models for multi-level cell (MLC) flash memories that provide accurate error-correcting code (ECC) performance estimation by modeling the empirically observed error characteristics under program/erase cycling stress. Through a detailed empirical error characterization of 1X-nm and 2Y-nm MLC flash memory chips from two different vendors, we observe and characterize the overdispersion phenomenon in the number of bit errors per ECC frame. A well-studied channel model, such as the binary asymmetric channel model, is unable to provide accurate ECC performance estimation. Hence, we propose a channel model based on the beta-binomial probability distribution [2-beta-binomial (2-BBM) channel model], which is a good fit for the overdispersed empirical error characteristics, and show through statistical tests and simulation results for BCH, low density parity check, and polar codes, that the 2-BBM channel model provides accurate ECC performance estimation in MLC flash memories.

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.

With an aim to characterize, model and understand the types of errors caused by the inter-cell interference (ICI) effect in flash memories, we perform a series of program/erase (P/E) cycling experiments designed to quantify the effects of ICI. We create a database of errors at various levels of granularity such as bit, cell, page, block and record the neighborhood data patterns of cells in error to provide a quantitative understanding of the underlying channel model in multi-level cell (MLC) flash memories. We then utilize this empirical data to model and study the flash memory channel as a time-varying 4-ary discrete memoryless channel (DMC). We also present results from experiments to quantify the error rate performance gain obtained by the use of constrained codes, which prevent some ICI-susceptible data patterns from being written to the flash memory.

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.

A new family of protograph-based codes with no punctured variable nodes is presented. The codes are constructed by using differential evolution, partial brute force search, and the lengthening method introduced by Nguyen et al.. The protograph ensembles satisfy the linear minimum distance growth property and have the lowest iterative decoding thresholds yet reported in the literature among protograph codes without punctured variable nodes. Simulation results show that the new codes perform better than state-of-the-art protograph codes when the number of decoding iterations is small.

While it is known that spatially-coupled low-density lattice codes (SC-LDLC) have better decoding performance than conventional (non-coupled) LDLC lattices, in this paper it is shown that their encoding complexity is also lower. Since nonzero elements are mainly in lower triangular entries of the sparse inverse generator matrix of SC-LDLC, iterative encoding with the Gauss-Seidel method performs well. The convergence speed of iterative encoding is evaluated by both the mean square error (MSE) and the symbol error rate between a given integer vector b and the inversely generated integer vector from the codeword of b. Numerical experiments show that the convergence of encoding for SC-LDLC is 3 times faster than that of the conventional LDLC, at an MSE of 10-10for dimension n = 10000.

We consider spatially-coupled LDPC codes for the three terminal erasure relay channel. It is observed that BP threshold value of spatially-coupled LDPC codes, in particular spatially-coupled MacKay-Neal code, is close to the theoretical limit for the relay channel. Empirical results suggest that spatially-coupled LDPC codes have great potential to achieve theoretical limit of a general relay channel.