Systematic Codes Correcting Multiple-Deletion and Multiple-Substitution Errors

We consider construction of deletion and substitution correcting codes with low redundancy and efficient encoding/decoding. First, by simplifying the method of Sima et al. (ISIT 2020), we construct a family of binary single-deletion 8-substitution correcting codes with redundancy (s + 1) (2s + 1) log(2) n + o(log(2) n) and encoding complexity O(n(2)), where n is the blocklength of the code and s >= 1. The construction can be viewed as a generalization of Smagloy et al.'s construction (ISIT 2020), and for the special case of s = 1, our construction is a slight improvement in redundancy of the existing works. Further, we modify the syndrome compression technique by combining a precoding process and construct a family of systematic t-deletion 8-substitution correcting codes with polynomial time encoding/decoding algorithms for both binary and nonbinary alphabets, where t >= 1 and s >= 1. Specifically, our binary t-deletion 8-substitution correcting codes of length n have redundancy (4t + 3s) log(2) n + o(log(2) n), whereas, for q being a prime power, the redundancy of q-ary t-deletion 8-substitution codes is asymptotically (4t + 4s - 1 - [2s-1/q]) log(q) n + o(log(q) n) as n -> infinity. We also con- struct a family of binary systematic t-deletion correcting codes (i.e., s = 0) with redundancy (4t - 1) log(2) n + o(log(2) n). The proposed constructions improve upon the redundancy of the state-of-the-art constructions.

Automated summary

This paper explores the construction of deletion and substitution correcting codes with low redundancy and efficient encoding/decoding. By simplifying existing methods and modifying syndrome compression techniques, a family of binary deletion and substitution correcting codes is proposed, with slight improvements for specific cases, as well as systematic deletion correcting codes being constructed.