Deletions and Insertions of the Symbol “0” and Asymmetric/Unidirectional Error Control Codes for the L 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 $L_{1}$ metric asymmetric error control codes over the natural alphabet, ${mathbf{I}}!{mathbf{I}}!!{mathbf{N}}$ . 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 $L_{1}$ 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).