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

2022/12/21 by Nguyen, Tuan Thanh, Cai, Kui, Siegel, Paul H.
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.2212.10721

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≥ 2 with at most \ceillog_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 2log₂ q+3 redundant bits.

Related

• Efficient Systematic Encoding of Non-binary VT Codes
• A New Version of q-ary Varshamov-Tenengolts Codes with More Efficient Encoders: The Differential VT Codes and The Differential Shifted VT Codes
• New Construction of q-ary Codes Correcting a Burst of at most t Deletions
• Non-binary Two-Deletion Correcting Codes and Burst-Deletion Correcting Codes
• Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions