Study On Construction And Decoding Methods Of Error-Correcting Codes Based On Rank Modulation For Flash Memories

Flash storage(also known as flash memory)system has become a very important nonvolatile storage technology because of its advantages of low energy consumption,good reliability and high storage capacity.However,as the storage capacity of the MLC flash memory increases and the size of MLC flash memory scales,the problems such as read/write disturbance,charge leakage,cell-to-cell interference and data retention noise make the data stored in flash memories damaged,which leads to the reliability of flash storage system more prominent.Error-control coding technology provides an effective way to solve these prob-lems faced by flash memories with large capacity and high reliability.However,classical error-control coding methods such as RS codes and BCH codes cannot effectively correct these special errors produced by flash memory devices with high storage capacity.There-fore,the constructions and encoding/decoding algorithms of error-correcting codes based on rank modulation scheme can be used to design error-control coding scheme for flash memories to reduce the asymmetric errors caused by the noise such as charge leakage and read/write disturbance,which improves the reliability of the data stored in flash memories.In this dissertation,the construction and decoding methods of error-correcting codes based on rank modulation scheme for flash memories are investigated.The main research results of this dissertation are summarized as follows:1.Based on permutation code interleaving,the construction method of the rank mod-ulation error-correcting code that can correct a single translocation error for cell's level of flash memory is proposed by making a detailed analysis of translocation error.By using the properties of permutation theory,the corresponding decoding method of the construct-ed rank modulation error-correcting codes is presented.The correctness of the proposed construction method and its decoding method is verified by an example.2.On the basis of analyzing in detail the construction principle of Levenshtein's permu-tation codes and interleaved permutation codes that can correct a single deletion,the array representations of the codewords for multipermutation codes are designed by using appropri-ate interleaving methods on the codewords of these two types of permutation codes.Based on the design ideas of Levenshtein's permutation codes and interleaved permutation codes,three types of construction methods for multipermutation codes that can correct a predeter-mined number of adjacent deletions are proposed with the aid of these array representations.Moreover,the corresponding decoding methods of these three kinds of multipermutation codes are presented,and the correctness and effectiveness of the proposed three construc-tion methods and their decoding methods are verified by some examples.3.After making a detailed analysis of the impact of a burst of deletions on the rest com-ponents in the codeword of multipermutation codes,based on the interleaving of t single-deletion-correcting multipermutation codes,we present a construction of multipermutation codes for correcting a burst of at most t deletions with shift magnitude one for t ?>2.More-over,an effective decoding method is proposed for the constructed multipermutation codes.The correctness of the proposed construction method and its decoding method is verified by an example.4.Under the Chebyshev distance metric,a simple construction method for regular mul-tipermutation codes is proposed by using the direct product opertation on multipermutation sets which correspond to the designed first class of multisets and have the identical mini-mum distance.Moreover,the multipermutation sets with different minimum distances are obtained by using the projection operation on the existing simple regular multipermutation codes from the designed second class of multisets.Based on the direct product opertation on these multipermutation sets,a new construction method for regular multipermutation codes is proposed.The proposed construction methods are provided to verified by some examples.