New Construction of q-ary Codes Correcting a Burst of at Most t Deletions
Wentu Song, Kui Cai, Tony Q. S. Quek · 2024
In this paper, for any fixed integer$q > 2$, we construct q-ary codes correcting a burst of at most$t$deletions with redundancy$\log n+8$log log$n$+ o(log log$n) >+\gamma_{q,t}$bits and near-linear encoding/decoding complexity, where$n$is the message length and$\gamma_{q,t}$is a constant that only depends on$q$and$t$. In previous works there are constructions of such codes with redundancy$\log n+O$(log$q$log log n) bits or$\log n+O$($t$2log log n)$+O(t\log q)$. The redundancy of our new construction is independent of$q$and$t$in the second term.