Two-Deletion Correcting Codes
Description
Background:
This seminar explores the design of error-correcting codes capable of correcting two deletions—a natural yet significantly challenging progression from single-deletion codes. The study of deletion (and insertion) correcting codes dates back to the early 1960s. Levenshtein’s work [3] showed that VT codes [5], originally designed for asymmetric error correction, also handle single deletion/insertion errors with near-optimal redundancy of at most log?(n) bits. This elegant construction spurred extensive research to extend these ideas to correct multiple deletions. However, extending VT codes to the two-deletion scenario has proven difficult; natural augmentations with additional check equations have not achieved the desired performance.
Modern Relevance & DNA Data Storage:
Deletion-correcting codes have gained practical importance in emerging fields like DNA data storage, where sequencing errors often manifest as deletions. In these applications, efficient and low-redundancy codes are crucial for reliable data retrieval, highlighting the importance of advancements in two-deletion correcting codes.
Seminar Focus:
Recent years have seen renewed interest in this topic, with several works proposing two-deletion correcting codes that achieve good asymptotic redundancy [1][2][4]. The goal of this seminar is to deeply understand two of these approaches. The student will develop detailed examples and illustrations to explain the code constructions, followed by an analysis comparing the redundancy of the two codes for various code lengths
Expected Outcomes:
- Detailed Examples: Step-by-step encoding and decoding demonstrations for two codes, illustrating the underlying principles.
- Visual Illustrations: Graphics that clearly depict the error-correcting capabilities.
- Comparative Analysis: A discussion comparing the two approaches, supported by quantitative analysis and visual data showing redundancy for different code lengths.
References:
[1] R. Gabrys and F. Sala, “Codes Correcting Two Deletions,” IEEE Transactions on Information Theory, vol. 65, no. 2, pp. 965–974, Feb. 2019, doi: 10.1109/TIT.2018.2876281.
[2] V. Guruswami and J. Håstad, “Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound,” IEEE Transactions on Information Theory, vol. 67, no. 10, pp. 6384–6394, Oct. 2021, doi: 10.1109/TIT.2021.3069446.
[3] V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals,” in Soviet physics doklady, Soviet Union, 1966, pp. 707–710.
[4] J. Sima, N. Raviv, and J. Bruck, “Two Deletion Correcting Codes From Indicator Vectors,” IEEE Trans. Inform. Theory, vol. 66, no. 4, pp. 2375–2391, Apr. 2020, doi: 10.1109/TIT.2019.2950290.
[5] R. R. Varshamov and G. M. Tenengolts, “Codes which correct single asymmetric errors (in Russian),” Automatika i Telemkhanika, vol. 161, no. 3, pp. 288–292, 1965.
Prerequisites
- Channel Coding course completed
- Very good understanding of linear algebra and combinatorics