Algebraic aspects of modern coding theory

本研究课题主要研究低密度奇偶校验码（LDPC）。 LDPC码配备了一个迭代的消息传递算法，该算法对与该码相关联的某个二分图进行操作。 该算法局部地作用于图，这一结果既体现了它的最大优点（低复杂度），也体现了它的最大弱点（非最优性）。 PI的重点是了解这个弱点。 因为算法是局部作用的，所以它不能判定它是作用在图本身上还是作用在图的某个有限非分歧覆盖上。 这导致了“伪码字”的概念，它来自与覆盖相对应的代码中的码字，并且损害了解码器。 因此，要理解LDPC码的性能，我们必须理解这些伪码字; PI考虑的大多数问题都源于理解LDPC码的伪码字的愿望。 在以前的联合工作中，PI给出了LDPC码伪码字的两种特征：通过所谓的“基本锥”和通过附加到码上的某个图的边zeta函数。 虽然基本的conecharacterization是有效的所有LDPC码，zeta函数特性是令人满意的，只有在特殊情况下的循环码。 PI将进一步研究基本锥和一般LDPC码的伪码字的zeta函数表征的发展。 另外的研究目标是非二进制LDPC码及其伪码字，以及LDPC码与另一类基于图的码：Turbo码之间的联系。 通过在数据中增加冗余，许多这样的错误可以被纠正。 如果信息被认为是固定长度的0和1的字符串，那么码字是长度更长的0和1的字符串，其中长度的差异表示添加的冗余量。 一组代码字被称为代码。 经典编码理论的很大一部分涉及到寻找代码的三个基本参数之间的权衡：代码的长度，代码的数量和最小汉明距离，即，任何两个不同码字的最小位置数。 虽然任何代码都可以纠正最多大约一半的最小距离的重量错误，但大多数代码可以纠正许多更高重量的错误。 现代编码理论的目标是找到那些允许解码算法的代码表示，这些解码算法允许纠正代码可以纠正的所有错误模式，而不仅仅是那些权重最多大约为最小距离一半的错误模式。 低密度奇偶校验（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.