Study On Synchronization Error Correcting Codes In DNA Storage

With the rapid development of science and technology,data storage technology has made great progress.However,the advent of the era of big data brings new challenges to traditional storage media.With the increasing amount of data,hard disk,flash memory and other devices can not meet the needs of people for data storage.The DNA chain of DNA storage system has ultra-high storage density,which has been widely concerned by many scholars.However,edit errors may occur in DNA sequence synthesis and sequencing,resulting in disastrous consequences for DNA storage system.Edit errors are mainly manifested in the insertion,deletion or substitution errors of some bases in the stored DNA sequence,namely,insertion,deletion and substitution errors.Error correction coding technology provides an effective way to solve the insertion,deletion or substitution errors in DNA storage system.Moreover,efficient error correcting codes can improve the reliability of DNA storage systems.Therefore,the research on the construction and decoding methods of error correcting codes for insertion,deletion or substitution in DNA storage wide attention of scholars in recent years.This thesis mainly studies the construction and decoding method of insertion/deletion/substitution error codes in DNA storage system.The main research results are as follows :1.The basic concepts of linear block codes and the construction of Knuth balanced codes are expounded.Moreover,the construction and decoding algorithm of binary VT codes which can correct single insertion/deletion error are analyzed.2.Aiming at the problem of random access in DNA storage system,a random access code for single edit error correcting in DNA storage system is proposed by interleaving the code for single edit error correcting in DNA storage system and the coding scheme of random access code proposed by Yazdi et al.The simulation results show that compared with the existing codes for single edit error correcting in DNA storage,the code access time constructed in this paper is significantly reduced when accessing DNA storage system,and the single edit error in DNA storage system can be corrected.3.Aiming at the problem of high error probability of HEDGES code decoding algorithm for correcting multiple edit errors in DNA storage system,an improved decoding algorithm for HEDGES code is proposed by selecting two nodes with the smallest weight in the search tree for the next bit prediction.Simulation results show that compared with the original HEDGES decoding algorithm,the improved decoding algorithm proposed in this thesis can further reduce the error probability in decoding.