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

随着对无差错数据传输和数据存储需求的增加，差错控制在数据通信和数据存储系统中变得越来越重要。 它已成为几乎所有数据通信或存储系统设计中不可或缺的一部分。 今天，非常复杂的差错控制方案被广泛用于通信和数据存储系统中，以实现可靠的数据传输和存储，例如无线通信、卫星通信、光通信、硬盘驱动器、光盘和许多其他系统。 本研究的目的是设计构造好的差错控制码的方法，并开发有效的差错控制方案，这些方案对于实现下一代数据通信和存储系统的无差错通信和数据存储具有巨大的潜力。 人们发现并重新发现了两类功能强大的码，即Turbo码和低密度奇偶校验（LDPC）码，这两类迭代译码的码在合理的实现复杂度下，性能接近香农的理论极限。 由于它们惊人的错误性能和实际实现，预计这两类代码将在未来10年左右的时间里对几乎所有的错误控制编码应用产生巨大影响。 本文的研究工作主要涉及这两类香农限逼近码的两个重要方面：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.