SGER: A unifying theory for capacity-achieving codes

本计画主要探讨低密度奇偶校验码及涡轮码等容量达成码之迭代译码之基本问题。具体来说，它的目的是找到一个统一的理论的伪码字的代码图，通过引入一个新的解码器，这样的代码。 目前文献中有三种伪码字的概念：图覆盖伪码字，对应于由原始码的坦纳图的有限覆盖定义的码中的码字;线性规划伪码字，是码的奇偶校验矩阵的基本多胞形中的有理点;以及计算树伪码字，其是码的坦纳图的计算树上的有效配置。 虽然文献中的大多数研究都集中在图覆盖伪码字和线性规划伪码字上（特别是Vontobel和Koetter已经证明这两个概念本质上是相同的），但Wiberg证明了计算树伪码字实际上是正确解码的障碍。在这个项目中提出的新的解码算法提供了一个精确的计算树pseudocodewords和其他两个概念的pseudocodewords之间的联系，从而允许现有的结果图覆盖和线性规划pseudocodewords进行修改，以适用于计算树pseudocodewords。 克劳德·香农（Claude Shannon）在1948年发表的著名论文《通信的数学理论》（A Mathematical Theory of Communication）及其信道编码定理催生了被称为编码理论的研究体系。 1993年Turbo码的发现和1996年低密度奇偶校验码的重新发现是编码理论的一个重要里程碑。 这两类代码配备了迭代消息传递解码算法，在该算法下，它们可以实现仅略高于香农定理所建立的最小值的信噪比的实际误比特率。 因此，这些码有时被认为在工程意义上解决了加性白色高斯噪声和类似信道的编码问题。然而，这些代码的解码算法远未完全理解，并且迄今为止在模拟中表现最好的代码是随机构造的。 因此，编码问题在数学意义上仍然非常未解决。 该项目的主要目标是更好地理解解码算法，目的是构建保证性能良好的代码的方法。

This project addresses fundamental questions in the area of iterative decoding of capacity achieving codes, including low density parity check(LDPC) codes and turbo codes. Specifically, it aims to find a unifying theory of pseudocodewords of codes on graphs, by introducing a new decoder for such codes. Currently, there are three notions of pseudocodeword in the literature: graph cover pseudocodewords, which correspond to codewords in codes defined by finite covers of the Tanner graph of the original code; linear programming pseudocodewords, which are rational points in the fundamental polytope of the parity check matrix of the code; and computation tree pseudocodewords, which are valid configurations on computation trees for the Tanner graph of the code. While most of the research in the literature has focused on graph cover pseudocodewords and linear programming pseudocodewords (and, in particular, Vontobel and Koetter have shown that these two notions are essentially the same), Wiberg proved that it is computation tree pseudocodewords that actually are the impediments to correct decoding. The new decoding algorithm proposed in this project provides a precise link between computation tree pseudocodewords and the other two notions of pseudocodewords, thus allowing existing results on graph cover and linear programming pseudocodewords to be modified to apply to computation tree pseudocodewords. This in turn provides an explanation for the empirical performance results for capacity achieving codes.Claude Shannon's famous 1948 paper "A Mathematical Theory of Communication" and its channel coding theorems spawned the body of research referred to as Coding Theory. The 1993 discovery of turbo codes and the 1996 re-discovery of low density parity check codes represent a major milestone in coding theory. These two classes of codes come equipped with iterative message-passing decoding algorithms under which they can achieve realistic bit error rates with signal-to-noise ratios that are only slightly above the minimum established by Shannon's theorems. As such, these codes are sometimes considered to have solved, in the engineering sense, the coding problem for the additive white Gaussian noise and similar channels. However, the decoding algorithms for these codes are far from completely understood, and the codes which perform best in simulations thus far are randomly constructed. Therefore, the coding problem remains very much unsolved in the mathematical sense. The primary goal of this project is a better understanding of the decoding algorithms, with an aim toward methods of constructing codes which are guaranteed to perform well.