Code Representation and Performance of Graph-Based Decoding

CCF-0829865基于图的解码的代码表示和性能PI：Paul H. Siegel，UC San Diego摘要：当与基于迭代图的解码算法配对时，接近信息理论性能极限的信道码的发现代表了编码理论和实践的重大进步。主要示例包括turbo码、低密度奇偶校验（LDPC）码和重复累积（RA）码。这些编码技术及其变体对数据传输应用产生了深远的影响，包括深空通信、数字视频广播和移动的无线电话。它们也准备用于其他环境，如高密度数字数据存储。这些编码和解码方案的共同之处在于，它们的性能和实现复杂度不仅取决于代码本身，还取决于代码的图形表示的选择。本研究探讨影响迭代译码算法性能的码表示特征，以及构造最佳码表示的方法。 这项研究有两个主要目标。首先是检查线性码表示的组合和图形特性，这些线性码表示作为具有理论和实际意义的几种类型的信道上的迭代解码器性能的品质因数。 对这些属性的理解指导改进的代码设计以及新的基于图的解码策略的开发。 第二个重点是分析和增强基于线性规划的解码器。研究了自适应引入约束以降低译码器复杂度和提高译码性能的方法。它还考虑了新的线性规划算法，利用稀疏代码表示。这两个研究推力之间的动态相互作用是通过研究迭代和线性规划解码器之间的关系，以及它们在均衡和检测通道与内存的应用。

CCF-0829865Code Representation and Performance of Graph-Based DecodingPI: Paul H. Siegel, UC San DiegoAbstract: The discovery of channel codes that approach information-theoretic performance limits when paired with iterative graph-based decoding algorithms represents a major advance in coding theory and practice. Prime examples include turbo codes, low-density parity-check (LDPC) codes, and repeat-accumulate (RA) codes. These coding techniques and their variants have had a profound impact on data transmission applications, including deep space communications, digital video broadcasting, and mobile wireless telephony. They are also poised for use in other settings, such as high density digital data storage. What is common to these coding and decoding schemes is that their performance and implementation complexity depend not only on the code itself, but also on the choice of graphical representation of the code. This research studies the characteristics of code representations that influence the performance of iterative decoding algorithms, as well as methods for constructing the best representations. The research has two major thrusts. The first is the examination of combinatorial and graphical properties of linear code representations that serve as figures of merit for iterative decoder performance on several types of channels having theoretical and practical significance. The understanding of these properties guides improved code design as well as the development of new graph-based decoding strategies. The second thrust is the analysis and enhancement of decoders based upon linear programming. The research studies the adaptive introduction of constraints to reduce decoder complexity and to improve performance. It also considers new linear programming algorithms that exploit sparse code representations. A dynamic interplay between these two research thrusts is achieved by studying the relationship between iterative and linear programming decoders, as well as their application to equalization and detection for channels with memory.