专栏首页arxiv.org翻译专栏单一编辑的编码序列重建(Information Theory)
原创

单一编辑的编码序列重建(Information Theory)

序列重构问题是由Levenshtein在2001年提出的,它考虑了这样一种通信场景:发送方从某个码本传输一个码字,而接收方获得该码字的多个有噪声的读码。常见的设置会假定码本是整个空间,而需要解决的问题是确定重构传输的码字所需的最小读次数。

在现代存储设备的驱动下,我们研究了一个问题的变体,其中噪声的读取次数N是固定的。具体地说,我们设计了从N个不同的噪声读码中重构码字的重构码。我们专注于渠道,介绍单编辑错误(即一个替换、插入或删除)及其变体,和设计重构代码的所有值n。特别是在一个编辑的情况下,我们发现,随着嘈杂的读取次数的增加,所需的冗余比特数量从log n + O(1) 减少到log log n + O(1) ,最终到O(1),其中n表示码字的长度。我们还证明了某些重构码的冗余度在一个比特的最优范围内。

原文题目:编码序列重建为单一编辑

原文: The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. The common setup assumes the codebook to be the entire space and the problem is to determine the minimum number of distinct reads that is required to reconstruct the transmitted codeword.

Motivated by modern storage devices, we study a variant of the problem where the number of noisy reads N is fixed. Specifically, we design reconstruction codes that reconstruct a codeword from N distinct noisy reads. We focus on channels that introduce single edit error (i.e. a single substitution, insertion, or deletion) and their variants, and design reconstruction codes for all values of N. In particular, for the case of a single edit, we show that as the number of noisy reads increases, the number of redundant bits required can be gracefully reduced from log n + O(1) to log log n + O(1), and then to O(1), where n denotes the length of a codeword. We also show that the redundancy of certain reconstruction codes is within one bit of optimality.

原文作者:Han Mao Kiah, Tuan Thanh Nguyen, Eitan Yaakobi

原文地址: https://arxiv.org/abs/2001.01376

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 时间约束的自适应影响最大化(Social and Information Networks)

    众所周知,影响最大化问题的目的是通过在扩散过程之前选择合适的种子用户来最大化一个信息级联在社交网络中的影响。在其自适应版本中,可以通过观察一定的扩散结果来选择额...

    用户6869393
  • 与异构服务器在线联合布置和分配虚拟网络功能(Networking and Internet Architecture)

    网络功能虚拟化(NFV)是一种新兴的虚拟化技术,具有显著降低成本和提高服务敏捷性的潜力。网络功能虚拟化使因特网服务提供商(isp)能够在不安装新设备的情况下使用...

    用户6869393
  • 积极的算法偏见无法阻止同性社交网络的分裂(Social and Information Networks)

    社会网络中的碎片化、回音室及其改进已经成为学术界和非学术界日益关注的问题。本文证明了在同质性假设下,即使在理想的异质性条件下,回音室和碎片化也是高度灵活的社会网...

    用户6869393
  • 用Emo-CNN从声音信号中感知压力:一种大脑化学方法

    情感在许多应用中起着关键作用,比如医疗保健,收集病人的情感行为。由于某些情感在理解人类情感方面的有效性,它们被给予了更多的重视。在这篇论文中,我们提出了一种从声...

    非过度曝光
  • SPINNING单车你需要知道的一些事(一)单车怎么调整

    • If toe cages and straps are used, be sure to align the ball of your foot over ...

    小飞侠xp
  • Duke@coursera 数据分析与统计推断 unit1 part2 introduction to data

    roughly the average deviation around themean, and has the same units as the data

    统计学家
  • 音频修复:回顾和重新加权(CS S)

    我们处理基于稀疏性的音频修复问题。 优化方法的结果实际上是填充间隙内信号能量不足。 我们建议基于稀疏性和凸优化的音频修复框架,以补偿这种能量损失。 新思路基于系...

    非过度曝光
  • 机器人控制器编程课程-教案02-基础

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    zhangrelay
  • AIM Tech Round 4 (Div. 2)(A,暴力,B,组合数,C,STL+排序)

    A. Diversity time limit per test:1 second memory limit per test:256 megabytes in...

    Angel_Kitty
  • ZOJ 3705 Applications

    Recently, the ACM/ICPC team of Marjar University decided to choose some new memb...

    ShenduCC

扫码关注云+社区

领取腾讯云代金券