Coding Theorems for Noisy Permutation Channels
Coding Theorems for Noisy Permutation Channels
复制标题
DOI：
10.1109/tit.2020.3009468
复制
发表时间：
2020-11-01
影响因子：
2.5
通讯作者：
Makur, Anuran
中科院分区：
文献类型：
--
作者：
Makur, Anuran
在本文中，我们正式定义和分析的噪声置换信道类。噪声置换信道模型构成了一个标准的离散无记忆信道（DMC），随后是一个独立的随机置换，重新排序的DMC的输出码字。虽然这个模型的编码理论方面已被广泛研究，特别是在可靠的通信在网络环境中的数据包进行换位的背景下，和密切相关的模型的DNA为基础的存储系统最近也进行了分析，我们发起了一个信息理论研究这个模型通过定义一个适当的概念，嘈杂的置换信道容量。具体来说，在可扩展性方面，我们证明了一个下界的噪声置换信道容量的任何DMC的随机矩阵的秩的DMC。在匡威的方面，我们建立了两个上界的噪声置换信道容量的任何DMC的随机矩阵是严格正的（条目明智的）。总之，这些界限产生的编码定理，其特征在于每一个严格的正满秩DMC的噪声置换信道容量，和我们的可扩展性证明产生一个概念上简单，计算效率高，和容量实现编码方案，这样的DMC。此外，我们还证明了著名的输出退化前序信道和噪声置换信道容量之间的关系。事实上，我们的匡威边界之一的证明利用了一个退化的结果，该结果为任何DMC构造对称信道，使得DMC是对称信道的退化版本。最后，我们举例说明了一些特殊情况下的二进制对称通道和（一般）擦除通道。有些令人惊讶的是，我们的研究结果表明，噪声置换信道容量通常是相当不可知的定义DMC的参数。
In this paper, we formally define and analyze the class of noisy permutation channels. The noisy permutation channel model constitutes a standard discrete memoryless channel (DMC) followed by an independent random permutation that reorders the output codeword of the DMC. While coding theoretic aspects of this model have been studied extensively, particularly in the context of reliable communication in network settings where packets undergo transpositions, and closely related models of DNA based storage systems have also been analyzed recently, we initiate an information theoretic study of this model by defining an appropriate notion of noisy permutation channel capacity. Specifically, on the achievability front, we prove a lower bound on the noisy permutation channel capacity of any DMC in terms of the rank of the stochastic matrix of the DMC. On the converse front, we establish two upper bounds on the noisy permutation channel capacity of any DMC whose stochastic matrix is strictly positive (entry-wise). Together, these bounds yield coding theorems that characterize the noisy permutation channel capacities of every strictly positive and full rank DMC, and our achievability proof yields a conceptually simple, computationally efficient, and capacity achieving coding scheme for such DMCs. Furthermore, we also demonstrate the relation between the well-known output degradation preorder over channels and noisy permutation channel capacity. In fact, the proof of one of our converse bounds exploits a degradation result that constructs a symmetric channel for any DMC such that the DMC is a degraded version of the symmetric channel. Finally, we illustrate some examples such as the special cases of binary symmetric channels and (general) erasure channels. Somewhat surprisingly, our results suggest that noisy permutation channel capacities are generally quite agnostic to the parameters that define the DMCs.