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

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 $\text{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.