Deletion Codes in the High-Noise and High-Rate Regimes
Deletion Codes in the High-Noise and High-Rate Regimes
复制标题
高噪声和高速率状态下的删除代码
DOI：
10.1109/tit.2017.2659765
复制
发表时间：
2014
影响因子：
2.5
通讯作者：
Carol Wang
中科院分区：
文献类型：
--
作者：
V. Guruswami;Carol Wang
删除的噪声模型在编码理论中构成了重大挑战，诸如二进制删除渠道的能力之类的基本问题仍在开放。在本文中，我们研究了<Italic>最坏情况的更难模型</ittiric>删除，重点是为高噪声和高速率的两个极端机制构建有效解码的代码。具体而言，我们以以下权衡构建多项式时时间可解码代码（对于任何<inline-formula> <tex-math notegy =“ latex”> $ \ varepsilon> 0 $ </tex-math> </inline-formula>） ：1）可以纠正分数<inline-formula> <tex-math notege =“ latex”> $ 1- \ varepsilon $的代码</tex-math> </inline-formula>带有速率<inline-formula> <tex-math notegy =“ latex”> $ \ mathop {\ mathrm {poly}} \ nolimits（\ varepsilon）$ </</ tex-math> </inline-formula>大小的字母<inline-formula> <tex-math notegy =“ latex”> $ $ \ Mathop {\ Mathrm {poly}} \ nolimits（1/\ varepsilon）$ </tex-math> </inline-formula>; 2）费率二进制代码<inline-formula> <tex-math notegy =“ latex”> $ 1- \ tilde {o}（\ sqrt {\ sqrt {\ varepsilon}）$可以纠正分数<inline-formula> <tex-math note法=“ latex”> $ \ varepsilon $ </tex-math> </inline-formula>删除的inline-formula>； 3）可以<Italic> list列表</italic>的二进制代码，<inline-formula> <tex-math notegy =“ latex”> $（1/2- \ varepsilon）$ </tex--数学> </inline-formula>带有速率的删除<inline-formula> <tex-math notegy =“ latex”> $ \ mathop {\ mathrm {poly}} \ nolimits（\ varepsilon）$ </tex-math> </inline-formula>。本文提供了第一个有效的构造，该结构符合校正限制字母上1接近1的删除分数的定性目标，并在固定字母上纠正速率差的恒定分数，速率接近1。上述结果使我们对这些制度中的删除代码构造的理解达到了与最坏情况相似的水平。
The noise model of deletions poses significant challenges in coding theory, with basic questions like the capacity of the binary deletion channel still being open. In this paper, we study the harder model of <italic>worst case</italic> deletions, with a focus on constructing efficiently decodable codes for the two extreme regimes of high-noise and high-rate. Specifically, we construct polynomial-time decodable codes with the following tradeoffs (for any <inline-formula> <tex-math notation="LaTeX">$ \varepsilon > 0$ </tex-math></inline-formula>): 1) codes that can correct a fraction <inline-formula> <tex-math notation="LaTeX">$1- \varepsilon $ </tex-math></inline-formula> of deletions with rate <inline-formula> <tex-math notation="LaTeX">$ \mathop {\mathrm {poly}}\nolimits ( \varepsilon )$ </tex-math></inline-formula> over an alphabet of size <inline-formula> <tex-math notation="LaTeX">$ \mathop {\mathrm {poly}}\nolimits (1/ \varepsilon )$ </tex-math></inline-formula>; 2) binary codes of rate <inline-formula> <tex-math notation="LaTeX">$1-\tilde {O}(\sqrt { \varepsilon })$ </tex-math></inline-formula> that can correct a fraction <inline-formula> <tex-math notation="LaTeX">$ \varepsilon $ </tex-math></inline-formula> of deletions; and 3) Binary codes that can be <italic>list-decoded</italic> from a fraction <inline-formula> <tex-math notation="LaTeX">$(1/2- \varepsilon )$ </tex-math></inline-formula> of deletions with rate <inline-formula> <tex-math notation="LaTeX">$ \mathop {\mathrm {poly}}\nolimits ( \varepsilon )$ </tex-math></inline-formula>. This paper gives the first efficient constructions which meet the qualitative goals of correcting a deletion fraction approaching 1 over bounded alphabets, and correcting a constant fraction of bit deletions with rate approaching 1 over a fixed alphabet. The above-mentioned results bring our understanding of deletion code constructions in these regimes to a similar level as worst case errors.