Multiple insertion/deletion correcting and detecting codes : structural analysis, constructions and applications
- Authors: Paluncic, Filip
- Date: 2012-08-01
- Subjects: Error-correcting codes (Information theory) , Coding theory , Engineering mathematics
- Type: Thesis
- Identifier: uj:8894 , http://hdl.handle.net/10210/5366
- Description: D.Ing. , This thesis is dedicated to an analysis of fundamental topics and issues related to deterministic insertion/deletion correcting and detecting codes. The most important contributions in this respect are the construction of a multiple insertion/deletion correcting code for run-length limited sequences and the construction and applications of multiple deletion (insertion) detecting codes. It is shown how run-length constraints and higher order moments can be combined to create a code which is simultaneously multiple insertion/deletion error correcting and runlength constrained. A systematic form of this code is presented, whereby any arbitrary run-length constrained sequence can be made into a multiple insertion/deletion correcting codeword by adding a prefix. This prefix is appended to the run-length constrained sequence in such a way that the resulting codeword is itself run-length constrained. Furthermore, it is shown that, despite the run-length constraints, the resulting code is guaranteed to have a better asymptotic rate than the Helberg code, the only other known non-trivial deterministic multiple insertion/deletion correcting code. We consider insertion/deletion detecting codes and present a multiple deletion (insertion) detecting code. It is shown that this code, which is systematic, is optimal in the sense that there exists no other systematic multiple deletion (insertion) detecting code with a better rate. Furthermore, we present a number of applications of such codes. In addition, further related topics of interest are considered. Firstly, jitter as a fundamental cause of insertion/deletion errors is investigated and as a result a counterpart to the signal-to-noise ratio in the amplitude domain is proposed for the time domain. Secondly, motivated by the correspondence of Levenshtein and Varshamov-Tenengol’ts codes, we investigate the insertion/deletion correcting capability of the single asymmetric error correcting Constantin-Rao codes within a wider framework of asymmetric error correcting and insertion/deletion correcting code structure correspondences. Finally, we propose a generalisation of Tenengol’ts’ construction for multiple non-binary insertion/deletion correction.
- Full Text:
A note on non-binary multiple insertion/deletion correcting codes
- Authors: Paluncic, Filip , Swart, Theo G. , Weber, Jos H. , Ferreira, Hendrik C. , Clarke, Willem A.
- Date: 2011
- Subjects: Insertion/deletion , Correcting codes
- Language: English
- Type: Conference proceedings
- Identifier: http://hdl.handle.net/10210/20202 , uj:16077 , ISBN: 978-1-4577-0437-6 , Citation: Paluncic, F. et al. 2011. A note on non-binary multiple insertion/deletion correcting codes. Proceedings of the IEEE Information Theory Workshop, 16-20 October, 2011, Paraty, Brazil.
- Description: Abstract: We propose the construction of a non-binary multiple insertion/deletion correcting code based on a binary multiple insertion/deletion correcting code. In essence, it is a generalisation of Tenengol’ts’ non-binary single insertion/deletion correcting code. We evaluate the cardinality of the proposed construction based on the asymptotic upper bound on the cardinality of a maximal binary multiple insertion/deletion correcting code derived by Levenshtein.
- Full Text:
Moment balancing templates for insertion/deletion correction
- Authors: Paluncic, Filip
- Date: 2010-02-24T08:42:11Z
- Subjects: Error-correcting codes (Information theory)
- Type: Thesis
- Identifier: uj:6642 , http://hdl.handle.net/10210/3042
- Description: M.Ing. , In practice, channels with only insertions and deletions are rare. More commonly, additive errors are also present. Therefore, additional redundancy bits are added to the encoded data stream to allow for insertion/deletion correction. In this dissertation, moment balancing templates are used to add a single insertion/deletion capability to an arbitrary additive-error-correcting code. Moment balancing can be used for systematic encoding of number-theoretic codes. The selection of a particular additive-error-correcting codebook has potential influence on the moment balancing template. In direct relation to this, partition distributions of linear sets are considered and their connection to moment balancing templates illustrated. As an alternative to fixed length moment balancing templates, a variable length approach to moment balancing is also considered. It is shown that variable length moment balancing templates result in better performance, in terms of redundancy, than the optimal fixed length moment balancing template. It is assumed that the boundaries of variable length Levenshtein codewords are known. To implement the variable length template in practice, multiple markers are needed. The delimitation of variable length codeword boundaries with these markers leads to longer marker sequences as compared with the fixed length templates.
- Full Text: