Error correcting codes for insertion and deletion of a symbol were first introduced by Levenshtein. Since then many researchers, including Hendrik Ferreira and his group, have extended these code design methods Let Z2∗ be the set of all finite length binary sequences def where Z2 = {0,1}. In this paper, we are interested in the efficient design of binary block codes capable of correcting t∈N or less deletions or insertions of a fixed binary symbol, say 0∈Z2. Even though the general problem of designing asymptotically optimal codes capable of correcting at most t deletions or insertions of a symbol appears to be very difficult some efficient solutions have been given recently for the particular problems of correcting the 0- insertion errors (i. e., the insertion of 0’s only) and the 0-errors (i. e., the deletion or insertion of 0’s). In this paper, we have given systematic codes capable of correcting t 0-errors and more. In particular, given t, k ∈ N, an efficient recursive method is presented to encode k information bits into a systematic t-0EC/(t+1)-0ED/AU0ED code oflengthn=k+r∈Nwheretheredundancyis r = t log2 n + o(t log n), as max{t, k} increases.
Systematic Error Correcting Codes for Insertion/Deletion of Zeros
Tallini, Luca G.;
2019-01-01
Abstract
Error correcting codes for insertion and deletion of a symbol were first introduced by Levenshtein. Since then many researchers, including Hendrik Ferreira and his group, have extended these code design methods Let Z2∗ be the set of all finite length binary sequences def where Z2 = {0,1}. In this paper, we are interested in the efficient design of binary block codes capable of correcting t∈N or less deletions or insertions of a fixed binary symbol, say 0∈Z2. Even though the general problem of designing asymptotically optimal codes capable of correcting at most t deletions or insertions of a symbol appears to be very difficult some efficient solutions have been given recently for the particular problems of correcting the 0- insertion errors (i. e., the insertion of 0’s only) and the 0-errors (i. e., the deletion or insertion of 0’s). In this paper, we have given systematic codes capable of correcting t 0-errors and more. In particular, given t, k ∈ N, an efficient recursive method is presented to encode k information bits into a systematic t-0EC/(t+1)-0ED/AU0ED code oflengthn=k+r∈Nwheretheredundancyis r = t log2 n + o(t log n), as max{t, k} increases.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
