Explicit two-deletion codes with redundancy matching the existential bound
Explicit two-deletion codes with redundancy matching the existential bound
We give an explicit construction of length-n binary codes capable of correcting the deletion of two bits that have size 2n/n4+o(1). This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size Ω(2n/n4). Our construction is based …