LDPC编码算法分析和研究

论文题目LDPC编码算法实现与分析学生姓名学生学号专业班级学院名称信息科学与工程学院指导老师学院院长2014年5月19日LDPC编码算法实现与分析摘要低密度奇偶校验码（LowDensityParityCheckCodes）由Gallager在20世纪60年代首次提出，经过30多年的沉寂，最终因为具有逼近Shannon极限以及译码复杂度低等明显优势得到研究者的重视[1]。随着通信领域相关技术的不断发展，加上LDPC码结构灵活，目前已广泛应用于深空通信、光纤通信、卫星数字视频和音频广播等领域。LDPC码已成为第四代通信系统强有力的竞争者。论文旨在研究基于MATLAB的LDPC码的编译性能仿真。主要的环节有：①LDPC码的构造；②LDPC码的相关编码实现；③LDPC码的译码实现。在整个设计及过程中，基于以上主要环节，实现对LDPC码的性能分析，并得出相关结论。在实现编码方面，主要采用的是基于奇偶校验矩阵的编码算法，而译码过程用到的是比特翻转（BitFlipping）译码算法。关键词：LDPC码；校验矩阵；编译码；MATLABImplementationandanalysisofLDPCencodingalgorithmAbstractLDPC(LowDensityParityCheckCodes)wasfirstproposedbyGallagerinthe1960s,after30yearsofsilence,becauseofeventuallyapproachingtheShannonlimitwithdecodingcomplexityandlowobviousadvantages,researcherspaidmoreattention.[1]Withthedevelopmentofcommunicationstechnologies,withflexibleLDPCcodestructure,LDPCcodehasbeenwidelyusedindeepspacecommunications,opticalcommunications,satellitedigitalvideoandaudiobroadcastingandotherfields.LDPCcodehasbecomethefourth-generationcommunicationssystemstrongcompetitor.ThePaperaimstostudytheperformanceofthesimulationbasedonMATLABaboutLDPCcodes.Themainareashavebeenidentified:①LDPCcodesconstruction;②LDPCcodesencoding;③LDPCcodedecoderimplementations.Throughoutthedesignandprocess,achievetheperformanceofLDPCcodeanalysisanddrawrelevantconclusions.Intherealizationofencoding,themainencodingalgorithmusedisbasedontheparitycheckmatrix,andthedecodingprocessusedisbitflip(BitFlipping)decodingalgorithm.Keyword:LDPCcodesParitycheckmatrixEncodinganddecodingMATLAB第Ⅱ页目录1绪论...................................................................11.1课题背景及目的.....................................................11.2国内外研究现状.....................................................11.3论文的组织结构及研究内容...........................................22LDPC码的相关背景知识..................................................42.1线性分组码........................................................42.1.1线性分组码的相关概念..........................................52.1.2线性分组码的性质.............................................52.2纠错码简介.........................................................62.3LDPC码的表示.....................................................62.4LDPC码的构造.....................................................73LDPC码的编码.........................................................103.1直接编码算法......................................................113.2基于校验矩阵的编码算法............................................113.3小结..............................................................154LDPC码的译码.........................................................164.1主要译码算法......................................................164.1.1比特翻转译码算法.............................................174.1.2加权比特翻转译码算法.........................................194.1.3置信传播译码算法.............................................204.2小结..............................................................215LDPC编译码算法仿真平台的实现.........................................21第Ⅱ页5.1LDPC编译码过程..................................................215.2仿真结果展示分析.................................................22总结和展望..............................................................26致谢....................................................................27参考文献................................................................291绪论1.1课题背景及目的自从信道编码理论被提出以来，研究者们就在各个方面做了很多的努力。包括寻找接近香农极限的性能码；包括通过各种手段降低编码和译码的复杂度；也包括提出更具实践意义的信道方案。正因为有了这些成就，才使得后来的研究者有了完善和改进的基础，把信道编码更加广泛地运用到信息领域的各个角落。随着通信领域相关技术的发展，早期的码，例如：BCH码，Turbo码，已经无法完全适应当今的要求。而且信息系统越来越要求有更高的数据速率，加上计算机硬件的不断发展以及相关理论的更新，使得LDPC码在一段时间的停滞不前之后，有了新的发展和突破。不得不说明的是，LDPC码在某些条件下拥有很多已经得到实际应用的良好性能，相对的他的复杂度并不算太高，而且结构又灵活，所以成为了时下第四代移动通信的热门研究点。同时LDPC码在很多领域都得到了良好地应用，比如：在探测未知的深空领域时。这些都给社会的发展带来了深远的影响。所以有理由相信LDPC码在未来的信息领域有巨大的前景。1.2国内外研究现状LDPC码能够取得现在的成就，自然少不了信道编码研究者们的不懈努力。BehairyH和ChangS.C提出了具有并行级联特点的Gallager码（PCGC），就是在Turbo码的编码中用到LDPC码。其方法就是在不适用交织机的情况下实现信息码元的输出，并且经实践得到了良好的效果[2]。YuKou，ShuLin等利用有线集合的代数方法，构造成功LDPC码，借此生成的循环码字可以用相对简单的具有线性反馈位移性质的寄存器进行编码，这一举措极大的简化了复杂性，从而使得到的纠错方面的能力更靠拢香农极限。根据查阅相关资料，当前在最好的情况下，LDPC码字性能与香农极限相比，仅仅相差0.0045dB[3]。M.G.Luby等提出，在非二元有限域中这个情况下，定义码有性能的改进，同样有这种可能的还包括校验矩阵。同时相比基于正则图定义的码，基于非正则定义的码性能更加好。他还提出某种双向图的LDPC码在可擦除信道中有较多的运用，而且可以实现时间复杂度是线性规律的编码和译码。同时D.J.C.Mackay通过对超泊松分布结构的相关性能的验证，发现当相关的矩阵的结构呈现具的是三角形结构时，更能实现快速编码[4]。T.J.Richardson和R.L.Burbanke研究了如何通过确定校验矩阵的稀疏性来得到更高效的编码器，如何是编码时间和码长度更加贴合线性关系增长。T.J.Richardson通过研究非正则图的复杂性来发现更优的非正则码LDPC码。刘水平等将编码器分子若干个子相互串联级联的编码器，从而实现非正则LDPC码的设计。这样做不仅能够保证低密度校验码的特点，实验还表明：这样一来简化了编码算法，而且码结构得到固定，从而实现更好的性能[5]。贺玉成等经过研究提出了一种迭代译码量算法，该算法是基于置信传播。其优势在于：首先，极大降低存储要求；其次，计算复杂度得到改善；最后，算法是呈现对称性特点的，这些优势使得改进后的LDPC码在实际通信中成为现实。由于摊就分析的不断深入，极大地优化了LDPC码的编码复杂性。因此，LDPC码在多个领域得到广泛应用[6]。叶芳等人研究出一种填充算法，该算法是通过构造稀疏的校验形矩阵来实现的。这种算法的优势在于当需要构造高圈长的校验矩阵时，实现起来的复杂度会比较低[7]。彭立等人介绍了一种以某一矩阵为子矩阵，通过对这类矩阵进行合适的排列组合，进而构造出低密度校验矩阵的一种LDPC码编码器的设计方案。Chiani、Myhre和Wadayama等人的主要研究工作是LDPC码在衰落信道中的应用。其中Chiani的主要工作是对有记忆块衰落的信道进行性能估评。Myhre提出了一种编码调制方案，主要是针对慢变化衰落信道的一种LDPC调制方案。Wadayama主要针对可能突发信道的LDPC码进行了研究，并且提出一种模型适用于隐马尔可夫噪声信道[8]。现今研究中，关于LDPC码的改进优化工作，主要往矩阵构造、编码算法改进优化等方面进行。随着LDPC吗的研究深入，其出色的性能，已经得到广泛的关注，并被用于卫星通信，光纤通信，移动通信以及压缩图像输出等总所数字通信领域。1.3论文的组织结构