List Decoding of Deletions Using Guess & Check Codes

2018/10/16 by Serge Kas Hanna, Hanna, Serge Kas, Salim El Rouayheb +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #DNA and Biological Computing #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · pdf · doi:10.48550/arxiv.1810.07281

openalex publication_date 2018/10/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Guess & Check (GC) codes are systematic binary codes that can correct multiple deletions, with high probability. GC codes have logarithmic redundancy in the length of the message k, and the encoding and decoding algorithms of these codes are deterministic and run in polynomial time for a constant number of deletions δ. The unique decoding properties of GC codes were examined in a previous work by the authors. In this paper, we investigate the list decoding performance of these codes. Namely, we study the average size and the maximum size of the list obtained by a GC decoder for a constant number of deletions δ. The theoretical results show that: (i) the average size of the list approaches 1 as k grows; and (ii) there exists an infinite sequence of GC codes indexed by k, whose maximum list size in upper bounded by a constant that is independent of k. We also provide numerical simulations on the list decoding performance of GC codes for multiple values of k and δ.

Cited by

• Oblivious Deletion Codes

Related

• Guess & Check Codes for Deletions, Insertions, and Synchronization
• Guess & Check Codes for Deletions and Synchronization
• On the List Decodability of Insertions and Deletions
• List Decoding of Insertions and Deletions
• A Universal List Decoding Algorithm with Application to Decoding of Polar Codes