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

上传资料

关闭

关闭

关闭

封号提示

内容

首页 低密度校验(LDPC)编码调制研究

低密度校验(LDPC)编码调制研究.pdf

低密度校验(LDPC)编码调制研究

gege
2011-05-10 0人阅读 举报 0 0 暂无简介

简介:本文档为《低密度校验(LDPC)编码调制研究pdf》,可适用于IT/计算机领域

博士学位论文高速数据传输中的低密度校验(LDPC)编码调制研究专业:通信与信息系统姓名:黄杰导师:朱近康中国科学技术大学二零零六年九月ResearchonLDPCCodedModulationforHighDataRateTransmissionThesissubmittedforthedegreeofDoctorofPhilosophyinCommunicationsandInformationSystemMajor:CommunicationsandInformationSystemCandidate:JieHuangSupervisor:ProfJinkangZhuUniversityofScienceandTechnologyofChinaSeptember高速数据传输中的低密度校验(LDPC)编码调制研究黄 杰中国科学技术大学fredandymailustceducn中国科学技术大学博士论文摘要第I页共页摘要本文研究高速数据传输中的低密度校验(LDPC)码编码的原理、有效编解码算法以及基于低密度校验编码的编码调制系统的分析和设计方法。LDPC码是一类能够达到Shannon极限性能的线性分组码。长的LDPC码的性能甚至于比turbo码的性能还要优越。与turbo码相比LDPC码的解码算法复杂度小而且易于并行实现这些都使得LDPC码成为了可以挑战turbo码的另一种信道编码方案具有广阔的应用前景。本文首先介绍了LDPC码的原理包括非规则的LDPC码及高阶域上的LDPC码的结构提出了一种集合{,,,}p−上的推广的LDPC码。接着探讨了LDPC码的有效编码算法及解码算法。对于LDPC码的编码问题介绍了具有半随机校验矩阵的LDPC的线性编码算法提出了集合{,,,}p−上的推广的LDPC码和高阶域环码的线性编码算法。对于LDPC码的解码问题介绍了二元LDPC码的和积(sumproduct)解码算法和对数域解码算法及高阶域LDPC码的基于多维FFT的解码算法和对数域解码算法提出了集合{,,,}p−上的推广的LDPC码的基于多维FFT的解码算法和对数域解码算法。接着简要探讨了低密度校验编码调制系统结构分析了其接收机及系统容量提出了二元LDPC编码的BICM系统的一种等效模型利用此等效模型可以将接收机输出的编码比特的对数似然率(LLR)信息的分布用混合高斯分布近似以便对系统做半高斯近似分析和设计。然后介绍了用于二元LDPC码分析和设计的密度进化和外信息转移图技术的原理及应用。本文还探讨了二元LDPC码分析的高斯近似算法的原理包括全高斯近似和半高斯近似算法提出了利用半高斯近似算法设计二元LDPC编码的BICM系统的方法并利用此方法设计了用于PSK调制的BICM系统的多个码率的LDPC码对所设计的码字做了性能仿真设计结果及仿真结果显示这种方法比外信息转移图及全高斯近似都要更精确同时比密度进化的计算量要小提供了一种性能和复杂度的很好的折衷。最后探讨了高阶域上的LDPC码在无限码长情况下的蒙特卡罗仿真原理提出了集合{,,,}p−上的推广的LDPC码在无限码长情况下的蒙特卡罗仿真原理给出了集合{,,,}p−上的推广的LDPC码的一些性能仿真结果通过分析无限码长下的蒙特卡罗仿真结果以及性能仿真结果发现集合{,,,}p−上的推广的LDPC码具有优异的性能。关键词:低密度校验编码算法解码算法比特交织编码调制高斯近似蒙特卡罗仿真中国科学技术大学博士论文Abstract第III页共页AbstractThisthesisstudiestheissueofefficientencodinganddecodingalgorithmsforLDPCcodesandtheanalysisanddesignissueofLowDensityParityCheck(LDPC)codedmodulationforhighdataratetransmissionLDPCcodesareShannonCapacityAchievinglinearblockcodes,whichcanevenbeatturbocodesatlongblocklengthComparedwithturbocodes,LDPCcodeshaveasimple“beliefpropagation”decodingalgorithm,whichcanbeeasilyadoptedforparallelimplementationThusLDPCcodesareregardedasachallengetoturbocodesandareverypromisinginmanyapplicationsInthisthesis,firstweintroducethestructureofLDPCcodes,includingthestructuresofirregularLDPCcodesandLDPCcodesoverGaloisfieldsWepresentakindofgeneralizedLDPCcodesoverset{,,,}p−WethendiscusstheissueofefficientencodinganddecodingalgorithmsforLDPCcodesWithrespecttotheencodingissue,weintroducethelineartimeencodingalgorithmforLDPCcodeswithsemirandomparitycheckmatrices,andproposethelineartimeencodingalgorithmsforgeneralizedLDPCcodesoverset{,,,}p−andcycleGF(p)codesWithrespecttothedecodingissue,weintroducethesumproductdecodingalgorithmandlogdomaindecodingalgorithmforbinaryLDPCcodesWealsointroducetheFastFourierTransformationbaseddecodingalgorithmandlogdomaindecodingalgorithmforLDPCcodesoverGaloisfieldsWepresenttheFastFourierTransformationbaseddecodingalgorithmandlogdomaindecodingalgorithmforgeneralizedLDPCcodesoverset{,,,}p−WethengiveabriefdiscussiononthestructuresofLDPCcodedmodulationsystemsandanalyzethereceiverandthesystemcapacitiesWeproposeanequivalentmodelforthereceiverofbinaryLDPCcodedBICMUsingthismodel,thedistributionoftheoutgoingLogLikelihoodRatio(LLR)messagesfromthereceivercanbeformulatedbymixedsymmetricGaussiandistributionsThen,weintroducetheprincipleandapplicationofdensityevolution(DE)andextrinsicinformationtransfer(EXIT)charttechnologyfortheanalysisanddesignofbinaryLDPCcodedmodulationWealsodiscusstheprincipleofGaussianapproximationalgorithmfortheanalysisanddesignofbinaryLDPCcodedmodulation,includingtheAllGaussianApproximation(AGA)andSemiGaussianApproximation(SGA)WepresentanovelmethodwhichdesignsbinaryLDPCcodedmodulationusingtheSGAalgorithmandusingthismethodwehavedesignedseveralLDPCcodeswithavarietyofratesforLDPCcodedBICMsystemwithPSKmodulationDesignresultsandsimulationresultsshowthatthismethodismoreexactthantheEXITandAGAalgorithmandissimplerthantheDEalgorithmThismethodoffersabettertradeoffbetweentheperformanceissueandthecomputationcomplexityissueFinally,wediscusstheprincipleofMonteCarlosimulationsforinfinitelengthLDPCcodesoverGaloisfieldsandpresenttheprincipleofMonteCarlosimulationsforinfinitelengthgeneralizedLDPCcodesoverset{,,,}p−MonteCarlosimulationresultsandperformancesimulationresultsshowthatgeneralizedLDPCcodesoverset{,,,}p−havegoodperformanceKeywords:Lowdensityparitycheck,encodingalgorithm,decodingalgorithm,bitinterleavedcodedmodulation,Gaussianapproximation,MonteCarlosimulation中国科学技术大学博士论文目录第V页共页目录摘要·····································································································································IABSTRACT···························································································································III第章引言···············································································································第章低密度校验编码····································································································§二元LDPC码··································································································LDPC码的Tanner图·································································································§高阶域上的LDPC码······················································································高阶域上的环码·····································································································§集合{,,,}p−上的推广的LDPC码··························································交换环上的LDPC码·······························································································第章低密度校验编码的编解码算法············································································§LDPC码的编码问题······················································································LDPC码的有效编码算法························································································具有线性编码复杂度的LDPC码·········································································§LDPC码的概率解码算法·············································································二元LDPC码的和积解码···················································································二元LDPC码的对数域解码···············································································基于多维FFT的高阶域及集合上的推广的LDPC码的和积解码·······················高阶域及集合上的推广的LDPC码的对数域解码············································第章低密度校验编码调制系统··················································································§LDPC码编码调制系统结构·········································································§LDPC码编码调制系统接收机及容量分析·················································§LDPC码编码调制系统设计方法·································································第章密度进化···············································································································§二元LDPC码的密度进化·············································································密度进化原理·······································································································离散化的密度进化·······························································································§用密度进化进行二元LDPC码的优化设计·················································第章外信息转移(EXIT)图分析与设计······································································§二元LDPC码的EXIT图···············································································中国科学技术大学博士论文目录第VI页共页外信息转移(EXIT)图···························································································EXIT技术的信息论基础·······················································································§用EXIT图进行二元非规则LDPC码的设计················································§MIMO信道下的LDPC编码系统设计··························································MIMO信道模型·····································································································MIMO检测器的EXIT曲线····················································································联合的MIMO检测器和符号节点解码器的EXIT曲线········································设计举例···············································································································§MAP解调器的EXIT函数·············································································第章高斯近似分析与设计··························································································§二元LDPC码的全高斯近似·········································································正则LDPC码的全高斯近似·················································································非正则LDPC码的全高斯近似·············································································§二元LDPC码的半高斯近似·········································································基于半高斯近似的LDPC码解码器分析······························································LDPC编码BICM系统设计····················································································LDPC编码BICM设计结果····················································································第章无限码长下的蒙特卡罗仿真·················································································§高阶域上LDPC码在无限码长下的蒙特卡罗仿真·····································§高阶域环码在无限码长下的蒙特卡罗仿真··············································§集合上推广的LDPC码的性能仿真及在无限码长下的蒙特卡罗仿真·····第章结束语·················································································································§本文工作及作者的主要贡献······································································§可继续研究的方向······················································································参考文献·······························································································································作者在攻读博士学位期间的研究成果和科研项目···························································致谢···································································································································中国科学技术大学博士论文第章引言第页共页第章引言本文的目的是探讨低密度校验编码的原理包括其有效编码算法和解码算法并研究了基于低密度校验编码的编码调制系统的分析和设计方法。低密度校验(LDPC)码是一类能够达到Shannon极限的线性分组码。长的LDPC码的性能甚至于比turbo码的性能还要优越。LDPC码的主要优点是存在一种叫做“置信度传播”(beliefpropagation)的迭代解码算法。这种解码算法的复杂度随着码长呈线性增长并且非常适合于并行实现。LDPC码最初是Gallager于年在他的博士论文里提出的。后来Tanner发展了Gallager的思想用Tanner图来表示码字定义了变量节点和限制节点Wiberg进一步发展了这种思想引入了状态变量节点使得传统的卷积码理论与“定义在图上的码”(codesdefinedongraphs)联系起来。在被遗忘了多年后Mackay和Neal于年重新研究了LDPC码证明在利用和积(sumproduct)算法解码时LDPC码具有接近Shannon极限的性能。年Richardson等人提出了密度进化方法用来分析和优化LDPC码。Chung等人在同一年提出了全高斯近似算法来简化密度进化并利用这种方法进行了二元非规则LDPC码的设计。年Ardakani提出了半高斯近似算法并利用半高斯近似算法分析和设计了BPSK调制下的二元非规则LDPC码。本文作者提出了利用半高斯近似算法设计二元LDPC编码的比特交织编码调制(BICM)系统的方法。在年Brink首先介绍了外信息转移(EXIT)图技术Brink用EXIT图技术分析和设计了二元非规则LDPC码并且利用EXIT图技术设计了LDPC编码的多输入多输出(MIMO)系统。年Land等人和Sutskover等人独立的对EXIT图方法进行了信息论探讨给出了EXIT图技术的信息论基础。LDPC码可以很自然的推广到高阶域。年Mackay和Davey发现高阶域上的LDPC码的性能比最优的turbo码性能还要好。Mackay和Davey还介绍了蒙特卡罗(MonteCarlo)仿真来分析高阶域上的LDPC码在无限码长下的行为。本文作者提出了一种集合{,,,}p−上的推广的LDPC码并且提出了利用MonteCarlo仿真来分析集合{,,,}p−上的推广的LDPC码在无限码长下的行为。信道编码的任务是要寻找具有线性编码复杂度和线性解码复杂度并能达到Shannon极限性能的码字。构造具有线性编码复杂度的LDPC码是一件很有意义的事。半随机(semirandom)结构的LDPC码就是一类具有线性编码复杂度的LDPC码。本文作者证明了高阶域上的环码(cyclecode)也是一类具有线性编码复杂度的LDPC码。另外本文作者提出了集合{,,,}p−上的推广的LDPC码的线性编码算法。LDPC码的解码算法有和积(sumproduct)算法、最小和(minsum)算法和最大积(maxproduct)算法等Kschischang等人在年用分解图(FactorGraph)理论统一了这些解码算法。在Kschischang等人的论文中还介绍了二元LDPC码的对数域解码算法。Barnault等人和Song等人在年独立的提出了高阶域上LDPC码基于多维快速傅立叶变换(FFT)的解码算法。年Wymeersch等人介绍了高阶域LDPC码的对数域解码算法。本文作者提出了集合{,,,}p−上的推广的LDPC码的基于多维FFT的解码算法和对数域解码算法。本文致力于探讨低密度校验编码的原理及低密度校验编码调制系统的分析与设计方法。比较全面的介绍了当前研究的现状着力探讨了低密度校验编码的编解码算法及基于低密度校验编码的编码调制系统的分析和设计方法。除了介绍二元LDPC码及高阶域上的LDPC码的结构外还提出了中国科学技术大学博士论文第章引言第页共页一种集合{,,,}p−上的推广的LDPC码并且提出了其线性编码算法及其基于多维FFT的概率域解码算法和其对数域解码算法同时还提出了一种高阶域环码的线性编码算法。对于二元LDPC码编码调制系统介绍了利用密度进化方法、外信息转移图技术及全高斯近似算法进行分析和设计非规则LDPC码的方法同时提出了利用半高斯近似算法进行二元非规则LDPC编码调制系统设计的方法设计结果和仿真结果显示这种方法比外信息转移图及全高斯近似都要更精确同时比密度进化的计算量要小提供了一种性能和复杂度的很好的折衷。对于高阶域上的LDPC码介绍了其在无限码长情况下的MonteCarlo仿真原理。同时还提出了集合{,,,}p−上的推广的LDPC码在无限码长情况下的MonteCarlo仿真原理并利用MonteCarlo仿真分析了其性能还给出了集合{,,,}p−上的推广的LDPC码的性能仿真结果。本文的组织结构如下。第二章介绍了LDPC码的原理包括非规则的LDPC码及高阶域上的LDPC码的结构提出了一种集合{,,,}p−上的推广的LDPC码。第三章探讨了LDPC码的有效编码算法及解码算法。对于LDPC码的编码问题介绍了具有半随机校验矩阵的LDPC的线性编码算法提出了集合{,,,}p−上的推广的LDPC码和高阶域环码的线性编码算法。对于LDPC码的解码问题介绍了二元LDPC码的sumproduct解码算法和对数域解码算法及高阶域LDPC码的基于多维FFT的解码算法和对数域解码算法并且提出了集合{,,,}p−上的推广的LDPC码的基于多维FFT的解码算法和对数域解码算法。第四章介绍了LDPC编码的BICM系统和MLC系统结构分析了其接收机及系统容量提出了二元LDPC编码的BICM系统的一种等效模型利用此等效模型可以将接收机输出的编码比特的对数似然率(LLR)信息的分布用混合高斯分布近似以便对系统做半高斯近似分析和设计。第五章介绍了二元LDPC码分析的密度进化原理及利用密度进化进行二元LDPC码设计的方法。第六章介绍了二元LDPC码分析的外信息转移图方法的原理及利用EXIT图技术设计二元非规则LDPC码及LDPC编码的MIMO系统的方法同时还介绍了EXIT图技术的信息论基础信息合并(informationcombining)的界最后给出了一些对称和非对称的PSK星座图和QAM星座图的EXIT曲线。第七章介绍了二元LDPC码分析的高斯近似算法的原理包括全高斯近似和半高斯近似算法提出了利用半高斯近似算法设计二元LDPC编码的BICM系统的方法并利用此方法设计了用于PSK调制的BICM系统的多个码率的LDPC码对所设计的码字做了性能仿真设计结果及仿真结果显示这种方法比外信息转移图及全高斯近似都要更精确同时比密度进化的计算量要小提供了一种性能和复杂度的很好的折衷。第八章介绍了高阶域LDPC码在无限码长情况下的蒙特卡罗仿真原理提出了集合{,,,}p−上的推广的LDPC码在无限码长情况下的蒙特卡罗仿真原理还给出了集合{,,,}p−上的推广的LDPC码的一些性能仿真结果通过分析无限码长下的MonteCarlo仿真结果及其性能仿真结果发现集合{,,,}p−上的推广的LDPC码具有优异的性能。第九章对全文作了总结并给出了一些未来可能的研究方向。中国科学技术大学博士论文第章低密度校验编码第页共页第章低密度校验编码§二元LDPC码低密度校验(LDPC)码最早由Gallager于年提出。但是并没有引起人们的关注直到年Mackay和Neal重新发现LDPC码在迭代译码时具有非常优越的性能越来越多的人开始研究LDPC码。从Gallager提出LDPC码到Mackay和Neal重新发现其优越性能这三十多年间只有少数几篇文章对其做了研究。其中Tanner推广了Gallager的构造方法给出了用二分图和短码迭代构造长码的方法并且还给出了其迭代译码算法Wiberg在其博士论文中推广了Tanner的思想发展了基于图形构造的码字的一般性迭代解码算法最小和(minsum)和和积(sumproduct)解码算法指出Viterbi算法Tanner算法`B’是minsum算法的特例forwardbackward算法Turbo码解码算法及Gallager解码算法都是sumproduct算法的特例。Luby等人发现非规则(irregular)的LDPC码具有非常优越的性能。Davey和Mackay考察了高阶域GF(p)上的LDPC码发现非规则的高阶域LDPC码的性能可以与已知的最优Turbo码相比。低密度校验码(LDPC)是一类线性分组纠错码。线性码^可以用生成矩阵G描述每一个消息s被映射成传输块即码字x。线性码也可以用其校验矩阵H等价描述所有的码字∈x^满足=Hx。对于一个尺寸为mn×的校验矩阵H而言其密度(density)定义为矩阵中非零元素的比例。顾名思义低密度校验码是指一类具有低密度的校验矩阵的线性码即校验矩阵H的大部分元素为零。低密度校验码最早由Gallager提出。Gallager定义了一类具有参数(,,)njkj≥的LDPC码这类码的码长为n校验矩阵H的每列有j个非零元素每行有k个非零元素。图给出了Gallager构造的一个(,,)的校验矩阵。这类码字是正则(regular)的。显然有mnkj⋅=⋅。如果校验矩阵的每行都是线性独立的那么码字的码率为()kjk−否则的话码率应该为'(nm)n−其中'm是校验矩阵H的行空间的维数。图低密度校验矩阵示例n=j=k=。在Gallager的定义中整个校验矩阵被分成j个子矩阵每个子矩阵每列恰好有一个非零元素最上面的子矩阵中非零元素是按照递减的顺序排放的下面两个子矩阵是最上面的子矩阵经过列置换得到的。通过考虑所有经过这样一种列置换作用得到的具有参数为(n,,)jk的校验矩阵的码字全体Gallager证明了几个非常重要的结论。假定码率和j≥给定在足够低的噪声水平及足够长的码长情况下最优解码器的错误概率呈指数减少同时在码率和j≥给定时码字的最小Hamming中国科学技术大学博士论文第章低密度校验编码第页共页距离随着码长呈线性增长。同时在参考文献中Gallager还考察了j=情况下码字的Hamming距离给出任一码字(n,,)k的最小Hamming距离随着码长至多呈对数增长的论断。假设矩阵H的尺寸是mn×对于二元域而言H的元素要么是要么是。如果H的元素i,jH为表示码字符号jx参与了第i行的校验方程。假设,ijH,ijH,ijH是第i行的三个非零元素那么第i行的校验方程为jjjxxx=()Gallager最初定义的LDPC码是正则(regular)的即其校验矩阵H的每行的重量是一样的每列的重量也是一样的。后来Luby等人发现非规则(irregular)的LDPC码有比规则的LDPC码更优越的纠错性能。参考文献中用分布对(,)λρ来描述非规则LDPC码其中,max():vdiiixxλλ−==∑(),max():cdiiixxρρ−==∑()iλ(iρ)代表与度为i的符号(限制)节点相连的边的比例,maxvd(,maxcd)代表最大的符号(限制)节点度。显然有()λ=和()ρ=。比如对于(,)正则的LDPC码有():xxλ=和():xxρ=。如果用,via(,cia)表示度为i的符号(限制)节点的比例。那么有,()()iivixdxaλλ=∫(),()()iicixdxaρρ=∫()反过来有,max,,()vviidvjjiajaλ=⋅=⋅∑(),max,,()cciidcjjiajaρ=⋅=⋅∑()码字的设计码率(designrate)为()()()()(,):xdxNMNxdxrρλλρ−∫==−∫()LDPC码的Tanner图Tanner推广了Gallager的构造方法并且介绍了一种二分图表示法这种表示方法后来被称为码字的Tanner图表示。在码字的Tanner图表示中有两种节点符号节点和限制节点。图中仅存在连接符号节点和限制节点的边。每个符号节点代表一个码字符号每个限制节点代表一个限制条件限制条件由所对应的子码结构定义。一般来说还要指定与限制节点相连的各个符号节点的顺序。图给出了一个(,)正则的二元LDPC码的Tanner图。通过Tanner图表示可以分析LDPC码的性能与其Tanner图的参数如直径(diameter)、周长(girth)及扩展系数(expansioncoefficient)间的关系,。周中国科学技术大学博士论文第章低密度校验编码第页共页长定义为图中最小环(cycle)的长度。在具体构造LDPC码的结构时应该尽量避免短的环的出现尤其是长度为的环。图一个(,)正则的LDPC码的Tanner图。§高阶域上的LDPC码Davey和Mackay首先考察了高阶域GF(p)上的LDPC码发现非规则的高阶域LDPC码的性能可以与最优的Turbo码相比。与二元域上的LDPC码不同的是校验矩阵H的非零元素可以取值域GF(p)里的任一非零元素。相应的校验方程变为i,jjj,i,,,mHx==∑()高阶域上的环码环码(cyclecode)是指具有参数(n,,)k的LDPC码。由于二元域上的环码的最小Hamming距离随着码长至多呈对数增长其性能并不好二元LDPC码的研究的热点主要集中在j≥的情况。但是最近参考文献从理论上证明了随着域指数p的增大高阶域GF(p)上的环码具有接近Shannon极限的性能。参考文献中汇报了一个码长为比特码率为的域GF()上的环码这一码字在bEN为分贝时误块率小于−这一码字甚至优越于度分布优化了的二元非规则LDPC码。本文作者在参考文献中介绍了一种环码的图形表示方法。对于具有尺寸为mn×的校验矩阵H的环码而言其结构可以用一个具有m个点n条边的图形G表示。顶点ic代表由校验矩阵的第i行所定义的限制关系。边jx代表对应于校验矩阵的第j列的码字符号。顶点ic和kc通过边jx相连当且仅当校验矩阵的第j列正好在第i行和第k行有两个非零元素。用符号(,)EGCH来表示高阶域GF(p)上的具有校验矩阵H和图形表示G的环码。假设一个GF()上的环码的校验矩阵为中国科学技术大学博士论文第章低密度校验编码第页共页=H⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦()则其对应的图形表示如图所示。图与H关联的图。假设C是图G的一个环用符号CH来表示校验矩阵H的子矩阵其行和列分别由环C的顶点和边决定称CH为与环C相关联的子矩阵。那么通过简单的行列置换CH可以转化为如式()所示的矩阵−H的形式其中的iα和iβ是域GF(p)里的元素。kkkαββαβαβα−−

用户评价(0)

关闭

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

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

提示

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

文档小程序码

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

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/24

低密度校验(LDPC)编码调制研究

仅供在线阅读

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利