Please use this identifier to cite or link to this item:
Title: Codes correcting bursts of deletions/insertions and tandem duplications
Authors: Nguyen, Tuan Thanh
Keywords: DRNTU::Engineering::Computer science and engineering::Data::Coding and information theory
DRNTU::Science::Mathematics::Discrete mathematics::Combinatorics
Issue Date: 2018
Source: Nguyen, T. T. (2018). Codes correcting bursts of deletions/insertions and tandem duplications. Doctoral thesis, Nanyang Technological University, Singapore.
Abstract: 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.
DOI: 10.32657/10220/47179
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Theses

Files in This Item:
File Description SizeFormat 
THANHthesisfinal.pdfFinal version of Phd thesis855.23 kBAdobe PDFThumbnail

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.