Efficient code designs of deletion/insertion of 0's errors, constant L1-weight codes and elementary symmetric polynomials (ad invito)

This talk 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 controlling much more; namely, they can correct at most t 0-errors, detect at most (t+1) 0-errors and, simultaneously, detect all occurrance 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-errors correcting codes. Optimal non-systematic and systematic code designs are given. In particular, for t in N, a recursive method is presented to define a family of systematic t-Sy0EC/(t+1)-Sy0ED/AU0ED codes with k in N information bits and length n=k+r in N where the redundancy is r=t*log_{2}k+o(t*log n), as max{t,k} increases. Decoding can be efficiently performed by algebraic means with the Extended Euclidean Algorithm (EEA).