The Mathematics of Pseudocodewords

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

Smarandache1313221 This project focuses on the analysis of certain vector spaces over finite fields, called low-density parity-check (LDPC) codes, that have a set of sparse vectors generating the dual space. While these codes show great promise in current and future communication systems, their performance has been limited by the existence of so-called pseudocodewords. The main goal of this research is to develop a comprehensive mathematical theory of these objects by combining tools from coding and information theory, linear algebra, combinatorics, and graph theory. It is achieved by an analysis of the codewords corresponding to the cover graphs of the associated code graphs -- called protograph-based codes -- and the pseudocodewords obtained by projecting these codewords onto the code graphs, an analysis of the pseudocodewords in the fundamental cones (with implications in linear programming decoding and iterative decoding), and an analysis of the pseudo-weights (the measure of performance under iterative decoding) with implications in code performance. Despite significant progress in the last decades, the performance of current communication systems is still not satisfactory in many situations, such as when delay is important, power is critical, or bandwidth is constrained. This project studies the reasons why current coding techniques underperform relative to theoretical limits and develops a mathematical theory that explains their shortcomings and helps design better codes. The investigator's joint appointment with the department of electrical engineering and her collaboration with engineering experts from academia and industry ensure that the project has an impact beyond the theoretical realm; the analytical findings are exploited to improve the reliability of current and future communication systems. Because reliable communication is at the heart of ubiquitous access to and exchange of data, the nation's information technology infrastructure benefits from the project. Its impact is, however, not restricted to channel coding, but extends to areas such as computer science, networking, and compressed sensing.