毕业论文题目：LDPC码的编译码算法研究
摘要
低密度奇偶校验码（Low Density Parity Check Codes，简称LDPC 码），本质上是一种线性分组码，更接近香农限。目前的研究均表明LDPC 码是信道编码中纠错能力最强的一种码,其译码器结构简单,在深空探测、卫星通信等领域可得到广泛的应用。文章介绍了LDPC 码,综述了其编码方法和译码方法。在编码方法中分别描述了校验矩阵的构造和基于校验矩阵的编码算法，对LDPC 码的快速编码方法进行分析。在译码方法中主要论述了消息传递译码算法、置信传播译码方法、最小和译码算法、比特翻转译码算法和加权比特翻转译码方法。对部分LDPC码的编译码就行了仿真，同时对LDPC 码的编译码方法的发展及应用前景作了分析。
本文的重点是对LDPC码的编译码算法的论述与研究，介绍LDPC码的基本原理和分类，分别从基于生成矩阵和基于校验矩阵详细讨论了LDPC码编码算法，简单介绍了线性分组码编码，LU分解法，RU分解法。并用简明例子对RU算法做了清晰的解释。对译码大致做了解释：分为软判决译码（MP算法）和硬判决译码（比特翻转算法和加权比特翻转算法）。在本文的最后用AWGN信道下LDPC码的性能仿真，主要是针对比特翻转算法进行仿真。做出理论比较。
关键词：LDPC码编译码MATLAB
Title：Encoding and Decoding Algorithms of LDPC Codes
Abstract：LDPC code, namely Low Density Parity Check Code, is a kind of linear block codes in nature, and the decoding performance of LDPC is more nearer to the Shannon limit. With it s best performance and simple decoder structure, LDPC codes will be widely used in deep space exploration, salite communications and other fields. While briefly introducing LDPC codes are introduced briefly, this paper summarizes the encoding and decoding algorithms. The encoding algorithm is described in two steps: the const ruction of parity-check matrix and the encoding method based on parity-check matrix. Analyze the rapidly coding method for LDPC code. As to decoding algorithm, MP decoding method, BP decoding method, Min-Sum decoding method, Bit-Flipping method and Weighted Bit-Flipping method are discussed. Emulate for the LDPC codes .The development and application of encoding and decoding methods is analyzed as well.
This article focuses on encoding and decoding algorithms of LDPC codes，According to the different methods of decoding algorithm, and makes the theoretical MATLAB simulation.
Key words：LDPC codes encoding and decoding MATLAB
目录
1引言 (1)
2 LDPC码概述 (3)
2.1线性分组码 (3)
2.2低密度奇偶校验码(LDPC码) (4)
2.2.1LDPC码定义 (4)
3 LDPC码的编码算法 (7)
3.1基于生成矩阵的编码算法(线性分组码编码) (7)
3.2基于校验矩阵的编码算法(LU分解法) (7)
3.3基于校验矩阵的编码算法(RU算法) (8)
4 LDPC码的译码概述 (13)
4.1MP算法集 (13)
4.2硬判决译码算法 (15)
4.2.1比特翻转算法 (15)
4.2.2加权比特翻转译码算法 (16)
5AWGN信道下LDPC码的性能仿真 (17)
5.1仿真软件简介（MATLAB&SIMULINK） (17)
5.2仿真与结果分析 (18)
5.3译码仿真系统框图及系统总流程图 (19)
5.4BF算法及其改进算法仿真 (20)
结论 (22)
致谢 (23)
参考文献 (23)
代码 (24)
1引言
通信系统的基本目的在于将信息由信源高效、可靠、有时还需安全地传送到信宿。有扰通信信道中的噪声会不可避免地对传输信息产生不同程度的干扰，从而可能降低通信可靠性。所以通信系统设计的核心问题就是在存在随机噪声的信道中如何克服干扰，减小信息传输的差错，同时又不降低信息传输的效率，即如何解决系统的有效性与可靠性之间的矛盾。一般地，通信系统的可靠性用误比特率(BER)来衡量，其有效性则用信息传输速率R比特信道符号来衡量。早期的人们普遍认为：通信系统的可靠性与有效性之间是一对不可调和的矛盾，一方的改善总是以牺牲另一方为代价，并指出当功率受限时，在有扰通信信道上实现任意小错误概率的信息传输的唯一途径就是把信息传输速率降低至零。Shannon信息和编码理论的奠基性论文“通信的数学理论”发表之后，改变了这一观点。他首次阐明了在有扰信道上实现可靠通信的方法，指出实现有效而可靠地传输信息的途径就是通过编码。根据Shannon的信息理论，数字通信系统的基本组成如图。
图1.1 数字通信系统基本模型
Shannon的信息理论从通信系统的整体最佳化来研究信息的传输和处理。比特是一种通用的信息表示形式，它本身并不依赖于信源或信道特征。
这就允许我们分别设计图1．1所示的两个阶段的信息处理，即信源编码和信道编码。Shannon不失最佳性地证明了这种分离性。图1．1中的信道部分只是信息传输所通过媒介的一种抽象，实际的信道是多种多样的，如电缆、光缆、存储设备、甚至我们所处的实际空间及外太空等等。对于通信系统设计者来讲，了解系统中信道的特性是必需的。根据信道的输入输出的取值连续与否可以将其分为离散信道、连续信道和离散输入连续输出信道；根据信道统计特性是否随时间改变可以将其分为平稳信道和非平稳信道：根据信道的输出之间是否具有相关性可将其分为记忆信道和无记忆信道；根据信道的特性对输入端是否具有对称性可以将其分为对称信道和非对称信道。实际应用中所涉及到的信道大多都是离散输入的平稳无记忆对称信道，下面给出几种常用的编码信道模型。
二进制对称信道(BSC)：输入为二值变量0、1，输出也为二值变量0、l，且传输过程中发生错误(输入为0输出为1或输入为1输出为0)的概率与输入无关：
二进制删除信道(BEC)：输入为二值变量0、1，输出或为输入的二值变量0、1，或为删除E，且通常传输过程中不同输入被删除的概率相同；
二进制输入高斯信道(BIAWGN)：输入为二值变量，输出为连续变量，且信道中的加性噪声为服从N(O，万2)的高斯随机变量。
在过去的几十年里，移动通信技术得到了迅猛的发展和广泛的应用，至今已发展了三代。第一代移动通信（1G）是以模拟传输的方式进行语音通话，主要是采用以蜂窝结构网为核心的模拟技术和频分多址（FDMA）动态寻址技术。第二代移动通信（2G）以数字传输的方式进行语音通话和数据业务，2G系统采用的是数字的时分多址（TDMA）或码分多址（CDMA）实现动态寻址功能，以GSM、CDMA系统为代表，实现了从模拟到数字系统的跨越。第三代移动通信（3G）是着重实现传统的移动通
信与开放式的因特网融合，各个国家的网络将融合为一个整体。而在移动通信更新换代中，信道编码技术是其中非常重要的一项。本文所论述的LDPC码即是信道编码的其中之一。
MATLAB将高性能的数值计算和可视化集成在一起，并提供了大量的内置函数，从而被广泛地应用于科学计算、控制系统、信息处理等领域的分析、仿真和设计工作，而且利用MATLAB产品的开放式结构，可以非常容易地对MATLAB的功能进行扩充。MATLAB的数据分析和处理功能十分强大，运用它对所涉及到的LDPC编译码进行仿真。
2 LDPC码概述
2.1 线性分组码
因为低密度奇偶校验码是一种特殊的线性分组码，所以本章将首先对线性分组码做一个概述，为讨论LDPC码作铺垫。
定义l：整数0，l，2，?，q．1，q是自然数，在模P加和乘运算下构成
一个伽逻华域GF(q)。
定义2：如果一个分组码C，包含N个由GF(q)中的元素构成的码字(，，?，)，则当且仅当C构成一个GF(q)上的矢量子空间时，称C为q进制线性码。在本篇论文里，只考虑二进制码，所以q=2。
定义3：线性码的维数等于对应的矢量空间的维数，一个长度为N，维数为K的线性码总共包括个长度为N的码字。
线性码还有如下一些有用的性质：
性质1：任意码字的线性组合仍然是一个码字。此性质的一个结论是
线性码必然包含一个全零码字。
性质2：线性码的最小距离等于其中一个最轻非零码字的汉明重量。这一性质表明确定线性码的最小距离(决定检错和纠错能力)要比一般的分组码要容易的多。
性质3：线性码中不可检测的错误图案与传输的码字无关，且由所有的非零码字组成。
假设(，，，是组成(N，K)--进制码空闭的一组基底，对任意一个码字c ∈C，存在唯一的表达形式
C=+++（2-1）
因为所有基元的线性组合仍然是一个码字，所以存在长度为K的码组和C中码字之间的一一映射。以下矩阵G就是由基矢按行排列而成。
2.2 低密度奇偶校验码(LDPC码)
2.2.1 LDPC码定义
LDPC码是线性分组码中较为特殊的一种，但是目前LDPC码并没有严格的数学定义。考虑到其结构上的特点和叙述上的方便，本文对LDPC码做如下的定义。LDPC码是一个m行n列的稀疏矩阵H的零空间，H称为LDPC码的校验矩阵，并且满足：
l、矩阵的行重、列重与码长的比值远小于1；
2、任意两行(列)最多只有1个相同位置上的1；
3、任意线性无关的列数尽量的大。
这样的LDPC码码长为n，校验位长度大约为m，信息位长度为k n-m。
一个规则LDPC码是指校验矩阵H满足列重和行重分别等于常数，和，因为我们并没有要求校验H是满秩矩阵，所以其码率为：
r1-=1- (2-2)
(2.3)式是一个n=10，=2，=4 ，r=0.5规则LDPC码的校验矩阵。
11110000001000111000H 010********
0100101010001001011
?????
???=???????? (2-3) 如果校验矩阵H 的列重和行重并不是常数，我们就称其为不规则LDPC 码，我们可以认为规则LDPC 码是不规则LDPC 码中的一个特例。不规则LDPC 码可以用重量分布多项式来方便的描述。假设最大列重和最大行重分别是和，则H 的列重分布多项式
(x)可以表示为：
(x)= （2-4） 其中，是重量为i 的列所占的比例，同时 (x) (1)=1。类似的，H 的行重分布多项式 (x)可以表示为：
(x)= （2-5） 是重量为i 的行所占的比例， (x)也满足 (1)=1。此时，码率r 满足： r1- （2-6）
值得注意的是，对于一个给定的码长n 和行、列重量分布多项式，我们得到的是一类LDPC 码而不是一个特定的LDPC 码。
我们得由上面的叙述我们知道，LDPC 码是由其校验矩阵H 定义的。对于一个线性分组码，其校验矩阵并不是唯一的。也就是说如果对于线性分组码的校验矩阵做行变换，得到的矩阵也是这个码的校验矩阵。但是，对于LDPC 码这种特殊的线性分组码而言，由于译码算法的设计和性能分析的需要，我们仅仅关心其属于稀疏矩阵的这个校验矩阵，因此，定义一个LDPC 码必须给出这个稀疏的校验矩阵才有意义。对于LDPC 码的生成矩阵，并没有其他特殊的限制。
为了分析的方便，我们可以用因子图来表示一个LDPC 码。图中的变量节点(i=0，l ，．．．，n-1)与校验矩阵的列(也即码字中的每一位)一一对应，
校验节点j(j=0，1，．．．，m-1)与校验矩阵的行(也即各个校验方程)一一对应。和；相连接，当且仅当校验矩阵中对应位置的元素是1。这样，该因子图是一个偶图，其邻接矩阵就是该校验矩阵。图2．1是(2．7)式中校验矩阵的因子图。由于LDPC码定义中的第2条的限制，因子图中不会存在长度等于4的圈(对任意一个偶图，圈的最小长度为4)。
图2.1 LDPC码的因子图表示
一般而言，不规则码的性能要优于规则码，但是实现的复杂度和分析的复杂度都要大得多。非规则码的编译码方法与规则码相似，而其性能却优于规则码，这是因为非规则码的“波浪效应”，在LDPC码的随机双向图中，对信息节点来说，其度数越高，它从校验节点所获得的信息也就越多，也就能更准确的判断其校验值；反之，从校验节点的角度来看，希望度数低，其度数越低，那么传播到相邻节点的有用信息也就越多。而非规则码的随机双向图就很好的平衡了信息节点与校验节点二者对度数的要求。而所谓的“波浪效应”也就是度数大的信息节点首先获得正确值，然后度数小的信息节点也可以获得正确值。非规则码的产生，使规则LDPC 码的定义产生了变化。在非规则码中，度的变化范围很大，往往最大度可达几十或上百，因此，我们更广泛地把度的变化很微小的LDPC码都称之为规则的。
非规则码的产生，使规则LDPC码的定义产生了变化。在非规则码中，度的变化范围很大，往往最大度可达几十或上百，因此，我们更广泛地把度的变化很微小的LDPC码都称之为规则的。
3 LDPC码的编码算法
3.1 基于生成矩阵的编码算法(线性分组码编码)
设m×n 的较验矩阵H 的所有行都是线性无关的。根据分组码定义，对于
输入信源u，u，编码后得到的码字c，c，满足方程：
H= 0
为了在接受端易于区分信息位和校验位，通常采用系统码。但是，对于任意一个随机构造的校验矩阵H,它具有非系统码的形式，因此首先需要对给定的校验矩阵H进行行列变换，分解成的形式，其中A为m(n - m)维的矩阵，
B为mm的满秩矩阵，则码字c=满足
即Au + Bp = 0
因此，得到校验位p = -Au
其中“-”表示向量- Au的逆元，在二进制编码中逆元是其本身。3. 2基于校验矩阵的编码算法(LU 分解法)
利用矩阵 B 的系数特性，对校验位p = -B-1Au的求解采用以下方法：首先对 B 矩阵进行LU 分解，即 B = LU，其中L 为下三角矩阵，U 为上三角矩阵，则校验位满足LUp = -Au，然后通过以下步骤计算校验位：1．z = Au，由于A是稀疏矩阵，所以计算复杂度正比于m。
2．令Up = y，则Ly = -z，通过前向递归运算得到y 的值。
3．通过后向递归运算，解方程Up = y 得到校验位p。
3.3基于校验矩阵的编码算法(RU算法)
在对LDPC码进行编码的时候，人们希望校验矩阵是下三角矩阵，如图3．1所表示。但在实际情况中，校验矩阵往往不能化为下三角矩阵。Richardson和Urbankc在提出了一种很好的编码算法，即RU算法。
RU算法仅仅通过行列置换将一般的低密度奇偶校验矩阵化为一个近似下三角矩阵，可以使编码复杂度从高斯消元法的o(m2)降为o(n+92)，其中g为近似下三角矩阵与下三角矩阵的差距，并且在最恶劣的情况下，它也只是与码长行的一小部分成比例。
首先，通过行变换与列变换的方法将奇偶检验矩阵重新排列为近似下三角形式，如图3.2所示。由于原矩阵J5r非常稀疏，而且在矩阵变换中只有行列交换，因此变换后的校验矩阵仍是稀疏矩阵，A、B、C、D、E、T分别是（m-g）（n-m）、（m-g）g、g（n-m）、g g、g（m-g）、（m-g）（m-g）维稀疏矩阵。并且T是下三角矩阵矩阵且对角线上的元素全部为l。
H= (3-2) 长度为k=n-m的信源向量s被编码成一个码字向量x=（s，，），、分别定义一个校验向量，长为g，长为m-g。编码步骤如下：
1、计算信源向量的上校正子
=A （3-3）
2、找出第二个校验向量的临时值，使得上校正子为零
= (3-4)通过回代算法可以在线性时间内得出这个向量，即计算的第一个比特，然后是第二个比特，然后是第三个，如此等等。
3、计算向量的下校正子
（3-5）
4、现在准备求第一个检验向量。
定义矩阵F=-EB+D并求出它的逆矩阵，这个计算只需要完成一次
而它的复杂度O()，这个逆矩阵是一个gxg维高密度矩阵。
设第一个校验向量为
(3-6) 这个操作的复杂度为o()。注意这时找第一个校验向量的正确值。
5、抛弃临时检验向量西并找出新的上校正子
(3-7) 这也可以在线性时间内完成。
6、求出第二个检验向量的值，使得上校正子为零
(3-8) 这个向量可以用回代算法在线性时间内求出。
计算,的复杂度如表3,1和表3.2所示。
表3．1计算的复杂度
操作复杂度备注
A O（n）稀疏矩阵和向量相乘
O（n）稀疏矩阵和向量相乘
O（n）稀疏矩阵和向量相乘
向量的减法运算
O（n）矩阵的求逆运算
高密度矩阵和向量相
乘
表3．2计算的复杂度
操作复杂度备注
A O（n）稀疏矩阵和向量相乘
O（n）稀疏矩阵和向量相乘A+ O（n）稀疏矩阵和向量相乘
向量的加法运算
O（n）稀疏矩阵和向量相乘- (A+)
例 2.4 一个(12,3,6)LDPC 码的校验矩阵如下：
将列重新按下序排列：1，2，3，4，5，6，7，10，11，12，8，9 得到一个g =2的近似下三角矩阵为
用高斯消元法消去矩阵 E ，得到
可以看到
矩阵U 是奇异矩阵，这种奇异性可以通过交换列5，8 来消除。于是最终列的排序为：1，2，3，4，10，6，7，5，11，12，8，9。对应的等价矩阵为
假设待编码的信息比特为s = (1 0 0 0 0 0)，按照上述步骤
计算：
()T
-1T T -ET As Cs 01????+=????
()T -1-1T T T 1U -ET As +Cs 01=P ??=?? 根据得到的计算
[]T
T T 1As Bp 1001????+=????
()T 1T T T 12T As Bp 1010=p -??+=?? 因此编码得到的码字为
()[]12s p p 100000011010=
将上述码字代入式（2.4）进行检验，得到HcT = 0，因此满足校验方程。上述有效编码方法，利用了校验矩阵的稀疏性，适用于任何基于稀疏校验矩阵的编码。
4 LDPC码的译码概述
LDPC码具有良好性能的重要原因之一是LDPC码采用了基于置信传播的迭
代译码算法，这是一种迭代概率译码算法，是LDPC码与传统纠错码的重要区别。
4.1 MP算法集
信息传递(Message Propagation，MP)算法是最主要的一类LDPC码译码算法，它具有严格的数学结构和良好的性能，使用它能对译码性能做定量分析。LDPC码译码算法中很多种都可以被归结到信息传递算法集中。
信息传递算法的主要思想就是通过在变量节点和校验节点之间来回传递概率似然值，最终找到正确的码字。这一过程在Tanner图上可以直观的表示出来，信息在Tanner图中沿着连接变量节点和校验节点的边双向传递。变量节点接收与它相连接的校验节点送来的节点信息，然后根据这些信息计算出反馈给各校验节点的信息。校验节点开始接收与它相连接的变量节点送来的节点信息，然后根据这些信息计算出反馈给各变量节点的信息，如此往复形成迭代。每次迭代结束后，对每个变量节点做判决，得出一个码字，再通过校验矩阵验证码字正确性。如果译码成功，则译码结束；否则继续迭代，直到达到预先设定的最大迭代次数。
信息传递算法为了保证传递信息的独立性，每个节点接收的信息都是从除自身之外的其他节点而来。但是由于现实中所使用的码长都是有限的，使得节点不可能永远收到与自身无关的信息，即存在环的影响。以一个行
重为，列重为的正则LDPC码为例，当前迭代周期中某一变量节点送来的信息直接来自。个校验节点，而这些校验节点所送来的信息又来自与各自相连的以一1个变量节点在上一迭代周期中送出的值，如下图所示的树状图表示它们之间的关系。因此，在LDPC码译码过程中环对译码的影响是不容忽视的。
图3.3 节点树
LDPC码有很多种译码方法，本质上大都是基于Tanner图的信息传递译码算
法。根据信息迭代过程中传送消息的不同形式，可以将LDPC的译码方法分为硬
判决译码和软判决译码。如果在译码过程中传送的信息是比特值，称之为硬判决
译码，如BF算法，它具有较低的译码复杂度，易于工程实现。但是与软判决译码相比，硬判决译码在性能上要损失约2-3dB；如果在译码过程中传送的信息是与后验概率相关的信息，称之为软判决译码，如置信传播译码算法。虽然软判决算法译码复杂度较高，但可以获得更好的译码准确性，比硬判决译码具有更大的编码增益。在AWGN信道中，它比硬判决译码要多2dB左右的软判决增益，而在衰落信道中，软判决增益超过5dB。硬
判决译码可以看成是l比特量化译码，而软判决译码可以看成无穷多比特量化译码。主要的硬判决译码算法有比特翻转算法(BF)、加权的比特翻转算法(WBF)等；软译码算法主要有置信传播算法(BeliefPropagation)、简化的最小和算法(Min-sum)、归一化最小和算法(Normalized Min．Sum)、偏移量最小和算法(OffsetMin．sum)等。
4.2 硬判决译码算法
4.2.1 比特翻转算法
Gallager在其论文中提出了硬判决译码算法，该算法是一种比较简单而且容易理解的译码算法，它对运算量和存储量的要求都很低，但是其性能相对比较差。
比特翻转算法(Bit Flipping Algorithm)可看成是置信传播算法的简化形式，而加权位翻转译码算法是在BF算法的基础上加上硬判决译码系数，其性能较比特翻转译码算法有一定程度的提高
比特翻转算法(Bit Flipping Algorithm)是Gallager在其论文中提出的被命名为
Gallager硬判决的译码算法。设码字c=为发送序列，经BPSK调制为序列x=，，，为接收的实数向量序列，由实数序列可以得到硬判决二元向量序列z=()：
（4-1）由此得到码字伴随式s=（）=，若，则说明接收向量
满足第j个校验方程；若s=0，则表示接收向量满足所有校验方程，接收码字z正确，译码成功；若伴随式为非全“0”向量时，接收序列z 有错误，此时则需计算出每个码元不满足校验方程的个数f==，搜索f中的最大值，翻转对应位置的码元。再重复上述的过程，直到译码成功后达到最大迭代次数。BF译码算法步骤如下：