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

arXiv2212.10721MaRDI QIDQ6421170FDOQ6421170

Authors: Tuan Thanh Nguyen, Kui Cai, Paul Siegel 

Publication date: 20 December 2022

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 $qge2$ with at most $ceillo{g}_{q}n+1$ redundant symbols, while the optimal redundancy required is at least $lo{g}_{q}n+lo{g}_q(q-1)$ symbols. Our designed encoder reduces the redundancy of the best-known encoder of Tenengolts (1984) by at least $2+lo{g}_q(3)$ redundant symbols, or equivalently $2lo{g}_{2}q+3$ redundant bits.

This page was built for publication: Every Bit Counts: A New Version of Non-binary VT Codes with More Efficient Encoder

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6421170)