Asymptotically optimal sticky-insertion-correcting codes with efficient encoding and decoding
Hessam Mahdavifar, Alexander Vardy · 2017
The problem of constructing sticky-insertion-correcting codes with efficient encoding and decoding is considered. An {n, M, r) sticky-insertion-correcting code consists of M codewords of length n such that any pattern of up to r sticky insertions can be corrected. We utilize BCH codes and their analogous in the Lee space to construct explicit and systematic codes that are immune to up to r sticky insertions. It is shown that the ratio of the number of constructed redundancy bits in the construction to a certain upper bound approaches one as the block length grows large, which implies asymptotic optimality of the construction.