タイトル : Systematic Codes Correcting Multiple-Deletion and Multiple- Substitution Errors 著者名 : Wentu Song; Nikita Polyanskii; Kui Cai; Xuan He 雑誌名 : IEEE Transactions on Information Theory 号数 : - DOI: 10.1109/TIT.2022.3177169 Abstract : 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 s-substitution correcting codes with redundancy (s + 1)(2s + 1) log2 n+o(log2 n) and encoding complexity O(n2), 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 s-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 s-substitution correcting codes of length n have redundancy (4t + 3s) log2 n + o(log2 n), whereas, for q being a prime power, the redundancy of q-ary t-deletion s-substitution codes is asymptotically (4t+4s-1-⌊2s-1/q⌋) logq n+o(logq n) as n → ∞. We also construct a family of binary systematic t-deletion correcting codes (i.e., s = 0) with redundancy (4t-1) log2 n+o(log2 n). The proposed constructions improve upon the redundancy of the state-of-the-art constructions.