Study On Construction Methods Of Error-Correcting Codes Under Rank Modulation Scheme

Nowadays,flash devices with high storage density,good reliability and high performance have been widely used in mobile computing,embedded systems and cloud storage systems.Multi-level cell(MLC)technology can improve the storage density of flash memories.However,noises such as charge leakage and reading-writing interference may damage the data of MLC flash memories which can lead to right translocation errors,regular translocation errors,burst stable erase errors and burst unstable erase errors.Therefore,MLC flash memory systems are facing with the reliability problem of data storage.Permutation codes and multi-permutation codes based on rank modulation scheme can improve the reliability and the storage efficiency of flash memories.By using the relative level of charge voltage between MLC flash memory cells to represent data,rank modulation scheme stores information in the form of permutations or multi-permutations.In recent years,the construction and decoding methods of permutation codes and multi-permutation codes based on rank modulation scheme have become an important study direction in the field of errorcontrol coding for flash memories.However,for right translocation errors,regular translocation errors and burst stable erase errors,there is no study on multi-permutation codes which can correct these errors.In this thesis,some construction methods of permutation codes and multi-permutation codes based on rank modulation scheme are studied.The main study results are as follows:1.By analyzing right translocation errors and regular translocation errors of multipermutations under rank modulation scheme,the construction methods of multi-permutation codes which can correct a single right/regular translocation error are proposed by using partition method of multiple sets and interleaving strategy of multi-permutations.The proposed multi-permutation codes have simple decoding methods.At the same time,the correctness of the construction and decoding methods of two kinds of permutation codes is verified by some examples.2.By making a detailed analysis of the attributes of single burst stable erasure error and single burst unstable erasure error in flash memory cells,two construction methods of permutation codes which can correct a single burst of stable/unstable erasures are proposed by using interleaving technology of permutation codes.The correctness and effectiveness of the construction and decoding methods of two kinds of permutation codes are verified by some examples.Performance analysis shows that the two kinds of permutation codes are asymptotically optimal.3.For the model of single burst stable erasure error in flash memory cells,a construction method of multi-permutation codes which can correct a single burst of stable erasures is proposed by using interleaving technology of permutation codes.For the model of a single burst of unstable erasures in flash memory cells,the construction and decoding methods of multi-permutation codes which can correct a single burst of unstable erasures are proposed by using a new rank demodulation scheme,and the multi-permutation codes have simple decoding methods.Moreover,it is proved that the proposed multi-permutation codes are asymptotically optimal.