CIF: Small: New Approaches to the Design and Analysis of Graphical Models for Linear Codes and Secret Sharing Schemes

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

NSF Proposal 0916919 New approaches to the design and analysis of graphical models for linear codes and secret sharing schemesAbstractError-correcting coding enables one to design reliable systems of transmission and storage of information and is used universally for sending packets over the web, in writing data on CD's and flash memory devices, and other similar means of modern communication. A very efficient method of encoding information for error protection is the so-called "iterative decoding," which assumes that every binary digit of transmission is recovered based on its realiblity and the realibility of a few other, carefully selected bits of the encoded message. This method of error correction is analyzed based on the representation of the encoding as a graph in the plane in which recovery from errors proceeds by successive exchange of information between the nodes of the graph in an iterative procedure performed in a number of rounds. One of the main goals of this research is to reduce complexity (the number of rounds) needed for reliable recovery of the transmission from errors in the communication medium.Graphical models of linear codes have so far been restricted to trellises, i.e., cycle-free graphs, and graphs with exactly one cycle (tail-biting trellises). This research studies complexity of realization of codes and iterative decoding algorithms on connected graphs with cycles, deriving complexity estimates from the tree-decomposition of graphs. One of the goals of this research is to find methods of constructing low-complexity realizations of codes for such well-known code families as Reed-Muller and Reed-Solomon codes, and explore the optimality gap of these representations. Methods of matroid theory used in the study of graphical models will also be explored in the analysis of access structures of secret sharing schemes and secure multi-party computation protocols.