Technical Program

Paper Detail

Paper Title On Deletion/Insertion of Zeros and Asymmetric Error Control Codes
Paper IdentifierTH4.R5.4
Authors Luca Tallini, Università degli Studi di Teramo, Italy; Nawaf Alqwaifly, Bella Bose, Oregon State University, United States
Session Insertion-Deletion Correcting Codes II
Location Saint Victor, Level 3
Session Time Thursday, 11 July, 16:40 - 18:00
Presentation Time Thursday, 11 July, 17:40 - 18:00
Manuscript  Click here to download the manuscript
Abstract This paper gives some theory and efficient design of binary block codes capable of correcting the deletions of the symbol “0” (referred to as 0-deletions) and/or the insertions of the symbol “0” (referred to as 0-insertions). This problem of correcting 0-deletions and/or 0-insertions (referred to as 0-errors) is shown to be equivalent to the efficient design of some L1 metric asymmetric error control codes over the natural alphabet, N. In particular, it is shown that t 0-insertion correcting codes are actually capable of correcting t 0-errors, detecting (t+1) 0-errors and, simultaneously, detecting all occurrences of only 0-deletions or only 0-insertions in every received word (briefly, they are t-Sy0EC/(t+1)-Sy0ED/AU0ED codes). From the relations with the L1 distance error control codes, new improved bounds are given for the optimal t 0-error correcting codes. In addition, some optimal non-systematic code designs are also given. Decoding can be efficiently performed by algebraic means with the Extended Euclidean Algorithm.