Study On Construction And Decoding Methods Of Insertion/Deletion Error Correcting Codes

Due to the influence of timing noise caused by timing uncertainty,synchronization errors often occur when some bits are inserted or deleted in the information sequence transmitted/stored by the communication/storage system.In general,insertion/deletion errors will have disastrous consequences for information transmission/storage.Some application scenarios that may cause insertion/deletion errors are DNA-based data storage system,high-density magnetic storage technology bit format media and non-volatile storage technology track storage.In the big data era of information explosion,people are increasingly demanding information transmission rate and information storage capacity.The insertion,deletion,and substitution errors that widely occur in DNA data storage systems are a challenge for system design.System design must take some technical means to overcome insertion,deletion and substitution errors,and error correcting codes technology to overcome these errors is a feasible technical solution.Therefore,detailed research on correcting insertion/deletion/substitution error coding technology will increase the flexibility of storage and communication system design and reduce the construction cost.However,the current understanding of insertion/deletion error-correcting codes is not detailed enough and many basic problems remain unresolved.Therefore,it is necessary to study the construction and decoding methods of error correcting insertion/deletion codes and improve the theoretical system of error control coding.In this thesis,the construction methods and decoding algorithms of q-ary codes for correcting single deletion errors and codes for correcting two insertion/deletion errors are deeply studied.The main research results of the paper are as follows:1.The basic concepts of deletion/insertion error correcting codes and the properties of optimal codes and perfect codes are described in detail.The construction and decoding method of VT codes in algebraic construction codes are mainly analyzed.Moreover,two simple and general error correcting codes construction and extension algorithms are given.2.For correcting single deletion error q-ary codes,a construction algorithm for correcting deletion error codes based on graph theory is proposed by converting the construction problem of deletion correcting codes into the problem of solving the maximum independent set on the graph.Then,based on the construction idea of deletion correcting codes introduced above and non-binary VT codes,a construction algorithm of correcting single deletion error q-ary codes with larger cardinality is proposed.The numerical results show that,compared with the non-binary VT codes,the proposed q-ary codes for correcting single deletion error has a larger base number.3.On the basis of detailed analysis of the existing construction ideas of correcting two deletion error codes,a 2-list decoding algorithm based on run is designed to correct two deletion error codes.Then,by extending the construction idea of correcting two deleted error codes to correcting two inserted error codes,a construction method of correcting two inserted error codes based on run and its 2-list decoding algorithm are proposed.At the same time,in order to correct the shortcoming that the 2-list decoding algorithm of two delete error codes can not be uniquely decoded,the error detection method of delete error is given,which reduces the number of sequences that cannot be uniquely decoded in 2-list decoding.Simulation results show that the proposed error detection method CRC can greatly reduce the number of sequences that cannot be uniquely decoded by 2-list decoding method.