Competitive Channel-Capacity
Competitive Channel-Capacity
复制标题
DOI：
10.1109/isit54713.2023.10206801
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
M. Langberg;Oron Sabag
中科院分区：
文献类型：
--
作者：
M. Langberg;Oron Sabag
我们考虑通过通道进行通信，其统计数据不完全已知，但可以参数化为有限的无记忆通道族。解决信道不确定性的典型方法是为系列中最差的信道设计代码，从而产生众所周知的复合信道容量。尽管这种方法很稳健，但如果最差信道的容量实现分布达到比其他信道低的速率，则可能会遭受性能损失。在这项工作中，我们通过竞争分析的视角应对渠道不确定性。这个想法是优化一个相对指标，比较设计代码和能够访问真实通道的透视代码的性能。为了允许通信速率适应所使用的信道，我们考虑具有固定信息比特数和随机解码时间的无速率代码。我们提出了两个竞争指标：两个代码的解码时间之间的竞争比，以及定义为预期速率之间的差异的遗憾。我们的主要结果是竞争比和遗憾的单字母表达式，表示为最大-最小或最小-最大优化。几个例子说明了我们的结果以及竞争分析方法对代码设计的好处。
We consider communication over channels whose statistics are not known in full, but can be parameterized as a finite family of memoryless channels. A typical approach to address channel uncertainty is to design codes for the worst channel in the family, resulting in the well-known compound channel capacity. Although this approach is robust, it may suffer a loss of performance if the capacity-achieving distribution of the worst channel attains low rates over other channels. In this work, we cope with channel uncertainty through the lens of competitive analysis. The idea is to optimize a relative metric that compares the performance of the designed code and a clairvoyant code that has access to the true channel. To allow communication rates that can adapt to the channel at use, we consider rateless codes with a fixed number of information bits and random decoding times. We propose two competitive metrics: the competitive ratio between the decoding times of the two codes, and a regret defined as the difference between the expected rates. Our main results are single-letter expressions for the competitive-ratio and the regret, expressed as a max-min or min-max optimization. Several examples illustrate our results and the benefits of the competitive analysis approach to code design.