LDPC Codes for Rank Modulation inFlash MemoriesFan ZhangElectrical and Computer Eng. Dept.Texas A&M UniversityCollege Station, TX [email protected] D. PfisterElectrical and Computer Eng. Dept.Texas A&M UniversityCollege Station, TX 77843hpfi[email protected] (Andrew) JiangComputer Science and Eng. Dept.Texas A&M UniversityCollege Station, TX [email protected]—An LDPC code is proposed for flash memories basedon rank modulation. In contrast to previous approaches, thisenables the use of long ECCs with fixed-length modulation codes.For ECC design, the rank modulation scheme is treated as partof an equivalent channel. A probabilistic model of the equivalentchannel is derived and a simple high-SNR approximation is given.LDPC codes over integer rings and finite fields are designed forthe approximate channel and a low-complexity symbol-flippingverification-based (SFVB) message-passing decoding algorithm isproposed to take advantage of the channel structure. Densityevolution (DE) is used to calculate decoding thresholds andsimulations are used to compare the low-complexity decoder withsum-product decoding.I. INTRODUCTIONFlash memories have become the most widely used non-volatile memories (NVMs) due to their high performance.They use the charge stored in floating-gate cells to representdata. Charge (e.g., electrons) can be injected into a cell bythe hot-electron injection mechanism or the Fowler-Nordheimtunneling mechanism, and be removed from the cell by thetunneling mechanism. The amount of charge in a cell is calledits level, and we can quantize it into one of q values to storelog2q bits. When q =2, it is called a single-level cell (SLC);and when q>2, it is called a multi-level cell (MLC). Toincrease data density, MLC flash memories with more levels(e.g., q =4, 8,...) are being actively developed.Flash memories have a distinct property called block era-sure. The flash memory cells are organized as blocks, whereevery block consists of about 105∼ 106cells. Although thecell levels can be increased individually, to decrease any cell’slevel, the whole block must be erased and then reprogrammed.Block erasures significantly reduce the longevity, speed andpower efficiency of flash memories. They also make cellprogramming (i.e., charge injection) difficult, especially forMLCs where the gap between adjacent cell levels is small,because the charge injection is a noisy process and any over-injection will lead to the expensive block erasure operation. Toremove the risk of over injection and make cell programmingmore robust and efficient, the rank modulation scheme wasThis material is based upon work supported by the National ScienceFoundation. The work of F. Zhang and H. Pfister was supported by Grant No.07407470. The work of A. Jiang was supported by grant No. 0747415 andgrant No. 0802107. Any opinions, findings, conclusions, or recommendationsexpressed in this material are those of the authors and do not necessarilyreflect the views of the National Science Foundation.Fig. 1. Block diagram for ECC with modulation codes for flash memory.proposed in [1], whereby the relative order of cell levels,instead of their absolute values, is used to represent data.Research has already been done on error-correcting codes(ECCs), rewriting codes and capacity analysis for rank mod-ulation. Based on the Kendall tau distance, error-correctingcodes for a single rank modulation block were explored in[1], [5]. In [5], a family of single-error-correcting codes wasconstructed, whose number of codewords is provably at leasthalf of optimal. In [1], the asymptotic rates of optimal ECCswere derived, and the existence of good t-error-correctingcodes was proved. Rewriting codes that enable data to berewritten without block erasures and capacity analysis werealso presented [4], [8].In this paper, we study LDPC codes for rank modulation.Compared to codes designed for a single rank modulationblock, where the cell levels are ordered into a permutation[1], [5], our LDPC code approach partitions the cells intomany small groups and uses rank modulation separately foreach group. In this work, we treat the rank modulation codeas part of the channel, as shown in Fig. 1. We consider thephysical channel together with the rank modulation encoderand decoder as the equivalent channel for the ECC. Weanalyze the equivalent channel, and study the design of goodLDPC codes for the channel. A family of symbol-flippingverification-based (SFVB) decoding algorithms is proposedand analyzed.The structure of the paper is as follows. In Section II,we study the equivalent channel model of rank modulation.Section III presents the LDPC codes design and the perfor-mance analysis for rank modulation. Section IV presents thesimulation results. Section V discusses some conclusions.II. EQUIVALENT CHANNEL OF RANK MODULATIONA. Rank ModulationConsider a group of n cells, whose levels are c1,c2,...,cn.Here ci∈ R for i =1,...,n, and represents the amountof charge stored in the i-th cell. Let Snbe the set ofISIT 2010, Austin, Texas, U.S.A., June 13 - 18, 2010859978-1-4244-7891-0/10/$26.00 ©2010 IEEE ISIT 2010m = n! permutations of length n. Specifically, we haveSn= {s1,s2, ··· ,sm} where, for i =1,...,m,si (si(1),si(2), ··· ,si(n))is a permutation of (1, 2, ··· ,n). The rank modulationscheme [4] defines a mapping RR : {(c1,...,cn) ∈ Rn}→Snas follows. If R(c1,c2,...,cn)=(i1,i2,...,in), then forany j1= j2∈{1,...,n}, ij1>ij2if and only if cj1≥ cj2.Namely, the function R ranks the n cells based on the relativeorder of their cell levels. The rank modulation scheme uses thepermutation induced by the cell levels, namely R(c1,...,cn),to represent data.Let Zm= {1, 2,...,m} be the ring of integers modulo m.Let Π be a bijection:Π:Sn→ Zm.As a modulation code, the rank modulation scheme has anencoder and a decoder, as shown in Fig. 1. Given a variablex ∈ Zmas input to the encoder, the flash memory programsthe n cells such that their cell levels (c1,...,cn) satisfyΠ(R(c1,...,cn)) = x.For the decoder, it takes the cell levels (c1,...,cn) as input,and outputs the variable Π(R(c1,...,cn)) ∈ Zm.B. LDPC Codes over Integer Rings for Rank ModulationOne way to design LDPC codes for rank modulation isto match the alphabet size of the LDPC codes and rankmodulation. We can define the LDPC code over the integerring Zm. As Fig. 1 shows. the outputs of the LDPC codeencoder are mapped to