Explicit and Efficient Constructions of Linear Codes Against Adversarial Insertions and Deletions
Explicit and Efficient Constructions of Linear Codes Against Adversarial Insertions and Deletions
复制标题
针对对抗性插入和删除的线性代码的显式有效构造
DOI：
10.1109/tit.2022.3173185
复制
发表时间：
2022
影响因子：
2.5
通讯作者：
Itzhak Tamo
中科院分区：
文献类型：
--
作者：
Roni Con;Amir Shpilka;Itzhak Tamo
在这项工作中，我们研究了针对对抗性插入-删除（insdel）错误的线性纠错码，这是一个最近受到广泛关注的主题。我们在<inline-formula> < text -math notation="LaTeX"> $\mathbb {F}_{q}$ </ text -math></inline-formula>上构造线性代码，对于<inline-formula> < text -math notation="LaTeX"> $q= {\mathrm {poly}}(1/\varepsilon)$ </ text -math></inline-formula>，可以有效地解码<inline-formula> < text -math notation="LaTeX"> $\delta $ </ text -math></inline-formula>的错误分数，并且具有率<inline-formula> < text -math notation="LaTeX"> $(1-4\delta)/8-\varepsilon $ </ text -math></inline-formula>。我们还表明，通过允许在<inline-formula> < text -math notation="LaTeX"> $\mathbb {F}_{q^{2}}$ </ text -math></inline-formula>上的代码在<inline-formula> < text -math notation="LaTeX"> $\mathbb {F}_{q}$ </ text -math></inline-formula>上的线性，我们可以在不牺牲效率的情况下将速率提高到<inline-formula> < text -math notation="LaTeX"> $(1-\delta)/4-\varepsilon $ </ text -math></inline-formula>。使用后一个结果，我们在<inline-formula> < text -math notation="LaTeX"> $\mathbb {F}_{2}$ </ text -math></inline-formula>上构造了完全线性代码，它可以有效地纠正高达<inline-formula> < text -math notation="LaTeX"> $\delta < 1/54$ </ text -math></inline-formula>的删除分数，并且具有率<inline-formula> < text -math notation="LaTeX"> $R = (1-54\cdot \delta)/1216$ </ text -math></inline-formula>。Cheng <斜体>等人。</斜体>(2021)构建的代码（非常小）的比率从零开始，可以纠正到<inline-formula> < text -math notation="LaTeX"> $\delta < 1/400$ </ text -math></inline-formula>的内部错误分数。他们还提出了在小油田上构造接近<italic>半单例界</italic>[在Cheng <italic>等人证明。</italic>(2021)]的线性码的问题。因此，我们的结果显著地改进了它们的构造，并且更加接近边界。
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> <tex-math notation="LaTeX">$\mathbb {F}_{q}$ </tex-math></inline-formula>, for <inline-formula> <tex-math notation="LaTeX">$q= {\mathrm {poly}}(1/\varepsilon)$ </tex-math></inline-formula>, that can efficiently decode from a <inline-formula> <tex-math notation="LaTeX">$\delta $ </tex-math></inline-formula> fraction of insdel errors and have rate <inline-formula> <tex-math notation="LaTeX">$(1-4\delta)/8-\varepsilon $ </tex-math></inline-formula>. We also show that by allowing codes over <inline-formula> <tex-math notation="LaTeX">$\mathbb {F}_{q^{2}}$ </tex-math></inline-formula> that are linear over <inline-formula> <tex-math notation="LaTeX">$\mathbb {F}_{q}$ </tex-math></inline-formula>, we can improve the rate to <inline-formula> <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> <tex-math notation="LaTeX">$\mathbb {F}_{2}$ </tex-math></inline-formula> that can efficiently correct up to <inline-formula> <tex-math notation="LaTeX">$\delta < 1/54$ </tex-math></inline-formula> fraction of deletions and have rate <inline-formula> <tex-math notation="LaTeX">$R = (1-54\cdot \delta)/1216$ </tex-math></inline-formula>. Cheng <italic>et al.</italic> (2021) constructed codes with (extremely small) rates bounded away from zero that can correct up to a <inline-formula> <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>half-Singleton bound</italic> [proved in Cheng <italic>et al.</italic> (2021)] over small fields. Thus, our results significantly improve their construction and get much closer to the bound.
同步字符串：小字母表上的高效确定性构造
DOI：
10.1137/1.9781611975482.132
发表时间：
2019
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Cheng, Kuan;Haeupler, Bernhard;Li, Xin;Shahrasbi, Amirbehshad;Wu, Ke
通讯作者：
Wu, Ke
具有与存在界限匹配的冗余的显式两次删除代码
影响因子：
2.5
作者：
Guruswami, Venkatesan;Hastad, Johan
通讯作者：
Hastad, Johan
最佳文档交换以及插入和删除的新代码
DOI：
10.1109/focs.2019.00029
发表时间：
2019
期刊：
IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
Haeupler, Bernhard
通讯作者：
Haeupler, Bernhard