首页> 外文期刊>IEEE Transactions on Information Theory >Covering Codes Using Insertions or Deletions
【24h】

Covering Codes Using Insertions or Deletions

机译:使用插入或删除覆盖代码

获取原文
获取原文并翻译 | 示例
           

摘要

A covering code is a set of codewords with the property that the union of balls, suitably defined, around these codewords covers an entire space. Generally, the goal is to find the covering code with the minimum size codebook. While most prior work on covering codes has focused on the Hamming metric, we consider the problem of designing covering codes defined in terms of either insertions or deletions. First, we provide new spherecovering lower bounds on the minimum possible size of such codes. Then, we provide new existential upper bounds on the size of optimal covering codes for a single insertion or a single deletion that are tight up to a constant factor. Finally, we derive improved upper bounds for covering codes using R >= 2 insertions or deletions. We prove that codes exist with density that is only a factor O(R logR) larger than the lower bounds for all fixed R. In particular, our upper bounds have an optimal dependence on the word length, and we achieve asymptotic density matching the best known bounds for Hamming distance covering codes.
机译:覆盖代码是一组码字,其中包含球的联盟,适当地定义的属性,这些码字周围涵盖了整个空间。通常,目标是找到具有最小大小码本的覆盖码。虽然大多数事先在覆盖码上的工作都集中在汉明度量上,但我们考虑设计根据插入或删除方面定义的覆盖码的问题。首先,我们在这些代码的最低可能大小上提供新的球面缩小。然后,我们为单个插入的最佳覆盖码的大小提供新的存在上限,或者单个插入或单次删除,其紧固到恒定因子。最后,我们使用R> 2插入或删除来派生用于覆盖码的改进的上限。我们证明了密度存在的代码,密度仅仅是所有固定R的因子O(R LOGR),特别是,我们的上限具有对单词长度的最佳依赖性,并且我们实现了最佳的渐近密度匹配汉明距离覆盖码的已知范围。

著录项

  • 来源
    《IEEE Transactions on Information Theory》 |2021年第6期|3376-3388|共13页
  • 作者单位

    Tech Univ Munich Inst Commun Engn D-80333 Munich Germany;

    Univ Calif San Diego Comp Sci & Engn Dept La Jolla CA 92093 USA|Univ Calif San Diego Qualcomm Inst La Jolla CA 92093 USA;

    Univ Calif San Diego Elect & Comp Engn Dept La Jolla CA 92093 USA|Univ Calif San Diego Ctr Memory & Recording Res La Jolla CA 92093 USA;

    Technion Israel Inst Technol Comp Sci Dept IL-3200003 Haifa Israel;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    Covering codes; insertions; deletions;

    机译:覆盖码;插入;删除;

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号