（通信与信息系统专业论文）dvbs2系统中ldpc译码器的研究与实现.pdf

摘要 手两要 纠错编码是通信系统实现可靠数据传输的一种有效方法。由于微电子技术的 发展，使以前难以实现的复杂译码算法在超大规模芯片中得到实现。低密度校验 码( l o wd e n s i t yp a r i t yc h e c k ，l d p c ) 以逼近s h a n n o n 极限的误码率性能和可 完全并行实现迭代译码的特点，成为纠错码研究的热点，并且被推荐为新一代通 信系统中主要纠错编码方案。本文以北京市嵌入式系统重点实验室的基于d v b - s 2 接收系统芯片设计项目为基础，详细介绍了l d p c 译码器的设计与实现。 本文基于d v b s 2 标准，对接收机的l d p c 译码部分进行研究。主要研究其校 验矩阵的特点，各种译码算法，分析其存储方式，着重于迭代译码的硬件实现。 通过软件平台上的仿真，并编写硬件代码。 本文首先介绍了d v b - s 2 系统以及标准中l d p c 码的特点，l d p c 译码器是 d v b - s 2 系统中的关键模块，译码算法的性能直接决定了整个系统的性能，本文 通过对几种译码算法进行性能分析和仿真比较，最终确定以最小和算法作为系统 的译码算法。d v b s 2 系统中l d p c 校验矩阵规模巨大，直接实现需要占用较多的 资源，并且有较大的处理时延。本文通过对标准中l d p c 码的结构特点进行分析， 利用校验矩阵的准循环移位特性，提出了结构化的存储方式及与之对应的部分并 行设计的流水线结构；采用s t a g g e r e dd e c o d i n g 方法，对比特节点信息实时更新， 大大减小了信息的存储空间，使得译码器在面积和数据吞吐量上都满足系统要 求。 最后，本文介绍了l d p c 和d v b s 2 系统的仿真平台，说明了在实验室环境下 设计并验证系统功能正确性的测试方法。利用先进的数字电视信号发生器( s f u ) 产生标准的d v b - s 2 测试信号对接收系统的功能进行验证。最终给出了l d p c 在高 斯信道下的仿真性能和综合结果。 本文的主要贡献在于针对l d p c 译码器的硬件实现，提出了部分并行处理的 结构，以较小的硬件资源实现了高吞吐量的译码。目前越来越多的通信系统采用 l d p c 码作为纠错码，这种部分并行的设计结构对其他系统的l d p c 译码器设计有 一定的借鉴意义。 关键词l d p c ；最小和译码算法；d v b - s 2 ；部分并行 a b s t r a c t a b s tr a c t e r r o rc o r r e c t i n gc o d i n gi sp o w e r f u la n de f f i c i e n ts c h e m et oe n s u r ee r r o r - f r e e t r a n s f o r m a t i o ni nad i g i t a lc o m m u n i c a t i o ns y s t e m s i n c et h eg r e a td e v e l o p m e n to f m i c r o - e l e c t r o n i c s ，c o m p l i c a t e dd e c o d i n ga l g o r i t h mb e c o m ep o s s i b l et ob ev l s i i m p l e m e n t e d ，w h i c hw a sf a ra w a yf r o mb e i n ga c c e s s i b l eb e f o r e l o wd e n s i t yp a r i t y c h e c kc o d e s ( l d p c ) h a v ee r r o r - c o r r e c t i n gp e r f o r m a n c e sc l o s e s tt ot h es h a n n o n s l i m i ta n da ni n h e r e n t p a r a l l e l i s md e c o d i n ga r c h i t e c t u r e ；t h e r e b yh a v e am o r e p r o m i s i n ga p p l i c a t i o nf u t u r ea n di sr e c o m m e n d e da st h ec h a n n e lc o d i n gp r o p o s a li n n e wt h eg e n e r a t i o nc o m m u n i c a t i o ns y s t e m s t h i sp a p e rd e t a i l e di n t r o d u c e st h ed e s i g n a n di m p l e m e n t so fl d p cd e c o d e ra sp a r to ft h ed v b - s 2s y s t e mp r o j e c to fb e i j i n g e m b e d d e ds y s t e mk e yl a b b a s e do nd v b - s 2 ，t h et h e s i ss t u d i e st h el d p cc o d e s ，w h i c hi n v o l v e sc o d e s t r u c t u r e ，d e c o d i n ga l g o r i t h m ，a n dm e m o r y a c c e s s s t r a t e g y a n dh a r d w a r e i m p l e m e n t a t i o no fa s i cd e s i g ne s p e c i a l l y s i m u l a t i o no ncp l a t f o r mi sd o n e ，a n d v e r i l o gc o d ei sf i n i s h e d t h i sp a p e ri n t r o d u c e st h ed v b s 2s y s t e ma n dt h ec h a r a c t e r i s t i co fl d p cc o d e l d p cd e c o d e ri st h ek e ym o d u l ei nt h es y s t e m ，w h o s ep e r f o r m a n c eh a sr e s p e c tt ot h e p e r f o r m a n c eo ft h es y s t e m t h i sp a p e rs e l e c t s t h em i n - s u ma l g o r i t h mt h r o u g h c o m p a r i n gt h ep e r f o r m a n c eo fs o m ea l g o r i t h m s t h em a t r i xo fl d p cc o d ei n d v b - s 2s y s t e mi ss ol a r g et h a ti ti s v e r yd i f f i c u l tt oi m p l e m e n tt h ed e c o d e ri n h a r d w a r e a na p p r o a c ho fd e c o d i n gl d p cs p e c i f i e d 、7 i ，i t hp a r i t yc h e c km a t r i c e sb a s e d o nc i r c u l a n tp e r m u t a t i o nm a t r i c e s ，埘t l ls t r u c t u r em e m o r ya n dac o r r e s p o n d i n g p a r t i a l l yp a r a l l e ld e c o d i n ga r c h i t e c t u r ei sp r o v i d e d a d o p t i n gt h es t a g g e r e dd e c o d i n g s c h e d u l e ，u p d a t i n gt h ei n f o r m a t i o no fb i tn o d e si nr e a lt i m e ，d e c r e a s et h em e m o r y , t h a tm a k et h ed e c o d e rs a t i s f i e st h ed e m a n di nt h r o u g h p u ta n dr e s o u r c e f i n a l l y , t h i sp a p e ri n t r o d u c e st h es i m u l a t i o np l a t f o r mf o rl d p ci nd v b - s 2 u t i l i z et h es f ut og e n e r a t et h et e s t i n gs i g n a l st ov i v i f i c a t et h es y s t e m a tt h ee n do f t h ep a p e r , t h es i m u l a t i o na n ds y n t h e s i sr e s u l ti sg i v e n t h em a i nc o n t r i b u t i o no ft h i sp a p e ri sp r e s e n t i n ga ni m p r o v e dp a r a l l e ld e c o d i n g a p p r o a c hf o rl d p cc o d e s a tp r e s e n t ，m o r ca n dm o r ec o m m u n i c a t i o ns y s t e mu s e l d p cc o d ea st h ec h a n n e lc o d i n gs c h e m e ，t h ea r c h i t e c t u r ei nt h i sp a p e rw i l lg i v ea r e f e r e n c et of u t u r el d p cd e c o d e rd e s i g n k e y w o r d ：l d p c ；m i n - s u ma l g o r i t h m ；d v b s 2 ；p a r t i a l l y - p a r a l l e l i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：数必日期： 燮圭趔 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：达鲣 导师签名：夏让2 坠日期：竺竺垒兰习 第l 章绪论 第1 章绪论 在过去几年中，前向纠错( f o r w a r de r r o rc o r r e c t i o nf e c ) 技术又一次成为 了人们关注的目标。由于微电子技术的发展，使以前难以实现的复杂译码算法在 超大规模芯片中得到实现，从而使复杂的纠错编码成为了通信系统中不可缺少的 一部分。前向纠错编码被视为无线通信和卫星通信在降低功率与带宽需求条件下 提供可靠数据传输的基础构件。 1 1 研究背景与现状 纠错编码是指在数据码流中人为地加入一些冗余数据，以对数据进行监督， 从而使该码流具有检错或纠错的能力，减少传输中误码对正确接收造成的影响。 1 9 4 8 年香农( s h a n n o n ) 在他的开创性论文“通信的数学理论 中，首次阐明了在 有扰信道中实现可靠通信的方法，提出了著名的有扰信道编码定理，奠定了纠错 码的基石。此后汉明( h a m m i n g ) ，斯列宾( s l e p i a n ) 、普兰奇( p r a n g e ) 等人在5 0 年 代初，根据香农的思想，给出了一系列设计好码和有效译码的方法。以后，纠错 码受到了越来越多的通信和数学工作者，特别是代数学家的重视，使纠错码无论 是在理论上还是在实际中都得到了飞速发展。 1 9 6 2 年，g a l l a g e r 首先提出了低密度奇偶校验码( l o wd e n s i t yp a r i t y c h e c k ) n ，别，同时他还提出了l d p c 码的概率译码算法，但是由于概率迭代译码计 算过于复杂，鉴于当时的技术发展水平很难实现，l d p c 码没有得到重视。自1 9 9 5 年m a c k a y 和n e a l 口1 重新发现低密度奇偶校验码的优越性后，从而引发了对l d p c 码研究的热潮，并被确定为未来高速宽带移动通信系统中信道编码的主要备选方 案之一。最近，l d p c 码也被提出作为第四代移动通信中的纠错抗干扰方案h 1 。 有关l d p c 码的研究，在理论方面，主要研究l d p c 码的性能，包括如何构造 好的l d p c 码一，刀，l d p c 码性能分析跚，简化译码算法的研究等随驯；另一方面侧 重于l d p c 码的实际应用，包括l d p c 码在各种实际通信系统，特别是未来高速宽 带移动通信系统，压缩图像传输，无线局域网中l d p c 码的硬件实现问题等。科学 工作者研究发现，l d p c 码的错误平底( e r r o rf l o o r ) 是不存在的n ，只要构造合 理，可以将误码率降到任意低。据此，i e e e 8 0 2 3 a n 工作小组全体通过，在面向 双绞线的l o o g b i t s 以太网标准草案中采用l d p c 。而此前休斯网络系统公司提 出的l d p c 前向纠错方案也被d v b 组织接纳为下一代卫星通信系统的标准n 副。 l d p c 码的硬件实现方面，近年发展十分迅速，已经有a h a 公司，意法半导体 公司等拥有自主知识产权的i p 核和相应编解码芯片，x i l i n x 公司也提供了l d p c 码编码器的i p 核n 引，这些l d p c 码基本上都是为满足d v b - s 2 标准的e f c 部分而 北京工业大学工学硕士学位论文 设计的，为d v b - s 2 机顶盒的供应商提供芯片和技术支持。 正是由于l d p c 码具有非常好的特点：逼近香农限的性能，译码可实行并行操 作，适合硬件实现，d v b - s 2 新一代数字卫星广播标准采用了l d p c 码和b c h 码一 同作为信道编码，使得系统支持更高效的调制技术，传输效率要比d v b - s 高 3 0 n 钔。但是l d p c 码组以一组数据帧作为译码单位，而且l d p c 一般采用软判决 的置信传播算法，实现非常复杂，因此在译码过程中需要较大的存储空间，并且 会产生较大的时延。如何设计l d p c 码的译码结构从而简化实现的复杂度，另外 通过并行处理来提高译码速率，提高吞吐量，缩短译码时延，减小芯片面积和功 耗是在l d p c 码实现过程中要考虑的核心问题。 1 2 信道编码概述 1 2 1 数字通信系统 一般的通信系统可以由图1 - 1 表示n 射。包括五个关键部分： ( 1 ) 信源产生传送到接收端的信息或信息序列。 ( 2 ) 发送器对信息进行处理，产生一个适合于信道传送的信号。 ( 3 ) 信道传输介质，可能是导线，电缆，无线电频段或者光束等等。 ( 4 ) 接收器完成发送器的逆过程，从信号中恢复信息。 ( 5 ) 信宿信息的接收端。 图卜1 数字通信系统 f i g u r e1 1d i g i t a lc o m m u n i c a t i o ns y s t e m s 在实际的通信系统设计中，信息传输的有效性和可靠性是通信系统的核心问 题，所谓可靠性即每一次传输过程能否在接收端得到正确的信息恢复。信息通过 信道传输，由于物理介质的干扰和噪声无法避免，信道的输入和输出之间仅具有 统计意义上的关系，在做出唯一判决的情况下将无法避免差错，其差错概率完全 取决于信道特性。因此，一个完整、实用的通信系统通常都包括信道编译码模块。 信号在传输前都会经过高度压缩以降低码率，传输错误会对最后的数据恢复产生 极大的影响，因此信道编码的性能显得尤为重要。 2 根据著名的香农公式n 6 1 ： c 小彘) m ， 其中形为信道带宽，乞为信号平均功率，0 为噪声的单边功率谱密度，信 道容量c 的单位为比特秒。在数字通信系统中，用e 代表每信息比特需要传输 的能量，则有： 厶= c e b ( 卜2 ) 于是香农公式变形为： c 旧急) m 3 ， 结果是： 墨：2 c w - l ( 1 4 ) o c w 由香农公式可知，当带宽形趋于无穷时，信道容量不会趋于无穷，而是趋于 一个渐进值。此时c w 专0 ，则有： 兰奠：l i m 2 c w - i ：h 1 2 ：一1 6 拈( 1 - 5 ) n o c w oc w 这个值被称为香农限。这是带宽无限的高斯白噪声信道达到信道容量所需的 最低信噪比，是通信系统传输能力的极限。香农公式研究了信道的传输能力的极 限，即传输的有效性问题。由式( 卜1 ) 可见，传输带宽和信噪比之间可以互换。 香农在证明信道编码定理时采用了随机编码的方法，这一方法的优点是能够给出 极限性能的数学表达式，但对于如何构造一个好的编码不能给出具体的指导。在 香农定理提出的五十多年里，寻找实际可译的好码，一直是信道编码理论研究的 关键f 1 题。 1 2 2 信道编码 信道编码的实质是在信息码中增加一定数量的冗余码元( 称为监督码元) ，使 它们满足一定的约束关系，这样由信息码元和监督码元共同组成一个由信道传输 的码字。一旦传输过程中发生错误，则信息码元和监督码元间的约束关系被破坏。 在接收端按照既定的规则校验这种约束关系，从而可达到发现和纠正错误的目 的。举例而言，欲传输k 位信息，经过编码后得到长为n ( n k ) 的码字，则增 北京t 业大学t 学硕十学位论文 加了m = n k 位监督码元，我们定义r = k n 为编码效率或码率。 ( 1 ) 构造好码 所谓好码，就是指编码效率高，译码错误率低，编译码算法简单的码。对好 码及其高效译码算法研究是编码理论研究的中心课题。根据信道编码定理： 设r 是信息传输的速率，c 是信道容量，则对于任意小的s 0 ，只要r c ， 就总存在一种信道编码方式，使得译码的平均错误概率只 s 。 这个定理表明，在不可靠的信道上完全可以实现可靠的信息传输，但是传输 速率绝不能超越信道的极限传输能力即信道容量，否则就不可能做到无误传输。 从理论上说，在信道带宽形专时，会有码长一，这时系统的传输能 力才有可能接近香农限。但是，接收端译码算法的复杂度是随着编码长度成指数 增长的，无限增加码长并不现实。即使在码长有限的情况下，随机编码方式所得 的码集也会很大。即便通过繁杂的搜索能找到好码，这种码也往往是无结构的， 在译码时只能用查表法，其复杂度无法接受。因此真正实用的信道编码都是通过 数学方法来构造，使码字具有便于译码的结构。因此其性能距香农限也有一定的 差距。这种差距也是信道编码研究人员开发新技术的源动力。 ( 2 ) 信道编码的分类 差错控制的基本方式可以粗分为两大类n ，类是反馈方式，包括反馈重发 ( a r q ) 、信息反馈( i r q ) 和混合纠错( h e c ) 等方式：另一类称为前向纠错( f o r w a r d e r r o rc o r r e c t i o n ，f e c ) 方式，所谓“前向 ，是指译码器根据码的规律性自动 纠正错误，其优点是单向传输，不需要反馈，纠错迅速，但缺点是码的构造复杂， 编码效率较低。信道前向纠错编码的分类方式很多，彼此之间又互相涵盖，如图 卜2 所示。 4 第1 章绪论 图卜2 前向纠错码的分类 f i g u r e1 2c l a s s i f i c a t i o nf o rf e c 根据对接收信号处理方式的不同，纠错码的译码可分为硬判决译码和软判决 译码。硬判决译码是基于传统纠错码观点的译码方法：解调器首先对信道输入值 进行硬判决，再将判决结果送入译码器，译码器根据解调器的判决结果，利用码 字的代数结构来纠正其中的错误信息。软判决译码则充分利用了信道输出波形信 息：解调器将匹配滤波器生成的一个实数值送入译码器，由于实数值包含了比硬 判决更多的信道信息，译码器通过概率译码充分利用了这些信息，从而使译码具 有更大编码增益。与硬判决译码相比较，软判决译码在a w g n 信道上有2 3 d b 的编码增益。软输出译码算法是目前编码理论最重要的译码算法，它被广泛应用 于l d p c 码的译码，获得了很好的译码性能。 构造接近香农限的纠错码一直是信道编码理论的理想，但直到2 0 世纪9 0 年 代以前，这个理想却是可望不可及的。在t u r b o 码出现之前，所有的纠错码性能 离香农限还有很大的一段距离，这些纠错码只能看作是好码，还不是非常好码。 1 9 9 3 年，b e r r o u 等人提出的t u r b o 码被看作信道编码理论研究的重要里程碑。 b e r r o u 等人将卷积码和随机交织器相结合，同时采用软输出迭代译码来逼近最大 似然译码，取得了超乎寻常的优异性能。t u r b o 码的性能逼近香农容量限，是一 种信道编码理论界一直梦寐以求的可实用非常好码，它的出现标志着信道编码理 论研究进入了一个崭新的阶段。随着t u r b o 码研究的深入，人们重新发现g a l l a g e r 早在6 0 年代提出的l d p c 码也是一种具有渐进特性的非常好码【l 】，它的译码性 能同样可以逼近香农限。由于l d p c 码在长码时具有超过t u r b o 码的性能，并且 具有译码复杂度低、可并行译码以及译码错误的可检测性等特点，成为了信道编 北京工业大学工学硕士学位论文 码理论新的研究热点。研究表明，t u r b o 码只是l d p c 码的一个特例，两者都是 基于图构造的低密度码，译码算法具有等价性，从而使两者在基于图模型的编码 研究中得到了统一。 1 3d v b - s 2 系统简介 d v b - s 2 标准自颁布以来迅速为世界上大多数的卫星广播营运商用于电视和 数据广播业务n 盯。d v b s 是第一个数字标准，自1 9 9 3 年底公布以来已广泛的应 用于全世界的广播电视业务中。它使用q p s k 调制方式，信道编码采用卷积码和 r s 码级连的方式。1 9 9 7 年又引入了用于卫星新闻采集和节目传送业务的 d v b d s n g 标准，其调制方式改为8 p s k 和1 6 q a m 调制。目前d v b s 与d v b d s n g 在欧洲、亚洲许多国家得到广泛应用。但是随着社会的发展，传送交互业务和高 清晰度电视( h t d v ) 、视频点播( v o d ) 、按次付费收视( p p v ) 等应用业务的需求量剧 增，再加上扩大广播电视覆盖范围的需要，共同推动了卫星电视直播技术 d t h ( d e t e c tt oh o m e ) 向d b s ( d i r e c tb r o a d c a s ts a t e l l i t e ) 发展，而仅用q p s k 解调电路限制了d b s 大功率卫星传送能力。 在过去的十年间，数字通信领域中的技术革新大量涌现，尤其是纠错编码技 术的研究已取得突破性进展。伴随这一趋势，同时由于服务商和用户对卫星通信 提供更大容量和更多新业务的需求不断增长，d v b 项目组于2 0 0 2 年开始着手进 行下一代卫星数字视频广播标准的制定，并于2 0 0 3 年公布了针对卫星宽带业务 的第二代标准一d v b - s 2 ，该标准目前已被国际电信联盟和欧洲电信标准协会采 纳为正式标准。 d v b - s 2 的目标，是实现最好的信号播送性能以及完整的系统灵活性和合理的 接收机复杂性。d v b - s 2 标准与d v b s 标准相比有以下优势： ( 1 ) 系统效率比d v b - s 提高3 0 ； ( 2 ) 结合了d v b - s ( 直接到用户的应用) 和d v b d s n g ( 专业应用) 两方面 的应用，扩展了应用领域； ( 3 ) 采用自适应编码，使卫星转发器的资源得到最充分的利用； ( 4 ) 实现成本低于1 9 9 4 年首次使用d v b s 的应用成本。 d v b - s 2 标准能够达到如此优异的性能，与其采用了当今信道编码技术和调制 技术发展的最新成果是分不开的。信道编码在卫星通信中的作用十分重要，卫星 通信通常数据的传送距离很远，为了对抗路径损失，要求发送信号有尽可能大的 能量。但由于航天器体积和负荷的限制，通常都是功率受限的，为此就要有高性 能的信道编码技术，即有很高的编码增益，同时满足误码率要求。 d v b s 2 具有很广的覆盖范围，且可快速配置，又不需要昂贵的陆基设施，非 6 第l 章绪论 常适合于发展中国家对边远地区的广播电视覆盖。我国1 9 9 8 年启动的国家广电 总局的“村村通 卫星直播试验平台t d h 也使用了d v b - s 标准。目前我国还有许 多边远农村、边境、偏僻山区用户的信号覆盖问题尚未解决，若要1 0 0 全国覆 盖，最经济有效的手段就是采用星上大功率的直播卫星系统。d v b s 2 的出现使 我们面临由d v b - s 向新标准过渡的问题，我国还处于发展卫星广播初期，现有接 收终端数量不多，应该尽早规划，直接采用新技术，实现卫星广播的跨越式发展， 紧密跟踪新标准和新技术的发展，学习总结运营经验，加紧研发具有自主知识产 权的接收终端，有着重要的现实意义。 1 4 课题研究内容及论文结构 本课题来源于北京嵌入式系统重点实验室的d v b s 2 解调芯片的项目。项目 的主要目标是针对d v b s 2 标准进行相应的硬件、软件开发，设计实现符合协议 标准的d v b s 2 接收机。接收机由模数转换模块，数字解调模块和信道译码模块 组成。为了在实验室测试接收机是否符合标准，利用s f u 设备发送标准信号作 为接收机的信源，完成对系统的测试。 本人主要承担了接收系统中l d p c 译码模块的设计与实现，包括译码算法的 软件实现，设计优化的硬件结构，最终以较小的硬件资源实现l d p c 译码器。 l d p c 码的校验矩阵非常大，如果不对译码器的结构进行设计，对于硬件实 现来说，译码器占用的硬件资源是难以想象的。另外，如果译码器采用串行结构， 译码器的处理时延达不到系统要求，因此本课题的核心问题是设计出并行的结 构，以提高译码器的吞吐量并尽量减小系统占用的硬件资源。l d p c 译码器对 r a m 操作频繁，因此必须合理设计数据的存储结构以避免r a m 的读写冲突问 题。 具体内容安排如下： 第l 章“绪论 ，主要阐述了l d p c 译码器研究现状和意义，信道编码的基本 理论，介绍了d v b - s 2 标准的发展现状，最终给出了本课题的主要研究内容。 第2 章“l d p c 码基本原理”，简单介绍了线性分组码基本理论，详细阐述了 l d p c 码的基本原理，定义和因子图模型，重点说明了d v b - s 2 标准中l d p c 码的 结构特点和编码算法模型。 第3 章“l d p c 码的译码算法”，分析了l d c p 码的相关译码算法，包括比特翻 转算法，置信传播算法和最小和算法，通过对三种l d p c 译码算法进行仿真和比 较，最终确定了最小和算法作为最终的实现方案。 第4 章“l d p c 译码器结构设计与实现”，详细阐述了l d p c 译码器的结构化存 储设计思想，利用校验矩阵的准循环特性设计出部分并行处理的译码器硬件结 7 北京工业大学工学硕士学位论文 构，采用s t a g g e r e dd e c o d i n g 方法，对比特节点信息实时更新，大大减小了信 息的存储空间，以较小的硬件资源实现了l d p c 译码器。 第5 章“译码器的硬件综合和仿真结果”，对l d p c 译码器进行了算法级和r t l 级仿真，并完成了对整个d v b - s 2 系统的集成测试，给出了仿真结果。最后给出 了硬件的综合结果。 第2 章l d p c 码摹本原理 第2 章l d p c 码基本原理 l d p c 码本质上是一种普通的线性分组码，可以用生成矩阵和校验矩阵来表 征；l d p c 码又是一种特殊的分组码，特殊性就在于它的校验矩阵中1 的数目 远小于0 的数目，称为稀疏性，“低密度”也来源于此。只有通过一定方法 构造的非常稀疏的校验矩阵，才能实现低复杂度的编译码。从性能上考虑，具有 大的最小距离的码字有很多都落在准循环码这个集合里，因此具有较大最小距离 的准循环码是l d p c 码研究的一个热点n9 矧。d v b - s 2 标准中的l d p c 码属于这类码。 本章首先介绍线性分组码和l d p c 码的基本概念和重要表征参数，然后详细分析 d v b - s 2 标准中的l d p c 码校验矩阵的结构特征和编码算法，并给出具体参数。 2 1 线性分组码 因为低密度奇偶校验码是一种特殊的线性分组码位1 1 ，所以本章将首先对线性 分组码做一个概述，讨论线性码的一些特性。 定义l ：整数0 ，1 ，2 ，g 一1 ，g 是自然数，在模g 加和乘运算下构成一个伽逻 华域g f ( q ) 。 定义2 ：如果一个分组码c ，包含个由g f ( q ) 中的元素构成的码字 ( c o ，q ，知一。) ，则当且仅当c 构成一个叩( g ) 上的矢量子空间时，称c 为q 进制 线性码。本文只考虑二进制码，所以q = 2 。 定义3 ：线性码的维数等于对应的矢量空间的维数，一个长度为维数为k 的线性码总共包括2 量个长度为的码字。 线性码还有如下一些有用的性质m 1 ： 性质l ：任意码字的线性组合仍然是一个码字。此性质的一个结论是线性码 必然包含一个全零码字。 性质2 ：线性码的最小距离等于其中一个最轻码字的汉明重量。 这性质表明确定线性码的最小距离( 决定检错和纠错能力) 要比一般的分 组码要容易的多。 性质3 ：线性码中不可检测的错误图案与传输的码字无关，且由所有的非零码 字组成。 假设( 岛，蜀，g 川) 是组成( ，k ) 二进制码空间的一组基底，对任意一个码 9 北京i 业大学工学颂士学位论文 字c c ，存在唯一的表达形式： c = a o g o + a l g l + + 一1 一l ( 2 1 ) 因为所有基元的线性组合仍然是一个码字，所以存在长度为k 的码组 ( a o ，a i ，a t e 一。) 和c 中码字之间的一一映射。以下矩阵g 就是由基矢按行排列而 成。 g = g o 。1 g l ，1 g k i ，i ( 2 2 ) 这一矩阵叫做码字c 的生成矩阵。通过生成矩阵和信息比特相乘可用来直接 编码k 位的数据组。令a = ( a o ，a a ，一。) 为待编码的二进制组。 c = a g = ( a o ，q ，一1 )= a o g o + 口1 9 l + + 一l g x l ( 2 - 3 ) 线性码c 的对偶空间表示为c 上，是一个( 一k ) 维的矢量空间。c 上的一个 基 ，啊，一川 可构造一个校验矩阵日。 h =( 2 4 ) 校验定理：矢量c 是码字的条件是当且仅当c h r = 0 。 校验矩阵也提供了确定最小码距的方便途径。若线性码c 的校验矩阵为日， 则c 的最小码距等于使各列线性组合之和等于零的最小非零列数。 如果c 的码重为w ，则c h7 是日中的w 列的线性组合。以上表达式定义了重 为w 的码字和日中w 列线性组合的一一映射关系。 如果使用系统码会大大简化数据组的译码。考虑一个生成矩阵为g 的线性分 组码c ，通过高斯消去和列交换，通常可以得到如下形式的生成矩阵。可以由生 成矩阵的各行线性无关以及列秩等于行秩证明上述结论。 1 0 川 忡 鼠轧 配 川 m 州 肌 礼；咿p 舢；杪 第2 章l d p c 码基本原理 g = 【幺i 尸】 1 0 0 ip o 。o p o 1 0 1 0 ip l ，o p 1 1 ；i i i ； 00 1 i p k - 1 o p k 吐l ( 2 - 5 ) 当一个数据组使用系统生成矩阵编码后，原始数据组会毫无变化地位于输出 码字的前面k 位。对生成矩阵的高斯消去并不会改变相关码字的码序列。但另一 方面，列变换可能会产生不属于原来码空间的码字。如果要求特定的码字被用到 时就不能进行列交换，则需要对前k 位以外的系数做一些调整。这会增加编码和 译码设计的复杂度。 对于一个给定的系统码生成矩阵，相应的校验矩阵可以表示为： h = | _ i 如一足l 一风 ，一x l 10 0 一只j 一足一l1 0 1 0 i i i ；i 。； l 一p o 一r l1 00 1 ( 2 - 6 ) 对二进制码，一p 7 = p r 。应该注意到，总能将给定校验矩阵的生成矩阵，通 过高斯消去转换成系统形式。 2 2 低密度奇偶校验码 与所有的线性分组码样，l d p c 码是一类对应于奇偶校验矩阵的线性分组 码。奇偶校验矩阵q 圳。仅仅包含0 和1 ，并且1 的密度非常低，是一个稀疏 矩阵。信息位为k 、码长为的l d p c 码可以用( 一k ) xn 的校验矩阵日来描述， 每一个码字c 都满足c h r = 0 。l d p c 码可以用一个二分图来表征，又称为t a n n e r 刚2 2 2 3 1 ，这是由于t a n n e r 在1 9 8 2 年首次用它来表示l d p c 码。在图论中一个图 是由顶点和边组成的，二分图指的是图中所有的顶点分为两个子集，任何一个子 集内部各个顶点之间没有边相连，任意一个顶点都和一个不在同一个子集里的顶 点相连。一个t a n n e r 图和一个校验矩阵完全对应。这两个子集内的节点在t a n n e r 图中称为比特节点和校验节点。t a n n e r 图按如下规则描画：当日中的元素h ，为 1 时，校验节点厂，= 0 ，1 ，n k l 连接到比特节点薯，江0 ，1 ，一1 。二 北京工业大学工学硕士学位论文 分图包括比特节点集合和校验节点集合两个顶点集合，比特节点和校验节点之间 的连线对应h 阵中的1 。一个二进制向量c = ( c o ，q ，知一。) ，当且仅当关于所 有校验节点的约束方程都满足时，即与之相连的比特节点之和模2 加为0 ，它才 是一个码字。简单的以= 8 ，码率为1 2 的l d p c 码为例来说明。假设此码的校 验矩阵为 h = m o ( 2 - 7 ) 朋2 鸭 图2 - i 是根据校验矩阵日画出的二分图。矩阵h 的每一行代表一个约束方 程，如图2 - i 中校验节点右侧的等式所示。校验矩阵一行中1 的个数称为校 验节点的度砖，一列中1 的个数称为比特节点的度以，在二分图中分别对应 校验节点和比特节点所连接的边的数目。以和z ，为常数的l d p c 码称为规则码， 否则称为非规则码。非规则码比规则码的纠错性能更好，但非规则性会增加硬件 实现的复杂性和降低运算单元重复使用的效率。图2 - 1 中的例子是一个规则码。 通常非规则码具有比规则码好的译码性能，但是实现结构复杂。因此实际应用中 通常采用规则码( c h i n am o b i l em u l t i m e d i ab r o a d c a s t i n gc m m b ) ，或者一种规 则与非规则混合的结构( d v b s 2 ) 。 所oc o o c 3 0 q o 白= 0 m lc l ( 3 c 2 0 q o = 0 m 2c o o q 0 9 0 c 7 = o m 3q o 岛0 岛o = o 信息节点度数d ，= 2校验节点度数d 。= 4 图2 - 1l d p c 码双向图 f i g u r e2 - 1t a n n e rg r a p ho fl d p c 1 2 巳1 0 1 0 巳o 1 0 1 q o o 1 1 巳1 1 o o 巳1 o o 1 巳o 1 1 o q o 1 0 l 巳1 0 1 o o l 2 3 4 5 6 7 c c c c c c c c 第2 章l d p c 码基本原理 皇皇曼曼曼曼曼曼曼曼曼鼍曼鼍曼曼鼍曼曼曼曼曼曼曼曼曼曼曼曼曼皇曼皇曼皇曼皇曼皇曼皇曼曼_ 一i i ii i iii 皇曼皇曼皇曼曼! ! ! ! 曼! 曼曼! 曼曼! 曼曼曼曼皇曼置 环路( g i r t h ) 是二分图中一个很重要的概念。在图论中，环路指的是由比 特节点、校验节点和边首尾相连组成的闭合环路；环的长度即t a n n e r 图中最小 环的长度；因为目前l d p c 码的最好的解码方法是和积译码算法( s u m - p r o d u c t a l g o r i t h m ) ，也称为置信传播算法( b e l i e fp r o p a g a t i o na l g o r i t h m ) n 2 钔，这种 算法是一种渐进最大似然的算法，如果t a n n e r 图中不存在环路，也就是环无穷 大，则这种算法等效于最大似然算法；当然，在码长固定的情况下，对于适用的 码字来说无环是不可能的；但是通过增大最小环路的长度，也可以提高码字的性 能，环路长度达到一定的值就可以接近无环时的性能比引。 决定码字性能的是码间距，但是我们无法去直接约束控制码间距；控制 t a n n e r 图的环虽然也有很大的难度，但却是可以通过一些方法消除长度较短的 环；一般来说，环路长度大的码字其码间距也大，但是码间距大的其环路长度不 一定就很大胆劓。所以，环路长度是目前设计l d p c 码最重要的概念之一。 2 3l d p c 码编码 得到l d p c 码的校验矩阵后，可以画出相应的t a n n e r 图，从一般的角度考虑 l d p c 码的编码，首先需要将各信息比特对应到图中各节点，这样所有的校验条 件都会被满足。用这种方法，l d p c 码的编码问题就会集中到分配信息比特的节 点的选择和计算其他比特节点值的技巧上。 为了将编码过程表示为矩阵形式，将长度为k 的信息比特口编码为l d p c 码 c ，需要进行以下运算c = a g ，这里c 是比特长的码字，哝。是生成矩阵。作 为一个例子，假设要在某信道上传输信息比特组口= 1 0l 1 】，首先用下面的 矩阵编码： | - 1 l10l0 0 h = j r ri ，】= l1 10lo1oi( 2 8 ) l1 0ll0 01 i g = 【i i p 】= lo0 0ll1 o1ool1o o010lo1 0 0ol011 ( 2 9 ) 码字c = a g = 1 0110 0 1 】。 初看起来，编码会有很大的计算量，因为所有的校验方程都必须得到满足， 其计算复杂度与码长的二次方成正比。但实际上，编码可以用更有效的方式完成， 北京工业大学工学硕士学位论文 其复杂度甚至只有译码复杂度的几分之一。现在存在几种不同的l d p c 码编码算 法，一些技术利用到了校验矩阵的稀疏性来实现有效编码乜5 1 ，而另外一些方法则 利用t a n n e r 图的某些结构使编码更直观和简单，重复累加( r e p e a t a c c u m u l a t e ) 算法就是一个利用某些结构的t a n n e r 图编码的例子。下面将对应用于d v b - s 2 标 准的r a 编码算法作简要的介绍。 2 3 1r a 编码算法 l d p c 码的编码过程十分复杂汹1 。对于系统码的编码尤其明显，因为稀疏的 校验矩阵会对应一个并不稀疏的生成矩阵。为了实现适合高码率的非规则l d p c 系统码，d v b s 2 使用的是一类称为扩展非规则累加码( e x t e n d e di r r e g u l a r r e p e a ta c c u m u l a t e ，e i r a ) 1 ，使用e i r a 码，校验矩阵被改变成如下形式： h = 【qi 鸠】 此处，目是m k 稀疏矩阵，h ，有如下形式： h 2 = 1 l1 110 o 0ll 11 ( 2 1 0 ) 对于给定约束的日矩阵，生成矩阵可以表达为如下的系统形式： g = 【ip 】 ( 2 一i i ) 那么p = 研何r ，并且何r 具有如下形式： 何r = 11 1 o ( 2 1 2 ) 根据矩阵何7 的形式可以看出它实际上是一个累加器的生成矩阵。因此 d v b s 2 的l