Error Probability Analysis of Binary Asymmetric Channels
Error Probability Analysis of Binary Asymmetric Channels
复制标题
二进制非对称信道的错误概率分析
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Organization
中科院分区：
文献类型：
--
作者：
S. M. Moser;Po;Hsuan;Organization
在他1948年的世界著名论文中，香农将信道容量定义为信息在通信信道上传输的最终速率，如果我们允许块长度无限大，则错误概率将消失。虽然这一结果具有巨大的理论重要性，但实际系统的现实情况看起来完全不同：没有通信系统会容忍由极大的块长度引起的无限延迟，也不能处理解码如此巨大的码字的计算复杂性。另一方面，也不需要具有恰好为零的错误概率，一个小的但有限的值就足够了。因此，问题是在一个实际的计划中可以做些什么。特别地，对于给定的固定最大块长度，可以在通信信道上发送信息的最大速率是多少（即，一个固定的最大延迟），如果我们允许一定的最大错误概率？在这个项目中，我们已经开始研究这些问题。研究了在最一般的二进制信道--二进制非对称信道（BAC）上具有很短块长的块码。它示出，只有两个可能的消息，触发器代码是最佳的，然而，取决于块长度和信道参数，不一定是线性触发器代码。进一步证明了最优解码规则是阈值规则。给出了最佳码对信道的一些基本依赖关系。本文研究了在二进制对称信道和Z信道中码字数很少的分组码。最佳的（在最小的平均错误概率的意义上，使用最大似然解码）的代码结构推导出的情况下，两个，三个，和四个码字和一个任意的块长度。结果表明，对于两种可能的消息，在BSC上，所谓的翻转码类型t是最佳的任何t，而在ZC上，翻转码类型0是最佳的。对于三个或四个消息的代码，它表明，所谓的弱翻转码的一些给定的类型是最佳的类型取决于块长度。对于所有的情况，我们提出了一个算法，可以从长度为n-1的最优码递归地构造出块长度为n的最优码。在两个和四个消息的情况下，最佳码是线性的。对于ZC，在五种可能消息的情况下，给出了递归最优码设计。这些最佳代码的推导在很大程度上依赖于一种新的方法，构建和分析的代码矩阵，而不是行（码字），但列。此外，这些结果也证明了最小汉明距离可能是错误的最佳码的设计准则，即使是非常对称的信道，如BSC。
In his world-famous paper of 1948, Shannon defined channel capacity as the ultimate rate at which information can be transmitted over a communication channel with an error probability that will vanish if we allow the blocklength to get infinitely large. While this result is of tremendous theoretical importance, the reality of practical systems looks quite different: no communication system will tolerate an infinite delay caused by an extremely large blocklength, nor can it deal with the computational complexity of decoding such huge codewords. On the other hand, it is not necessary to have an error probability that is exactly zero either, a small, but finite value will suffice. Therefore, the question arises what can be done in a practical scheme. In particular, what is the maximal rate at which information can be transmitted over a communication channel for a given fixed maximum blocklength (i.e., a fixed maximum delay) if we allow a certain maximal probability of error? In this project, we have started to study these questions. Block-codes with very short blocklength over the most general binary channel, the binary asymmetric channel (BAC), are investigated. It is shown that for only two possible messages, flip-flop codes are optimal, however, depending on the blocklength and the channel parameters, not necessarily the linear flipflop code. Further it is shown that the optimal decoding rule is a threshold rule. Some fundamental dependencies of the best code on the channel are given. Block-codes with a very small number of codewords are investigated for the two special binary memoryless channels, the binary symmetric channel (BSC) and the Z-channel (ZC). The optimal (in the sense of minimum average error probability, using maximum likelihood decoding) code structure is derived for the cases of two, three, and four codewords and an arbitrary blocklength. It is shown that for two possible messages, on a BSC, the so-called flip codes of type t are optimal for any t, while on a ZC, the flip code of type 0 is optimal. For codes with three or four messages it is shown that the so-called weak flip codes of some given type are optimal where the type depends on the blocklength. For all cases an algorithm is presented that constructs an optimal code for blocklength n recursively from an optimal code of length n− 1. In the situation of two and four messages, the optimal code is shown to be linear. For the ZC a recursive optimal code design is conjectured in the case of five possible messages. The derivation of these optimal codes relies heavily on a new approach of constructing and analyzing the code-matrix not row-wise (codewords), but column-wise. Moreover, these results also prove that the minimum Hamming distance might be the wrong design criterion for optimal codes even for very symmetric channels like the BSC.