论文标题
具有非信号相关性的多访问通道编码
Multiple-Access Channel Coding with Non-Signaling Correlations
论文作者
论文摘要
我们解决了在各方之间的非信号相关性的帮助下为经典多访问通道（MAC）编码的问题。众所周知，非信号援助不会改变经典点对点渠道的能力。但是，最近观察到，可以从两人非本地游戏中构建Mac，同时将游戏的胜利概率与Mac的能力联系起来。通过考虑纠缠增加获胜概率的游戏，这表明对于某些特定类型的渠道，发件人之间的纠缠可以增加容量。 我们在不信号相关性的帮助下为了解MAC的能力区域做出了一些贡献。我们开发了一个线性程序，该程序计算以$ N $ W $的$ N $副本编码的最佳成功概率，其大小在$ n $中的多项式增长。解决此线性程序使我们能够实现MAC的内在界限。将此方法应用于二进制加法器频道，我们表明，使用非信号援助，即使零错误也可以达到$ 1.5425 $的$ 1.5425 $，在未辅助的情况下，最大总比率容量为$ 1.5 $。对于嘈杂的通道，零错误的非信号辅助能力区域是微不足道的，我们可以使用串联代码在容量区域中获得可实现的点。应用于二进制加法器频道的嘈杂版本，我们表明非信号援助仍然可以提高汇率容量。补充这些可实现的结果，我们在非信号辅助容量区域中给出了与未辅助区域相同的表达的外部结合，只是不需要通道输入是独立的。最后，我们表明，只有在每个发件人之间共享非信号援助的能力区域与没有援助的情况相同。
We address the problem of coding for classical multiple-access channels (MACs) with the assistance of non-signaling correlations between parties. It is well-known that non-signaling assistance does not change the capacity of classical point-to-point channels. However, it was recently observed that one can construct MACs from two-player non-local games while relating the winning probability of the game to the capacity of the MAC. By considering games for which entanglement increases the winning probability, this shows that for some specific kinds of channels, entanglement between the senders can increase the capacity. We make several contributions towards understanding the capacity region for MACs with the assistance of non-signaling correlations. We develop a linear program computing the optimal success probability for coding over $n$ copies of a MAC $W$ with size growing polynomially in $n$. Solving this linear program allows us to achieve inner bounds for MACs. Applying this method to the binary adder channel, we show that using non-signaling assistance, the sum-rate $1.5425$ can be reached even with zero error, which beats the maximum sum-rate capacity of $1.5$ in the unassisted case. For noisy channels, where the zero-error non-signaling assisted capacity region is trivial, we can use concatenated codes to obtain achievable points in the capacity region. Applied to a noisy version of the binary adder channel, we show that non-signaling assistance still improves the sum-rate capacity. Complementing these achievability results, we give an outer bound on the non-signaling assisted capacity region that has the same expression as the unassisted region except that the channel inputs are not required to be independent. Finally, we show that the capacity region with non-signaling assistance shared only between each sender and the receiver independently is the same as without assistance.
