Research On Construction Methods Of Rank Modulation Codes

As the storage density of NAND flash memory increases,the reliability of the data stored in the cells has become one of the important problems in the research and application for the large-capacity storage system of flash memories.Since the information is stored by the relative ranking of the cells' charge levels,rather than by the absolute values of the charge levels,the rank modulation scheme can eliminate the risk of cell over-programming and reduce the effects of asymmetric errors.Thus,every group of cells induces a permutation,which is derived by the ranking of the level of each cell in the group.The problems of overprogramming and charge leakage in flash memory can be alleviated by permutation codes and multi-permutation codes based on rank modulation scheme.Therefore,error-correcting codes based on rank modulation scheme have received much attention.In recent years,the study on permutation codes and multi-permutation codes mainly focuses on the constructions of error-correcting codes and related decoding methods.In the dissertation,the construction and decoding methods of permutation codes and multi-permutation codes based on rank modulation scheme in flash memories are studied.The main results of the dissertation are summarized as follows:1.Limited-magnitude errors in cell charge levels can be characterized by the Chebyshev metric.For the problem that a kind of existing(7)n(10)k,k!,d(8)systematic permutation codes which can correct limited-magnitude errors lacks encoding and decoding procedures under the Chebyshev metric,an encoding method of these systematic permutation codes is proposed by using the ranking mapping of the permutations and the interleaving techniques of(7)n,M,d(8)permutation codes under the Chebyshev metric.Moreover,a decoding method for the(7)n(10)k,k!,d(8)systematic permutation codes is presented by using the unranking mapping of the permutations and the projection technology for(7)n,M,d(8)permutation codes under the Chebyshev metric.The correctness of the proposed encoding and decoding methods for systematic permutation codes is verified by some calculation examples.2.By constructing a subgroup code and using its coset codes to partition the set of information permutations,a new construction of(7)k(10)n,k!,d(8)systematic error-correcting codes for permutations is presented under the Chebyshev distance.Compared with the existing systematic error-correcting codes for permutations,the proposed code construction can achieve much larger code cardinality and hence higher code rates.To facilitate the encoding and decoding of the constructed codes,we also investigate the concepts of ranking and unranking for permutations,and generalize them to M-ranking and M-unranking for multi-permutations.Based on these mapings,the encoding/decoding algorithms of the proposed systematic permutation codes are presented.Moreover,examples are provided to demonstrate the encoding/decoding algorithms.3.For the problem of a single burst symbol-invariant deletion(SID)error in rank modulation codes for flash memories,by interleaving techniques for permutations,we construct two classes of permutation codes which can correct a single burst symbol-invariant deletion(SID)of length up to t.Moreover,a class of balanced multi-permutation codes capable of correcting a single burst SID of length up to t is presented.The simple decoding procedures for the constructed codes are included in proofs and verified by examples.4.For the problem of a single burst unstable erasure(BUE)error in multi-permutaiton codes,we propose a new rank demodulation method of cell states to transform the problem of a single burst unstable erasure(BUE)in a t-balanced multi-permutation into the sub-problems of a single permutation-invariant erasure(PIE)in t permutations.Based on the rank demodulation method,we propose two classes of t-balanced multi-permutation codes to correct a single BUE of length up to t by interleaving t single-PIE-correcting permutation codes.The decoding methods for the proposed codes are included in the proofs and demonstrated by examples.