Codes correcting bursts of deletions/insertions and tandem duplications

• Main Author: Nguyen, Tuan Thanh
• Other Authors: Chee Yeow Meng
• Format: Theses and Dissertations
• Language: English
• Published: 2018
• Subjects: DRNTU::Engineering::Computer science and engineering::Data::Coding and information theory; DRNTU::Science::Mathematics::Discrete mathematics::Combinatorics
• Online Access: https://hdl.handle.net/10356/89953; http://hdl.handle.net/10220/47179
• Institution: Nanyang Technological University

Error-correcting codes have played an important role in improving efficiency and reliability in classical communication and data storage systems. This thesis is devoted to the design of error-correcting codes to combat the most crucial errors that arose from modern communication and data storage systems such as deletions, insertions, duplications (a special type of insertions), and we refer them as codes correcting edits. Designing codes correcting deletion and insertion errors has been the subject of a large body of works in the literature and to the best of our knowledge, there exist only constructions for optimal codes capable of correcting a single deletion or single insertion in permutation codes and q-ary codes. The research on codes combatting multiple errors is very limited. The main objective of this thesis is to design codes capable of correcting burst errors, i.e. those errors that occur at adjacent positions. Throughout this thesis, we propose several constructions of burst deletion/insertion-correcting codes over permutations, multipermutations or more generally, over a q-ary alphabet. Special attention is given to the case of burst deletion-correcting codes in permutations and multipermutations. Here, such codes improve the reliability and memory endurance of non-volatile memories such as flash memories. Besides code constructions, we also provide efficient error decoders to recover codewords from errors with linear-time complexity. In addition, we introduce codes correcting tandem duplications, a special type of insertion errors, that has applications that store data in living organisms. We are concerned with designing efficient channel encoders (or source decoders) that encode (decode) any arbitrary sequence (arbitrary codeword) to a corresponding codeword in our design codes (to the original sequence) with the purpose of achieving high rate and low complexity. Our encoding/decoding algorithms are based on enumerative coding, finite-state machine, and algebraic number theory. While these techniques are standard in constrained coding and combinatorics literature, our contribution is a detailed analysis of the space and time complexities of the respective algorithms.