Search

Polar code constructions based on mutual information or Bhattacharyya parameters of bit-channels are intended for hard-output successive cancellation (SC) decoders, and thus might not be well designed for use with other decoders, such as soft-output belief propagation (BP) decoders or successive cancellation list (SCL) decoders. In this letter, we use the evolution of messages, i.e., log-likelihood ratios, of unfrozen bits during iterative BP decoding of polar codes to identify weak bit-channels, and then modify the conventional polar code construction by swapping these bit-channels with strong frozen bit-channels. The modified codes show improved performance not only under BP decoding, but also under SCL decoding. The code modification is shown to reduce the number of low-weight codewords, with and without CRC concatenation. [ABSTRACT FROM PUBLISHER]

A primary source of increased read time on nand flash comes from the fact that, in the presence of noise, the flash medium must be read several times using different read threshold voltages for the decoder to succeed. This paper proposes an algorithm that uses a limited number of rereads to characterize the noise distribution and recover the stored information. Both hard and soft decoding are considered. For hard decoding, this paper attempts to find a read threshold minimizing bit error rate (BER) and derives an expression for the resulting codeword error rate. For soft decoding, it shows that minimizing BER and minimizing codeword error rate are competing objectives in the presence of a limited number of allowed rereads, and proposes a tradeoff between the two. The proposed method does not require any prior knowledge about the noise distribution but can take advantage of such information when it is available. Each read threshold is chosen based on the results of previous reads, following an optimal policy derived through a dynamic programming backward recursion. The method and results are studied from the perspective of an SLC Flash memory with Gaussian noise, but this paper explains how the method could be extended to other scenarios. [ABSTRACT FROM PUBLISHER]

Multilevel flash memory contains blocks of cells that represent data by the amount of charge stored in them. The cell writing—or programming—process applies specified voltages in a sequential manner, injecting charge to achieve a desired level. Reducing a cell level requires a costly block erasure, so programming only increases cell levels. Parallel programming, whereby a common voltage is applied to a group of cells to inject charge simultaneously, simplifies circuitry and increases programming speed. However, cell-to-cell variations and limited programming round can adversely affect its precision. In this paper, we consider algorithms for efficient cell programming. Since cell levels are quantized to a discrete set of values, our objective is to minimize the number of cells that are not quantized to their target levels. For a specified number of programming rounds, we derive an optimal parallel programming algorithm with complexity that is polynomial in the number of cells. We extend the algorithm to account for intercell interference, where the voltage applied to a cell can affect the level of adjacent cells. We then consider noisy programming of a single cell, with and without feedback about the cell level. In both scenarios, we present an algorithm that, for a given number of programming rounds, minimizes the probability of an incorrect cell level. [ABSTRACT FROM AUTHOR]

We consider t-write codes for write-once memories with n cells that can store multiple levels. Assuming an underlying lattice-based construction and using the continuous approximation, we derive upper bounds on the worst-case sum-rate optimal and fixed-rate optimal n-cell t-write write-regions for the asymptotic case of continuous levels. These are achieved using hyperbolic shaping regions that have a gain of 1 bit/cell over cubic shaping regions. Motivated by these hyperbolic write-regions, we discuss construction and encoding of codebooks for cells with discrete support. We present a polynomial-time algorithm to assign messages to the codebooks and show that it achieves the optimal sum-rate for any given codebook when n = 2. Using this approach, we construct codes that achieve high sum-rate. We describe an alternative formulation of the message assignment problem for n≥ 3, a problem which remains open. [ABSTRACT FROM PUBLISHER]

Inter-cell interference (ICI) is one of the main obstacles to precise programming (i.e., writing) of a flash memory. In the presence of ICI, the voltage level of a cell might increase unexpectedly if its neighboring cells are programmed to high levels. For q-ary cells, the most severe ICI arises when three consecutive cells are programmed to levels high - low - high, represented as (q-1)0(q-1), resulting in an unintended increase in the level of the middle cell and the possibility of decoding it incorrectly as a nonzero value. ICI-free codes are used to mitigate this phenomenon by preventing the programming of any three consecutive cells as (q-1)0(q-1). In this work, we extend ICI-free codes in two directions. First, we consider binary balanced ICI-free codes which, in addition to forbidding the 101 pattern, require the number of 0 symbols and 1 symbols to be the same. Using combinatorial methods, we determine the asymptotic information rate of these codes and show that the asymptotic rate loss due to the imposition of the balanced property is approximately 2%. Extensions to q-ary cells, for q>2 are also discussed. Next, we consider q-ary ICI-free write-once-memory (WOM) codes that support multiple writes of a WOM while mitigating ICI effects. These codes forbid the appearance of the (q-1)0(q-1) pattern in any codeword used in any writing step. Using properties of two-dimensional constrained codes and generalized WOMs, we characterize the maximum sum-rate of t-write ICI-free WOM codes or, equivalently, the t-write sum-capacity of an ICI-free WOM. [ABSTRACT FROM PUBLISHER]

Phase-change memory (PCM) is a promising nonvolatile solid-state memory technology. A PCM cell stores data by using its amorphous and crystalline states. The cell changes between these two states using high temperature. However, since the cells are sensitive to high temperature, it is important, when programming cells (i.e., changing cell levels), to balance the heat both in time and in space. In this paper, we study the time–space constraint for PCM, which was originally proposed by Jiang and coworkers. A code is called an (\alpha,\beta,p)-constrained code if for any \alpha consecutive rewrites and for any segment of \beta contiguous cells, the total rewrite cost of the \beta cells over those \alpha rewrites is at most p. Here, the cells are binary and the rewrite cost is defined to be the Hamming distance between the current and next memory states. First, we show a general upper bound on the achievable rate of these codes which extends the results of Jiang and coworkers. Then, we generalize their construction for (\alpha\geqslant 1,\beta=1,p=1)-constrained codes and show another construction for (\alpha=1,\beta\geqslant 1,p\geqslant 1)-constrained codes. Finally, we show that these two constructions can be used to construct codes for all values of \alpha, \beta, and p. [ABSTRACT FROM AUTHOR]