Algebraic aspects of modern coding theory

点击翻译按钮获取中文摘要

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.