Codes Correcting Two Bursts of Exactly $b$ Deletions
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908521513091072 |
|---|---|
| author | Ye, Zuo Sun, Yubo Yu, Wenjun Ge, Gennian Elishco, Ohad |
| author_facet | Ye, Zuo Sun, Yubo Yu, Wenjun Ge, Gennian Elishco, Ohad |
| contents | In this paper, we investigate codes designed to correct two bursts of deletions, where each burst has a length of exactly $b$, where $b>1$. The previous best construction, achieved through the syndrome compression technique, had a redundancy of at most $7\log n+O\left(\log n/\log\log n\right)$ bits. In contrast, our work introduces a novel approach for constructing $q$-ary codes that attain a redundancy of at most $5\log n+O(\log\log n)$ bits for all $b>1$ and $q\ge2$. Additionally, for the case where $b=1$, we present a new construction of $q$-ary two-deletion correcting codes with a redundancy of $5\log n+O(\log\log n)$ bits, for all $q>2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_03113 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Codes Correcting Two Bursts of Exactly $b$ Deletions Ye, Zuo Sun, Yubo Yu, Wenjun Ge, Gennian Elishco, Ohad Information Theory In this paper, we investigate codes designed to correct two bursts of deletions, where each burst has a length of exactly $b$, where $b>1$. The previous best construction, achieved through the syndrome compression technique, had a redundancy of at most $7\log n+O\left(\log n/\log\log n\right)$ bits. In contrast, our work introduces a novel approach for constructing $q$-ary codes that attain a redundancy of at most $5\log n+O(\log\log n)$ bits for all $b>1$ and $q\ge2$. Additionally, for the case where $b=1$, we present a new construction of $q$-ary two-deletion correcting codes with a redundancy of $5\log n+O(\log\log n)$ bits, for all $q>2$. |
| title | Codes Correcting Two Bursts of Exactly $b$ Deletions |
| topic | Information Theory |
| url | https://arxiv.org/abs/2408.03113 |