Graph-Based Codes

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

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.