Explicit construction of q-ary 2-deletion correcting codes with low redundancy

• Main Authors: Liu, Shu, Tjuawinata, Ivan, Xing, Chaoping
• Other Authors: School of Computer Science and Engineering
• Format: Article
• Language: English
• Published: 2024
• Subjects: Computer and Information Science; Insertion and Deletion; Efficient Construction; Error Correction
• Online Access: https://hdl.handle.net/10356/173448
• Institution: Nanyang Technological University

We consider the problem of efficient construction of q -ary 2-deletion correcting codes with low redundancy. We show that our construction requires less redundancy than any existing efficiently encodable q -ary 2-deletion correcting codes. Precisely speaking, we present an explicit construction of a q -ary 2-deletion correcting code with redundancy 5 log n +10 log log n + 3 log q + O (1) where q is assumed to be a constant with respect to n . Using a minor modification to the original construction, we obtain an efficiently encodable q -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 a q -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 additional q -ary sketches that the original q -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.