（通信与信息系统专业论文）ldpc编译码的dsp实现.pdf

l d p c 编译码的d s p 实现 中文摘要 l d p c 编译码的d s p 实现 中文摘要 低密度奇偶校验码( l d p c ，l o wd e n s i t yp a r i t yc o d e s ) 是一种能逼近s h a n n o n 容 量限的渐进好码，在长码时其性能甚至超越t u r b o 码。l d p c 码的译码采用的是基 于置信传播的软输出迭代译码算法，复杂度低，是一种次优的译码算法。由于低密 度奇偶校验码具有诸多优点，它在信息可靠传输中的良好应用前景已经引起学术界 和i t 业界的高度重视，成为当今信道编码领域最受瞩目的研究热点之一，低密度 奇偶校验码的应用也已经被提到日程上。 本文对l d p c 码的研究以及创新成果主要体现在对译码算法的改进与编译码算 法的硬件实现两方面。 文章首先论述了l d p c 码的基本原理，在理解l d p c 码基本编译码理论的基础 上，深入分析了l d p c 码简化译码算法的实现原理及性能表现，进而提出一种新的 归一化最小和译码算法。对各种算法译码性能的仿真结果表明，对于中短长度的规 则l d p c 码，本文提出的改进算法，在增加很小计算复杂度与译码迭代次数的前提 下，可获得好于经典l l rb p 译码算法的性能。 其次，根据实际应用需求，有别于以往采用的f p g a + d s p 的l d p c 码编译码 实现方法，本文提出并实现了集l d p c 码编码与译码功能为一体的基于d s p 的 l d p c 编译码器，从而降低系统硬件成本。针对实现过程中遇到的问题，文章给出 了有效的数值存储方法、矩阵运算方法以及编程技巧，并对优化后的结果进行了分 析。 最后，开发了基于l a b w i n d o w s c v i 的l d p c 编译码器测试平台，该平台为用 户提供简洁清晰的人机交互界面，具有串口参数设置、信源产生、信道模拟、编译 码进度、结果分析及显示等功能，其与l d p c 编译码器相结合，完整地实现了l d p c 编译码系统。 关键词：l d p c 码，译码算法，d s p ，优化，测试平台 作者：陈蓉 指导教师：汪一鸣 t h ei m p l e m e n t a t i o no f e n c o d i n ga n dd e c o d i n gs y s t e mo f l d p cc o d e sb a s e do nd s pa b s t r a e t t h e i m p l e m e n t a t i o no fe n c o d i n ga n dd e c o d i n gs y s t e m o fl d p cc o d e sb a s e do nd s p a b s t r a c t l o wd e n s i t yp a r i t yc h e c k ( l d p c ) c o d e sa r eac l a s so fc a p a c i t ya p p r o a c h i n ge r r o r c o r r e c t i n gc o d e so fw h i c ht h ed e c o d i n gp e r f o r m a n c ec a ng e tn e a rs h a n n o nl i m i t f o r l o n gc o d el e n g t h , l d p cc o d e sc a ne v e no u t p e r f o r mt u r b oc o d e s b a s e do nb e l i e f p r o p a g a t i o n ，t h ec o m p l e x i t yo fd e c o d i n ga l g o r i t h m si sv e r yl o w d u et ot h e s ea d v a n t a g e s ， t h ea p p l i c a t i o no fl d p cc o d e si nr e l i a b l ec o m m u n i c a t i o nh a v er e c e i v e dg r e a ti n t e r e s t a n dh a v eb e c o m eo n eo ft h em o s ta t t r a c t i v ef i e l d si nc h a n n e lc o d i n gc o m m u n i t y n o wt h e a p p l i c a t i o no fl d p c c o d e sh a sb e e np u to nt h ea g e n d a t h ec r e a t i v ew o r ko ft h i s p a p e ri sm a i n l ym a n i f e s t e d i nt w oa s p e c t s ：t h e i m p r o v e m e n to fd e c o d i n ga l g o r i t h ma n dt h ei m p l e m e n t a t i o no fe n c o d i n ga n dd e c o d i n g s y s t e mo fl d p cc o d e s b a s e do nd s e f i r s to fa l l ，t h i sp a p e ri n t r o d u c e st h eb a s i cp r i n c i p l e so fl d p cc o d e sa n dv a r i o u s s i m p l i f i e dd e c o d i n ga l g o r i t h m sa r et h o r o u g h l ya n a l y z e da n dc o m p a r e d o nt h i sb a s i s ，t h e p a p e ri n n o v a t i v e l yp r o p o s e dan e wd e c o d i n ga l g o r i t h mc a l l e dm - n m s ( m o d i f i e d n o r m a l i z e dm i n s u m ) f o rs h o r tr e g u l a rl d p cc o d e s ，s i m u l a t i o nr e s u l t ss h o wt h a tt h e i m p r o v e da l g o r i t h mo u t p e r f o r m st h el l rb pa l g o r i t h mw i t ho n l yam o d e s ti n c r e a s ei n c o m p u t a t i o nc o m p l e x i t y a c c o r d i n gt ot h ea p p l i c a t i o nr e q u i r e m e n t ，t h i sp a p e ri m p l e m e n t sb o t ht h ee n c o d i n g a n dd e c o d i n gs y s t e mo nd s pr a t h e rt h a nd s pc o m b i n e dw i t hf p g a ，w h i c hm e a n st h e r e d u c t i o no fs y s t e mc o s t t or e a l i z et h es y s t e m ，e f f i c i e n tm e t h o d so fp a r a m e t e r s s t o r a g e a n dm a t r i xo p e r a t i o n sa r ep u tf o r w a r d f u r t h e r m o r e ，t h er e s u l t so fo p t i m i z a t i o no ft h e p r o g r a ma r ep r e s e n t e da n da n a l y z e d f i n a l l y , ap c b a s e dt e s tp l a t f o r mi sd e s i g n e du s i n gl a b w i n d o w s c v io fa m e r i c a n n a t i o n a li n s t r u m e n tc o m p a n ya st h es o f t w a r ed e v e l o p m e n tt 0 0 1 o f f e r i n gaf r i e n d l y h u m a n c o m p u t e ri n t e r f a c e ，t h et e s tp l a t f o r mh a sav a r i e t yo ff u n c t i o n s ，s u c ha ss e t t i n gt h e t h ei m p l e m e n t a t i o no f e n c o d i n ga n dd e c o d i n gs y s t e mo f l d p cc o d e sb a s e do nd s p a b s t r a c t p a r a m e t e r so fs e r i a lc o m m u n i c a t i o n ，g e n e r a t i n gd a t at ob ee n c o d i n g ，a d d i n gn o i s e ， a n a l y z i n ga n dd i s p l a y i n gr e s u l t sa n ds oo n t h u st h ew h o l ee n c o d i n ga n dd e c o d i n g s y s t e mo fl d p cc o d e si sa c c o m p l i s h e d k e y w o r d s ：l d p cc o d e s ，d e c o d i n ga l g o r i t h m ，d s p , o p t i m i z a t i o n , t e s tp l a t f o r m i i i w r i t t e nb yc h e nr o n g s u p e r v i s e db yw a n gy i m i n g 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体己经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名： 留盔日期：生! # ：出 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：臣墨 日期：之耸：! ：兰亟 导师签名：i 圭煎日期：壑竺孥：兰 l d p c 编解码的d s p 实现第一章绪论 1 1 数字通信与信道编码 第一章绪论 通信系统旨在将信息由信源高效、可靠、有时还需安全地传送到信宿。有扰通 信信道的噪声会对传输信息产生干扰，从而可能降低通信可靠性。所以，通信系统 设计的中心问题是在随机噪声干扰下如何有效而可靠地传输信息。一般地，通信系 统的可靠性用错误比特率( b e r ) 衡量，有效性用传输速率r 比特信道符号衡量。早 期，人们普遍认为：通信系统的可靠性与有效性是一对不可调和的矛盾，在有扰通 信信道上实现任意小错误概率的信息传输的唯一途径就是把传输速率降低至零【l 】。 s h a n n o n 信息和编码理论的奠基性论文“通信的数学理论1 2 1 于1 9 4 8 年发表之后， 改变了这一观念。他首次阐明了在有扰信道中实现可靠通信的方法，指出实现有效 而可靠地传输信息的途径是编码。在这篇论文中s h a n n o n 证明了数据压缩和传输的 基本定律从而奠定了信息理论的基石，s h a n n o n 也因此被称为“信息论之父 。根据 s h a n n o n 的信息理论，数字通信系统的基本组成如图1 1 所示【3 1 。 i j 编码信道 图1 - 1 数字通信系统模型 一般的通信系统均可以用图1 1 来表示( 如果将存储介质看成信道的话，存储 系统也可以用上述模型表示，这时数字调制解调器分别对应于写入写出单元) 。如 图1 1 所示，发送端包含四个模块：信源、信源编码、信道编码和数字调制器。信 源编码就是用二进制( 或多进制) 序列来表示信源输出的过程，其目的是除去信源 l d p c 编解码的d s p 实现第一章绪论 的冗余以减少通信负担，因而也称为数据压缩。任何信源都有一个被称为信源熵的 量，它表征了信源的平均不确定程度。信源编码定理【4 】指出信源熵是数据压缩的下 界；信道编码与信源编码正相反，它通过在信息序列中引入冗余来实现通信的可靠 性，任何信道都存在一个被称为信道容量的值，它表征了信道的传输能力；数字调 制就是将信息序列映射成适合信道传输的信号的过程。对应地在接收端也有相应的 四个模块用于实现相反的过程。 由于噪声是影响通信可靠性的关键因素，一个自然的想法是构建可靠的信道以 减少噪声。但是这种想法在很多情况下是无法实现的，而且也没有必要。r e b l a h u t 曾指出“与其花费大量的金钱去建造一条好的通信信道不如采用信道编码! i s 】。因 此，从通信系统的经济性角度考虑信道编码也是必不可少的。 综上所述，信道编码是解决通信有效性和可靠性这对矛盾的关键，也是实现通 信系统经济性所必需的。但是，s h a n n o n 在【2 】中关于信道编码定理的证明是存在性 的，因而如何在实际系统中实现信道编码仍然是一个难题。 定理1 1 ( 信道编码定理) 6 j 任意离散输入无记忆平稳有噪信道都有一个被称为信道容量的值c ，它标志着 信道传输能力的上限，只要信息传输速率r c ，就存在一种编码方式，当平均码 长足够大时，译码错误概率可以做到任意小；反之，则无论采用何种编码方式也不 可能保证错误概率任意小。， 信道编码定理和信源编码定理、率失真理论一起构成了s h a n n o n 三大编码定理。 s h a n n o n 在证明上述信道编码定理时采用了三种技术： 1 ) 编码采用了随机编码思想； 2 ) 让码长趋于无穷； 3 ) 译码采用了最大似然译码。 一般可将信道编译码器所使用的纠错码从性能上分为坏码和好码。所谓坏码是 指只有将码率降至零才能使误码率为任意小的编码方式：而好码又可以分为当误码 率任意小时，码率逼近信道容量限的非常好码和码率可达到的非零最大值小于信道 容量限的一般好码。虽然s h a n n o n 指出一个随机选择的码以很高的概率为好码，但 随机码的最大似然译码复杂度往往与码长呈指数关系，即在误码率随码长趋于无穷 2 l d p c 编解码的d s p 实现第一章绪论 而趋向于零的同时，译码复杂度以指数增长，因而尽管一般的随机码是好码，但不 能看作是实用码。 自信道编码定理提出以来，人们一直致力于构造纠错能力接近理论极限，编译 码复杂度可接收的信道编码。大致的发展过程可以分为以下几个阶段【7 】： 2 0 世纪5 0 年代至6 0 年代，主要研究各种有效的编译码方法，如纠单个错误的 h a m m i n g 码、g o l a y 码、r e e d m u l l e r 码以及著名的b c h 码编译码方法，奠定了线 性分组码的理论基础。 6 0 至7 0 年代初是信道编码发展过程中最为活跃的时期。不仅提出了许多有效 的编译码方法，如门限译码、迭代译码、软判决译码、卷积码的v i t e r b i 码等。而且 还研究了信道编码的实用化问题，如码的重量分布、译码错误概率和信道模型等， 为信道编码的实用化打下了坚实的基础。期间，f o m e y 提出了较为实用的串行级联 码，它在译码复杂度没有明显增加的情况下，性能得到较大改善。 7 0 年代初至8 0 年代是纠错码发展史中具有极其重要意义的时期。在理论上以 g o p p a 为首的一批学者，构造了一类线性循环码川o p p a 码，其中一类子码能达 到s h a n n o n 信道编码理论中所指出的性能。而且，在这期间，大规模集成电路和微 机的迅速发展，为纠错码的实用打下了坚实的基础。 自8 0 年代初以来，g o p p a 等人从几何观点讨论分析码，利用代数曲线构造了 一类代数几何码。代数几何码是一类范围非常广的码，在理论上已经证明它具有优 越的性能。 进入9 0 年代，t u r b o 码【8 】【9 】的出现掀起人们对伪随机编码和软输入软输出迭代 译码算法的研究高潮，出现了一系列利用迭代译码的编码方式，如l d p c 码、乘积 码等，这些码都可以达到接近s h a n n o n 极限的优异性能。 1 2l d p c 码的提出和发展状况 l d p c ( l o wd e n s i t yp a r i t yc h e c k ) 码最初由g a l l a g e r l l o 】【1 1 1 在上个世纪六十年代 初发现，但是限于当时的计算水平和人们对这种形式非常简单的码的认识不足，数 年来它一直遭受冷遇，这期间只有r m i c h a e lt a n n e r 等对它进行了零星的研究，且 几乎没有实质性的进展。而自从l d p c 码被m a c k a y 和n e a l 等人重新发现之后， 其优越的性能【1 2 】【1 3 】j 艮快引起研究人员的重视，l d p c 码迅速成为人们研究的焦点。 l d p c 编解码的d s p 实现 第一章绪论 经过多年的研究和发展，人们在各方面都取得了突破性的进展，l d p c 码的相关技 术也日趋成熟，并且已经开始有了商业化的应用成果。 l d p c 码的研究与进展大体包括以下几个方面： 1 l d p c 码结构及其优化 因为l d p c 码是一种线性分组码，它的码结构可由校验矩阵确定，所以所谓码 结构设计也就是校验矩阵的构造。 按照校验矩阵的行和列是否都具有固定个数的非零元素可将l d p c 码分为规则 码和非规则码。另一种分类方法是将它分为二元域和多元域上的l d p c 码。 m g l u b y 等指出，非规则l d p c 码的性能优于相应的规则l d p c 码【1 4 】【1 5 1 。而 m c d a v e y 等的研究表明多元域上的l d p c 码的性能较二元域上g a l l g a e r 码的性能 有较大提高，且域的阶数越高，编码的性能越好。 目前有关l d p c 码的构造方法有很多，主要分为两类：随机构造和结构化构造 方法。随机l d p c 码的构造是基于某种设计规则或需要的码。长的随机l d p c 码具 有逼近香农限的能力，但是，随机码通常编码复杂。结构化构造方法又可以分为代 数构造方法和组合方法。代数方法中包括基于有限几何的构造方法和基于循环置换 矩阵的方法。结构化构造的l d p c 码可以保证中长码和短码具有好的距离特性。 2 l d p c 码的译码研究和性能分析 在l d p c 码译码算法的研究方面，g a l l a g e r 最早提出了二元离散信道下概率译 码算法。m a c k a y 基于连续信道和软判决译码提出的和积( s u mp r o d u c t ) 译码算法，在 文献 1 6 1 中被称之为置信传播( b p - b e l i e f p r o p a g a t i o n ) 算法，该算法实质上是g a l l a g e r 概率译码算法的对数域实现。b p 算法译码性能好但硬件实现复杂度高，为了达到 算法复杂度和译码性能的最佳折中，先后提出了各种简化算法。 随着l d p c 码的逐步实用化，人们对译码算法的性能分析也作了大量的研究。 当码长无穷长，不存在短环路的条件下，针对不同的信道和不同的译码算法，采用 高斯近似、密度进化和e x i t 等分析方法，能精确的分析出l d p c 码的理论极限 【1 7 】- 【2 2 1 。当码长为有限长时，可对二进制删除信道和a w g n ( a d d i t i v ew 1 1 i t eg a u s s i a n n o i s e ) 信道下的性能进行分析。 3 l d p c 码的应用 4 l d p c 编解码的d s p 实现 第一章绪论 虽然t u r b o 码在3 g 通信标准中获得了主导地位，但是与t u r b o 码相比，l d p c 码有3 个明显的优势。首先，l d p c 码具有套较为系统的优化设计方法、更强大 的纠错能力和更低的地板效应。其次，由于l d p c 码迭代译码算法为并行算法，可 实现完全并行的操作，便于硬件实现，延时远远小于t u r b o 码的串行迭代译码算法。 第三，l d p c 码本身即有抗突发错误的特性，不需要引入交织器，避免了可能带来 的时延。这些优点使得l d p c 码在信道条件较差的无线移动通信中展现出了巨大的 应用前景，非常适合于在未来的移动通信系统中应用。现在许多正在拟订的通信标 准都更多的关注了l d p c 码，例如卫星通信标准d v b s 2 已经采纳l d p c 码作为前 向纠错码。此外，l d p c 码在一些实际系统中也得到了应用。v o c a lt e c h n o l o g i e sl t d 推出了一种用于w l a n 的l d p c 脯0 不对称解决方案，采用该方案后用于i e e e 8 0 2 1 l a b g w l a n 移动终端的电池寿命可延长至原来的4 倍【2 3 1 。原f l a r i o n 公司推 出的f l a s h o f d m 移动无线芯片组采用l d p c 码作为纠错方案，可用于基于口的 移动宽带网，大大增加了传输距离，增强了对无线信道环境的抵抗能力【2 4 1 。相信 l d p c 码将在光纤通信、卫星数字视频和声频广播、磁光全息存储、移动和固定无 线通信、电缆调制解调器和数字用户环线( d s l ) 中得到广泛应用。 1 3 课题意义及主要工作 随着l d p c 码研究的不断深入及其成功成为新一代数字卫星广播( d v b s 2 ) 等 标准的信道编码方案，l d p c 码具有越来越重要的应用价值，l d p c 码编译码器的 设计实现也成为近年来研究的热剧2 5 】。 目前，l d p c 码编码器多采用现场可编程门阵列f p g a ( f i e l dp r o g r a m m a b l eg a t e a r r a y ) 实现，这主要是由于编码时涉及大量矩阵运算，复杂度高，人们希望通过硬 件电路设计来实现并行处理。而l d p c 码译码器的实现方法则存在两种：一种是采 用f p g a ：另一种是基于数字信号处理器( d i g i t a ls i g n a lp r o c e s s o r , d s p ) 等指令串行 执行系统【2 6 1 。而实际应用中，信息的发送与接收多为双向，因此，信道的终端需同 时具备信道编码与译码功能。鉴于d s p 系统具有运算能力强，速度快，体积小，采 用软件编程灵活度高等优点，我们希望通过对l d p c 码编码程序进行合理设计，充 分利用d s p 的流水功能，提高编码效率，最终设计出集l d p c 码编码与译码功能 为一体的基于d s p 的l d p c 编译码器。 l d p c 编解码的d s p 实现 第一章绪论 本课题正是以此为研究背景，提出并实现了基于a d s p b f 5 3 7 的l d p c 编译码 系统。论文的主要工作有：首先，在研究分析l d p c 码多种译码算法实现原理与性 能的基础上对最小和译码算法做出改进，并通过仿真比较给出改进后算法的译码特 性。其次，针对d s p 处理器的特点，研究了l d p c 码编译码算法在a d s p b f 5 3 7 e z k i tl i t e 开发板上的实现与优化。最后，开发了基于l a b w i n d o w s c v i 的主机 p c 端的应用程序，该程序与l d p c 编译码器相结合，完整地实现了l d p c 编译码 系统。 1 4 论文结构 本论文结构安排如下： 第二章，简述低密度奇偶校验码的基本原理以及l d p c 码的常用编码方法，重 点分析本设计中采用的可实现线性编码复杂度的基于近似下三角形的编码方法。 第三章，较为详细的讨论了l d p c 码的译码算法原理。在研究经典置信传播算 法及各种改进算法的基础上，提出一种改进的l d p c 最小和译码算法，并就各种算 法的性能与复杂度之间的关系，进行了多角度的分析比较。 第四章，首先介绍本设计中使用的硬件开发平台a d s p b f 5 3 7e z k i tl i t e 板。 给出了l d p c 编译码器的系统软件框架以及系统初始化模块与通信模块的设计思路 与实现方法。随后针对d s p 中编译码实现所面临的问题，提出了新的数值存储方法、 矩阵运算方法以及编程技巧，并对优化后的结果进行了分析。在实现编译码功能的 基础上，对系统中采用的通信方式叫s 一2 3 2 串口进行了设计研究，实现了波特 率自适应功能。 第五章，较为详细的阐述了基于d s p 的l d p c 码编译码器测试平台的设计和 关键模块的功能。给出了基于l a b w i n d o w s c v i 的主机p c 端应用程序的开发过程 及最终实现效果。 第六章总结论文，阐述创新点并提出进一步研究的方向。 6 u ) p c 编解码的d s p 实现第二章u ) p c 基本原理及编码算法 第二章l d p c 码基本原理及编码算法 2 。1l d p o 码基本原理 l d p c 码是一类可以用非常稀疏的矩阵或者二分图定义的线性分组码，最初由 g a l l a g e r 发现，但由于当时技术条件的限制，l d p c 码一度为人们所忽略。随着计 算机能力的增强和相关理论( 如图论，b e l i e f 传播，t u r b o 码等) 的发展，m a c k e y 和n e a l 重新发现了它，并证明l d p c 码在应用迭代译码置信传播算法的情况下具 有非常好的接近于香农限的性能，且当码长足够长时其性能可超越t u r b o 码，这激 起了编码界对l d p c 码的研究热情，成为继t u r b o 码之后纠错码领域掀起的又研 究热潮。 2 1 1 线性分组码 人们通常在有限域上讨论码构造，具有g 个元素的有限域通常称为伽罗华 ( g a l o i s ) 域，用凹( 日) 或者表示。最简单的域是只有一个零元素和一个单位元 的二元域凹( 2 ) 。一个( y l , k ) 的线性分组码是将k 位的信息序列u = ( 1 a ) 映射成 ，2 长的码字c = ( c o c n 一1 ) ，其中校验元个数为m = n - k 。设c f 、c ，是某( 玎，七) 分组 码的任意两个码字，a l 、a 2 是码元字符集中的元素，那么当且仅当g i c f + a 2 c _ ，也是 码字时，这个码称为线性码。以下讨论的分组码是建立在g f ( 2 ) 上的二进制线性分 组码。 行向量 c o ，c 1 ，c 川】的所有组合实际上构成了一个g f ( 2 ) 上的以维向量空间 s ，其中的元素共有2 一个。而信息序列共有2 毒种组合，对应的码字也只能有2 蠢个 ( 称为许用码字) ，这些码字构成空间s 的一个k 维子空间c 。那么c 就可以由k 个 线性无关的刀维向量g o ，g 组成。g o ，g 是c 的一组基底。某一码字和其对 应的信息序列u 的关系可以表示为：c = ”o g o + + “k - l g 露一l 。 写成矩阵形式即： 7 l d p c 编解码的d s p 实现第二章l d p c 基本原理及编码算法 g 谢g ： ( 2 。) l g 七一。j g 矩阵称为生成矩阵，秩为k ，经过有限的行运算和列置换后，该矩阵可转化 成系统形式g = 【iip 】，其中i 为k k 的单位矩阵，p 是kx ( 九一k ) 维矩阵。这时， 生成的码字前k 位与信息元对应，余下的加一k ) 位比特即为校验元。 对应每一个k 的生成矩阵g ，存在一个0 一k ) n 的矩阵h ，g 的行和h 的 行正交，即g h t = 0 ，称h 为校验矩阵。易证得码字和校验矩阵满足以下关系： c h t = 0 或者h e t ：0 。 一个码字中非零元素的个数称为码重，任意两个码字之间对应位置上不同的元 素个数称为汉明距离。两个码字之间的汉明距离表示它们的差别或相似程度。距离 越大，则从一个码字变成另一个码字的可能性越小。因此，最小距离与纠错能力直 接相关，应尽量使码字间最小距离最大。 由于线性分组码中两个码字之和( 和与差在二进制运算下等价) 也是一个码字， 因此求两个码字之间的距离即是求它们的和所形成码字的重量。码字间的最小距离 也就是码字集合中非全零码字的最小重量。可见一个线性分组码的重量分布完全决 定了该码的距离分布。 2 1 2l d p c 码的定义及二分图表示 l d p c 码可以由它的校验矩阵h 来定义，h 是一稀疏矩阵，矩阵中除很少一部 分元素为非零元素外，其它大部分的元素都是零即所谓的“低密度 。 l d p c 码也可以用二分图( 也称t a n n e r 图) 来表示。二分图和校验矩阵h 是直接 对应的，由比特节点( 也可称为变量节点) 、校验节点和连接它们的边组成。每个校 验节点q 对应于h 的一行，每个比特节点v 对应于h 的- n 。当码字中某一比特包 含在某一校验方程中，即校验矩阵中相应位为1 时，校验节点和比特节点间存在连 线，我们将这条边称为相邻边，相邻边两端的节点称为相邻点。每个节点的相邻边 条数称为该节点的度数( d e g r e e ) 。 8 l d p c 编解码的d s p 实现第二章l d p c 基本原理及编码算法 1 l 1lo l0 o o1 h = lo 0 oo o0 llo o0 o ol0 0l0lol 0 001o ololl v ov lv 2v 3v 4v 5v 6v 7v 8v 9 c o c l c 2 c 3 c 4 图2 1 ( 1 0 ，2 ，4 ) 规则l d p c 码的奇偶校验矩阵和二分图 图2 - 1 所示是一个二元域上的l d p c 码，其校验矩阵每一列有盛( = 2 ) 个非零元 素，每一行有d c ( = 4 ) 个非零元素，或、以分别表示与比特节点和校验节点相连的 边数。当其为常数，即所有比特节点的度数一样、所有校验节点的度数也都相同时， 这样的l d p c 码称为规则( r e g u l 砷l d p c 码，简称规则码，表示为( 或，以) ，其中万 为码长。规则码的码率计算公式为： r ：1 一旦：1 一立 玎d 。 ( 2 - 2 ) 当二分图中的比特节点的度数不尽相同( 校验节点的度数也有相应变动) 时， 这样的l d p c 码称为非规贝j j ( i r r e g u l a r ) l d p c 码，简称非规则码。非规则码通常用度 数分布对( d e g r e ed i s t r i b u t i o np a i t ) ( 五，p ) 来描述： p ( x ) = 艺- p i x 一1 ， 1 = 2 ( 2 - 3 ) 上式分别为比特节点和校验节点的度数分布多项式；丑( 肛) 表示与度数为i 的 比特( 校验) 节点相连的边数在总边数中所占的比例；d ，( 以) 表示比特( 校验) 节 点中的最大度数。非规则码的码率计算公式为： 心一器 【五( x ) 出 ( 2 4 ) 由于非规则码中节点度数分布的不均匀，度数高的比特节点受到较多的校验约 束的监督，将较快地被正确译码。同时，它们又将给其它度数较低的节点提供更可 9 卜 x2 西m = 、， x ，l 允 l d p c 编解码的d s p 实现第二章l d p c 基本原理及编码算法 靠的译码信息。这就是所谓的“波浪效应( w a v ee f f e c t ) ”。 2 1 3l d p c 码校验矩阵的构造 l d p c 码是一种随机码，没有特定的生成多项式和校验多项式。描述该码的参 数为码长和稀疏校验矩阵中比特节点和校验节点的度数分布。构造方法是根据通信 系统中要求的码长和码率来确定校验矩阵的维数，然后通过线性编程工具等获得性 能优异的度数分布表达式。最后根据优异的度数分布填充非零元素的位置。目前已 有多项技术来具体构造校验矩阵，主要分为代数构造和随机构造两类。代数构造方 法的优点是能够给出所需校验矩阵的结构并有效避免短环路的存在，但是由于代数 构造方法受限于特定代数结构的特性，无法构造出任意码率的校验矩阵。而随机构 造方法虽然能构造出理论上的好码，但由于校验矩阵的随机性，在编译码电路实现 上复杂度过高。 2 2l d p c 码通用编码方法 l d p c 码的难点在于它的编码方法，本节主要讨论随机构造l d p c 码的几种通 用编码方法。 2 2 1 线性分组码通用编码方法 设m ，z 的校验矩阵h 的所有行都是线性无关的。根据分组码定义，对于输入 信源u ，u f 舻用，编码后得到码字c ，c f 打，满足方程：h e t = 0 。 为了在接收端易于区分信息位和校验位，通常采用系统码。但是，对于任意一 个随机构造的校验矩阵h ，它不具有系统码的形式，因此首先需要对给定的校验矩 阵h 进行列变换，分解成【ab 】的形式，其中a 为mx ( n 一所) 维的矩阵，b 为mxm 维的满秩矩阵，则码字c = 【uip 满足 a i b 悱o ( 2 - 5 ) l p j 则a u + b p = 0 ( 2 6 ) 因此得到校验位 p = 一b 叫a u ( 2 7 ) 1 0 l d p c 编解码的d s p 实现 第二章l d p c 基本原理及编码算法 该方法的计算复杂度表现在计算b a ，大约为o ( m 3 ) 。但是，若在实际的通 信系统中采用相同的校验矩阵，则b - 1 a 可通过预计算并存储，其计算复杂度为 o ( m ( n 一所) ) 。 2 2 2 高斯消去法 通过高斯消元将校验矩阵转化为如图2 2 所示的下三角形式，将码字c 划分为 系统部分s ，s f 舻州和校验部分p ，p f 研，即c = ( s , p ) 。如下构造系统编码器： 1 ) 将甩一m 维信源符号作为s ； 2 ) 用回代法确定m 个校验符号，即对于，【m 】，计算： 刀一所1 - l p l = 凰，s _ ，+ zi - i ，- ，卅历p j ( 2 - 8 ) j = l j = l n mm 工宣 n 图2 2 具有下三角形式的校验矩阵 在高斯消去法中，将校验矩阵h 转化为图2 2 所示形式的计算复杂度为o ( n 3 ) ， 实际的编码复杂度为o ( n 2 ) ，另外在经过高斯消元后h 不再稀疏，将加大译码时的 复杂度。 2 2 3 准下三角形校验矩阵编码算法 准下三角形校验矩阵编码算法是由r i c h a r s o n 和u n b a n k e 提出的【2 7 k t g 称, r u 算法) ，该算法充分利用了校验矩阵的稀疏性，可实现线性编码复杂度。r u 算法包 含两个阶段：预处理阶段和实际编码阶段。 步骤1 ：预处理 ( 1 ) 三角化 l d p c 编解码的d s p 实现第二章l d p c 基本原理及编码算法 为了不改变h 矩阵的稀疏特性，仅对h 矩阵的行和列重排，得到如图2 3 所示 准下三角矩阵。 暑工 n 图2 - 3 准下三角形式校验矩阵 将矩阵表示成如下形式 h ：侩n b 三1 ( 3 - 6 ) if d ej 其中a ：( 聊一g ) ( 挖一聊) ；b ：( m g ) g ；t ：( 川一g ) ( ，”一g ) ；f ：gx ( ，z 一，竹) ； d ：g g ；e ：gx ( m g ) 。上述子矩阵都为稀疏阵并f 1 t 为下三角阵，对角线元 素为l 。在三角化过程中，使矩阵间隙g 尽可能小。 ( 2 ) 秩验算 对h 左乘矩阵 o 使其成为右下角为0 的矩阵 f ，a b 西 h t l a + f - e t l b + do j 定义矽= 一e t b + d 。在这里，需要检验= 一e t 一1 b + d 是否非奇异。若是奇 异的，则需进一步执行列交换以消除奇异性。 步骤2 ：编码 定义c = ( s ，p l ，p 2 ) ，其中s 为系统部分( 即信息元) ，p i , p 2 为校验部分，p l 的 长度为g ，p 2 的长度为m g 。根据方程h c 7 = 0 可得： l d p c 编解码的d s p 实现第二章l d p c 基本原理及编码算法 a s 7 + b p j + t p ；= 0 ( 3 7 ) ( - e t 一1 a + f ) s r + ( 一e t b + d ) p i r = 0( 3 8 ) 根据( 3 1 0 ) 式得 p i = 一矽- 1 ( 一e t a + f ) s 7 ( 3 9 ) 因此，一旦矩阵一一1 ( 一e t 一1 a + f ) 己知，只需简单的矩阵相乘运算就能得到p l ， 计算复杂度为o ( g 幸( 甩一，2 ) ) 。如表2 1 所示步骤计算，可以进一步降低复杂度。表 2 1 不预先计算好一矽一1 ( 一e t 一1 a + l i ) 再乘以s r ，而是将整个计算划分为几个小步骤， 以提高计算效率。 表2 - 1p ；= 一矽- i ( 一e t 一1 a + f ) s7 的计算过程 操作步骤注释复杂度 a s 7 乘以稀疏矩阵 o ( n ) t 一1 a s r 】t 一1 a s7 】= y7 营 a s7 】= t y 7 d ( ) 一w t 一1 a s7 】 乘以稀疏矩阵 d ( 胛) f s r 乘以稀疏矩阵 d ( ，2 ) 一e t 一1 a s7 】+ 【f s7 】 加法运算 d ( 力) 一一1 【- e t 一1 a s 7 + f s7 】乘以g xg 矩阵o ( 9 2 ) 根据( 3 - 9 ) 式得 p ；= 一t 一( a s7 + b p l r ) 具体的计算过程如表2 2 所示。 ( 3 一l o ) l d p c 编解码的d s p 实现第二章l d p c 基本原理及编码算法 表2 - 2p ；= 一t - i ( a s7 + a p f ) 的计算过程 操作步骤注释复杂度 a s 7 乘以稀疏矩阵 0 ( 刀) b p j 乘以稀疏矩阵 d ( 玎) a s7 + b p j 加法运算 d ( 羟) 一t 一( a s7 + b p j )一t 一1 ( a s7 + b p i ) = y7 一( a s r + b p f ) = t y 7 d ( 玎) 2 2 4 编码算法的选择 通过以上分析可见，一般的系统编码方法主要存在的缺点是：计算复杂度高； 校验矩阵的稀疏性遭到破坏。而在准下三角形校验矩阵编码方法中，预处理步骤后 所得矩阵仍为稀疏矩阵，这不仅将降低编码时矩阵运算的复杂度，更有利于对矩阵 实现压缩存储，从而降低系统对存储空间的需求。 此外，对于准下三角形校验矩阵编码方法，一个给定的校验矩阵h ，只需进行 一次预处理，因此预处理操作可采用固件方式实现，即直接将预处理操作的结果以 合适的形式存于d s p 中，而实际的编码操作则利用d s p 处理器完成。 综上所述，本文选用准下三角形校验矩阵编码算法，硬件实现时使用的h 矩阵 大小为1 2 5 x2 5 0 ，三角化过程后矩阵间隙g 的值为3 7 。具体编码器的设计，如校验 矩阵如何存储；矩阵运算如何实现等将在第四章中阐述。 2 3 本章小结 在基本线性分组码的概念上引入l d p c 码的概念，对l d p c 码的基本原理和通 用的编码方法进行研究。考虑到用d s p 实现编码的特殊性，专门针对计算复杂度、 校验矩阵的稀疏性以及压缩存储方法等问题，对如何选择编码方法进行了分析，并 详细阐述了本论文采用的准下三角形校验矩阵编码算法。 1 4 l d p c 编解码的d s p 实现 第三章l d p c 码译码算法 第三章l d p o 码译码算法 好的信道编码使得编码后的码字序列具有较强的纠错能力，为有效的抗信道噪 声提供了可能。译码则是将这种可能转化为现实的过程，译码算法的优劣决定了能 否最大程度的发挥编码本身具备的这种纠错潜力。好的译码算法将起到画龙点睛的 作用。尤其是在长码的条件下，译码算法的复杂度决定了工