Every Bit Counts: A New Version of Non-binary VT Codes with More Efficient Encoder

Abstract

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.