资源描述
厦门大学不同仿真平台下LDPC编译码效率对比课程名称： 现代编码理论 任课教师： 洪少华 王琳 院 系： 通信工程系 姓 名： 张琳 林治 学 号： 23320131153234 23320131153224 摘要现代编码理论通过软判决译码、和积算法、因子图这三个核心概念在指导着众多“好码”的仿真和实现。本文分别在C语言环境和MATLAB环境下对比低密度奇偶校验码的编译码效率，并分析对比了两种仿真平台的优缺点。关键词： 现代编码理论 软判决译码 低密度奇偶校验码AbstractModern encoding theories through the soft decoding and encoding ,product algorithm and factor diagram three core concepts in guiding many simulation and implementation of the good code. This paper respectively contrast of low density parity check code decoding efficiency in C language environment and MATLAB environment, and then analyze the advantages and disadvantages of the two kinds of simulation platform.Key Words: Modern encoding theories the soft decoding and encoding LDPC(low-density parity-check) codes目录摘要1Abstract2绪 论41.1研究背景41.2通信系统模型41.3 因子图51.4 软判决译码51.4.1逐位软判决译码51.4.2.逐组软判决译码61.5 基于网格图上分组码的Viterbi译码71.5.1、分组码与网格图的关系71.5.2基于Shannon乘积的最小网格图设计81.5.3.软输入/软输出的译码算法8第二章 LDPC原理与BP译码原理102.1LDPC原理102.2和积算法原理13第三章 仿真分析183.1仿真结果分析：183.2 C语言和MATLAB语言的仿真对比：19第四章 总结与展望20参考文献21绪 论1.1研究背景 编码是信息从一种形式或格式转换为另一种形式的过程。用预先规定的方法将文字、数字或其他对象编成数码，或将信息、数据转换成规定的电脉冲信号。现代编码，是编码的一个新分支，基于一些理论基础来指导较好的编码方向。现代编码中常用的经典理论，如因子图，和积算法等，已经得到广泛应用，并指导编码出很好的编译码方法，如ldpc码，原木图ldpc码等，用不同的方法在各种信道下会得到不同的结果，基于它们的性能比较也必然成为一个很重要的因素。1.2通信系统模型主要包括：信源，编码器，信道，译码器，信宿这五部分，如如1.1所示： 图1.1 数字通信模型信源：产生消息和消息序列的源编码器信源编码器，信道编码起，保密编码器信道信号的传输通道译码器信源译码器，信道译码起，保密译码器，和编码器的功能相反信宿消息传送的归宿 实际的通信还需要，同步，调制，解调等多个步骤，才能保障通信的准确到达，根据实际的要求和需要，可适当地增加一些均衡等技术。1.3 因子图将一个具有多个变量的全局函数因子分解成几个局部函数的积而形成的一个双向图叫因子图。如g（x1,x2,x3,x4,x5）是具有5个变量的实质函数，将其分解成5个局部函数之积，即： 则对应的因子图如图 所示。在该图中，每个变量对应于一个变量节点，每个局部因子对应于一个函数节点，这两类节点构成因子图的顶点集。图1.2 因子图因子图的定义与联合概率密度函数之间，提取-乘积算法与边缘密度求取之间有极大的相似性，因此，可在概率个随机过程领域，因子图分析法有极大的应用。1.4 软判决译码在寻找较为实用的次最佳软判决译码方法或准最佳软判决MLD算法中，一般可分为使码字的每个码元译码错误概率最小的逐位软判决译码方法，和使码字错误概率最小的逐组软判决译码方法.虽然这二类软判决译码方法都是准最佳或最佳的，但其译码的基本思想并不完全相同.1.4.1逐位软判决译码Massey提出了适用于大数逻辑可译码的APP译码算法12，这是一种门限译码，用于硬判决时就是大数逻辑译码.而后，Forney等人提出了渐近APP算法13，但仅适用于正交码.1976年Hartman和Rudolph对这种算法进行了推广，提出了HR算法14.这种算法利用有限域上的FFT变换，能适用于任何线性分组码，而Massey的算法，仅仅是HR算法的一种特例.HR算法对每位码元的判决，是基于计算它的对偶码的码字的后验概率基础上，因此它的译码复杂性是O(2n(1-R).Weldon提出的重量删除译码(WED)算法，使逐位软判决译码开始走向实用，因为它的计算复杂性并不是n的指数函数而是多项式函数，当然性能比APP差.如何减少译码复杂性而性能又接近APP，是这类算法的研究方向.有关这类算法的发展过程，请参考文献16.在逐位软判决译码算法中，特别值得提出的是由Bahl等人提出的，用迭代方法计算每位码元最大后验概率的BCJR算法，这种算法适用于任何线性分组码和卷积码.由于在计算每个码元的最大后验概率时采用迭代方法，因此计算速度很快.这种算法刚刚提出时，并没有引起有关理论和工程界的多大注意.直到1993年Berrou等人提出Turbo码后，这种算法才引起了人们的广泛注意，并且对它作了各种改进.有关这种算法的最近进展情况，将在后面的Turbo码一节中作进一步介绍.以码字为单位的最大似然译码，一直是理论上讨论得最多，实际中也用得最为广泛的一类译码方法.1.4.2.逐组软判决译码最早的逐字软判决译码是1954年Wagner提出的仅适用于n,n-1,2码的译码算法，这也可以说是软判决译码思想的萌芽.系统开始研究逐字软判决译码始于Forney的工作，Forney在他的博士论文中首次提出了广义最小距离译码(GMD)3，19.GMD译码是一种迭代纠错译码.算法需要d/2次硬译码，得到d/2个候选码字，然后挑出一个最好的作为译码器输出.在1993年的国际信息论会议上，有四位学者分别提出用Berlekamp-Massey算法，能够一次得到所有GMD的候选码字20.GMD译码的基本思想可以说是以后几乎所有各种逐字软判决译码的基础，Chase21在GMD译码思想基础上提出了Chase算法.Chase算法是一种伴随式译码，利用可信信息寻找最可能的错误图样，根据试探错误图样数目的不同，分为三种算法：Chase1,2和3.其译码复杂性能以Chase1最高，Chase3最低；当然译码性能以Chase1最好，Chase3最差.在中等码长和中等纠错能力情况下，Chase2算法的复杂性可以为人们所接受且译码性能很接近MLD，因此在实际中用得最多.正因如此，自八十年代至今各国有关学者，在改进Chase2算法方面做了大量工作.其中心思想是加快它的译码速度并改善译码性能.因此主要围绕以下二个问题研究：(1)引入结束试探的门限标准，以减低译码的平均时间提高译码速度，其关键是尽早找到重量最轻的错误图样，或最似然的码字.(2)在(1)的基础上，扩大Chase2的试探集合，使尽量包含最似然信的码字，以提高译码性能.我们在1986年首先引入了结束译码的门限标准，从而使译码的平均时间得到大幅度减少，以后范平志等作了进一步改进23，最近我们又提出了根据信噪比变化，从固定门限变为可变门限的思想，使译码时间得到进一步缩短.国外学者如Forney、Lous、Fossorier、Snyder、Beery、Vardy、Kaneko、Lin、Taipale等，在此方向上也提出了许多性能达到或接近MLD、译码平均时间比Chase2更少的改进算法.如1994年和1997年Kaneko、Nishijima等提出的KN算法，为了使试探图样中能包含最似然的码组，其试探图样的数目和结束试探的标准也随信噪比变化25.又如Fossorier和Lin提出的FL算法，也是一种性能能达到预先指定要求或接近MLD的改进Chase算法26，27.它的基本思想也是根据每个码元可信度的大小，对其重新排序，根据对译码性能要求，计算为了达到该性能所需的试探次数，然后再进行多次信息集译码.所有这些算法，都是Chase2算法的改进，其中心思想都是利用接收码元的可信信息的硬判决译码器进行多次译码，以找到与发送码字最似然的码字，并在给定的判决门限或标准下结束译码.1.5 基于网格图上分组码的Viterbi译码1.5.1、分组码与网格图的关系1974年，Bahl等首次将分组码用网格图表示,从而揭示了分组码与卷积码之间的联系,1978年Wolf又系统地提出了分组码的网格图表示,并将卷积码的Viterbi译码算法用于分组码的译码,Forney进一步分析了分组码的网格图结构,并为一些分组码设计了有效的软判决译码算法，而Muder基于图论的方法将分组码的网格图的设计形式化，为分组码网格图结构的研究奠定了基础.一个分组码的网格图可按段表示和构造.设C是GF(q)上的一个(n,k)线性码，则C的网格图有n+1层，每一层的状态集为Vi,i=0,1，n，网格图的分支由0，1，q-1标识，每条路径对应一个码字.如果V0只有一个状态S0，每个状态都出现在某条长为n的路径上，并且从S0出发的任意两条长为i的路径表示不同的i元组(或i维矢量)，则将这样的网格称为真正的网格图.线性码与真正网格图之间存在一一对应关系，但非线性码不一定存在真正的网格图表示.对于给定时间轴，Wolf、Forney和Muder构造的网格图是唯一真正的最小网格图，即|Vi|是最小的,i=0,1,，n.定义网格图指标为，则min(k,n-k-2)smin(n,n-k)其中=n-k-d+1，d为码C的最小距离如果C为完备码，则smin(n,n-k-3)30,31显然，最小网格图指标s与码的坐标次序有关11,31，即与生成(校验)矩阵中列的百列方式有关，对生成(校验)矩阵列的重排运算称为置换将码C在置换意义下能够达到的最小指标s称为绝对最小网络图尺寸s(C),s=s(C)的网格图称为绝对最小网格图，s(C)可以刻划码的Viterbi译码算法的时间复杂性.由于一般分组码的网格图比较复杂，不便于译码实现，所以，Forney提出了结构化的网格图构造方法.利用Forney的方法，一个网格图可由许多结构相同的子网格图组成，从而便于译码的并行处理，但这样的网格图与码的结构有关，目前只知道RM码和Golay码等几种码存在这种规则网格图.Forney最小规则网格图的构造方法的关键也在于码元坐标的次序，由于译码问题的难处理性，可以设想，对于一般分组码很难找到一个有效的方法求具有最小网格图的最佳置换.实际上，最近已经证明了某种求置换问题是NPC问题，正因为这样，对于给定码利用其组合(或代数)特性求其网格图结构就具有重要的理论和应用价值.但是，对于即使是很特殊的码要求其最小网格图也是很困难的.因此，对于实际应用，我们可基于近似最小网格图设计有效的译码算法，实际上，许多译码思想都是这样的。1.5.2基于Shannon乘积的最小网格图设计Forney等人提出的网格图构造方法只对某些特殊的码找到了对应的最小网格图，而对于绝大多数码尚不清楚其最小网格图指标s(C)和最小网格图的结构.但是，由一些码的代数结构可知，这些码可由一些“小”的线性码构成，如果已知这些小线性码的网格图结构，则有可能由这些网格图构造给定码的最小网格图35,36.设T，是两个n+1层网格图，第t层的状态分别为,i=1,，Nt,，网格图的每条分支代表h个字符，则T与的Shannon乘积T也具有n+1层，第t层的状态由表示，i=1,，Ni,.当且仅当T中有一条连接状态的分支,中有一条连接状态的分支时，T中有一条连接状态和状态的分支，该分支的标号为,其中的加法为GF(q)中的矢量加法，分别为分支的标号，例如，由四个子码的最小网格图可构造出(8，4，4)RM码的最小网格图.这里给出的网格构造方法对于比较小的线性码是非常有效的，但是，如果线性码空间比较大，则这种构造方法也是比较复杂的.1.5.3.软输入/软输出的译码算法软输入/软输出的译码算法是Turbo码译码必需的算法.自Turbo码出现以来，这方面的研究也引起了关注.最优的算法是BCJR算法17及软输入/软输出Viterbi算法46.人们在此基础上，提出一些次优的译码算法，以降低复杂度，提高译码速度.S.S.Pietrobon68注意到函数f(z)=ln(1+ez)(z0)的如下性质：z=0时，f(z)取最大值f(0)=ln2=0.693，随着z的增大，f(z)迅速下降，当z7时，f(z)接近0.利用这一性质，可以由MAP算法得到次优的logMAP算法.V.Franz59提出了M-BCJR算法和T-BCJR算法.BCJR算法有两个递推公式.考虑一个网格图，设其有L级，则前向递推公式(t是行向量)t=t-1.t,t=1,，L后身递推公式(t是列向量)t=t+1.t+1,t=L-1,，1转换矩阵t(i,j)=PrSt=j,Yt|St-1=i,t=1,，LM-BCJR算法与T-BCJR算法基于这样一个事实，在与中，有些分量接近于0，可以忽略M-BCJR算法：每次递推时，只保留t与t中M个量大的分量T-BCJR算法：每次递增推时，忽略t与t中小于某门限T的分量模拟结果表明，T-BCJR算法优于M-BCJR算法，与BCJR算法性能接近，但计算量减少50%90%第二章 LDPC原理与BP译码原理2.1LDPC原理LDPC 码可以由它的校验矩阵 H 来定义， H 是一稀疏矩阵，矩阵中除很少一部分元素为非零元素外，其它大部分的元素都是零即所谓的“低密度”。LDPC 码也可以用二分图(也称 Tanner 图)来表示。二分图和校验矩阵 H 是直接对应的，由比特节点(也可称为变量节点)、校验节点和连接它们的边组成。每个校验节点对应于 H 的一行，每个比特节点对应于 H 的一列。当码字中某一比特包含在某一校验方程中，即校验矩阵中相应位为 1 时，校验节点和比特节点间存在连线，我们将这条边称为相邻边，相邻边两端的节点称为相邻点。每个节点的相邻边条数称为该节点的度数(degree)。LDPC码的校验矩阵的构造方法是一个值得注意的问题。对于信道编码，影响编码性能的一个重要因素是最小码距。对于LDPC码，由于译码算法的限制，Tanner图中度的分布、圈的分布以及girth的大小也会影响译码性能。通常我们希望LDPC 码具有最小码重即最小码距，又希望避免Tanner图中短圈的出现。但这些因素之间是相互矛盾的。增加LDPC 码的最小码重，必然要增加校验矩阵H的行重和列重，随之而来的就是Tanner图中短圈出现的可能性有所增加。因此对于已经确定了度分布多项式的LDPC码，如何构造校验矩阵H，既然增加最小码重同时又能避免短圈的存在，并且要具有较低的硬件实现复杂度，一只是LDPC 码研究领域中的一个焦点。一般说来，构造LDPC码的奇偶校验矩阵有两种方法：一种是随机或伪随机结构的，即在对度分布和最小全场等因素做一定限制的条件下，利用计算机搜索方法进行随机货这类随机生成奇偶校验矩阵；另一种是利用代数学或者组合理论构造LDPC码的奇偶校验矩阵，使之具有规律的结构，易于理论分析。下面我们分别介绍一下。Gallager随机构造法。Gallager的做法是用稀疏校验矩阵的随机置换和级联来模拟随机码。具体矩阵如下：其他方法如MacKay的随机构造法。还有高斯消去法、类上三角矩阵的编码等等。4MacKay的方法为：保证列重固定，而行进行均匀化的处理，并且要求交叠不超过1。高斯消元法是利用代数的方法。校验矩阵H给定后，H为MxN的矩阵，然后假设其满秩。编码后的码字x需要满足。根据这个属性，一种常用的LDPC码的直接编码方法就是高斯消元法。利用高斯消元法将校验矩阵化为下图的形式。x可以分为两部分，s和p，分别表示系统位和信息位。编码步骤如下：系统位s为要发送的N-M个信息比特；由于变换后的矩阵具有上三角矩阵的形式，所以校验比特p通过向后递推的公式如下类上三角矩阵的编码是为了降低复杂度的。高斯消元法编码复杂度很高，考虑利用校验矩阵的稀疏性来降低复杂度。为了保持校验矩阵的稀疏特性，只对校验矩阵进行行列变换，得到图2.4形式的类上三角矩阵。设变换后的校验矩阵为：所有的子矩阵均可看做系数矩阵。为了得到递推的公式，将校验矩阵做线性变换，左乘一个矩阵，变换后的矩阵为利用变换后的矩阵可以进行校验位的递推。将x分为三部分，s表示系统比特，表示校验比特。两部分校验比特的递推公式如下：上式中所有的矩阵仍为稀疏矩阵，进一步分析可以得出的计算复杂度分别为.在g很小的时候，运算复杂度和码长成线性关系。2.2和积算法原理LDPC码的译码方法有硬判决译码和软判决译码方法。对于LDPC码来说，主要的硬判决译码算法有比特翻转（Bit-Flipping,BF）算法以及在此基础上进行改进的算法。比特翻转算法属于硬判决译码，是通过基于Tanner图的信息传递来进行译码，最先有Gallager提出。基于Tanner图的信息传递的比特翻转算法的基本过程是：在每一次迭代过程中根据某一种准则决定将其中的某一个比特进行翻转，直至迭代过程结束或者校验方程全部满足。这种译码算法的核心在于确定比特翻转的准则，如Gallager最初提出的BF算法，准则是不满足校验方程个数最多的比特进行翻转，后来提出的加权算法主要是在翻转准则加入变量节点可靠性度量，改进算法主要是在检测翻转过程中防止出现翻转成环的现象，这些改进都进一步提高了性能，而没有增加复杂度。下面具体介绍比特翻转算法。本文采用的是和积算法3。原理如下：首先介绍因子图。因子图是一种用于描述多变量函数的方法。一般来说，在因子图中存在两种节点，一种是变量节点，一种是函数节点。如下所示：一个函数g（x），通常可以写为如下形式：写成和积算法的形式就是：下面介绍具体算法步骤：这是一种迭代算法，所以通常需要好几轮迭代才能完成。调制后每一个码字c=（c1，c2，.）映射为传输序列s，然后s通过信道，接收到的序列为y，根据y， 首先介绍所用到的有关符号的含义：1、 初始化计算信道传递给比特借点的初始概率。然后对每一个比特借点i和与其相邻的校验借点，设定比特借点传向校验节点的初始消息为当在AWGN信道中采用BPSK调制时，码字 映射为传输序列,接收端码字为信源等概率分布,此时概率BP译码的初始消息为2、 迭代处理步骤1：校验节点消息处理对所有的校验节点j和与其相邻的比特节点i，第L次迭代时，计算第j个校验节点传向第i个比特节点的消息步骤2：比特节点消息处理对所有的比特节点i和与其相邻的校验节点j，计算第i个消息其中是校正因子，使步骤3：译码判决对所有比特节点计算硬判决消息其中是校正因子，使若3、停止若或者达到最大迭代次数，则结束运算，否则从步骤1继续迭代。第三章 仿真分析3.1仿真结果分析：我们采用的是C语言平台和MATLAB平台，SNR为0到5dB，第一幅图为BER曲线，第二幅图为FER曲线，采用的是置信度传播算法。通过在MATLAB中调用C语言的译码程序完成。由于MATLAB要先转化为C语言才进一步编译，所以理论上MATLAB的编译码效率更低。仿真的结果确实验证了这个结论。我们从最后一个图可以看到，C语言的仿真要比MATLAB快了一倍。 图3.1 BER 曲线图3.2 帧差错率曲线3.2 C语言和MATLAB语言的仿真对比：同时，我们还对比了C语言和MATLAB语言下的编译码速度（低SNR情况下）:SNR0123BER0.121220.0712140.019210.00242C20 sFER0.967740.769230.352940.06237BER0.121220.0712140.019210.00242Matlab 56 sFER0.967740.769230.352940.06237 并且，我们还发现，随着SNR的提高，译码的时间不是线性增长的，例如，为5dB时，译码完成时间为448.5972秒。第四章 总结与展望本文对C语言和MATLAB语言下的LDPC编码效率有了一个新的认识，发现基于C语言的LDPC码编码效率有明显的优势，对以后的工作做了一些铺垫。参考文献1C.E.Shannon.A mathematical theory of communication.BSTJ,27:379423,July and:623656,Dct.19482S.Lin and D.J.Costello.(王育民，王新梅译).差错控制编码：基础与应用.北京：人民邮电出版社，19863G.D.Forney,Jr.Concatenated codes.Sc.D.Thesis,M.I.T.,Cambridge,Mass,1965,also MIT Press Research Monograph 37,19664王新梅，肖国镇.纠错码：原理与应用.西安：西安电子科技大学出版社，19915F.J.Mac Williams and N.J.A.Sloane.The Theory of Error-Correcting Codes.New York,North-Holland,19776M.A.Tsfasman,S.G.Vladut and T.Zink.Modular curves shimura curves and Goppa codes better than Varshamov-Gilbert bound,Math.Nachr.,1982,104:13287G.L.Feng T.N.Rao.IEEE Trans.Inform.Theory,1993,39:37458E.R.Berlekamp,et al.IEEE Trans.Inform.Theory,1978,24:3843869G.Ungerbock.IEEE Trans.Inform.Theory,1982,28:556710J.H.Conway and N.J.A.Sloane.Sphere Packings,Lattices and Groups.New York:Springer-Vertag,198811G.D.Forney,Jr.IEEE Trans.Inform.Theory,1988,34:11231151,1152118712J.L.Massey.Threshold Decoding.Cambridge,MA:MIT,Press,196313G.D.Forney,Jr.Study of correlation codin.Technical report.No.RADC-TR-67-410,196714C.R.P.Hartman,C.P.Rudolph.IEEE Trans.Inform.Theory,1976,22:51451715E.J.Weldon Jr.IEEE Trans.Inform.Theory,1971,17:71371816王新梅.通信学报，6(3)：6266,198517L.R.Bahl,J.Cocke,F.Jeinek and J.Raviv.IEEE Trans.Inform.Theory,1974,20:24828718C.Berrou,A.Glavieux and P.Thitimajshima.ICC93,1993,1064107419G.D.Forney,Jr.IEEE Trans.Inform.Theory,1966,12:12513120G.D.Forney,Jr.,A.Vardy.IEEE Trans.IT42:1996,1992202621D.Chase.IEEE Trans.Inform.Theory,1972,18:17018222王新梅.电子科学学刊,1986，8：40140723范平志，陈志，靳蕃.电子学报，18(4)：111114,199024刘镔，王新梅.电子科学学刊,1997，19：411415
展开阅读全文