Explicit Construction of q-Ary 2-Deletion Correcting Codes With Low Redundancy
Shu Liu, Ivan Tjuawinata, Chaoping Xing · IEEE Transactions on Information Theory · 2024
We consider the problem of efficient construction ofq-ary 2-deletion correcting codes with low redundancy. We show that our construction requires less redundancy than any existing efficiently encodableq-ary 2-deletion correcting codes. Precisely speaking, we present an explicit construction of aq-ary 2-deletion correcting code with redundancy 5 logn+10 log logn+ 3 logq+O(1) whereqis assumed to be a constant with respect ton. Using a minor modification to the original construction, we obtain an efficiently encodableq-ary 2-deletion code that is efficiently list-decodable. Similarly, we show that our construction of list-decodable code requires a smaller redundancy compared to any existing list-decodable codes. To obtain our sketches, we transform aq-ary code-word to a binary string which can then be used as an input to the underlying base binary sketch. This is then complemented with additionalq-ary sketches that the originalq-ary codeword is required to satisfy. In other words, we build our codes via a binary 2-deletion code as a black-box. Finally we utilize the binary 2-deletion code proposed by Guruswami and Håstad to our construction to obtain the main result of this paper.