An Improved Bound on the Fraction of Correctable Deletions
An Improved Bound on the Fraction of Correctable Deletions
复制标题
可纠正删除分数的改进界限
DOI：
10.1109/tit.2016.2621044
复制
发表时间：
2015
影响因子：
2.5
通讯作者：
J. Håstad
中科院分区：
文献类型：
--
作者：
B. Bukh;V. Guruswami;J. Håstad
我们考虑使用固定字母的代码针对最坏情况符号删除。对于任何固定的<inline-formula> <tex-math notegy =“ latex”> $ k \ ge 2 $ </tex-math> </inline-formula>，我们在大小<inline--公式> <tex-math notegy =“ latex”> $ k $ </tex-math> </inline-formula>以正速率，从<inline-formula> <tex-math notegy =“ latex”> $ 1-（{2}/（{k+\ sqrt {k}}}））$ </tex-math> </inline-formula>。特别是，对于二进制代码，我们能够恢复接近<inline-formula> <tex-math notegy =“ latex”> $ 1/（\ sqrt {2} +1）= \ sqrt {2} - 1 \大约0.414 $ </tex-math> </inline-formula>。以前，即使在非结构上，已知以正率更正的最大缺失分数也是<inline-formula> <tex-math notegement =“ latex”> $ 1- \ theta（1/\ sqrt {k}）$ </</</ Tex-Math> </inline-formula>，二进制案例约为0.17。我们的结果将<inline-formula> <tex-Math notegy =“ latex”> $ k $ </tex-math> </inline-formula> arline-formula> arighable> ary代码的可更正删除的最大限额列为<inline-formula> <tex-math note =“ latex”> $ 1- \ theta（1/k）$ </tex-math> </inline-formula>，因为<inline-formula> <tex-math notagion =“ latex”> $ 1-1/k $ </tex-math> </inline-formula>即使对于更简单的擦除模型，在其中已知缺失符号的位置的较简单模型。缩小<inline-formula> <tex-math notegy =“ latex”> $（\ sqrt {2} -1）$ </tex-math> </tex-math> </inline-formula>和1/2的差距可通过二进制代码更正的最坏情况仍然是一个诱人的开放问题。
We consider codes over fixed alphabets against worst case symbol deletions. For any fixed <inline-formula> <tex-math notation="LaTeX">$k \ge 2$ </tex-math></inline-formula>, we construct a family of codes over alphabet of size <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> with positive rate, which allow efficient recovery from a worst case deletion fraction approaching <inline-formula> <tex-math notation="LaTeX">$1-({2}/({k+\sqrt {k}}))$ </tex-math></inline-formula>. In particular, for binary codes, we are able to recover a fraction of deletions approaching <inline-formula> <tex-math notation="LaTeX">$1/(\sqrt {2} +1)=\sqrt {2}-1 \approx 0.414$ </tex-math></inline-formula>. Previously, even non-constructively, the largest deletion fraction known to be correctable with positive rate was <inline-formula> <tex-math notation="LaTeX">$1-\Theta (1/\sqrt {k})$ </tex-math></inline-formula>, and around 0.17 for the binary case. Our result pins down the largest fraction of correctable deletions for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-ary codes as <inline-formula> <tex-math notation="LaTeX">$1-\Theta (1/k)$ </tex-math></inline-formula>, since <inline-formula> <tex-math notation="LaTeX">$1-1/k$ </tex-math></inline-formula> is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between <inline-formula> <tex-math notation="LaTeX">$(\sqrt {2} -1)$ </tex-math></inline-formula> and 1/2 for the limit of worst case deletions correctable by binary codes remains a tantalizing open question.