Gilbert-Varshamov-like lower bounds for deletion-correcting codes
Gilbert-Varshamov-like lower bounds for deletion-correcting codes
复制标题
类似 Gilbert-Varshamov 的删除校正代码下界
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
L. Dolecek
中科院分区：
文献类型：
--
作者：
Frederic Sala;Ryan Gabrys;L. Dolecek
开发出能够纠正不止一个缺失的良好代码仍然是一项难以捉摸的任务。最近的一些论文，比如Kulkarni和Kiyavash的论文，把重点放在了更容易处理的问题上，即在这些码的基数上推导上界。在本工作中，我们开发了删除校正码基数的gilbert - varshamov型下界。我们的方法是基于极值图论结果的应用。给出了二进制和非二进制单错纠错码和多错纠错码的几个界。我们引入了一个界，据我们所知，这是删除纠正码大小的最强现有下界。我们的工作还揭示了底层Levenshtein图的一些结构性质。
The development of good codes which are capable of correcting more than a single deletion remains an elusive task. Recent papers, such as that by Kulkarni and Kiyavash [3], instead focus on the more tractable problem of deriving upper bounds on the cardinalities of such codes. In the present work, we develop Gilbert-Varshamov-type lower bounds on the cardinalities of deletion-correcting codes. Our approach is based on the application of results from extremal graph theory. We give several bounds for the cases of binary and non-binary single- and multiple-error correcting codes. We introduce a bound that is, to the best of our knowledge, the strongest existing lower bound on the sizes of deletion-correcting codes. Our work also reveals some structural properties of the underlying Levenshtein graph.