Algebraic and Geometric Constructions of Shannon Limit Approaching Codes and Turbo Decoding of Reed-Solomon Codes

随着对无差错数据传输和数据存储需求的增加，错误控制在数据通信和数据存储系统中变得越来越重要。它已成为几乎所有数据通信或存储系统设计中不可或缺的一部分。今天，非常复杂的误差控制方案被广泛应用于通信和数据存储系统中，以实现可靠的数据传输和存储，例如无线通信、卫星通信、光通信、硬盘驱动器、光盘和许多其他系统。本研究的目的是设计出构造良好的错误控制码的方法，并开发出有效的错误控制方案，为未来一代数据通信和存储系统实现无错误通信和数据存储提供巨大的潜力。近年来，错误控制码和译码算法有了很大的发展。两个强大的码族，被称为涡轮码和低密度奇偶校验（lDPC）码，已经被发现和重新发现。这两个具有迭代解码的代码族已被证明在合理的实现复杂性下执行接近香农的理论极限。由于其惊人的错误性能和实际实现，预计这两类代码将在未来10年左右对几乎所有错误控制编码的应用产生巨大影响。本文研究了这两类Shannon极限逼近码的两个重要方面：LDPC码的构造和RS码的turbo译码。LDPC码的构造基于组合方法，如有限几何、超有限域、统计实验设计、置换群和图。在这些方法中，点、线、有限几何中的超平面、平衡不完全块设计、仿射置换群、路径和图的独立集被用于构造不包含短循环的LDPC码。所有的构造方法都是系统的，构造的代码具有良好的结构特性，简化了编码和解码的实现。RS码的Turbo解码是基于将代码二进制分解为一组简单的二进制分量码，并将代码表述为自连接代码，RS码本身作为外部代码，分量码作为Turbo编码安排中的内部代码。译码分turbo内译码和外代数软判决译码两个阶段进行。

As the demand for error-free data transmission and data storage increases, error control becomes increasingly important in data communication and datastorage systems. It has become an integral part in almost every data communication or storage system design. Today very sophisticated error control schemes are being used in a broad range of communication and datastorage systems to achieve reliable data transmission and storage, such aswireless communication, satellite communication, optical communication, hard disc drives, compact disks and many others. The objective of this research is to devise methods for constructing good error control codes and to develop efficient error control schemes which have great potential to achieve error-free communication and data storage for the future generationof data communication and storage systems.Recently, there have been dramatic developments in error control codes anddecoding algorithms. Two families of powerful codes, known as turbo andlow density parity check (lDPC) codes, have been discovered and rediscovered.These two families of codes with iterative decoding have been shown to perform close to Shannon's theoretical limits with reasonable implementationcomplexity. As a result of their amazing error performance and practicalimplementation, it is anticipated that these two classes of codes will havean enormous impact on virtually all applications of error control coding overthe next 10 years or so. This research involves in two important aspectsof these two classes of Shannon limit approaching codes: construction of LDPC codes and turbo decoding of Reed-Solomon (RS) codes. The construction of LDPC codes is based on combinatoric appraches, such as finite geometries overfinite fields, statistical experimental designs, permutation groups andgraphs. In these approaches, points, lines, hyperplanes in finite geometries, balanced incomplete block designs, affine permutation groups, and pathsand independent sets of graphs are used for constructing LDPC codes whoseTanner graphs do not contain short cycles. All the construction methodsare systematic and codes constructed have good structural properties whichsimplify encoding and decoding implementations. Turbo decoding of a RS code is based on binary decomposition of the code into a set of simple binary component codes and formulating the code as a self concatenated code with the RS code itself as the outer code and the component codes as inner codes in a turbo coding arrangement. The decoding is carried out in two stages, turbo inner decoding and outer algebraic soft-decision decoding.