An Overview of Capacity Results for Synchronization Channels
An Overview of Capacity Results for Synchronization Channels
复制标题
DOI：
10.1109/tit.2020.2997329
复制
发表时间：
2021-06-01
影响因子：
2.5
通讯作者：
Ribeiro, Joao
中科院分区：
文献类型：
--
作者：
Cheraghchi, Mahdi;Ribeiro, Joao
与无内存渠道相比，同步通道（例如众所周知的删除渠道）更难分析，并且它们是信息理论和理论计算机科学中许多基本问题的根源。关于同步通道的最基本的开放问题之一是衍生其能力的精确表达。不幸的是，当应用于同步通道时，大多数经典信息理论技术都会出色地出现。因此，必须考虑新的方法来解决这个问题。这项调查给出了过去几十年来付出的巨大努力，以更好地了解同步渠道的（广泛定义）能力，包括主要结果和它们的新技术。除了通常的通道容量概念外，我们还讨论了对抗同步通道的零错误能力。
Synchronization channels, such as the well-known deletion channel, are surprisingly harder to analyze than memoryless channels, and they are a source of many fundamental problems in information theory and theoretical computer science. One of the most basic open problems regarding synchronization channels is the derivation of an exact expression for their capacity. Unfortunately, most of the classic information-theoretic techniques at our disposal fail spectacularly when applied to synchronization channels. Therefore, new approaches must be considered to tackle this problem. This survey gives an account of the great effort made over the past few decades to better understand the (broadly defined) capacity of synchronization channels, including both the main results and the novel techniques underlying them. Besides the usual notion of channel capacity, we also discuss the zero-error capacity of adversarial synchronization channels.