论文标题
通过撕纸频道进行通信
Communicating over the Torn-Paper Channel
论文作者
论文摘要
我们考虑在一个随机将消息块“撕裂”到不同尺寸的小部分并随机散装的频道上进行交流的问题。对于具有块长度$ n $和长度$ {\ rm几何}（p_n）$的二进制撕裂纸通道，我们将容量描述为$ c = e^{ - α} $，其中$α= \ lim_ {n \ to \ fto \ to \ infty} p_n} p_n \ log n $。我们的结果表明，$ {\ rm几何}（p_n）$长度片段和确定性长度的情况 - $（1/p_n）$片段在质上有所不同，令人惊讶的是，前者的容量更大。直觉上，这是由于以下事实：在随机片段中，有时会观察到大片段，从而提高了能力。
We consider the problem of communicating over a channel that randomly "tears" the message block into small pieces of different sizes and shuffles them. For the binary torn-paper channel with block length $n$ and pieces of length ${\rm Geometric}(p_n)$, we characterize the capacity as $C = e^{-α}$, where $α= \lim_{n\to\infty} p_n \log n$. Our results show that the case of ${\rm Geometric}(p_n)$-length fragments and the case of deterministic length-$(1/p_n)$ fragments are qualitatively different and, surprisingly, the capacity of the former is larger. Intuitively, this is due to the fact that, in the random fragments case, large fragments are sometimes observed, which boosts the capacity.
