（通信与信息系统专业论文）ldpc码分析和译码算法的研究.pdf

南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位 获得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文 ( 包括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论 文，并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可以将 公开的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检 索、文摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向 教育部指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息研究所和 中国学术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文 数据库，通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h t m 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答 辩；提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 奎明 2 0 1 0 年5 月3 0日 南开大学研究生学位论文作者信息 论文题目l d p c 码分析和译码算法的研究 姓名李明学号 2 1 2 0 0 6 0 3 1 5 答辩日期2 0 1 0 年5 月2 5 日 论文类别 博十口 学历硕十团硕士专业学位口 高校教师口 同等学力硕士口 院 系 骶信息技术科学学院专业通信与信息系统 联系电话 1 3 5 6 4 5 8 6 7 1 4e m a i l l i m i n g _ 1 9 8 0 _ 2 0 0 8 1 6 3 c o r n 通信地址( 邮编) ：天津市南开大学信息学院五教3 0 7 ( 3 0 0 0 7 1 ) 备注：是否批准为非公开论文 否 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 45ji0i 伽4mw-舢8 i川i_脚y 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行研究工作所取得的研 究成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人创作的、 已公开发表或者没有公开发表的作品的内容。对本论文所涉及的研究工作做出贡献的其 他个人和集体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人 承担。 学位论文作者签名： 奎明2 0 1 0 年5 月3 0 日 非公开学位论文标注说明 根据南开大学有关规定，非公开学位论文须经指导教师同意、作者本人申请和相关 部门批准方能标注。未经批准的均为公开学位论文，公开学位论文本说明为空白。 论文题目 申请密级 口限制( 2 年)口秘密( 1 0 年)口机密( 2 0 年) 保密期限 2 0 年月日至2 0年月日 审批表编号批准日期 2 0年月日 限制2 年( 最长2 年，可少于2 年) 秘密l o 年( 最长5 年，可少于5 年) 机密2 0 年( 最长1 0 年，可少于1 0 年) 摘要 摘要 在1 9 6 3 年g a l l a g e r 在他的博士论文里提出了低密度奇偶校验码( l d p c 码) 。但是在后来的几十年里，l d p c 码一直被人们忽视，一直到m a c k a y 在1 9 9 6 年提出它是一种更加接近香农极限的编码。因此现在l d p c 码变成了编码领域的 研究热点。低密度奇偶校验码是一种用稀疏校验矩阵进行校验的性能优越的纠 错码。论文对l d p c 码进行了详细的分析研究。主要内容有：l d p c 码的编码和 l d p c 码的性能分析、迭代译码算法、改善l d p c 码译码性能。 b p 译码算法是基于二分图的迭代译码算法，在二分图不含有圈的情况下， b p 算法是一种最优的译码算法。二分图在有限大的时候，圈是不可避免的，因 此，b p 算法是一种比最优算法次一层的译码算法。在l d p c 校验矩阵设计中， 我们主要实现短环( 环长4 ) 的消除。本文在详细分析t u r b o 码的迭代译码的 基础上，实现了l d p c 码的b p 迭代译码算法，b p 算法的优点是译码复杂度低同 时利于实现并行译码，这使l d p c 码特别适合于高速通信系统。 本文仿真了a w g n 信道下l d p c ( 2 0 4 8 ，1 0 2 4 ) 和l d p c ( 1 0 0 0 0 ，5 0 0 0 ) 码的 性能，与现在通用的( 2 ，1 ，6 ) 卷积码比较，并且通过仿真的性能比较，证明 l d p c 是一种性能优异的纠错码，在低信噪比低的时候尤其明显。 针对迭代译码的特点，提出了信源冗余和纠错译码的反馈模型，改善了迭 代译码算法性能，使得译码效率得到很大的提高。 关键字：l d p c 码迭代译码b p 算法t u r b o 码准同步数字序列 a b s t r a c t a b s t r a c t 1 1 119 6 3 g a l l a g e rl o wd p a r i t y tl d p cc o d eh a v een e a r - s h a n n o nl i m i tp e r f o r m p r e l d p c i so n eo f fe r r o r - e o r r eh i c hi st h ec o d es db s p e c t sa r e t h ec o d i n go fl d p c c o d ea n db pi t e r a t i v ed e c o d i n ga l g o r g l y z i n gt h ep e r f o r m a n d p cc o d e ，a n d i m p r o v i n e r f o r m a n c e o cu s i n gt h er e d u n d a n c eo fs y n c h r o n i z a t i o nc o d e s i n t h o r m a t i o ni n t e r c e p t i o ns y s t e m i nt h ef i e l d ，b pa l g o r i t h mi sc o n c e r n e d b p , b a p a r t i t eg r a p hi su s e dt oi t e r a t i v e d e c o d i n ga l g o r i t h m r t hl e n g i p a r t i t eg r a p hi o u l db eo p t i m a l b u tw h e nt h ec o d e l e n g t hi sf i n a l ，a r ei n e v i t a b l ei t h mi sh y p o o p t i m a i nt h i sp a p e r ，i nt h ed e s i g n o c h e c k i x ，w er e a l i z e dm e t h o d sw h i c he l i m i n a t e4g i r t ho nb i p a r t i t eg r a p h b a s e do n p r o f o u n e db pi td e c o d ea l g o r i t h mo fl p d cc o d e b pa l g o r i t h ma r ee a s i l yp a r a l l e f a s t e rt o d e ，s ot h a tt h e ya r es u i t a b l ef o rt h eh i g h - s p e e dc o m m u n i c a t i o ns y s t e m s i nt h i sp a p e r ，w et h ep e r f o r m a n c ( 10 0 0 0 ，5 0 0 0 ) a n dl d p c ( 2 0 4 8 ，10 2 4 ) u n d e r a w g n c h a n n e l c o m p a r i n gw i t hg e n e r a l ( 2 ，1 ，6 ) c o n v o l u t i o nc o d eb yu s i n gv i t e r b i a l g o r i t h m ，。 a s s o c i a t i n go u rpw o r t es c o u t i n g ，g e n e r a l l y ，i nt h es a t e l l i t ec o m m u n i c a t i o n ， t h e r ea r es o m ec o d e sp d hs t ao fs y n c h r o n i z a t i o nc o t e e nm a xa n dcc o d i n g “b i g i d e a ，i m p r o v et h ep e r f o m c eo fb pi t e r a t i v ed e c o d i c he n h a e r c e p t i n ge f f i c i e n c yo f i n f o r i n t e r c e p t i o ns y s t e m k e yw o r d s ：l o wd e n s i t yp a r i t yc h e c k b e l i e fp r o p a g a t i o na l g o r i t h m c o d ei t e r a t i v ed e c o d i n ga l g o r i t h m t u r b oc o d e ，p d h 目录 目录 摘要。i a b s t r a c t i i 目录。i i i 第一章引言1 第一节信道编码的基本概念。2 1 1 1错控制系统的分类和纠错码的分类3 1 1 2 汉明距离和重量4 第二节信道编码定理4 1 2 1 香农定理4 1 2 2 常用的纠错编码5 第三节纠错码的研究最新进展5 第四节g ai ja g e r 码6 1 4 1 g ai la g e r 编码7 1 4 2g ai ia g e r 译码9 第二章信息截获系统中l d p c 码分析1 2 第一节l d p c 码的分类1 2 2 1 1规则的l d p c 码l2 2 1 2 非规则l d p c 码1 4 第二节构造好的l d p c 码1 5 2 2 1 m a c k a y 的构造方法1 6 2 2 2l u b y 的构造方法一17 2 2 3d a v e y 的构造方法l8 第三节生成l d p c 码18 2 3 1 分组码的校验矩阵和生成矩阵一1 8 2 3 2l d p c 码编码1 9 2 3 3 实现的例子2l 第四节小结2 4 第三章l d p c 码的迭代译码算法2 5 第一节t u r b o 码的迭代译码算法2 5 3 1 1t u r b o 码迭代译码的原理和组成2 5 3 1 2sis 0 译码器的译码算法一2 6 第二节b p 译码算法3 7 3 2 1b p 算法概述3 7 3 2 2l d p c 迭代译码算法3 9 第三节迭代译码算法性能仿真4 2 第四节小结4 4 第四章利用信源冗余改善迭代译码性能4 5 第一节群路信号的同步理论4 5 第二节常用的复接信号4 7 第三节利用同步码冗余改善b p 译码算法性能4 8 第四节小结5 0 i i l 第五章结论与进一步工作5 l 参考文献5 2 致谢5 3 个人简介、在学期间发表的学术论文与研究成果5 4 i v 第一章引言 第一章引言 通信系统目的是将信息由信源高效且可靠地传送到信宿，应用领域有深空 通信、无线通信、数据传输和存储等等。由于数据传输的信道总是存在各种噪 声和干扰，这导致信宿接收到的信息总会有不同程度的差错，使得通信可靠性 降低；所以为了提高通信的可靠性往往加入冗余信息，这又降低了通信的有效 性，怎样克服通信系统中可靠性和有效性这一对最主要矛盾，香农的信息和编 码理论提出实现有效并且可靠地传输信息的途径是编码。根据香农的信息理论， 数字通信系统基本组成【2 】如图1 1 所示： 图1 1 数字通信系统 图中可见信源编码的目的是把信源发出的消息如语音、文字、图像、流媒 体等等信息转换成二进制信道形式的信息序列的形式即信息码元。信道编码【6 】 的目的是在实际环境的信道情况下，寻找最可信的途径来进行信息传输。其实信 道编码的实质就是在信息码中增加一定数量的多余码元( 称为监督码元) ，让它 们满足一定的约束关系，通过信息码元和监督码元共同组成一个经过信道传输 的码字。举个例子，要传输k 位信息，通过编码后得到长为n ( n k ) 的码字，增 加了n k = r 位监督码元，在这里我们定义r = k n 为编码效率( 码率) 。香 农的编码理论给出了利用编码可以平衡信道通信中的可靠性和有效性的矛盾， 但是他没有给出具体如何编码的方案，也没有说明实现起来的复杂度。因此， 第一章引言 关于信道编码的研究都集中在如何在最充分的利用传输资源( 即带宽、功率、 实现复杂度) 的前提下，选择最佳的编码方式，去逼近香农极限。 1 9 4 8 年，香农( s h a n n o n ) 在他的那篇非常著名的论文通信的数学理论中 提出并且证明了：对于一个信道容量为c 的有干扰的信道，消息源产生信息的 速率为r ，只要腿c ，则总可以找到一种信道编码和译码方式使编码错误概率 p 随着码长n 的增加，按指数下降到任意小的值，若r c ，则不存在编译码方 式来实现无误传输。这一结论为信道编码指出了明确方向，可是它仅仅是一个 存在性定理证明，在实际的应用中并未给出怎样去找出这种性能优良的编码方 式。在近5 0 年来，人们一直在寻求实现复杂度合理的更优秀编译码方法，去逼 近s h a n n o n 理论的理想界限。最终研究出了许多的信道编码方式如：b c h 码、 r s 码、乘积码、卷积码、t u r b o 码以及r s 码结合卷积码形成的级联码等都是 逼近香农界限的好的编码 3 1 1 4 。 但是在现实的通信环境包括：微波通信、卫星通信、短波超短波通信、移 动通信等等都不是理想的传输信道【2 】【4 】，因为在信道中存在着各种噪声、衰落、 多用户干扰、码间干扰、功率限制和多径传输等。所以对于在实际的通信信道 中，关键是要寻找一种最优的编码方法，来提高传输的效率和可靠性。对于 a w g n ( j 3 1 性高斯白噪声) 信道，低密度校验码( l d p c ) 是一种比目前其它的编 码更加逼近香农极限的编码。因为低密度校验码考虑到了以下四个因素：1 ) 充 分反映传输可靠性的差错概率；2 ) 如何提高度量带宽有效性的频谱利用率；3 ) 如何提高度量功率有效性的信噪比；4 ) 如何实现编解码的复杂度。l d p c 码提 供优良的编码增益，和目前比较流行的t u r b o 码进行比较它有较低的运算复杂 度，并且随着硬件技术的快速发展以及高速并行编解码算法使l d p c 码的编解 码得以实现，最终l d p c 必将成为目前信道编码领域热门的研究课题 7 】 1 0 】。 在本章中，首先介绍了信道编码的基本概念，并且引出了信道编码领域中 一个非常重要的定理一香农编码定理。说明了目前l d p c 码得到广泛的应用是 因为这种编码更加逼近香农极限。 第一节信道编码的基本概念 在研究l d p c 码之前，我们先介绍一下信道编码的基本概念和基础知识。 2 第一章引言 1 1 1错控制系统的分类和纠错码的分类 在数字通信系统中，利用纠错码和检错码进行差错控制的方式大致有一下 几类 1 8 1 ( 1 ) 重传反馈方式( a r q ) 。就是发送端发出能够发现( 检测) 错误的序 列，接收端收到通过信道传来的码后，在译码器根该码的编码规则，判决收到 的码序列中有无错误，并通过反馈信道把判决信号通知发送端。发送端根据这 些判决信号，把接收端认为有错的消息再次传送，直到接收端认为正确接收为 止。 ( 2 ) 前向纠错方式( f e c ) 。就是发送端发送能够被纠错的码，接收端收到 这些码后，通过纠错译码器不仅能够自动地发现错误，而且能自动地纠正接收 码字中的错误。 上述各种差错控制系统中所用的码，基本都是在译码器自动发现错误的检 错码，要不就是不仅能发现错误而且能自动纠正错误的纠错码，要不是能纠正 删除错误的纠删码。除了按这种方法划分外，通常还按以下方式对纠错码进行 分类： ( 1 ) 按照对信息元处理方法的不同，分为分组码和卷积码两大类。 分组码是把信源输出的信息序列，以k 戈码元划分一段，通过编码器把这 端k 个信息元按一定规则产生r 个校验( 监督) 元，输出长为n = k + r 的一个码 组。因此每一码组的校验元仅与本组的信息元有关。分组码用( n ，k ) 表示，n 表示码长，k 表示信息位。本文研究的l d p c 码就是一种分组码。 卷积码是把信源输出的信息序列，以k 0 个码元分为一段，通过编码器输 出长位n 0 ( = k 0 ) - - 段的码段。但是该码段的n o k 0 个校验元不仅与本组的信息 元有关，而且也与前m 段的信息元有关，称m 为编码存储，因此卷积码常用 ( n o ，k 0 ，m ) 表示。 ( 2 ) 根据校验元与信息元之间的关系分为线性码和非线性码。若校验元和 信息元之间存在的关系是线性关系，则称为线性码；否则，称为非线性码。本 文研究的l d p c 码就是一种线性分组码。 3 第一章引言 1 1 2 汉明距离和重量 在两个n 重x 、y 之间，如果对应位取值不同的个数，我们称它们之间的汉 明距离，用d ( x ，y ) 表示。在n 重x 中非零码元的个数，我们称之为汉明重量， 简称为重量用、( x ) 表示。( n ，k ) 分组码中，如果任两个码字之间的距离的最小 值，我们称为该分组码的最小汉明距离d 0 ，简称最小距离。( n ，k ) 分组码中，r = i d n 为分组码的码率。 r 和d o 是( n ，k ) 分组码的两个重要参数，其中r 是衡量分组码编码效率的 参数；但是d 0 是衡量分组码抗干扰能力大小的参数。其中纠错编码基本任务就 是构造出r 一定，d o 尽可能大的码，或d 0 一定，r 尽可能高的码【6 】。 任一个( n ，k ) 分组码，若要在码字内： ( 1 ) 检测e 个随机错误，其中就要求码的最小距离d = e + 1 ； ( 2 ) 纠正t 个随机错误，就要求d = 2 t + l ； ( 3 ) 纠正t 个随机错误，同时检测e ( = t ) 个错误，就要要求d 针e + 1 ； ( 4 ) 纠正t 个错误和p 个删除，就要要求d = 2 t + p + l 。 1 2 1香农定理 第二节信道编码定理 对于每一个离散的无记忆信道，总存在一个非负实数的信道容量c ，对任 意实数p o ，存在码率r 小于c 的编码和译码算法，可以使误码率小于p 。该 信道中希望实现码率r 大于c 的无差错通信是不可能的【1 8 】。 ( 原文：a s s o c i a t e dw i t he a c hd i s c r e t em e m o r y l e s sc h a n n e li san o n n e g a t i v en u m b e r c ( c a l l e dt h ec h a n n e lc a p a c i t y ) 、) r i t l lt h ef o l l o w i n gp r o p e r t y f o ra n gp 0a n dr = ra n dd e c o d i n ga l g o r i t h ms u c ht h a tf r e q u e n c yo f d e c o d i n ge r r o r si sl e s st h a np e r r o r - f r e ec o m m u n i c a t i o na tr a t e sa b o v ec a p a c i t yi s n o tp o s s i b l e ) 译码算法若用最大似然译码，则随着码长的增加其译码错误概率p 可任意 小。由信息论的基本知识可知，在高斯白噪声信道时，信道容量 4 第一章引占 p 。胪1 0 9 2 叶高 ( b i t s ) ( 1 - 1 ) 式中： 形：信道所提供的带宽； 只= e ，t ：信号功率； e 。：信号能量； 丁：分组码信号的持续时间即信号宽度； 只w ：单位频率的信号功率； 0 ：单位频率的噪声功率 只( w n o ) ：信噪比。 香农极限，就是在r t 专o o ，要求带宽寸o o ，此时只要求信噪比 既o - 1 6 d b ，就可实现高斯白噪声信道下的无误码传输。这称之为香农极 限。 编码增益，就是在给定误码率条件下，不同编码方法可节省的功率，称之 为编码增益。 1 2 2 常用的纠错编码 目前在短波通信中常用的分组码有：汉明码、循环码、b c h 码、r s 码等【6 】， 卷积码是卫星通信、移动通信中最常用的纠错码方式【4 】【5 】。而r s 码和卷积码 形成的级联码是d v b s 1 标准中的采用的纠错码，是目前使用最多的一种级联 码【4 】。 第三节纠错码的研究最新进展 通过香农信道编码定理界定了纠错编码的性能，与此同时也证明了随机码 是好的编码，但是它的译码太复杂。所以人们孜孜不倦地追求如何构造一个好 的编码在逼近香农限同时译码也比较简单，然而常用的编码方式在接近香农限 之前性能纠急剧下降，根本无法逼近香农极限，直到1 9 9 3 年，t u r b o 码的发现， 其编码性能非常逼近香农限，所以这标志着信道编码理论进入了新的阶段，其 中l d p c 码就是在这个研究中被重新发现的。 5 第一章引言 l d p c ( l o w e rd e n s i t yp a r i t yc h e c k ) 码是一类可以用稀疏校验矩阵或者二 分图定义的线性分组纠错码，最初由g a l l a g e r 在1 9 6 3 年发现的，故亦称 g a l l a g e r 码【l 】。经数十年的沉寂，随着计算机能力的增强和相关理论( 如图论、 可信度传播、t u r b o 码等) 的发展，m a c k a y 和n e a l ，重新发现了它，并证明它 在与基于b p ( 可信度传播) 的迭代译码相结合的条件下具有逼近香农限的性能 【1 3 。l d p c 的重新发现是继t u r b o 码后在纠错编码领域又一个非常重大进步。 l d p c 码的特点是：性能大大优于t u r b o 码，于此同时具有较大灵活性并且有 较低的差错平底特性，描述简单，对严格的理论分析具有可验证性，译码复杂度 低于t u r b o 码，且可实现完全的并行操作，硬件复杂度低，因而适合硬件实现： 吞吐量大，极具高速译码潜力。研究结果显示，对于二元输入的a w g n 信道，码 率为1 2 的非正贝i j l d p c 码可具有距容量不n o 0 6d b 的门限；计算机仿真结 果表明，最好的非正贝i l d p c 码( 长度为1 0 6 ) 可获得在b e r = 1 0 6 时仅偏离容量 0 1 3d b 的性能，优于迄今所知道的最佳t u r b o 码；当码长为1 0 7 、r = 1 2 时，其性能距香农限只差0 0 4d b 。 l d p c 码的优异性能及其在信息可靠传输中的良好应用前景( 例如光通信、卫 星通信、深空通信、第4 代移动通信系统、高速与甚高速率数字用户线、光和 磁记录系统等) 9 】，l d p c 在许多情况下将取代t u r b o 码的趋势日趋明显，已引起 世界各国学术界和i t 业界的高度重视，成为当今信道编码领域最瞩目的研究热 点。近几年来国际上对l d p c 码的理论研究和工程应用方面研究都取得重要进展。 下面具体说明一下g a l l a g e r 最初发现的l d p c 码以及g a l l a g e r 码的译码算法。 第四节g a iia g e r 码 1 9 6 3 年，g a l l a g e r 在自己的一篇著名的博士论文【l 】中提出一种基于稀疏校 验矩阵的线性分组码，也就是l d p c 码( l o wd e n s i t yp a r i t y - - c h e c kc o d e ) 。他 不但证明了l d p c 码的优良性能：( 1 ) 这些码字的典型最小距离d o 随分组码 长n 的增加线性增加；( 2 ) b s c 信道下译码错误的典型概率随分组码长n 指数 减小，而且提出了两种迭代译码算法。但是其实现复杂，需要大量的乘加预算， 由于6 0 年代硬件的计算能力远远满足不了要求，当时并不被人们所关注和认 同。而当时人们关注的大都是集中到容易实现的编码方式上，例如r s 码和卷 积码的级联码等。直到1 9 9 3 年在b e r r o u 等提出了t u r b o 码之后，尤其于1 9 9 9 6 第一章引苦 年m a c k a y 等人发现，l d p c 码的性能足以和t u r b o 码相比，而且更容易实现， 于是人们逐渐把兴趣转移到l d p c 码的研究上来。 1 4 16 aiia g e r 编码 可用随机二分图g 产生g a l l a g e r 码( 如图1 2 所示) ，g 的左边是1 1 个变量 结点，它表示码元比特的校验约束关系；g 的右边是r 个校验结点，向量 ( 而，x 2 ，) 为g a l l a g e r 码的码字，当且仅当对每个校验结点该向量满足校验约 束关系，即每个校验结点所关联的变量结点的值和等于0 ( g f ( 2 ) 域) 。这种类 型的g a l l a g e r 码的码率至少为( n - r ) n 。 x l + x 3 + x s = 0 x 2 + x 4 + x 6 = 0 x l + x 2 + x 6 = 0 图1 2 二分图表j i 的g a l l a g e r 码 一个码长为n ，信息位数为k 的线性码由一个生成矩阵g m 定义，信息序列 分组m 通过g 被映射到码字x = m g 。线性码可以由一致校验矩阵h 等效描 述，所以码字均满足h x ，= 0 。校验矩阵的每一行表示个校验约束，其中所 有非零构成一个元素对应的码元变量构成一个校验集。 g a l l a g e r 定义了g f ( 2 ) 上的参数( n ，j ，i ) 的码是码长为n 其校验矩阵h 中每 一列由j 驴= 3 ) 个“1 和每一行由i ( i j 均为整常数，j b ，则称a 为b 的父节点，b 为a 的子节点。如果顶点v 的父 节点集合有s ( v ) 表示，则图3 3 可描述为： s ( v 1 ) = 矽 s ( v 2 ) = s ( v 3 ) = v l ( 3 - 4 1 ) s ( v 4 ) = 1 ，l ，v 2 s ( v 5 ) = v 3 ，v 4 ) 如果g 为一个d a g ，x 为一随机变量序列( n 个) 且该集合中的元素与g 的 顶点一一对应，则联合概率密度p ( x ) 可根据g 分解为： p ( x ) = p ( x ，ij ( 菇，) ) ( 3 - 4 2 ) t = l 定义节点x 的可信度为： 皿( 口) = p ( x = as ( x ) ) ( 3 4 3 ) 这里的可信度，就是在编码领域中通常说的后验概率。类似t u r b o 码的m a p 译码算法。b p 算法为种分布式消息传递算法，分布处理在d a g 图中的每一 个顶点处进行。我们把每一顶点看成是一个处理机。每一个处理机可同它的父 处理机和子处理机交换信息。处理机的处理过程可用图3 4 描述： 3 8 第三章l d p c 码的迭代译码算法 u ix 的父节点u m y iy 2y m x 的子节点 图3 4x 节点处理示意图 图中，x 从其子节点得到的信息( y ) = p ( r j = yx = 功和从其父节点得到的 信息万( “) = p ( u = u ) 。节点x 处可计算条件概率函数 p ( xu ) = p ( xu 。= 甜 ，u m = u 。) ，从而计算节点x 的可信度值。只有所有的 父节点和子节点的消息都达到后该节点才能被激活，激活后接收所有父节点的 消息向量7 l 。，r ) 和所有子节点的消息向量乃x ( z ) 并根据这些消息更新本节点 的可信度值，然后将计算后的信息返回到所有的父节点和子节点。如果图中所 有的节点均不具备激活条件则任意选择一节点激活。p e a l 曾经证明如果d a g 为树图形式，则在一定的迭代次数后，各个节点的可信度等同于该节点的最大 后验概率值，并且在以后的迭代中不再有太大改变，这就是可信度传播( b e l i e f p r o p a g a t i o n ) 算法 1 3 1 4 1 。 3 2 2l d p c 迭代译码算法 l d p c 迭代译码算法就是b p 算法的一个应用实例，从上一节我们知道，d a g 是根据随机变量间的相关性得到的。如果我们把信息比特序列和冗余比特序列 看成是两组随机变量，则再它们之间也一定存在着一定的映射关系。在这个意 义上，迭代译码过程可以对应于一个d a g 图，图3 5 为迭代译码的d a g 图。 3 9 第三章l d p c 码的迭代译码算法 v l u 1 x l y 1 v k有噪信息比特序列 y k 1信息比特序列 冗余比特序列 有噪冗余比特序列 图3 5 迭代译码的d a g 图 g a l l a g e r 论文中给出的迭代译码算法，经过后来的学者不断的改进和演化， 形成了今天的b p 算法，在很多文献中也称为和积( s u m p r o d u c t ) 算法。概括 地说，就是在给定信道估计和接收信号的条件下，在迭代的每一步，都对有噪 序列的每一个符号估计其后验概率，并将估计值输入下一次迭代。 整个译码过程可以看作在t a n n e r 二分图上的b p 算法的应用，具体的迭代 过程如下：在编码的校验矩阵a 中，将参与第m 个校验约束的信息比特集合记 为l ( m ) 暑 ，：a 。，= l 。同样的将第，个信息比特参与的校验集合记为 m ( i ) 兰 m ：a 。，= 1 ) 。l ( m ) ，为1 4 m ) 与第z 比特的差集。算法包括两个交替执行 的部分，与a 中非零元素相关的数值g 。，和，逐次更新。g 二，是指已知除第m 个外其他所有校验约束的信息时，x 的第，比特取值为x 的概率( x 为发送端发 送的码字) 。r 2 , 在已知x 的第，比特为x ，其它比特满足相互独立的概率分布 q 。，：，( 聊) ， 时第m 个校验约束得到满足的概率。如果a 的二分图没有圈， 在经过一定次数的迭代后，改算法可以得出所有比特的精确后验概率。具体的 迭代过程如下： ( 1 ) 初始化：令p o = p ( x l = 0 ) ( 比特x ，取0 的先验概率， p j = p ( x ，= 1 ) = 1 一p ? 。对于每一个满足a ，= l 的( ，历) ，变量g 易和 第三专l d p c 码的迭代译码算法 g ：，分别被初始化为p j ) 和p ；。 ( 2 ) 迭代第一步：对于每一个校验约束m 和对应的每一个，三( 朋) 计算 两个概率：一个是喝，当x t = 0 ，且其它比特 x ，t ，) 对应于相互 独立的概率分布 g ：n g _ ：l ，) 时，校验约束m 得到满足的概率，定义如 下： o = ( p ( x = o lx t = o ) 兀编) ( 3 - 4 4 ) x t 0 t ( 小) 小) ，( 小) 小，- 上【m ) 坍 另一个是艺，当而= 1 时，校验约束得到满足的概率，定义如下： ，=( p ( 而= 1x = 1 ) 兀g 翥) ( 3 4 5 ) x i 0 ( 坍) m ) ，三( 小) mf ( 历) 小 式中，概率内的求和为模2 和。条件概率的取值为0 或1 ，取决于假 设的x ，的值是否满足模2 求和式。这一步的计算可以根据前后向递 归算法适当简化。定义： 耐= q o 厂g 朋1 ， ( 3 4 6 ) 可以得到： 吒= 匕一艺，= 兀吒， ( 3 - 4 7 ) l e l ( m ) u 利用数学归纳法可得到瑶( x = 0 或1 ) 的计算式： 1 + ( 一1 ) 工t ， = 二 ( 3 - 4 8 ) ( 3 ) 迭代第二步：利用计算所得值壕和t ，更新概率值g ：，和g ：，。对于每 个，计算： g 三，= m lp 夕兀档， ( 3 - 4 9 ) m m ( ，) m g 二，= t z , m l p j 丌艺， ( 3 - 5 0 ) 所m ( ，) 小 其中口。，为归一化系数使得 4 l 第三章l d p c 码的迭代译码算法 q o l + g 乙= l ( 3 5 1 ) 同时计算出比特，取值为0 和l 的伪后验概率g ? 和g ；： q j ) = 口，p j ) n 端 ( 3 5 2 ) 肌m ( ，) q j - 口，p jn 乇， ( 3 5 3 ) m e m ( ，) ( 4 ) 迭代第三步：当q j o 5 时令毫= 1 ，反之毫= 0 ，这样就生成了舅。 如果校验方程詹= 0 m o d 2 成立，则译码成功并结束，x = 圣；否则 回到迭代过程的第二步，如果迭代次数超过设定的最大门限仍没有 得到正确译码，译码也结束，并报告译码错误1 8 1 6 1 7 。 第三节迭代译码算法性能仿真 为了检验l d p c 码的迭代译码算法的性能，仿真了，a w g n 信道下l d p c 的 编译码过程，给出了性能比较。由于b p 算法在初始化时的赋值和信道特性密 切相关，所以先分析a w g n 信道的特性，并同时给出迭代译码的初始化条件。 假设在时间k 时，发送的信息为u 。，u 。为 一1 ，+ 1 ) 的集合，将u 编码后生成码序 列x ( 包括信息位和校验位) ，传输时经过b p s k 调制，传输信道为均值为0 ， 方差为仃2 的a w g n 信道，接收码序列为y ，则在k 时刻接收的比特值为y k ， 在y 。的对数似然比为： 1 ，一( y k l 广、 儿耻l n 型丝乩亟竺至三 尤p ，( o y k ) 1 ，一( y k “) 、 疆i 铋p ( 瓦) ( 3 。5 4 ) = - - ( y k - - 1 ) 2 一- - ( y k + 1 ) 2 = 盟= 盈 2 0 - -2 0 ：22 0 ：26 ：2 且满足： 4 2 第三章l d p c 码的迭代译码算法 所以解得： p r ( 1 y t ) + p ( 0 儿) 2 l ( 3 5 5 ) ( 3 5 6 ) ( 3 5 7 ) 将( 3 5 6 ) 和( 3 5 7 ) 式作为译码初始化p j 和p j ) 的初值；图3 6 是迭代门限设 为1 0 0 ，l d p c ( 1 0 0 0 0 ，5 0 0 0 ) 和l d p c ( 2 0 4 8 ，1 0 2 4 ) 的性能仿真图；图3 7 是迭代门限设为1 0 0 ，l d p c ( 1 0 0 0 0 ，5 0 0 0 ) 和l d p c ( 2 0 4 8 ，1 0 2 4 ) 与( 2 ，1 ， 6 ) 卷积码的性能比较。 信噪i ：h e b n 0 卜曲 图3 6l d p c 码a w g n 信道下肿i - - r - “f j 匕仿真 4 3 每高 一+ 一 一 户 k ， ) y 一、 、 v l 0 只 只 第三章l d p c 码的迭代译码算法 芷 山 雹 湃 留 咄 螺 丑 图3 7l d p c 码和( 2 ，l ，6 ) 卷积码a w g n 信道下性能比较 从上图可以看出，l d p c 码的性能比( 2 ，1 ，6 ) 卷积码的性能优越很多， 应该是一种逼近香农限的好码。 第四节小结 本章详细分析了迭代译码算法，为了更好的理解l d p c 的迭代译码算法b p 算法，首先研究了比较成熟的t u r b o 码迭代译码算法。在理解了t u r b o 码的迭 代译码算法基础上，详细分析阐述了l d p c 的迭代译码算法- - b p 算法，并给出 了具体的实现步骤。最后给出了在a w g n 信道下，l d p c 码的b p 算法的性能 仿真，以及与卷积码的性能比较。 第四章利用信源冗余改善迭代译码性能 第四章利用信源冗余改善迭代译码性能 目前的卫星通信中，为了加大传输容量同时提高传输效率，通常需要将若 干个低速数字信号以数字复用的方式合并成为一个高速的大容量数字信号，后 再用高速信道传输网来传。我们把各路低速数字信号合并而成的大容量数字信 号称为群路信号。群路信号主要分为两类，一是称为准同步数字序列( p d h ) ， 另一种称为同步数字序列( s d h ) 。在我们实际的卫星侦察中，多采用准同步数 字序列。 第一节群路信号的同步理论 在卫星通信中，通常信源由不同比特速率的群落信号组成，从而来适应各种 传输条件和传输介质。将两种( 包括两种) 以上的数字信号按时分复用方式接成 单一的复合数字信号，我们把这一过程称为数字复接，相反地的在接收端的逆 过程称之为数字分接。数字复接和数字分接的功能框图如图4 1 所示【2 】： 4 5 第四章利用信源冗余改善迭代译码性能 图4 1数字复接和解复接的功能框图 群路信号是由多个分支信号按时分复用的方式依次接入的，将数据流划分 为多组相继连接的数字时隙，同时把各分支信号按自己的编号依次填入自己的 时隙。我们为了在接收端在任何的时间接入都能正确地实施解复接，所以必须 周期地指示群路信号的起始位置，即将数据流划分成为多层帧格式，在复接时 周期地插入帧定位信号( 帧同步码) ，各时隙位置就可以根据帧定位信号加以确 定。通常一帧信号由帧定位信号、信令码、勤务码、各分支信号信息码组成。 在群路信号中，各分支信号信息码、勤务码、信令码等组成的数据流是一 个随机信号流，但是帧同步信号是相对固定码型。巴克( b a r k e r ) 对帧同步码 的选择进行了研究，他利用自相关函数作为码型的度量标准。随后一些研究者 又推荐出一