Some New Constructions of q-ary Codes for Correcting a Burst of at Most t Deletions - Wentu Song; Kui Cai; Tony Q. S. Quek (Entropy)
In this paper, we construct q-ary codes for correcting a burst of at most t deletions, where <semantics>t,q≥2</semantics> are arbitrarily fixed positive integers. We consider two scenarios of error correction: the classical error correcting codes, which recover each codeword from one read (channel output), and the reconstruction codes, which allow to recover each codeword from multiple channel reads. For the first scenario, our construction has redundancy <semantics>logn+8loglogn+o(loglogn)</semantics> bits, encoding complexity <semantics>O(q7tn(logn)3)</semantics> and decoding complexity <semantics>O(nlogn)</semantics>. For the reconstruction scenario, our construction can recover the codewords with two reads and has redundancy <semantics>8loglogn+o(loglogn)</semantics> bits. The encoding complexity of this construction is <semantics>O<mfenced separators="" open="(" close=")">q7tn(logn)3</mfenced></semantics>, and decoding complexity is <semantics>O<mfenced separators="" open="(" close=")">q9t(nlogn)3</mfenced></semantics>. Both of our constructions have lower redundancy than the best known existing works. We also give explicit encoding functions for both constructions that are simpler than previous works.