Research On Encoding And Decoding Algorithms For Binary Codes Correcting Multiple Insertion/Deletion Errors

Insertion/deletion errors,that is,inserting or deleting some information symbols in the process of information transmission.That causes the sending sequence and the receiving sequence to be out of synchronization.With the increase in the transmission rate of communication systems and storage capacity,modern communication systems and storage systems have more and more stringent requirements for information synchronization.While receiving symbols,it is difficult for receiver to keep information synchronization because of physical constraints.Insertion/deletion errors often occur in high-density magnetic storage systems,racetrack memory,DNA storage,RFID communications,and file synchronization systems.Failure to synchronize may result in disastrous consequences for the transmission and storage of information.In order to use cheap hardware and smaller large-capacity data storage devices,it is necessary to improve the error correction codes to solve the shortcomings of the present technologies.Constructing efficient codes that corrects insertion/deletion errors can improve the reliability of related system and simplify the system design.As early as the 1960 s,scholars proposed that Varshamov-Tenengolts(VT)codes can be used to correct single insertion/deletion error with the best asymptotic code rate.However,how to construct the code which can correct multiple insertion/deletion errors with the better code rate has always been an open issue.In recent years,with the design requirements of new storage systems and high-speed wireless communication systems,researchers have begun paying attention to error correction code techniques with good performance and capability of correcting multiple insertion/deletion errors.This thesis mainly studies on some construction and decoding methods of correcting multiple insertion/deletion errors for binary codes.The main results are as follows:1.In-depth analysis of the segmented insertion/deletion error models.By changing the prefix of the present correcting segmented insertion/deletion error codes,an improved correcting segmented insertion/deletion binary code construction method is proposed with a specific decoding algorithm.Some examples and simulation results show that the proposed scheme has better code rate and lower decoding complexity.2.Analyzed the Guess & Check(GC)code scheme,which based on the concatenation encoding of system MDS codes and repeated codes.Proposed an improved GC code scheme based on Marker codes from the perspective of reducing the number of possible cases.Compared with GC codes,when the code length is short,the new scheme can correct constant deletions with lower decoding complexity.3.Aiming at the possible problem of wrong matching phenomenon of Marker sequence in the decoding algorithm of new scheme,the other improved GC code encoding and decoding scheme which based on Buffer Encoding Method is proposed.The second-order improved scheme uses a encoding method based on mapping a buffer string,which effectively solves the problem of wrong matching phenomenon of Marker sequence.Simulation results show that the second-order scheme can significantly improve the decoding reliability.