论文标题
系统的单删除多重物质纠正代码
Systematic Single-Deletion Multiple-Substitution Correcting Codes
论文作者
论文摘要
Smagloy等人的最新工作。 （ISIT 2020）表明，单删除$ s $ substitution校正代码的冗余至少$ $（s+1）\ log n+o（\ log n）$，其中$ n $是代码的长度。他们还提供了单台上和单物质代码的构造，其冗余$ 6 \ log n+8 $。在本文中，我们提出了一个系统的单位单位$ s $ s $ subSubStitution纠正长度$ n $的代码，最多$ n $，最多$ n $（3s+4）\ log n+n+o（\ log n）$和多项式编码/解码复杂性，其中$ s \ geq 2 $是常数。具体而言，提出的代码的编码和解码复杂性分别为$ O（n^{s+3}）$和$ o（n^{s+2}）$。
Recent work by Smagloy et al. (ISIT 2020) shows that the redundancy of a single-deletion $s$-substitution correcting code is asymptotically at least $(s+1)\log n+o(\log n)$, where $n$ is the length of the codes. They also provide a construction of single-deletion and single-substitution codes with redundancy $6\log n+8$. In this paper, we propose a family of systematic single-deletion $s$-substitution correcting codes of length $n$ with asymptotical redundancy at most $(3s+4)\log n+o(\log n)$ and polynomial encoding/decoding complexity, where $s\geq 2$ is a constant. Specifically, the encoding and decoding complexity of the proposed codes are $O(n^{s+3})$ and $O(n^{s+2})$, respectively.
