Study On Construction And Decoding Methods Of Deletion Correcting Codes

As the data transfer rate and storage capacity increase in communication and storage systems,the receiver fails to recover synchronization due to timing defects,time noise and the limitation of the manufacture technics,etc.It typically manifests itself in the deletion or the insertion of several symbols for the synchronization errors in the transmission or storage sequence.Moreover,for disconnected,intermittent,and low-bandwidth environments,these insertion or deletion errors manifest themselves in bursts where the errors tend to cluster together from the perspective of the communication systems,which are also called burst insertion or burst deletion errors.The representative systems that may involve insertion or deletion errors include high-density magnetic storage system,racetrack memory,and DNA storage.In general,because the channel that produces insertion/deletion error has memory,the traditional error correcting code technology for the memoryless channel is difficult to directly apply to correct insertion/deletion error.Therefore,the study of constructing codes capable of correcting insertion/deletion errors and devising its encoding and decoding algorithms has received extensive attention from scholars in recent years.Constructing codes that can correct multiple insertion/deletion errors is a challenging problem since a relatively small number of insertion/deletion errors may cause the transmitted and received sequence to be vastly different,although Levenshtein proved that the VT code can correct single insertion/deletion error in the 1960 s.In the thesis,the construction and decoding methods of the codes correcting single burst of deletion errors and the GC(Guess & Check)codes based on VT syndromes that can correct multiple deletion errors with high probability are investigated in detail.The main research results of the thesis are as follows:1.The basic concepts of linear block codes and the construction methods of two typical linear block codes that include BCH code and RS code are described in detail.Moreover,the construction and decoding methods of binary VT codes and non-binary Tenengolts codes that can correct single insertion/deletion errors are analyzed in detail.2.For single b-burst deletion errors,by interleaving exponential coefficient codes/odd coefficient codes with higher code rate and RLL-VT codes,the construction methods of two codes capable of correcting single b-burst deletion errors are proposed,and the corresponding decoding algorithms are given.The analysis shows that compared with the existing codes capable of correcting single b-burst deletion errors,the constructed code can improve the code rate in a relatively short code length range.Moreover,the correctness of these construction methods and their decoding algorithms are verified with examples.3.On the basis of analyzing the construction principle of the GC codes that can correct multiple deletion errors with high probability in detail,a single-layer VT syndromes-based GC codes and its encoding and decoding methods are proposed by adding the VT syndromes to the GC codes.Simulation results show that compared with the GC codes,the single-layer VT syndromes-based GC codes can not only significantly reduce the decoding time,but also reduce the probability of decoding failure.Moreover,by extending the structure of singlelayer VT syndromes to the structure of intersecting double-layer VT syndromes,a doublelayer VT syndromes-based GC codes and its encoding and decoding methods are proposed,which further reduces the decoding time.