Graph-Based Codes

University Of Nebraska-Lincoln, Lincoln NE

Investigators

Abstract

ABSTRACT Principal Investigator: Walker, Judy L. Proposal Number: DMS - 0903517 Institution: University of Nebraska-Lincoln Title: Graph-Based Codes Generally speaking, the goal of coding theory is to enable reliable transmission of data. This proposal considers both channel coding, i.e., reliable transmission of data across a noisy channel, and network coding, i.e., reliable transmission of data through a network. Channel coding is the appropriate model for most traditional applications, such as the transmission of satellite pictures from outer space, the storage (and retrieval) of computer data on a disk drive, and the transmission of a voice (or data) signal for a land line telephone. In each of these situations, information can be thought of as being put into a channel so that the (possibly corrupted) information comes out of the other end of the channel. Network coding, on the other hand, involves more complicated relaying, and possibly combining, of information. This is the correct model for a variety of more modern applications, such as cellular telephone networks (with their system of towers), sensor networks, camera surveillance networks, and peer-to-peer networks. In both (modern) channel coding and network coding, graph theory plays a crucial role. This proposal considers two types of channel codes based on graphs: codes defined by Tanner graphs and codes defined by tail-biting trellises. In each case, the codes come equipped with an iterative message-passing decoding algorithm that operates on the associated graph, that is extremely efficient, and that corrects, with high probability, many more error patterns than are guaranteed by the code's minimum Hamming distance. However, in both cases, the relevant algorithm's performance is hindered by the existence of pseudocodewords, which are objects that arise in similar ways as do codewords and which compromise the decoder. Thus to understand the performance of the algorithms, one must understand the pseudocodewords; most of the problems described in this proposal relating to channel coding stem from this observation. In network coding, the network over which we want to send information is modeled by a network, in the graph theory sense of the word. This proposal concerns both lossless networks, where one assumes any information transmitted is received without errors, and lossy networks, where one assumes that errors and/or erasures can occur. The problem in the lossless case is therefore not how to encode the information, but rather, given a network with its sources and sinks and given a desire to simultaneously transmit certain pieces of information from the sources to the sinks, how does one designate what information should be carried across each of the edges of the network? In the lossy case, one must consider this question along with the questions of how to ensure low error rates and how to guarantee robustness of the network.