论文标题
每个位都计数：具有更有效编码器的非二进制VT代码的新版本
Every Bit Counts: A New Version of Non-binary VT Codes with More Efficient Encoder
论文作者
论文摘要
在这项工作中，我们提出了一个新版本的非二进制VT代码，该代码能够纠正单个删除或单个插入。此外，我们提供了第一个已知的线性时间算法，该算法将用户消息编码为$ q $ -ary -arphabet的这些长度n代码，最多$ q \ ge 2 $使用$ \ ceil {\ log_q n} + 1 $冗余符号，而最佳冗余符号至少是$ \ log_q n + log_q n + log_q qu（1）$ 1）。我们设计的编码器将Tenengolts（1984）最著名编码器的冗余减少至少$ 2+\ log_q（3）$冗余符号，或等效于$ 2 \ log_2 q+3 $冗余位。
In this work, we present a new version of non-binary VT codes that are capable of correcting a single deletion or single insertion. Moreover, we provide the first known linear time algorithms that encode user messages into these codes of length n over the $q$-ary alphabet for $q\ge 2$ with at most $\ceil{\log_q n} + 1$ redundant symbols, while the optimal redundancy required is at least $\log_q n + \log_q (q - 1)$ symbols. Our designed encoder reduces the redundancy of the best-known encoder of Tenengolts (1984) by at least $2+\log_q(3)$ redundant symbols, or equivalently $2\log_2 q+3$ redundant bits.
