Efficient 0-insertion/deletion error control codes based on Reed-Solomon codes

This paper gives some efficient designs for binary block codes capable of controlling 0-errors, namely, the deletion of the symbol "0"(termed 0-deletions) and/or the insertion of the symbol "0"(termed 0-insertions). Based on Reed-Solomon codes, for all t, k ∈ N - {0}, efficient designs are provided for t-Sy0EC constant weight codes with k information bits and length n ∈ N bits. These codes are self synchronizing and can correct t 0-errors, detect (t +1) 0-errors, and simultaneously detect all occurrences of either only 0-insertions or only 0-deletions in every received word (i. e., they are t-Sy0EC/(t + 1)-Sy0ED/AU0ED). The length of the proposed codes is n(t, k) = k + O(t log log n) whenever 1/[C log2 log2 (k + t)] ≲ k/t = O(log log n), where C ∈ R+ is a positive real constant. Hence, if t is sufficiently large so that t = Ω(k/log log n), but t < Cklog2 log2(k +t) then the redundancy, r = n - k, scales as O(t log log n). This result is remarkable as it demonstrates that, for certain large values of t, the optimal asymptotic redundancy is lower than the well known t log n asymptotic redundancy achieved for small values of t.