We study error exponents for the problem of low-rate communication over a directed graph, where each edge in the graph represents a noisy communication channel, and there is a single source and destination. We derive maxflow-based achievability and converse bounds on the error exponent that match when there are two messages and all channels satisfy a symmetry condition called pairwise reversibility. More generally, we show that the upper and lower bounds match to within a factor of 4. We also show that with three messages there are cases where the maxflow-based error exponent is strictly suboptimal, thus showing that our tightness result cannot be extended beyond two messages without further assumptions.
翻译:我们研究了在有向图上低速率通信的误差指数问题,其中图中每条边表示一个嘈杂的通信渠道,且有一个单一的源和目标。我们推导了基于最大流的可实现性和对话界限,这些界限是匹配的,当图中有两个消息且所有通道满足称为成对可逆性的对称性条件时。更一般地,我们表明上限和下限在因子4内匹配。我们还表明,当有三个消息时,有些情况下基于最大流的误差指数严格次优,因此表明我们的紧密性结果不能在没有进一步假设的情况下推广到两个消息以上。