Title | ||
---|---|---|
Explicit and Efficient Constructions of Linear Codes Against Adversarial Insertions and Deletions |
Abstract | ||
---|---|---|
In this work, we study linear error-correcting codes against adversarial insertion-deletion (insdel) errors, a topic that has recently gained a lot of attention. We construct linear codes over
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {F}_{q}$ </tex-math></inline-formula>
, for
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q= {\mathrm {poly}}(1/\varepsilon)$ </tex-math></inline-formula>
, that can efficiently decode from a
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\delta $ </tex-math></inline-formula>
fraction of insdel errors and have rate
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(1-4\delta)/8-\varepsilon $ </tex-math></inline-formula>
. We also show that by allowing codes over
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {F}_{q^{2}}$ </tex-math></inline-formula>
that are linear over
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {F}_{q}$ </tex-math></inline-formula>
, we can improve the rate to
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(1-\delta)/4-\varepsilon $ </tex-math></inline-formula>
while not sacrificing efficiency. Using this latter result, we construct fully linear codes over
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {F}_{2}$ </tex-math></inline-formula>
that can efficiently correct up to
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\delta < 1/54$ </tex-math></inline-formula>
fraction of deletions and have rate
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$R = (1-54\cdot \delta)/1216$ </tex-math></inline-formula>
. Cheng
<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al.</i>
(2021) constructed codes with (extremely small) rates bounded away from zero that can correct up to a
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\delta < 1/400$ </tex-math></inline-formula>
fraction of insdel errors. They also posed the problem of constructing linear codes that get close to the
<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">half-Singleton bound</i>
[proved in Cheng
<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al.</i>
(2021)] over small fields. Thus, our results significantly improve their construction and get much closer to the bound. |
Year | DOI | Venue |
---|---|---|
2022 | 10.1109/TIT.2022.3173185 | IEEE Transactions on Information Theory |
Keywords | DocType | Volume |
Insertion-deletion codes,linear insdel codes | Journal | 68 |
Issue | ISSN | Citations |
10 | 0018-9448 | 0 |
PageRank | References | Authors |
0.34 | 13 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Roni Con | 1 | 2 | 1.38 |
Amir Shpilka | 2 | 1095 | 64.27 |
Itzhak Tamo | 3 | 548 | 36.05 |