用于低密度奇偶校验译码的近似计算电路

论文总字数：22431字

摘 要

Abstract II

第一章 绪论 1

1.1 引言 1

1.2 LDPC码的研究背景及研究现状 2

1.3 LDPC码的实现与应用 3

1.4 研究目的和主要内容 3

第二章 LDPC码简介及其译码算法 5

2.1 LDPC码及其二分图表示 5

2.2 LDPC码的消息传递译码算法 8

2.2.1 BP 算法 10

2.2.2 对数似然比表示的BP算法（LLR-BP） 12

2.2.3 最小和算法（MS） 14

2.2.4 归一化的最小和算法（NMS） 15

第三章 基于近似运算的NMS 16

3.1 近似加法器 16

3.1.1 Generate（g）信号、 propagate（p）信号和Kill（k）信号 16

3.1.2 计算精度温和下降的近似加法器（Accuracy Gracefully-Degrading Adder,GDA） 18

3.2 归一化因子的确定 21

3.3 限幅幅度及量化比特数目的确定 22

第四章 算法性能仿真 26

4.1 典型译码算法实现及其仿真结果 26

4.2 图像处理结果 26

4.3 基于近似运算的NMS仿真结果 28

总结与展望 30

总结 30

展望 30

致谢 31

用于低密度奇偶校验译码的近似计算电路

摘要

上世纪60年代，虽然Gallager提出了低密度奇偶校验码（LDPC码），并给出了相应的概率译码算法，但是受到当时硬件计算能力的限制并没有得到重视，近年来随着硬件的不断发展，限制LDPC码发展的瓶颈被打破，LDPC码以其优良的性能又重新走进了人们的视野，成为了研究热点。与此同时，近似计算由于可以在计算性能和计算能耗上得到折中，或者能够在损失一部分计算精度的基础上得到其他方面的提高，也得到了人们的关注。本文重点对LDPC码的译码算法进行了学习以及研究，并基于近似加法器对最小和译码算法进行了改进。

本文着眼于LDPC码的译码算法，学习并研究了BP算法，最小和算法（MS）以及归一化的最小和算法（NMS），从迭代次数，运算复杂度等方面比较了算法之间的不同以及优势和劣势，并给出了一定仿真环境下的误码率曲线。

由于归一化的最小和算法中只含有一些简单的求和以及比较运算，最适合于硬件实现，在对近似加法器有了一定研究之后，将近似运算应用在迭代译码上，基于计算精度温和下降的近似加法器（GDA），对NMS算法的迭代过程进行改进，提出了一种近似迭代计算的最小和译码算法，仿真其误码率特性，验证了该思想的可行性。由于采用了近似加法器，硬件实现时，不论其面积还是计算复杂度都会有所降低。

关键词：LDPC码；近似加法器；最小和算法

Abstract

In the year of 1962, Gallager first proposed the low-density parity-check (LDPC) code and its corresponding probabilistic propagation decoding algorithms. But it was not taken seriously at that time because of the limited level of computer. Recently, with the development of the computer, LDPC codes attract more and more attention. At the same time, approximate computing also become a research hotspot these days as it is able to tradeoff computation quality and computational effort for various applications. This paper focus on the decoding algorithms of LDPC codes and make some improvement on the minimum-sum decoding algorithm based on approximate adder.

We focus on decoding algorithms of LDPC codes including belief propagation algorithm (BP), minimum-sum algorithm (MS) and normalized minimum-sum algorithm (NMS). We compared these algorithms from the number of iterations, the complexity of computing and etc. Also, the performances of bit-error-rate are given.

There is no very complex calculation in NMS so that it is suitable to realize in hardware. After studying the approximate adders, approximate computing is applied in NMS. The accuracy gracefully-degrading adder is substitute for the precise adder. Similarly, the performance of bit-error-rate is given and prove that the effectiveness of this method. In this way, the area of the hardware can be reduced, as well as the complexity.

Key words: LDPC codes; approximate adder; minimum-sum algorithm

1. 绪论
   1. 引言

20世纪以来，通信以及计算机技术在以惊人的速度在发展。在这一发展过程中，不得不提的及其重要的一部分就是在60年前香农发表了他的一篇开创性的文章《通信中的数学理论》，在这之后，通信领域得到了长足的发展。在这篇文章中，香农提出并构建了这样一个问题的框架：如何能够高效的并且可靠的传输信息？同时，香农给出了一个基本的答案，唯有编码可以做到这一点。在当时，寻求一种可以达到理论传输极限的实用性的编码方案成为了信息理论以及通信问题研究中的核心。

在上个世纪九十年代初期，伴随着编码领域一些基础范例的出现，编码得到了极大的发展。在现代编码领域中，随机稀疏图模型所描述的码被认为是一个大型的复杂系统，编码和译码通过一些高效的局部算法所完成。码不同比特之间的局部联系是比较简单的，但是从总体来看，码字是很复杂的，也只有这样才能保证高效而又可靠的通信，随机码就是受到香农最初的理论的启发而出现的。这一阶段是在编码理论以及实践过程中令人激动的阶段，除了已经取得的一些进展，很多基础的问题仍待解决。短时间内，现代编码理论不会替代传统的编码，随时随地的，RS（Reed-Solomon）码在我们生活中无处不在，使得我们的生活井井有条。现代编码理论提供了多种多样的信息系统的解决方案，目前绝大多数的无线通信系统中都应用了现代编码理论。香农理论中典型的问题就是，在充满噪声的信道中传输消息，在接收端如何才能准确的收到消息。为了解决这样一个通信问题，信道编码译码就显得极其重要了^[1]。

考虑点对点的通信场景，如图1.1所示。信源通过信道（电话线，无线或者存储介质等）传输一定的信息（通话，图像或者数据等）到接收端。

信源

信道

接收

图1.1 基本的点到点通信问题

在香农1948年发表的论文中，他建立了基本的通信模型并且说明了点对点通信问题可以分解为图1.2表示的两个独立的问题。

图1.2 分解的点对点通信问题

首先，信源编码器将信源的信息转换为一定的比特流，在理想的条件下，信源编码器会除去消息中一切的冗余信息，这样得到的比特流也就含有最少的比特数目，但是同时保证消息是完全精确的。之后信道编码器在比特流中添加冗余，也就是进行信道编码，可以有效的抵抗信道中的噪声干扰。

• 1. LDPC码的研究背景及研究现状

在1948年香农提出一系列开创性的理论，40多年前，Gallager提出了LDPC码^[2]，其中包括了两种开创性的思想：迭代译码以及随机受限码的构造。然而，除了Zyablov和Pinsker的论文以及Tanner和Margulis的论文，Gallager的工作被学术界大部分的学者所忽略了近30年。随着Turbo码的提出，人们发现，以上两个思想也在Turbo码上得以体现，这样LDPC码才重新进入了人们的视野，开始单独被拿来研究^[3]。

20世纪90年代中期，MacKay等人在对基于图模型的编码译码的研究热潮下重新对LDPC码进行了研究，并且证明了LDPC码在高斯信道以及BSC（二进制对称信道）下的性能比标准的卷积码和级联码还要好，可以达到像Turbo码一样逼近香农极限^[4]。在这之后，LDPC码成为差错控制领域的研究热点之一。

在LDPC码中，多种因素都会影响其译码性能，比如编码算法的设计，稀疏矩阵的构造，译码算法的设计等。借鉴之前的一些研究，在理想的编码条件下，也就是Tanner图中不存在闭合回路时，BP（Belief Propagation）译码算法的译码结果与最大似然译码算法的结果不相上下。但是在码长有限时必然会存在闭合回路。在这种情况下，BP算法的性能就与理论译码性能有所差距，如何缩小差距将是一个研究课题。除了软信息译码算法之外硬判决算法虽然性能上稍微差一些，但是译码复杂度很低，比较适合在诸如光钎通信这样信道条件比较好的系统中应用。针对硬判决的译码算法改进同样是未来的一个研究方向。

近些年来，在如何有效的分析以及提高LDPC码的性能上已经有了大量的研究^[5]。究其原因，除了它在译码性能上的优秀表现，另外一个能够吸引人们关注的重要的原因就是BP算法内在的可以并行实现的特性，每个节点（校验节点和变量节点）的计算都是非常简单的，这样就可以达到一个很高的译码速度。可以预想到，高效的LDPC编码器以及译码器是在硬件实现上的一个关键问题。

• 1. LDPC码的实现与应用

通常的，不同的编码方法其编码复杂度是不一样的，而且有可能会有很大的区别。采用信息矢量去和生成矩阵相乘的编码方法，由于LDPC码的码长很长，复杂度是很高的。因为我们首先构造的是一个稀疏校验矩阵，再通过诸如高斯消元的方法得到生成矩阵，虽然校验矩阵是稀疏矩阵(数值为0的元素数目远远多于非0元素的数目)，但是就不再具有稀疏矩阵的性质了。难以让人接受的编码复杂度限制了LDPC码的进一步发展，于是人们对于如何降低编码复杂度也进行了大量的研究，其中，Urbanke以及Richardson在[6]中提出了一种通用的适用于所有LDPC码的编码方法。利用贪婪算法通过一系列行列变换，校验矩阵变换为近似下三角矩阵的形式，使得编码复杂度大大降低。

在未来的移动通信系统中，高速数据传输将是其发展的必然趋势。一旦数据传输速率有了大幅的提高，原本就存在的多径衰落所带来的问题就更加明显。传统的信道均衡技术已经无法解决急剧恶化的符号间干扰问题。对于广泛应用在无线通信中的高速率传输的正交频分复用（OFDM）系统，它将宽带系统分割成若干个窄带信号，其中相互正交的子载波并行传输，有效的避免了传输信号的选择性衰落。因为OFDM具有优良的抗多径衰落能力，被IEEE802.16a宽带无线接入标准纳入其物理层的调制技术^[7]。

• 1. 研究目的和主要内容

本文的研究重点在于LDPC码的译码。为了保证译码结果的可靠性，重点研究LDPC的迭代译码算法，比如BP算法，最小和算法（Minimum-Sum），归一化的最小和算法（Normalized Minimum-Sum）等，并给出了不同迭代译码算法的相关仿真曲线。其中，由于最小和译码算法中没有BP算法中正切以及反正切这样复杂的运算，更加适合于硬件实现，因此在限幅量化之后给出了最小和算法的相关仿真曲线。

在实际应用中，LDPC译码电路的面积、功耗以及译码速率都是工程中所关心的要素。近似计算可以简化计算过程，减小电路面积，提高运算速率。本质上，最小和算法是一种概率传播译码算法，将近似运算应用到译码过程中，性能可以得到一定的提升。根据这个思想，提出了一种基于近似运算的归一化最小和算法，将近似加法器应用于译码过程中并给出了相关的仿真曲线，证明了该思路的有效性。

1. LDPC码简介及其译码算法
   1. LDPC码及其二分图表示

LDPC码和目前为止研究的网格码和分组码有着显著的区别，首先，相比于其他两种码，LDPC码是随机构造的。除此之外，LDPC码对应译码算法的复杂度和其对应的分组的长度是成一种线性的复杂度。LDPC码因为其出色的性能在很多应用中都引人注目。在本节中，会介绍构造规则LDPC码的基本方法以及它的二分图表示。LDPC码及其译码器和香农编码定理提出的码有些不同，它可以看做是在一组大型分组码中进行筛选得到的。MacKay^[8]证明，将随机编码与LDPC的稀疏生成矩阵结合起来，随着码长的增长，可以接近香农极限。

假若有一线性分组码，其码率是，它可以由一个大小为的奇偶校验矩阵来表示，其中，。中的每一个元素都是有限域中的元素。本文只考虑二进制码，因此，校验矩阵中的元素不是0就是1，而且所有的运算操作都是模二运算。中的所有码字向量都属于的零空间，也就是满足。给定一个奇偶校验矩阵，可以得到与之对应的大小为的生成矩阵，满足。根据可知，生成矩阵可以作为编码器的一部分。

从最简单的角度来看，LDPC码是一种线性分组码，其奇偶检验矩阵是稀疏矩阵，也就是说，校验矩阵中的元素只有少部分是非零的。在[2]中，Gallager提出了一种构造LDPC码的方法，也就是在奇偶校验阵中随机的放入0或者1，同时满足一个约束条件，即中的每行有固定数目个1，每列也有固定数目个1。比如一个的奇偶校验矩阵，如图2.1。该矩阵中，，，码长。这种类型的矩阵就是规则的长度为的的LDPC码。在一个的LDPC码中，每一个信息比特都参加了个校验等式的校验，每一个校验位比特都包含了个信息位的信息。校验阵中的1所占的比例为，由于与相比是非常小的，所以这个比值是非常接近于0的，这也是低密度奇偶校验码的名字由来。

图2.1 Gallager型低密度奇偶校验矩阵

现在来确定由定义的LDPC码码率，由于奇偶校验矩阵是随机构造的，不能保证矩阵不同的行之间是线性无关的，也不能保证矩阵是满秩的。事实上，在图2.1中，的秩为13，而由它确定的码字码率为。一般的，这样随机构造的矩阵都不会是满秩的。我们可以消除行与行之间的线性相关性而找到一个满秩的大小为的奇偶校验矩阵，但是这个矩阵就不一定是规则的了。当比较大的时候，比较好的做法就是保留原来那个不满秩的矩阵，设计其码率为。

在定义好一个的规则LDPC码之后，现在要构建这样一个码字。首先要确定，，和，他们之间存在着一定的约束关系：，为了保证码率小于1，要小于。假定码长和码率由应用来确定，下面所要确定和的合适的值。在[2]中，Gallager给出了在典型的规则LDPC码中，最小码距是随着码长线性增加的，因此，大部分规则LDPC码中的和都在满足上述约束的条件下选取3或4。如果码长比较长的时候，随机选取哪些比特是1是很复杂的，而系统码的思想就为了解决这个问题而产生了。

Tanner在[9]中利用二分图将奇偶校验矩阵表示出来，使得LDPC码理论研究得到了极大的发展，因此，LDPC的二分图常常被称为Tanner图。在二分图中，所有的节点被分为两个子集，节点之间的连线只发生在不同的子集内，相同的集合中的节点没有连线。在LDPC码中，两个子集节点分别为变量节点和校验节点。在比特的码字中有个变量节点，其对应的校验矩阵如果有行，就对应着个校验节点。如果，那么在第个变量节点和第个校验节点之间就存在连线。图2.1中的矩阵对应的二分图对应于图2.2。在Tanner图中，一个节点上的边的数目被称为这个节点的度。可以看到，一个规则LDPC码对应的二分图中含有个度为的变量节点以及个度为的校验节点。

图2.2 对应的二分图

很明显，引入二分图之后，LDPC码可以根据它来化简，也可以用Tanner图来定义码字。这样就可以根据一系列的校验节点，变量节点以及边来对LDPC码来进行研究。一组以及码长可以确定“一类”LDPC码，把它表示为。一旦节点的度选定之后，我们在构造二分图的时候仍然有自由的空间，可以确定图中不同的连接方式。

一个“套接边”就是指对于一个节点，可能连接它的边。比如说，一个变量节点有个套接边意味着有条边可能与其相连。对于变量节点，一共有个套接边，对于校验节点，一共有个套接边。很明显，变量节点套接边的数目要与校验节点套接边的数目相同。一个特定的边的连接方案就可以表示为一个从变量节点套接边到校验节点套接边的集合。在Tanner图中一条单独的边可以表示为，说明该边是第个变量节点的套接边与第个校验节点的套接边相连的。

从集合中选取一个随机码也就是在个元素中随机选取了一个排列。很多排列都会导致Tanner图中出现“平行边”，所谓平行边，也就是在同一个校验节点或者变量节点上连接了多个边。规定在奇偶校验矩阵中，出现的偶数个平行边将会被删除。如果他们从Tanner中被删除了，一些节点的度将会被改变，此时码字也将不会再是规则LDPC码，如果他们没有被删除，这些平行边的存在将会导致迭代译码算法的性能降低。因此在构造Tanner图的过程中，我们必须对排列的选取进行限制，规定不能出现平行边。

非规则LDPC码不能从节点的度这个概念去定义，而采用度分布去描述Tanner图中不同节点所具有的不同的度。度分布的多项式可以由式2.1给出：

（2.1）

式中的系数表示Tanner图中与一个度为的节点相连的边的比重系数。用表示平均度分布的逆分布，由式2.2给出：

（2.2）

表示基于度分布的节点的平均的度，为了证明，设所有节点的数目为，表示度为的节点的数目，则Tanner图中所有边的数目为。因为系数表示Tanner图中与一个度为的节点相连的边的比重系数，可以得到。结合式2.2可以得到。

• 1. LDPC码的消息传递译码算法

上文已经提到过，低密度奇偶校验码的优势就是可以在译码过程中利用迭代译码的算法使得译码复杂度与码长成线性关系。现在已经有了LDPC码的图形化表示，就可以根据置信传播的译码算法进行译码。置信传播译码算法是基于图模型的消息传递译码算法的一个具体实现。所有的消息传递译码算法都必须遵循下面的定理。

定理2.1（外信息定理）：通过边传递的来自节点的信息不能根据先前通过边得到的信息来确定。

在介绍译码算法之前，首先要建立起来这个译码问题模型。首先，基于奇偶校验矩阵构造了一个LDPC码，而也将会应用在译码算法中。为了对信息序列进行编码，首先需要得到编码矩阵，可以依据约束。为了找到一个合适的，首先将转变为等价的系统码对应的奇偶校验矩阵的形式：

（2.3）

于是，系统码对应的生成矩阵可以由式2.4给出：

（2.4）

编码之后的消息序列由式2.5给出：

（2.5）

剩余内容已隐藏，请支付后下载全文，论文总字数：22431字