加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 LDPC编码技术研究(硕士论文)

LDPC编码技术研究(硕士论文).pdf

LDPC编码技术研究(硕士论文)

shiwenlu518
2010-12-22 0人阅读 举报 0 0 暂无简介

简介:本文档为《LDPC编码技术研究(硕士论文)pdf》,可适用于IT/计算机领域

中国科学技术大学硕士学位论文LDPC编码技术研究姓名:冯军申请学位级别:硕士专业:通信与信息系统指导教师:周武旸摘要捅妥LDPC(Low.DensityParity.Checkcodes)码是一种基于矩阵构造编码和迭代译码的新型信道编码方案它具有很低的译码复杂度并且拥有逼近香农极限的优异性能目前最好的LDPC码字性能距香农极限仅O.dB。随着研究的深入LDPC码的编码复杂度也得到很大改善这使得它在无线通信、深空通信、光纤通信以及介质存储等多个领域都得到了广泛的应用。本文首先介绍了信道编码的发展历程以及LDPC码的基本原理和摹本概念然后从校验矩阵的构造方法、迭代译码算法以及性能分析等几个方面对LDPC码进行了讨论介绍了相关技术的主要研究成果并针对每种技术提出了自己的看法和改进方案。LDPC码校验矩阵的构造方法主要包括随机化构造、半随机化构造和结构化构造三种类型在引入各种算法原理的同时比较了它们各自的优缺点。然后本文提出一种基于先验信息的LDPC码编码方法该方法通过在校验矩阵中的弱比特位置插入先验信息可以有效避免由小循环以及不合理的度分布带来的不利影响提高了译码性能加快了译码迭代收敛速度。对于LDPC码的译码算法分硬判决和软判决两部分进行了讨论分析了各算法的性能、特点以及适用性。在此基础上本文提出一种改进的加权BP译码算法。考虑到校验矩阵各个比特节点受到的保护程度有差异它们在迭代译码过程中提供的概率信息也具有不同的可靠性因此在处理信启、迭代时为每个比特节点赋予一个权值以优化它们提供的信息的概率贡献。结果表明这样的处理可以提高系统性能减少正确译码所需迭代次数。最后本文还研究了密度进化和高斯近似等理论分析方法。通过跟踪译码迭代过程中信息的概率密度函数它们可以有效预测具有某一类特性的LDPC码字的性能同时还能够确定信道域值并帮助优化设计低密度校验矩阵的度分布。关键词:LDPC码矩阵构造先验信息加权译码SIP线条SIP铅笔SIP铅笔SIP铅笔SIP铅笔中国科学技术大学硕士学俺沦文candete咖inethechannelvaluelimitforsuccess如ltransmissionandcouldoptimizethedegreedistributionforIowdensityparitymatrix.KeyWords:LDPCcodesmatrixconstructionprioriknowledgeweighteddecoding中国科学技术大学学位论文原创性和授权使用声明本人声明所呈交的学位论文是本人在导师指导下进行研究工作所取得的成果。除己特别加以标注和致谢的地方外论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。本人授权中国科学技术大学拥有学位论文的部分使用权即:学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版允许论文被查阅和借阅可以将学位论文编入有关数据库进行检索可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。保密的学位论文在解密后也遵守此规定。作者签名:垄登渺g年r其J!日第l章绪论第章绪论§.数字通信系统描述通信系统是为了将信源信息高效、可靠地传送到接收端。有扰通信信道的噪声会对传输信息产生干扰从而可能降低通信可靠性。所以通信系统设计的中心问题是在随机噪声干扰下如何有效而可靠地传输信息。一般地通信系统的可靠性用错误比特率(BER)来衡量有效性用传输速率R比特/信道符号来衡量。早期人们普遍认为通信系统的可靠性与有效性是一对不可调和的矛盾【lJ在有扰通信信道上要实现任意小的信息传输错误概率的唯一途径就是把传输速率降低至零。Shannon信息和编码理论的奠基性论文《通信的数学理论》f】于年发表之后改变了这一观念他首次阐明了在有扰信道中实现可靠通信的方法指出实现有效而可靠地传输信息的途径是编码。目前典型的数字通信系统如有线通信、无线通信、雷达和声纳等系统的基本组成如图.所示。编码信道图.数字通信系统模犁在数字通信系统中信源编码器将消息源产生的二进制信息序列进行信源编码目的是在允许的失真范围内通过尽可能地去除信源中的冗余从而使用最少的比特以尽可能有效地表示信源。在这里对于信号失真的度量依赖于信源的性质和实际的应用环境其中最为常用的失真度量为信号的均方误差。Sh锄on在信源编码定理【】中指出对于给定信源和失真度量D一定存在最小速率为R=尺(D)(比特/信源符号)的信源编码方式用以描述信源而平均失真不超过D。显然信源的率失真函数尺(D)给出了在确定失真度量条件下信源的最小速率。信号在信道中传输时存在着信道噪声、衰落、各种干扰以及信道本身的非理想频率响应等诸多不利因素。为了保证数据传输的可靠性通常将信源编码器输出的信息比特流在发送之前进行信道编码即通过有效地添加冗余使得接收器能够以非常高的概率正确的从已经失真的接收信号中还原出原始信息比特流。Sh踟on在他著名的信道编码定理中给出了在噪声信道中数据传输速率的上界即信道容量。信道编码定理是:若SIP铅笔SIP铅笔中国科学技术大学硕士学位论文有一离散、平稳、无记忆信道其信道容量为C只要待传送的实际信启.率尺<C总可以找到一种编码当输入序列足够长时译码差错率(即误码率)R<占£为一个任意小的正数反之当R>C时任何编码的R必大于O。该定理指明存有扰信道中只要信息传输速率小于信道容量就有可能实现任意可靠的信息传输。这个存在性定理告诉我们可以实现接近信道容量的传输速率进行通信。当在噪声信道上的数据传输速率R小于诱噪声信道的容量C时一定存在一种信道编码方案使得在接收端出错的概率任意小反之如果R>C则一定不存在这样的方案。根据以上讨论不难看出编码在现代通信系统中起着全关重要的作用已经成为了现代通信系统中不可或缺的一个重要组成部分。编码可以从总体上划分为两类:信源编码和信道编码。这两类编码在通信系统中有着不同的作用其中信源编码研究如何更加有效地表示信源而信道编码则是研究如何克服信道中的各种失真从而保证数据的可靠传输。Sh锄on在信源信道分离定理【(source.ch锄elseparatjoncheo叫)中指出假定在接收端所允许的信号的最大失真为D如果信源的码率小于信道容量尺(D)<C则接收端可以在允许失真D范围内恢复信源输出相反小存在这样的方案。分离定理的一个重要意义在于它证明了信道编码的设计可以不依赖于具体的信源类型。本文研究的内容是信道编码所以假定信源产生的信息经过了有效的信源编码产生的信息比特流为满足独立同分布的二进制比特流然后研究信道编码技术对于出错比特的纠错能力。§.信道编码理论发展历程香农提出了信道编码定理并在其证明中引用了三个基本条件【】:、采用随机编码方式、码字长度趋于无穷大、采用最大似然译码算法。指出一个随机选择的码以很高的概率为好码对于随机码的最大似然译码其译码复杂度G与所传输的信息比特数呈指数关系即为G=exp㈣)随机码的误码率上限为以~G一晶(足)憎误码率风随着码长Ⅳ趋于无穷大而趋向于的同时译码复杂度以指数增长可见随机码在实际系统里其实并不实用。由于信道编码定理证明的非构造性并没有给出如何构造逼近香农容量限的编码方法构造一个逼近香农容量限的纠错码成了众多学者争相研究的课题并逐渐形成了信息论的一个重要分支玮道编码理论。五十多年来人们对构造实用好码的探索基本上是按照香农所提出的后两条基本条件为主线展开的。虽然从理论上讲除了目前已知的码外几乎所有的码都是好码但到目前为止离构造出真正意义上的实用好码还有较长的距离。尽管如此国内外众多数字和信息论学术界的研究人员仍然取得了很多优异的研究成果。从构造方法上看纠错码可分为分组码和卷积码两大类。在上个世纪五十年代到六十年代人们主要研究了线性分组码。这类编码以代数中的群论、域论等理论为数学基础利用各种代数方法设计好的纠错码并研究与之相适应的译码算法。SIP铅笔SIP铅笔SIP铅笔第章绪论第一个分组码是年发现的能纠正单个错误的汉明(HarmTling)码。年汉明(Ha舢血ngR聊发表的论文《检错码与纠错码》【】是开拓编码理论研究的第一篇论文。这篇论文主要考虑在大型计算机中如何纠正单个错误。但是H锄ming码存在许多卅i足的地方首先是效率不高码率只有/其次是纠错能力不行只能纠正单一的错误。M.Golay针对汉明码的缺点提出了性能更好的格雷码(Golay码)【。Golay发现了两种编码一种是二元Golay码采用个数据比特个校验比特为一组能纠正个错误。第二种是三元Golay码以三进制数为运算域个数据符号个校验符号为一组可以纠正个错误。这两种码基本原理相同都是将g元符号按每七个分为一组然后通过编码得到咒.后个g元符号作为冗余校验符号最后由校验符号和信息符号组成有刀个g元符号的码子符号编码码率为r=舶。Muller在年以布尔逻辑代数方式提出了Reed.Muller码(RM码)J它比Hamming码和Golay码好的地方是它可以改变码字大小和纠错能力是Iked在Muller基础上得到的一种新的分组码也是继格雷码之后提出的最主要的一类分组码。RM码在汉明码和格雷码的基础上前进了一大步在码字长度和纠错能力方面具有更强的适应性。继RM码之后Pr觚ge于年又提出了循环码的概念f引。循环码实际上也是一类分组码但是它的码字具有循环移位特性即码字比特经过循环移位以后仍然是码字集合中的码字。这种循环结构使码字的设计范围大大增加同时大大的简化了编译码结构。循环码的一个非常重要的子集就是分别由Hocquen曲em在年以及Bose和RayChuadhuri研究组在年几乎同时提出的BCH(BoseChuadhuriHocquen曲em)码BCH码的码字长度为甩=珂m一其中朋为一个整数。二元BCH码(旷)的纠错能力限为<(所一)/。年Reed和Solomon将BCH码扩展到非二元(q>)的情况得到了RS(Reed.Solomon)码。RS码的最大优点是其非二元特性可以纠正突发错误并日.它也能纠正随机错误。但直到年Berlekamp给出了一个非常有效的译码算法之后RS码才在实际系统中崭露头角比如在CD播放器、DVD播放器以及CDPD(CellularDigitalPacketData)标准中都得到了很好的应用。上面所讨论的这些都是分组码分组码本身的一些不足限制了它的运用。第一它必须是按帧传输、按帧译码这样在帧长较长时会带来一定的时延。第二是要求准确的帧同步这样才能准确译码。多数分组码要求解调器的硬判决输出这样又会带来一些判决误差影响性能。另外分组码的译码方法通常都采用大数逻辑译码和捕错译码其译码复杂度与码长成指数关系码长越长译码复杂度越大而且上升趋势很快所以基本上不实用。能够实用的只是短码长的情形而短码的性能有限难以达到逼近Sharulon极限的目标Shannon限的逼近需要长码这就需要去寻找能够有效译码的长分组码。中国科学技术大学颂士学位论文年EIiaLs等人首先提出了卷积码【】。卷积码不是将数据分割成不同的分组而是通过移位寄存器将校验比特加入输入数据流中。每甩比特输出是当前七比特输入和寄存器中的聊比特的线性组合每次输出总的比特数与约束长度七有关其码率为存一次编码间隔中数据比特七与输出比特数行之比。卷积码与分组码不同在于它在编码的过程中引入了寄存器增加了码元之间的相关性在相同的复杂度下可以获得比分组码更高的编码增益但是这种相关性同时也增加了分析和设计卷积码的复杂性。随着人们对卷积码研究的深入在卷积码的译码算法方面出现了序列译码算法、门限译码算法和维特比(Viterbi)译码算法【加】。维特比Ⅳiterbi)译码算法的出现使卷积码逐渐成为研究和应用的重点以后出现的TCM(栅格编码调制)技术进一步确立了卷积码在纠错码应用中的主导地位特别是在通信系统中得到了极为广泛的应用。其中约束长度肛码率为/和/的Odenwalder卷积码已经成为商业卫星通信系统中的标准编码方法。在移动通信领域GSM采用约束长度肛码率为/的卷积码在IS.CDMA系统中上行链路中采用的是约束长度庐码率为/的卷积码。卷积码的主要问题是对突发性错误的纠错能力差。但是采用交织和卷积码结合的方式可以在码比特送入信道前进行分组交织再进行卷积码编码存接收端先解交织再译码。经过这一交织与解交织的过程突发性错误就变成了随机错误。卷积码性能得到改善。经过上个世纪几十年的研究和实践纠错码理论和技术取得了很大的发展但是距离Shannon理论极限仍然还有一定的距离难以找到逼近Sha肌on极限的编码方案这使得人们一度认为Shamon极限仅仅是理论上的极限是不可能达到的。此时法国的C.Be啪u等人在年提出了一种全新的信道编码方案:Turbo码⋯J在信道编码的理论和应用中取得了突破性的进展具有里程碑的意义。它打破了串行级联编码的结构采用并行级联编码。Turbo码的基本思想在于利用短码构造长码在译码时将长码化为短码再利用软输入/软输出的迭代译码算法(MAP算法SOVA算法)达到了接近Shannon极限的性能。Turbo码的优异性能使其一度成为编码界研究的热点其理论和技术也逐渐成熟起来。Turbo码在通信中有广词的应用前景在诸如星际探测、移动通信、数字电视、数字广播、卫星通信中都得到广泛应用。但是Turbo码也有自身的缺点它的译码复杂度仍然较高且码长较长时交织器的存在使得时延较大。就在人们热点研究Turbo码的时候有人注意到了一种早在年就由Gallager提出来的信道编码方案LDPC码(LowDens埘Par时Checkcodes)‘屹J【J它利用校验矩阵的稀疏性使得译码复杂度只与码长成线性关系在长码长的情况下仍然可以有效的进行译码因而具有更简单的译码算法。后来D.J.Mackay、M.Neal和N.Wibe唱等人对LDPC码重新进行了研究fJ】】发现LDPC码与Turbo一样具有逼近Sha衄on极限的SIP线条SIP线条SIP线条SIP线条SIP线条SIP线条SIP线条SIP线条SIP线条SIP线条SIP铅笔SIP铅笔SIP铅笔第l幸绪论为其前向纠错编码方案美国Hu曲es公司和一些研究机构也已经研究出使用LDPC码的编译码芯片。Wimax以及BG等标准里面也采用了低密度的编译码方案。相信随着LDPC码的进一步技术成熟更多的未来通信系统会采用这种具有优异性能和应用前景的编码方法。§.论文研究内容及安排第一章介绍了信息论和信道编码的发展历程重点介绍了LDPC码的提出与发展过程分析了每种信道编码的优缺点同时在它们之间就某方面的特性作了简要比较。第二章主要介绍了LDPC码的一些基本概念和基本原理包括其产生、发展、特点、定义以及编译码思想。第三章从编码的角度重点分析了目前主要的低密度校验矩阵构造方法并给出了一种基于先验信息的LDPC码编码方案。第四章重点讨论了LDPC码的迭代译码算法并提出一种基于加权方案的BP译码改进算法。第五章介绍了两种LDPC码的经典理论分析方法比较了它们各自的特点。第六章是对本文所讨论内容的总结以及对目前LDPC码的研究现状的看法同时指出了LDPC码的未来发展趋势。SIP铅笔SIP铅笔SIP铅笔第章LDPC码基本原珲第章LDPC码基本原理§.LDPC码概述LDPC(Low.Dens时Par时.CheckCodes)码是一种由稀疏校验矩阵定义的线性分组码最初由Gallager于年提出【】。但由于当时技术条件的限制人们的兴趣大都集中在有实现可能的编码方式上比如卷积码、级联码等以至于LDPC码在很长一段时间内几乎被人们遗忘。直到年Mackay和Neal随机构造的LDPc码J存码长很长时性能超过了Berrou等人提出的Turbo码而且在实现上更有优势才激起人们重新研究LDPC码的热情。LDPC码具有诸多优异特性。其校验矩阵是一个天然交织器译码复杂度随着码长的增加呈线性增长且具有逼近Sh锄on极限的性能它的描述和实现简单有严格的理论分析工具可对其进行验证它的译码算法可并行处理有利于在硬件上的并行实现减少了译码时延可进行动态判决译码即在迭代译码过程中进行译码判决以决定是否结束译码进程如此可以减少译码迭代次数由于具有较大的码距使得不能被译码检测的错误很少因此具有良好的检错性能很少出现误码甲台(errorfloor)现象误码率随信噪比的增大快速下降有成熟的T锄er图和因子图等简单实用的图模型描述使得理论分析更加简单有效。目前仍然存在很多因素在限制LDPC码的实际应用。由于校验矩阵中短循环的存在当码长很短时性能较差因此只有长码才能体现LDPC码存性能上的优势但随之带来了许多问题。长码的编码复杂度高而且对于硬件存储器的需求也大虽然目前已经有了线性时间编码复杂度的实现方法但与卷积码等编码方式相比仍然太大。另外LDPC码需要对一组信息序列一起编码码长较长时为了接收完所有信息比特进行编码需要等待较多的时间而这将带来编码的时延。所以研究更加快速实用的编码方法成为一个重点问题。’§.LDPC码的定义LDPC码可用一个稀疏的非系统的校验矩阵且。圳。。定义其中月为码长七为信息位个数所有码字C均满足C×Hr=。校验矩阵“稀疏”是因为矩阵中除了少数元素为“l"外其余大部分元素全部是“”其每行中“”的个数(以下简称行重)远远小于校验矩阵的列数。根据LDPC码校验矩阵元素为“”分布情况的不同可以将之分为Regular和Irregular两种。RegularLDPC码(正则LDPC码)中每一行为“l”的元素个数相同并且每一列为“”的元素个数也一样即矩阵的各行行重和各列列重分别一致反之如果校验矩阵的行重或者列重不一致就称为I玎egularLDPC码(非正则LDPC码)。根据GalIager最早给出的正则LDPC码的定义描述如下【】:SIP线条SIP线条中国科学技术大学颁上学位论文正则LDPC码:对于一个码长为甩校验位长为耽的LDPC码若其校验矩阵每行“”的个数全为k每列“”的个数全为.i则称其为正则LDPC码记参数为(%/J幼并且通常满足条件歹<毛/<<朋k<以。Gallager证明了当歹≥时这类LDPC码具有很好的汉明距离特性。非正则LDPC码:类似于正则LDPC码的定义不同的是校验矩阵每列“l"的个数或每行“"的个数不全部相同。研究表明通过优化非正则LDPC码的校验矩阵中元素“l”的分布可以得到比正则LDPC码更好的性能不过在硬件实现方面具有更大的复杂度需要更多系统资源。对于校验矩阵风。假设其秩为.=rank(邱那么其合法码字个数是一。若校验矩阵不满秩即.<聊则合法码字个数大于一m。LDPC码的码率R应该为R=伽一枷而大家常常用R’=(聆一所)/门计算码率由于R’≤R所以应让校验矩阵尽量满秩才可以让月’接近真实的R值。LDPC码的校验矩阵一般都是用非系统形式给出的。例如~个()的校验矩阵可以用图.所示:Ⅳ=OOOOlOOOOOOOOOOOOOOO图.()LDPC码的校验矩阵除了用校验矩阵表示LDPC码以外还可以用双向的图模型表示LDPC码其中Talmer图表示是比较方便的一种可以形象地刻画LDPC码的编译码特性。Taruler图是一种双向图可以用G={(yE)}表示其中y是节点的集合y=%U圪。对维数为聊×"的校验矩阵日。。。圪=(l⋯玩)称为比特节点对应校验矩阵的列同时对应码字中的比特位圪=似c⋯c。)是校验节点对应校验矩阵的行也就是校验方程。E是比特节点和校验节点之间相连的边的集合£∈%×K同类节点之间没有边相连只有在两类节点之间有边存在。如果校验矩阵的第f行第./列元素为非零则Tanner图的第个比特节点与第f个校验节点有一条边相连。即当矗=l时节点c与之间有一条边相连边(c)∈E。与节点相连的边数目称为该节点的度(degree)从某个节点出发又回到此节点为一循环(cycle)所经过的边的条数称为循环的周长其中最短循环的周长称为图G的girth。校验矩阵的行重和列重与节点的度一致Tanner图与校验矩阵一~对应。上图中的校验矩阵刘‘应的Tanner图如图.所示具有个比特节点和个校验节点每个比特节点都有条边每个校验节点都有条边。lOSIP线条SIP线条SIP线条SIP线条SIP铅笔SIP铅笔SIP铅笔SIP铅笔中国科学技术大学硕士学位沦文日=睇:)陋日=I(·)lCDEJ。该矩阵形状如下:..卜一nm’HIg◆·●一m占■◆..I一心◆图.近似下三角校验矩阵形状将校验矩阵左乘如下矩阵匕一∞得到b曼cE幺j口)plf.、\一ET一|AcET。lBDoj。那么mr=驴可以分解为如下两个表达式:sr却’印=口()(一ET一Ac)sT《一ETBD)pl=oQ·q定义够=一Er一曰D并日.假设妒非奇异则求解上面两式可得:pf=一缈一f一E丁一彳ajr()p罗=一r一似Jr却’J()通过如上两个公式可以计算校验信息p和p:从而得到码字。下面对这种矩阵变换编码方法的复杂度进行分析由前面推导可知因为系统信息比特可以直接得到所以复杂度就集中在计算p和p:的两个公式。根据Richardson和Urbanl(e在】中有关复杂度计算的描述对于p和p:的计算复杂度估计分别如表.和表.所示:统计两个关于计算校验信息p和p:的复杂度的分析表格可以得到矩阵变换方法的编码复杂度为D(以)。为了降低编码复杂度应该让g尽量小。Richardson等存文章中提出了三种Greedy算法对矩阵的下三角化进行讨论它们是Greedy算法A、Greedy算法B和Greedy算法C其中Greedy算法AH、Greedy算法BH和Greedy算法CH分别表示直接作用算法A、B和C于校验矩阵而Greedy算法AHT、Greedy算法BHT第章LDPC码摹木原理和Greedy算法CHT表示作用三种算法于校验矩阵的转置。三种Greedy算法可以让g尽量小从而降低LDPC编码的复杂度表校验信息pJ的计算复杂度分析.操作解释复杂度sr稀疏矩阵与向量的乘法D(胛)ZJ(彳Jr)令一=j’复杂度同上(门)一E(r一爿s’)令y=丁一’彳J’复杂度同上D(门)csl稀疏矩阵与向量的乘法(甩)(一Er一彳Jr)(or)两个向量的加法运算D(甩)一fEr一。srC奢r)g×g的密集矩阵与向量的乘法()表·校验信息p的计算复杂度分析操作解释复杂度爿Jr稀疏矩阵与向量的乘法p(刀)B设稀疏矩阵与向量的乘法D(胛)纠sr)(却'J两个向量的加法(甩)一丁一阳Jr却f夕令一=(爿Jr却.)则jr一一D(刀)仍然是稀疏矩阵与向量的乘法矩阵燹决算法编冯过程总结如卜:第一步:预处理过程输入非奇异校验矩阵输出形如(三三:)的等价矩阵并且要保证一Er一曰JD为非奇异矩阵。预处理过程包括近似下三角化校验矩阵和矩阵的秩校验。近似下三角化是通过行列置换将校验矩阵变成形如(:三:)的近似下三角矩阵并且通过应用几个Greedy算法让g尽量小。矩阵的秩校验则是利用高斯消元法完成如下矩阵运算:(一:丁一)(:三:)=(一Er乞c一£占j口)c·关键是要检验矩阵一£r一占D是否奇异如果奇异那么需要进一步进行列置换使它最终非奇异。‘第二步:实际编码过程当校验矩阵已经按照预处理过程的要求化成了形如中国科学技术大学硕士学位论文(三三:)的非奇异矩阵那么对于给定的输入信息序列s只需要通过公式()和()计算校验信息p和儿就可以得到编码输出码字c=pp肌)。校验矩阵变换编码算法虽然可以实现近似线性的编码复杂度但是它对编码矩阵的原始结构要求较高很多矩阵仅通过简单的行列置换并不能满足该方法的诸多限制条件因此应用也遇到一些困难。降低编码复杂度的另外一个有效措施是设计具有特殊结构的校验矩阵如循环码和准循环码仅通过信息位或者校验位数量的移位寄存器即可实现该类编码复杂度低与分组长度成线性关系没有大的编码延迟而且易于硬件实现。类循环码已经成为当前的一个研究热点。§.LDPC码的译码思想LDPC码的译码算法有硬判决译码算法、软判决译码算法和混合判决译码算法三种。它们有着不同的纠错性能和译码运算复杂度硬判决译码复杂度低但性能相刘。最差软判决译码纠错性能最好刁<过复杂度也最高混合判决译码则在性能和复杂度之间有一个折中。Gallager在其博士论文【中提出了两种LDPC码的译码方法一种称为比特翻转(BitFlippingBF)译码另一种是信息传递译码。BF译码是一种基于迭代的硬判决译码算法它首先对输入译码器的数据进行硬判决然后将得到的“O”、“”序列代入所有校验方程计算各个校验子的结果如果发生错误校验方程不满足则根据校验结果找出使得校验式不成立数目最多的比特节点并将该比特节点对应的比特值进行翻转(变为或l变为)至此完成一次迭代。迭代中止条件是达到最大迭代次数或者所有校验方程都校验成立。BF译码操作简单硬件实现容易但性能要比软判决译码差很多。Gallager的软判决概率译码可以看作是Tanner图上的置信传播(BeliefPropagaIionBP)译码算法也称为和{|}{算法((SumProductAlgo“thmSPA)或信息传递(MessagePassingMP)译码算法由于其性能最优因此应用也最广。译码思想大致是:对某一个接收码字进行译码时先根据接收数据和信道信息初始化每个比特节点的概率软信息再将比特节点的概率信息传递给校验节点校验节点的概率信息是参与该校验方程的所有比特节点对该校验方程的概率贡献:然后校验节点将概率信息传递给比特节点对于某个比特节点而言该软信息就是它所参与的所有校验方程对它的概率贡献最后比特节点利用从它参与的所有校验方程那里得到的概率信息以及信道初始化信息进行译码判决。如此则完成了一次信息传递和迭代过程当某次判决译码成功或者达到迭代次数上限时就停止译码否则进入下一次迭代过程。经过几十年地不断发展LDPC码的译码算法得到不断完善出现了很多新的译码算法。包括年Tanner提出的基于Tannef图的并行译码算法年Richardson第翼矍鋈嘉甜为烈靳簦萋北蠹羹l蓁霎翼|霎|薹|冀霰豢萎j预羹搓冀嚣霎喜雾疆塑曼章薹垂羹垂耋谚岑羹臻i羹一霎l飘i毫t薹i塾霪焉墨甥型|霎÷蘸堋博嗜錾塞囊至牟拆蓁咎氅囊一萋鬟i鬟$靼震理鬟孽噬舂强蔼瑶嵩蠼窿鋈羹都亲妤嘉捌霎壅薹雾西醋粕妻西浏浑塞邑舐霎磺她啪臻唾膏羹臻曼霎型虱勤马幽蚕茧薹摹虿蠹装蓁鹰惯佃鹭也I复舞霎有的虑萎纛露j薹吲鹤薹|强第章LDPC码校验矩阵构造方法第章LDPC码校验矩阵构造方法LDPC码的编码关键就是构造低密度奇偶校验矩阵不仅如此校验矩阵在译码过程中也起着至关重要的作用。根据构造方式的不同目前LDPC码校验矩阵主要有随机化、半随机华和结构化等几种构造方法。随机化构造方法在LDPC码的早期研究中出现较多以Gallager、Mackay以及Richardson等人为代表。此方法构造的校验矩阵由于具有随机特性因而纠错性能良好但由于矩阵结构不固定无法实现简单编码译码时校验矩阵的存储复杂度也高所以在实际系统中的不易应用特别是磁记录和光纤通信等高速传输场合。近年来结构化的构造方法已经成为LDPC码校验矩阵构造领域的主要研究热点如循环码和类循环码、几何设计法、组合设计法以及性能优越的PEG方法等。这是因为结构化构造方法不仅可以克服校验矩阵中短循环的产生而且生成的LDPC码字可以是循环码或类循环码具有线性时间编码复杂度同时矩阵具有确定的结构便于硬件实现。性能上由于结构化方法可以设计ginh较大的码字因此并不会比随机校验矩阵构造的码字差多少。§.随机构造法..Gallager构造法Gallager最早在】中提出了一种简单的LDPC码校验矩阵随机化构造法此方法构造的校验矩阵度分布为(矾以)其中矾≥构造过程如下:根据校验矩阵码长以及行列重等参数首先设计一个基矩阵风基矩阵中每列都只有一个元素值为并且第f行中为l的元素全都分布在从(f一)以到试的以个连续列中如图.所示。然后对基矩阵做随机列变换得到其余玑一个子矩阵并将这矾一个子矩阵以等概率随机排列的方式叠放在基矩阵的下面从而构成一个LDPC码的集合如图.所示。风=ll⋯、、rJt个ll⋯、vJ以个l图。l基矩阵结构H=HQ乃(凰)死.一(风)⋯、·、Jt个l图.由基矩阵构造LDPC码的校验矩阵其中刀(凰)表示通过凰的随机列变换生成的子矩阵。可以看出用这样的方法得到第章LDPC码校验矩阵构造方法§.半随机构造法校验矩阵的随机构造方法可以不受码长、码率等参数限制参数选择灵活而且性能好不过其不固定的结构使得编码复杂度高。下面介绍一类半随机的LDPC码它们具有编码简单以及参数选择灵活的特点。..半随机LDPC码文献【】介绍了一类半随机LDPC码它将码长为九信息位为七的LDPC码校验矩阵分解为两个子矩阵形如胃=【H一日d】。其中Ⅳ“是一个(胛一七)×克的矩阵称为信息位矩阵它采用随机方法构造日是一个(l一。七)×(”一七)的矩阵称为校验位矩阵它是双对角线形式的下三角方阵具有如下形式:Hp=O⋯UUO⋯UUO⋯【)UO⋯O⋯相应的将校验矩阵所对应的码字向量c分解为对应的校验位向量c和信息位向量cd即有c=【cp一】校验矩阵与码字向量c之间有如下关系:广.胁r=日日d】|二‘『|.HfHoJ=口()L~J在二进制情况下公式(.)可变换成如下形式:日即P=日屯d()由上式可知给定任意一个信息位向量cd能够利用构造出的校验位矩阵日P和信息位矩阵日d直接计算出cp从而得到码字向量c。有两种方法可以计算c一是cP=日PrI【日ccd】二是直接对公式(.)进行高斯消元求得cP后者较前者更简单具有线性计算复杂度。总结半随机构造法先是利用随机方法构造一个信息位矩阵HJ然后根据参数设定一个校验位矩阵日给定信息位向量cd后再分两步完成编码:l、计算中间映射向量l=日dcd、用高斯消元法解方程Hc=l求得校验位向量c从而获得编码码字c=陋cd】..兀旋转LDPC码文献】描述了一种基于兀旋转的LDPC码构造方法它实际上是在半随机LDPC码的基础上来构造的。由半随机LDPC码的校验矩阵结构可知日=【ⅣPⅣ】在冗旋转SIP铅笔SIP铅笔SIP铅笔SIP铅笔SIP标注SIP铅笔SIP铅笔SIP铅笔SIP铅笔SIP铅笔SIP铅笔中国科学技术大学硕上学位沦文次数。假设区组矩阵抒是以X中的元素为行区组为列的矩阵那么矩阵中元素拓=l表示元素屯被区组所包含否则^=O。根据如上对应关系还可以得到w=掀。介绍了BIBD理论后下面详细讨论如何利用三维循环网格图来构造BIBD和LDPC码的校验矩阵。...基于三维循环网格图的BIBD构造根据BIBD理论如果构造了一个BIBD那么就可以对应得到一个LDPC码的奇偶校验矩阵从而得到一组LDPC码字。这里介绍一种用三维循环网格图构造BIBD的方法。首先构造一个尺度为C×R×Q的三维循环网格图描述如下:上口ffcP(CRQ)={(xJz):≤x≤C一≤y≤R一O≤z≤Q一)其中R为质数Q、C为正整数(C一般取为)C、又、Q可分别看作三维循环网格图对应X、Y、Z坐标上的量如图.所示:图.()三维循珂、网格图构造网格图之后需要对网格内各个元素点进行编号一般按照Z轴优先X轴其次Y轴最后的顺序将各个元素节点编号填入网格内。想要在网格图内部构造~组平面然后在各个平面内生成一组直线直线对应着均衡不完全区组设计的各个区组而直线上各个点就对应着区组中的元素。为了构造一组平面先在图中顶部R.C平面内构造一组直线然后沿着该直线向Z轴切开网格图得到一组切面作为甲面组再在该组甲面内部作直线得到区组。下面详细介绍这个过程以及相关参数的选择。拈嬲嬲●X萋錾曼篓蚕篓瞬卸卿矧崮矛杰霪霪囊陉薹|雾巡蠢霸童列霾墓ii。l登j照苌垂竖萋蓁蠢竺羹囊豁爷可墨葫童墅雾舅耱鐾墼冀琵罂篷嘎萋巨缘分羹和不平行子翥鬟薹瑟馨烊篓霎鋈可汁堕塞i夔i羹l捌霎:部霪萋叫崾雾隧霎莲萋型一堇垡爵鲜i薹|囊鋈诗篓一倒}丰{獯摒丽菊丽菰稀萋僮卷雾耋萋二羹=型f蓁耄二照冀嚣型理蓁耄羹羹嚣耋靖蟹鋈i霎仕薹球蓁希端型而萎芦萋墼薹羹蓁薰藿錾霎:薰鬟*望i璀暄季暨蟛⋯量冀|警喜=翼些附鸯冀篷填鍪螫弱塑需攫薹爷蠡可她i雕戊姜量茎绸鏊i耄刿型¨。副}引誊薹|趔薹i掣萋霎妻氨薹蒺圭季錾霎秘i蓼凳襄冀鼋囊妻萋塑誉昼萋鲔x中l斐蚕薹霉喜藩同巍刍她嗣童墓i霎蓊墼~嚣黧饕溪豢垫薹塞塑耋霉臻建鬻到墅要k墼笔握篓露菘囊堤蔷哩墼霁攀藉掣羹j掣利如蠢超翼繁乳囊按凰器斜一手帑器竹薹辩蓁^*羹!萋一霎。剥壁笋塞翥情瘗幕=囊雾翥鬟羹掣塞纛霉些茎喜藿l萎霎萎霎霪主璧莲l耋囊器ii耋霎二掌貉臻萝主鐾瞧铂攀厦缘萋季一些羹纛蓄羹毪一蠢珊奏薹筵循圉L墨彳蓝丙薹雾篓薹嚣旭凰稍蓁鏊F:型沛囊羹刽型冀卧更需雾番碡蓁三蓁丽蠹羹院蓍羹妻黼鬟蹦裂薹甭百露澜羹霪基霎妻l蓄萋|||幕幽薹面奏耄i引引勰拳当箫希麓曩霎皿雾蹙雾爱誓誊希萎爨蔫篓囊一萨一零{显篓萋篓墓主耋雾鏖留鲢喾r雕雾囊型爱萼提叠曜螺葡篓蚕《墅雾髅堡雾萋起遵圣i蠕姜嚣矿以|蓐墅薹涠嗟狻囊j攀堕雾磊瑚淄哺誊毛耋奠秦翼掣利邑劐双蓁l薹霎萋一霎蓁萎奏奏:毒萎萎耋专辜§詈睾篓篓霎i鬈髦:ii皇蠢垂蓄i等羹薹雾鍪霆蓁薹羹雾蒌囊蓁鏊羹圃雾羔篓熏瓷垂耋纛囊霎霸裂载£墓型霎叫誉i是鏊曜旱耋群哙导囊善膏叁囊苴猁降靖甥莉攀鍪雾莹量蓁塞篙裂导潦廿慧遣悟静j墓存囊鋈望羹零藿塌露唆皤蠖季妊薹雾陲鬻甚竖爵錾爱薯悬篪坫:}鬟薹羹孰趔薹囊囊薹亚篓。r基霸蒂忑幕罐:荫篓蔫鞲鍪阿塑≯篷鐾蠢萎薹黍鬲端赢裂£蠢笪雾树融掣验理阻堕芎篡i薹!蓁塞蔷剖娄割剽剡翔塞蓊旨矍薹叶羹霆参列塑希量~垫謦雾蓁冀鬣鬣撵鍪篓墓薹翥娶摹髦薹搿埔囊蚓馥蚕二莓嶷环囊埔蘸攀钙邂筌蠢羟巍璎翔一蜊薹喜翦雾l囊j鬟攀蓄j喜南£篓耋稀鬓冀褐鏊豆冀雾瓤錾篓蕈煞醑耪裤猎诺落耀垮瑗霎霎季摹旨露孽季萋||耋黎青薹菱妻喜羹囊j蓁i羹攀和蘩瑚送竖C熹鋈蒸孺雾靴蒜誊i剐彭雾霁荫萎驰匪羹斜囊萋鬈篓笺导美需鬟器!荔馨循型驯薷萎墼豢羹冀雾藿馥雾囊蓬璧絷鬟羲笞毋一羹薹引赚醋至鱼谨蓁薹‰型冀誊囊经瞥藿缉士塑亘线薹名塞静曩型妻蓁零狻耀瑙望嚣塑塑鑫靶毖袭霎弛冀蓄辇萋蓠羹雾簿粤至霁塑羹薹捌酉雾羞亟袋毳杉:灞隋囊碍毳簦茎曲士辫型显零薹蓁型缸霉墅蓁篓霾薅l萋一{主i羹蓁薹篓霎萎紊妻窭墼霸凳鎏莠蓁垄i主!薹羹!x第非LDPC码接艟摊孵毋碹刀{篓④逸一携避霆!薹羹鋈霪蓁雾茎蓁皑鉴矍羹耋葡!碧豳萋崇磊落些簿擀群鬻掣醋霄蛩融翅i降陶羹儒涮礞缚储薹能妊翼i季{。~罾坚颡囊震羹鬯琵*薹!霉一lj茎士褥蛾剥耋蓁雨枣奶碰僦蓟和蓟划耋藿参羹薹薹匡羹羹蓁萋妻薹萎i霎垂鐾li耋薹i≤i当“爹茎囊窭需拶譬墼转群一鏊薹芳蠢蓁烈篓稻蠢霁鬟朝乳霎銎I燮霰鎏垦鬻丢雾奘薷甥罐噻鹱霉=蒜囊蓥第薹|l羹羹藕堀强薹坦臻霎璧粪罐太墓m薹塞霪塞弱鬻塑鬟裤笛i薹魁坚囊:蔷缳il震l鲢剿稳别墅零i导堂螃降刽隋朔畴囊耐巍嵩甘苦蒙苴箸晏鉴lll麒羹鄯蓟画蠢一後一能氧萎茎囊孽琴i萎矿型固∥彰列薹羹麓馏墁翟醭鬈掣蜡霉薹鬲缳鳓矍鬻塑将孺薹霎!重爵博糁蓁|i硐雾阿誊菖黟照运裢得塑鍪謦艘罐嶝霎i荐分兜蓓啄砻阿薹錾塞薹萋一羹蒌蒌羹薹。妻雾霎霎萝莹薹萼主雾羹鬻l蓁}i!鍪委耋霪篓羹熏囊冀垂薹鋈粪冀蓁薹萋髻薹囊毒奏辚型痒蜀塑霎冀虿蓍理挂藿堪薹降雾i燃蔓驽凝萋娶过蓁荪F融钔兰彭ii{l研雾圈霪哥曜债博圃蟹薹雕邵醵弘娃醐融錾雾!菁理雕型霸缝蹦硭南辐旌萎刖一圳羹薹蒯鼬黼戈“辅掘训搦划为i沾嶝霎萋哩雾|羹||錾刖卤型塑萝篇出墨蓁雾菰集匿箝藩蕾垂鬻笾蓁羹羹鬻玉%雅蛩磊著塑霎薹籍鏊I舛巷懒蓥擞塑薹曛甜i参。蓁:薹菱鬻澎猁莲硷篡罐冀磊强耋鳞矗薹篇髯鞋薹雾一绻烈型£磁偌沲曼薹芎颤嘲囊滔霎薹塑磊颡叫西药霎雪塞霾垡耋季∞i强瀵臻瑙坦汽州强一礞辇垂|篓|妻|萋!粪鬻翼羹迂薹i冀霎鬟鎏霾鼙蔫塑星塑囊蓁雾霆管孵冀震蠹教鞭簇提环粪曼蒌雾锢霎麦薹塑雾髦薷霪耋塞蓁蓥埋枣i萋蓁|辫霞爵笋薹割萋薹塞蓠蓁需幽毋。凰劐瑗幕蘸羹委冀蓥囊羹鬻崩羹蓁藿蓊羹薹舔j惹薹霸再薹肇奏篓麓薹瓢霎蝇难皱翻盯}支剽镁塑爹矍一理坚翟罄召型智裂雾磊誉‘型型型爱磅式方阵璧颡璺藿催i掣息鋈耋剧轷羹稀篮怎耀翼雾鳖型菰竺薹鬈邕垂盘薹篓薹需需舜眩塑奏耋蜀黍登襄叁萎副鬻囊。蓁蓼塾蠹霎m薹臻氆捌碉琅捌羹篓量鍪雨酗妻羹霎傍j规鬻i萋i耋!錾雾耄恼锗毒翼蠢藿辫键羹翥霆尉.司l萎|i羹霎l犁击雅睦薹x中国科学技术大学硕士学位论文G=【(ck。∞B缸铆(M))’k(M)。鲫(州)】()根据环%上乘法和加法运算的封闭性两个分块循环矩阵运算的结果还是一个分块循环矩阵所以G显然也是一个分块循环矩阵。因此存假定鼠。。矩阵满秩的条件下得出了二进制的分块循环生成矩阵G的系统形式。不过对一个RC×尺C的多项式矩阵求逆比较复杂可以利用高斯消元法对核一心矩阵%。作高斯消元处理得到核心生成矩阵q。。。基本思想:通过一系列的行交换和行间相加运算(如有必要可作列交换)将且。化简为fk.川最。.x『f(坩卅)的形式那么G州=I(%州M))’肿c)咧¨)I。在对皿。。化简过程中如涉及到列交换则需要在进行化简的同时记录每次列交换的位置最后根据这些记录对瓯憎进行相应的逆列交换从而得到符合条件的核心生成矩阵并根据映射规则得到最终的二进制生成矩阵G。这种做法看起来易于实现不过对于多项式矩阵的高斯消元也的确比较复杂。由于多项式环中并不是每个元都有乘积逆元所以直接高斯消元不太可能。简单以Q=为例=的多项式环为:{Olxxlxxzxlx石)其中运算是对lx求模的由于l石是z的因式所以找不到lx的乘法逆元但是对于单个z的指数项的元总是有逆元的。具体步骤如下:一、先把校验矩阵化为『尸其中涉及到行交换或者列交换要保证需化为单位矩阵的元素不为并且只含有最多一项关于x的指数项否则可以通过交换行或者列来实现。厂p二、得到最初的生成矩阵l』rJ然后根据交换列的记录刘‘生成矩阵作相应行变换得L』J到最终的生成矩阵。作者在文章中还给出了相应编码器的硬件实现结构并行的处理使得该算法具有很高的编码效率详细设计不再作讨论。..PEG构造法PEG构造算法是Xiao.YuHu等人提出的一种低密度校验矩阵构造方法⋯【l此方法以Edgeby.Edge的方式在Tanner图的校验节点和比特节点之间建立边的连接增加新边时可以使图的ginh达到最大能够生成性能优越的码字。利用PEG方法可以构造正则码和非正则码将校验矩阵变换为上三角形式可以获得线性时间编码。将准循环码的限制加入到PEG算法中将比特节点和校验节点分组以组为单位设置边可以获得准循环码的校验矩阵性能与代数几何法得到的准循环LDPC码相近【】。第章LDPC码校验矩阵构造力‘法...PEG算法原理PEG算法构造矩阵的思想:Tamer图中的边一条~条地加进去每次加入新的边时都预先作一些处理使得新加入的边在原来的T觚ner图基础上尽量不要构成新的环或者让新生成环的周长尽量大。这样可以保证Taruler图中尽量少出现短环让编码性能得到提高。在叙述构造步骤前先定义一些符号:y=珞U眨为所构造的校验矩阵对应的Tanner图中的节点珞={&函⋯.岛一。}为疗个比特节点集圪={铂cl⋯..%一)为肌个校验节点集。饺={吐。以..⋯以一.)为比特节点度的非递减排序其中么。为第/个比特节点的度『为到疗一l并且幽≤以l≤⋯..≤以一。眈={以。以h⋯如.。)为校验节点度的非递减排序其中以为第/个校验节点的度/为到某肌一并且或o≤以l≤⋯..≤屯E=(瓦U毛U⋯。U民一。)为协mer图中所有边的集合。其中层为与比特节点乃相连的所有边的集合。瓦‘为比特节点s上的第k条边≤七≤以一l矾:即从J出发在深度为的范围内直接或间接与s相连的校验节点的集合所谓深度为的范围是指从J出发沿TaIuler图的边形成的一个以J为顶点的树形结构(见图.)有珀勺深度而该树每层的节点是指校验节点。Ⅳ≥:这是心的补集即觚UⅣj=圪它是在J的深度为的生成树范围内还没有被包括进去的校验节点的集合。●●●●●●Depth图。从毛延伸出的深度为Z的生成树在PEG方法中.当给定Taruler图参数包括比特节点数甩、校验节点数肌、比特节点度序列n可以按照依次添加边的方法在比特节点和校验节点之间设置新边新入的边对图的ginh影响尽可能小可以使比特节点的本地ginh达到最大。关键就是要找到与此比特节点距离最远的校验节点并在它们之间设置新边下面描述PEG算法的执行过程。中国科学技术大学硕士学位论文对于比特节点从第O个到第.个根据各自的度巩依次添加边。对于第O个比特节点在当前校验节点集合州中选择一个度最低的校验节点a与之相连得到(町q)专霹其中E是比特节点J的第一条入射边。如果不是第一条入射边那么在当前图集合基础上将比特节点J展开成深度为f的子图直到集合Ⅳ:的元素数目达到校验节点的数目聊或者心≠≯而Ⅳj=矽。在这种情况之前Ⅳ:≠痧说明还有比特节点s没触及到的校验节点那么只需要存Ⅳj中选择一个度最低的校验节点与比特节点J相连即可否则比特节点s已经触及了所x中国科学技术火学硕上学位沦文容易被纠错列重小的比特节点由于参与的校验方程数少译码时能获得的外信息也更少纠错更困难。因此在非正则LDPC码中不同列重的比特节点受到的保护程度也/≮一样。如何估计LDPC码的比特节点之间的差异性仍是一个问题由于它受小环、列重等多种因素影响所以需要综合考虑各项因素。密度进化【】和高斯近似㈣都是分析LDPC码的有效工具通过跟踪译码过程中比特节点和校验节点概率密度分布的变化i仅能估计译码门限还能估计译码的迭代收敛性以及每个比特节点的出错概率遗憾的是这两种方法都假设码长无限长和实际有限码长情况下的结果有较大差距。联合高斯近似分析方法适于有限码长情况它是在高斯近似的基础上将节点向量的概率分布看作联合高斯分布通过计算节点向量的协方差矩阵以及均值向量得到节点向量的联合高斯分布概率密

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/13

LDPC编码技术研究(硕士论文)

仅供在线阅读

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利