Algebraic aspects of modern coding theory

本项目涉及一类低密度奇偶校验(LDPC)码。LDPC码配备了一种迭代消息传递算法，该算法在与该码相关联的某个二部图上操作。该算法局部地作用于图，这导致了它的最大优点(低复杂性)和最大缺点(非最优性)。私家侦探的重点是了解这一弱点。因为该算法作用于局部，所以它不能区分它是作用于图本身还是作用于图的某个有限未分支覆盖。这就引出了“伪码字”的概念，伪码字来自与封面相对应的代码中的码字，并且危及解码器。因此，要了解LDPC码的性能，我们必须了解这些伪码字；PI认为的大多数问题都源于对LDPC码伪码字的了解。在以前的联合工作中，PI给出了LDPC码伪码字的两种刻画：通过所谓的“基本锥”和通过附加在码上的某一图的边Zeta函数。虽然基本特征描述对所有LDPC码都有效，但Zeta函数描述仅在循环码的特殊情况下才令人满意。PI将进一步研究基本锥体，并开发用于一般LDPC码的伪码字的Zeta函数表征。其他的研究对象是非二进制LDPC码及其伪码字，以及LDPC码和另一类基于图的码：Turbo码之间的联系。通过向数据添加冗余，这些错误中的许多都可以纠正。如果信息被认为是固定长度的字符串0‘S和1’，则码字是长度较长的0‘S和1’S的字符串，其中长度的差异表示添加的冗余量。称为代码的码字集合。经典编码理论的很大一部分是关于寻找一个码的三个基本参数之间的权衡：它的长度、它的码字数和它的最小汉明距离，即任何两个不同的码字不同的最小位置数。虽然任何代码都可以粗略地纠正最小距离的一半的权重错误，但大多数代码可以纠正许多显著更高的权重错误。现代编码理论的目标是找到那些允许译码算法的代码表示，这些译码算法允许纠正代码可以纠正的所有错误模式-不仅是那些重量最多大约是最小距离的一半的错误模式。到目前为止，现代编码理论最伟大的成就之一是低密度奇偶校验码(LDPC)的发现和随后的发展。这些代码的实用性源于这样一个事实，即它们配备了一种非常有效的解码算法，该算法对与代码相关的特定二部图进行操作。本项目的主要目标是进一步了解这种译码算法的理论性能，特别是通过研究与二部图的有限覆盖相关的码所产生的所谓的伪码字。

This project concerns the class of Low Density Parity Check (LDPC)codes. LDPC codes come equipped with an iterative message-passingalgorithm which operates on a certain bipartite graph associated tothe code. The algorithm acts locally on the graph, and this resultsin both its greatest strength (low complexity) and its greatestweakness (nonoptimality). The PI's focus is on understanding thisweakness. Because the algorithm acts locally, it cannot distinguishif it is acting on the graph itself or on some finite unramified coverof the graph. This leads to the notion of "pseudo-codewords", whicharise from codewords in codes corresponding to the covers and whichcompromise the decoder. Thus to understand the performance of LDPCcodes, we must understand these pseudo-codewords; most of the problemsthe PI considers stem from the desire to understand pseudo-codewordsof LDPC codes. In previous joint work, the PI has given twocharacterizations of the pseudo-codewords of an LDPC code: via theso-called "fundamental cone" and via the edge zeta function of acertain graph attached to the code. While the fundamental conecharacterization is valid for all LDPC codes, the zeta functioncharacterization is satisfactory only in the special case of cyclecodes. The PI will further her study of the fundamental cone and thedevelopment of a zeta function characterization for pseudo-codewordsof general LDPC codes. Additional targets of study are non-binaryLDPC codes and their pseudo-codewords as well as the connectionsbetween LDPC codes and another class of graph-based codes: turbocodes.Whenever information is transmitted across a channel, errors are boundto occur. By adding redundancy to the data, many of these errors canbe corrected. If the information is thought of as strings 0's and 1'sof fixed length, then the codewords are strings of 0's and 1's oflength some longer length, where the difference in lengths representsthe amount of redundancy which was added. A collection of codewordsis called a code. A large part of classical coding theory isconcerned with finding the trade-offs between three fundamentalparameters of a code: its length, its number of codewords, and itsminimum Hamming distance, i.e., the minimum number of positions inwhich any two distinct codewords differ. While any code can correctall errors of weight at most rougly half its minimum distance, mostcodes can correct many errors of substantially higher weight. It isthe goal of modern coding theory to find those representations ofcodes that admit decoding algorithms that allow for correction of allthe error patterns that the code can correct --- not only those whichhave weight at most roughly half the minimum distance. One of thegreatest achievements of modern coding theory so far is the discoveryand subsequent development of the class of Low Density Parity Check(LDPC) codes. The usefulness of these codes stems from the fact thatthey come equipped with a very efficient decoding algorithm whichoperates on a certain bipartite graph associated to the code. Themain goal of this project is to further the understanding of thetheoretical performance of this decoding algorithm, especially throughthe study of the so-called "pseudo-codewords" which arise from codesassociated to finite covers of the bipartite graph.