Search

In the conventional index coding problem, the messages transmitted by the source to satisfy the demands of the receivers are error-free. However, in practice, the messages may be error prone which led to the introduction of error-correcting index codes. An error-correcting index code is an encoding scheme which enables every receiver to decode its demanded message even in the presence of certain number of transmission errors. Formally, an index code capable of correcting at most $\delta $ errors at all its receivers is defined as a $\delta $ -error-correcting index code. In this paper, we explore the connections between vector linear error-correcting index codes and discrete polymatroids. This is motivated from the connections between linear network error-correcting codes and matroids. It is shown that a vector linear error-correcting index code exists if and only if there exists a representable discrete polymatroid satisfying certain conditions. Differential error-correcting index codes which allow different receivers to have different error-correcting capabilities are also studied. Note that the $\delta $ -error-correcting code is a special case of a differential error-correcting index code. Error correction at a subset of receivers is another special case which is discussed. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The code design of non-binary low-density parity-check codes for the erasure channel, under maximum a posteriori decoding, is addressed. In particular, a partially structured ensemble of codes, characterized by a careful control of the amount and of the connectivity of the variable nodes of small degrees, is proposed. The identified ensemble of codes is analyzed in terms of asymptotic thresholds and weight distribution and it is shown that codes from the ensemble provide a remarkable trade-off between waterfall performance, error floor, and decoding complexity. As an example, the performance curve of a short (256,128) code on the memoryless 16-ary erasure channel tightly approaches the Singleton bound at least down to a codeword error rate of 10^-9, at low decoding complexity. [ABSTRACT FROM AUTHOR]

In this work, we consider high-rate error-control systems for storage devices using multi-level per cell (MLC) NAND flash memories. Aiming at achieving a strong error-correcting capability, we propose error-control systems using block-wise parallel/serial concatenations of short Bose-Chaudhuri-Hocquenghem (BCH) codes with two iterative decoding strategies, namely, iterative hard-decision decoding (IHDD) and iterative reliability based decoding (IRBD). It will be shown that a simple but very efficient IRBD is possible by taking advantage of a unique feature of the block-wise concatenation. For tractable performance analysis and design of IHDD and IRBD at very low error rates, we derive semi-analytic approaches. The proposed error-control systems are compared with various error-control systems with well-known coding schemes such as a product code, multiple BCH codes, a single long BCH code, and low-density parity-check codes in terms of page error rates, which confirms our claim: the proposed error-control systems achieve good tradeoffs between error-performance and complexity as compared to the traditional schemes and is also very favorable for implementation. [ABSTRACT FROM PUBLISHER]