Constrained Codes that Mitigate Inter-Cell Interference in Read/Write Cycles for Flash Memories

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