Graph-Based Codes

主要研究人员：Walker，Judy L.建议编号：DMS-0903517机构：内布拉斯加大学林肯分校标题：基于图形的编码一般而言，编码理论的目标是实现可靠的数据传输。该方案既考虑了信道编码，即通过噪声信道可靠地传输数据，也考虑了网络编码，即，通过网络可靠地传输数据。信道编码是适用于大多数传统应用的模型，例如从外层空间传输卫星图像，在磁盘驱动器上存储(和检索)计算机数据，以及传输用于陆线电话的语音(或数据)信号。在这些情况中的每一种情况下，信息都可以被认为被放入通道中，以便(可能被破坏的)信息从通道的另一端传出。另一方面，网络编码涉及更复杂的信息中继以及可能的组合。这是适用于各种更现代应用的正确模型，例如蜂窝电话网络(及其塔系统)、传感器网络、摄像机监视网络和对等网络。在(现代)信道编码和网络编码中，图论都起着至关重要的作用。该方案考虑了两种基于图的信道码：由Tanner图定义的码和由咬尾网格定义的码。在每种情况下，码都配备了迭代消息传递解码算法，该算法在关联图上操作，非常高效，并且以很高的概率纠正比码的最小汉明距离保证的更多的错误模式。然而，在这两种情况下，相关算法的性能都受到伪码字的存在的阻碍，伪码字是以类似于码字的方式出现的对象，并且危及解码器。因此，为了理解算法的性能，必须理解伪码字；本提案中描述的与信道编码有关的大多数问题都源于这一观察结果。在网络编码中，在图论意义上，我们想要发送信息的网络是由网络建模的。该建议涉及无损网络和有损网络，在无损网络中，假设传输的任何信息都是无差错的，在有损网络中，假设可能发生错误和/或擦除。因此，无损情况下的问题不是如何对信息进行编码，而是给定一个具有其信源和信宿的网络，并且给出同时将某些信息从信源传输到信宿的愿望，如何指定应该通过网络的每个边缘携带什么信息？在有损耗的情况下，必须考虑这个问题以及如何确保低错误率和如何确保网络的健壮性的问题。

ABSTRACTPrincipal Investigator: Walker, Judy L. Proposal Number: DMS - 0903517Institution: University of Nebraska-LincolnTitle: Graph-Based CodesGenerally 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.