Deletions and Insertions of the Symbol “0” and Asymmetric/Unidirectional Error Control Codes for the L1 Metric

This paper gives some theory and efficient design of binary block codes capable of controlling 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 controlling 0-deletions and/or 0-insertions (referred to as 0-errors) is shown to be equivalent to the efficient design of L1 metric asymmetric error control codes over the natural alphabet, IN. In this way, it is shown that the t 0-insertion correcting codes are actually capable of controlling much more; namely, they can correct t 0-errors, detect (t + 1) 0-errors and, simultaneously, detect all occurrences of only 0-deletions or only 0-insertions in every received word (briefly, they are t-Symmetric 0-Error Correcting/(t + 1)-Symmetric 0-Error Detecting/All Unidirectional 0-Error Detecting (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. Optimal non-systematic code designs are given. Decoding can be efficiently performed by algebraic means using the Extended Euclidean Algorithm (EEA).