（信号与信息处理专业论文）分布式信源编码算法与应用研究.pdf

分布式信源编码算法与应用研究 摘要 分布式信源编码( d s c ) 是指对一组相互关联的信源进行编码， 各个信源单独进行编码( 因此称为分布式) ，并将编码后的信息送到 同一个解码器来进行联合解码。这种编码方法降低了编码端的工作 量，在解码时考虑了各节点之间的信息冗余，提高了编码效率，并将 编码端的复杂度部分转移到了解码端。因此分布式信源编码能够适应 那种编码能力受限的应用场景，如无线传感器网络等。本文就分布式 信源编码算法与应用进行仿真研究。 本文讨论了l d p c 码在分布式信源编码中的应用。利用a w g n 信道来模拟信源之间的相关性，通过伴随式来对信源进行编码压缩， 然后采用比特反转的译码方法来进行联合译码。通过仿真来对l d p c 码应用到分布式信源编码中的性能进行分析。 并针对分布式视频编码方案中的p r i s m ( p o w e r - e f f c i e n t ，r o b u s t ， 1 1 i g h c o m p r e s s i o n ，s y n d r o m e b a s e dm u l t i m e d i ac o d i n g ) 方案提出一种基 于h a s h 搜索的改进方案。该改进方案不仅可以降低编码时需要传送 的比特数，还大大降低了解码端的计算复杂度与时延。 关键词：分布式信源编码l d p c 码分布式视频编码p r i s m r e s e a r c ho nd i s t r 【b u t e ds o u r c e c o d i n g a l g o i u t h m sa n da p p l i c a t i o n s a b s t r a c t d i s t r i b u t e ds o u r c ec o d i n g ( d s c ) r e f e r st ot h ec o m p r e s s i o no ft h e o u t p u t so ft w oo rm o r ep h y s i c a l l ys e p a r a t e ds o u r c e s t h ec a t c hi st h a tt h e s o u r c e sd on o tc o m m u n i c a t ew i t he a c ho t h e r ( h e n c ed i s t r i b u t e dc o d i n g ) t h e s es o u r c e ss e n dt h e i rc o m p r e s s e do u t p u t st oac e n t r a lp o i n tf o rj o i n t d e c o d i n g t h i se n c o d i n gm e t h o dg r e a t l y r e d u c e st h ew o r k l o a do f e n c o d i n gn o d e s ，a n d t h ed e c o d e rt a k et h e r e d u n d a n c yi n f o r m a t i o n b e t w e e nn o d e si n t oa c c o u n t ，i m p r o v et h ec o d i n ge f f i c i e n c y a n dt h e c o m p l e x i t yi sp a r t l yt r a n s f e r r e dt ot h ed e c o d e rf r o mt h ee n c o d e r s od s c i sa b l et oa d a p tt ot h ee n c o d i n gc a p a c i t y - c o n s t r a i n e ds c e n a r i o s ，s u c ha s w i r e l e s ss e n s o rn e t w o r k t h i st h e s i sf o c u s e so nt h er e s e a r c h e so n d i s t r i b u t e ds o u r c ec o d i n ga l g o r i t h m sa n d a p p l i c a t i o n s t h i sp a p e rd i s c u s s e st h ed i s t r i b u t e ds o u r c ec o d i n gu s i n gl d p c u s i n ga w g nc h a n n e lt oi m i t a t et h ec o r r e l a t i o nb e t w e e nt h es o u r c e s ，w e c o m p r e s st h es o u r c ew i t ht h es y n d r o m ee n c o d i n gm e t h o d ，t h e nd e c o d ei t b yt h ew a yo fb i tr e v e r s i o nw i t hs i d ei n f o r m a t i o n w ea n a l y z et h e p e r f o r m a n c e o fd i s t r i b u t e ds o u r c e c o d i n gu s i n gl d p cw i t h t h e e m u l a t i o nr e s u l t s t h e nl d p ci si n t r o d u c e di n t ot h ep r i s m ( p o w e r - e f f i c i e n t ，r o b u s t ， m g h c o m p r e s s i o n ，s y n d r o m e - b a s e dm u l t i m e d i ac o d i n g ) s c h e m ei nt h i s p a p e r c o n t r a s tt ot h eh a s hm o d u l ei np r i s m ，t h i sp a p e rp r o p o s e sa h a s h - b a s e dm o t i o ns e a r c hs c h e m e t o g e t t h em o s t p o s s i b l e s i d e i n f o r m a t i o nb e f o r es y n d r o m ed e c o d i n g a n dt h i sp r o p o s a ls c h e m e n o to n l yl o w e r st h eb i t so fh a s hi ne n c o d e r , b u ta l s og r e a t l yl o w e r st h e c o m p u t a t i o nc o m p l e x i t ya n dd e l a yi nd e c o d e r k e yw o r d s ：d i s t r i b u t e ds o u r c e c o d i n g l d p cd i s t r i b u t e d v i d e oc o d i n gp r i s m 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： j ：金盈 日期： 金! 罩：三： ! 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 硷盐 日期： 导师签名： 莓豸婴蕃 日期： 北京邮电人学硕上学化论文 绪论 1 1 论文研究背景 第一章绪论 近年来，无线传感器1 ) 6 9 络( w s n ，w i r e l e s ss e n s o r n e t w o r k ) 引起人们的广 泛关注和研究，在军事、环境以及医疗等领域都得到了很好的利用。无线传感 器网络是集成了传感器、嵌入式计算、网络和无线通信四大技术而形成的一种 全新的信息获取和处理技术，是一种新型的无基础设施的无线网络，能够协作 地实时监测、感知和采集各种环境或监测对象的信息，并对其进行处理、传送 到需要这些信息的用户，具有十分广阔的应用前景。 但是它也存在着一定的局限性，它不像电脑和英特网那样适用广泛，而是1 应用于特定的环境下，例如：温度测量，实时录像监控等领域【l 】。与其他的无 线网络相比，无线传感器网络中传感器节点的能量有限而且不能够实时更新。 因此传感节点的信息处理能力和无线通信的容量都受到了很大的影响。为了克 服这些限制就要使得组成无线传感器网络的各个部分得到充分的利用，需要设 计能耗较低的通信协议和算法。分布式信源编码( d s c ，d i s t r i b u t e ds o u r c ec o d i n g ) 便是其中的解决方案之一。 分布式信源编码是指对相互之间不能进行通信的多个相关传感器的数据分 别进行压缩，并将压缩后的结果发送到同一个中心节点进行联合译码。这种分 布式的编码方式不仅降低了编码器的复杂度，而月减少了网络中通信的数据量， 同时还节约了传感器节点的功耗。因此，d s c 是无线传感器网络研究中的重要 一环，不仅如此对于在分布式环境下处理语音，图像等大数据量的应用中也是 至关重要。 与传统信源编码相比，d s c 采用的是多对一的编码模式，将编码器端的复 杂度转移到译码端，使得作为编码端的无线传感器节点尽可能被设计得简单和 高效，而作为译码端的接收节点具有足够的能力进行联合译码。每个传感器节 点可以独立工作，因此不需要接收器，这样可以节省硬件费用和传输能耗。然 而在实际的工作中我们仍然需要一个接收器来完成其他的操作，例如路由，控 制和同步工作，但是不需要像传统模式那样功能强大。 在d s c 模式下，要达到与传统的编码同样的效率，需要充分利用相邻节点 北五f f h b 电人学硕上学位论文绪论 之间的相关信息来进行编码。因此需要对信源的相关性进行建模，分布式信源 编码中的相关模型，利用虚拟信道来模拟信源的相关性，从而达到压缩信源降 低传输速率的目的。 同时随着网络与无线技术的发展，以分布式信源编码为理论基础的分布式 视频编码也越来越受到人们的重视。与传统视频编码相比，分布式视频编码 ( d i s t a l b u t e dv i d e oc o d i n g ) 借鉴分布式信源编码思想，将编码端的复杂度尽可 能地转移到解码端，这种特性更加符合无线视频、无线监控等视频应用场景的 需要。 传统视频编码标准，如m p e g 和h 2 6 x 等，都是通过d c t 、量化、熵编码、 运动估计与补偿等算法来充分利用原始视频序列在时间域与空间域上的相关 性，充分挖掘视频信号中的冗余信息来尽可能地压缩视频数据。在利用视频数 据时间域的相关性上，为了能够准确预测当前帧数据，传统视频编码标准均采 用了运动估计算法。而由于运动估计算法的复杂性，使得在传统视频编码标准 中，编码端的复杂度是解码端的5 1 0 倍。这种传统的视频编码标准适用于那 种经过一次编码而多次解码的应用场景，如视频光盘存储，视频点播和视频广 播等应用场景。然而在一些视频应用场景中如无线视频、无线传感器监控网络 等场景。以典型的无线视频传感器网络为例，这种网络由大量的、低成本的、 能量受限的摄像头传感器节点组成，获得被监视对象或场景在空间、时间上都 具有不同程度重叠性的视频数据流，并对其进行压缩处理和进行无线传输。在 这类视频应用场景中，编码端往往都是一些计算能力和耗电量等受限的终端， 这就需要在编码端尽可能地降低复杂度；而相应的解码端往往都是具有一定计 算能力的服务器或者监控中心，这种解码端可以承受较高的复杂度。然而那种 编码复杂度较高的传统视频编码标准中，无法适用于这类应用场景。在这种情 况下，编码复杂度较低的分布式视频编码的研究越来越受到人们的重视。 1 2 论文主要研究内容 论文主要对分布式信源编码相关算法进行仿真和性能分析，以及对以分布 式信源编码为理论基础的分布式视频编码中的p r i s m ( p o w e r - e f f c i e n t ，r o b u s t , l l i 曲- c o m p r e s s i o n ，s y n d r o m e b a s e dm u l t i m e d i ac o d i n g ) 方案进行仿真，并提出一 个可以降低译码端复杂度的改进算法。 首先通过阅读有关资料学习分布式信源编码的理论基础，包括s l e p i a n w o l f 定理等，对分布式信源编码，以及分布式信源编码在视频中的应用方案有一定 的了解，并将相应的算法应用到一定的场景中。 2 北京邮电人学硕士学位论文绪论 学习l d p c 码编译码原理。并在此基础上，建立相关信源模型将l d p c 码 应用到分布式信源编码中来，仿真分析其性能的好坏，并针对分布式视频编码 中的p r i s m 方案提出一种可降低解码复杂度的方案。并将l d p c 码应用到该改 进方案中。 1 3 论文结构 本文主要研究分布式信源编码理论与算法，对采用l d p c 码的分布式信源编 码性能进行了仿真。并针对分布式视频编码中的p 融s m 提出一种可降低解码复杂 度的方案。本文的具体结构如下： 第二章，本章介绍了分布式信源编码的理论基础，以及利用伴随式进行分 布式信源编码的方案( d i s c u s ：d i s t r i b u t e ds o u r c ec o d i n gu s i n gs y n d r o m e s ) 第三章，本章对具有良好抗噪性能l d p c 码的构造、特点以及编解码方法 进行了说明，介绍了l d p c 码应用到d s c 中的编解码算法，并对其进行了仿真 分析。 第四章，本章对以分布式信源编码为理论基础的分布式视频编码的产生、发 展以及应用场景进行了说明。介绍了几种分布式视频编码方案，并针对其中的 p r i s m 方案提出了一种基于h a s h 搜索的可降低解码复杂度的改进算法； 第五章，总结全文，讨论下一步的工作和需要解决的问题。 北京邮电人学硕上学位论文 分布式信源编码理论基础 第二章分布式信源编码理论基础 早在1 9 7 3 年，d s l e p i a n 和j k w r o l f 从理论上证明无损压缩时相关信源的 独立编码和联合编码同样有效，从此奠定了分布式信源编码的理论基础【2 】到 现在经过了三十多年的发展。目前在分布式信源编码领域中，主要的研究分支 有：嵌套网格码，t u r b o 码，l d p c 码等 2 1 分布式信源编码介绍 分布式信源编码( d s c ) 是指对一组相互关联的信源进行编码，各个信源 单独进行编码，并将编码后的信息送到同一个解码器来进行联合解码。这种单 独编码联合解码的方式可以降低编码端的工作量，并且在解码时考虑了各节点 之间的信息冗余，从而提高编码效率，并将编码端的复杂度部分转移到了解码 端。当前，分布式编码在国外已经成为传感器阵列研究中的重要内容，在国内 也开始受到越来越多的研究者的关注。 d s c 的以下两个特点使之可以匹配传感器节点的能量要求：1 ) 低能耗和 低复杂度的编码器，这能够延长无线传感器节点的生存期；2 ) 有效的高压缩率， 因为数据的传送速率直接影响到节点的能量消耗【l 】。 d s c 采用多对一的编码模式，将编码器的复杂度转移到解码端，使得无线 传感节点被设计成尽可能简单和高效，而接收节点具有足够的能力进行联合译 码。每个传感节点可以独立工作，因此不需要接收器来进行交互，这样就可以 节省硬件费用和传输能耗。然而在实际的工作中仍然需要一个接收器来完成其 他的操作，例如路由，控制和同步工作，但是不需要像传统模式那样功能强大。 在d s c 模式下，如果要达到与传统的编码同样的效率，需要充分利用相邻 节点之间的相关信息来进行编码。 2 2 分布式信源编码的理论基础 分布式信源编码要求在编码端进行独立编码，在解码端联合解码，在解码 端解析并利用信息冗余。这种编码方式能否有效地解析信源之间的相关性，能 在何种程度上利用信源之间的相关性? s l e p i a n - w o l f 定理和w y n e r - z i v 定理从理 4 北京邮电人学硕- 上学位论文分布式信源编码理论基础 论上给出了说明。早在1 9 7 3 年，d s l e p i a n 和j k w o l f 就从理论上证明了在无 损压缩时相关信源的独立编码( 联合译码器的复杂度增加) 和联合编码同样有 效，从而奠定了d s c 的理论基础。随后a w y n g r 和j z i v 提出联合高斯信源 的有损编码方案，并给出了率失真函数【3 】。 2 2 1 离散信源的s l e p i a n w o l f 编码 2 2 1 1s l e p i a n w o l f 编码定理 s l e p i a n - w o l f 编码适用于针对离散信源的分布式信源编码。假定序列 ( 五，r ) ：二l 表示一对离散的独立同分布的相关随机变量x 和y ，依据仙农的信 源编码定理，如图2 1 ( a ) 所示，对信源x 和y 进行联合编解码，只要总的编码 速率大于x 和y 的联合熵h ( x ，y 1 就可以对信源进行无损压缩。例如，可以先 把y 压缩为日( 】，) 比特每符号，然后基于y 的完整信息，将x 压缩为h ( x r ) 比特每符号；解码端先由h ( r ) 无损的恢复y ，然后结合y 和h ( x r ) 无损的 恢复x 。这种编码方式为联合编译码。 ( a ) 图2 1 联合编码与独立编码( a ) x 和y 的联合编译码，编码器之间相互协作，需要的总 速率为( x ，y 1 ；( b ) x 和y 的分布式独立编码和联合译码，编码器之间不通信， s l e p i a n w o ”理论认为需要的最少总速率仍为何( x 。y ) 如果需要对x 和y 进行独立压缩，那么编码比特率为多少? 又该如何来恢 复呢? 这种情形如图2 1 ( b ) 所示。一种方法是分别用片( x 1 和日( y ) 进行单独编 码，这时当x 和y 存在相关性时，其总速率r = h ( x ) + g ( r 1 h ( x ，y ) 。然 而s l e p i a n w o l f 认为当两个信源单独进行编码时，总速率r = h ( x ，】，) 也是足够 的。s l e p i a n w ，o l f 编码定理从理论上给出了证明，如果两信源f x ，y 1 的联合分布 满足p ( x ，y ) ，可达速率域满足以下条件时： 北京邮电人学硕士学位论文 分布式信源编码理论基础 曷h ( x i y ) 垦n ( r i x ) 曷+ r 2 h ( x ，y ) 式( 2 - 1 ) 式( 2 - 2 ) 式( 2 3 ) 信源无损压缩时的独立编码方式和联合编码同样有效。如图2 2 所示。 s l e p i a n - w o l f 编码可以扩展到任意各态历经过程，可数字符集和任意数目的相关 信源等情形。 联合解码 图2 - 2 两相关信源时的s l e p i a n - w o l f 速率域 与证明仙农信道编码定理类似，证明s l e p i a n w b l f 定理时所用到的随机装 箱的方法是渐近的和不可构建的。在设计实用码字时，首先设计码字逼近图2 2 的a 点，使得编码速率为r i + 墨= h ( xiy ) + 日( y ) = h ( x ，y 1 ，称作解码端拥 有边信息y 时对x 的信源编码，编码框图如图2 3 所示。同理，只需要互换x 和y 即可实现图中b 点。a 和b 两个点之间的连线上的点则可以通过时分复用 实现，比如为a 和b 设计的码字分别占用百分之五十的时间，就可以实现中点 c 。a 和b 点的编码称为不对称编码，c 点的编码称为对称编码。在不对称编 码时，编码的目标是基于x 和y 之间的条件统计信息( 或者相关性模型) ，以 逼近于日( x i y l 的速率来对x 进行编码。 x 无损编码器 代2 - l ai ，l l 联合解码器 ( 伴随子模式) 伴随子比特7 一一 图2 3 解码端拥有边信息y 时对x 的信源编码 6 北糸邮电人学硕上学位论文分布式信源编码理论皋础 2 2 1 2 二进制信源的s l e p i a n - w o l f 编码举例 下面以举例对s l e p i a n - w o l f 编码进行说明： 设x 和y 为等概率的二进制三元组，即x ，l ， o ，l l ，其相关性可以用为x 和y 之f a g 汉明距如( x ，y ) sl 来表示，则日( x ) = 日( 】，) = 3 比特。对于给定 的y ，x 共有四个等概率的可能情况。例如当y 为0 0 0 时，x 0 0 0 ，o o l ，0 1 0 ，1 0 0 j ， 即h ( x l y ) = 2 比特。如果对x 和y 进行联合编码，则需要用3 比特来表示y ， 2 比特来表示x 的四种与y 相关的可能选择情况，这样总共需要 日( x ，y ) = 日( xi 】，) + 日( 】，) = 5 比特来对x 与y 进行无损压缩。在不进行联合 编码的情况下，需要r = 日( 力+ h ( y ) = 6 比特来对x 与y 进行无损压缩。相比 之下，联合编码的传送速率有所降低。 如果解码端知道边信息y ，而编码端不知道y ，而仅仅知道x 与y 之间的 相关性信息。根据s l e p i a n w r o l f 定理，只需要发送日( xiy 1 = 2 比特来代替用3 比特表示的x ，就可以保证译码端完成无损译码。实现方式如下：首先将x 的 所有可能的输出结果划分为四个不相交的集合。乙= 0 0 0 ，l l1 1 ， z 0 l = 0 0 1 ，l l o ，= 0 1 0 ，1 0 1 ，z 矗= 1 0 0 ，0 1l ，保证每个集合内的两个码字 的汉明距以= 3 。然后发送2 比特来表示x 所属的集合z 。的序列g - s 。译码端 就可以结合y 和j ( 即z 。) 进行联合译码，选择在集合互中满足“( x ，】，) sl 条 件时对应的x 。由于集合z 。中的两个码字的汉明距为“= 3 ，则可保证译码的 唯一性，且达到了 s l e p i a n w o l f 给定的速率域界限 日( x ，y ) = m ( xi 】，) + 日( y ) = 3 + 2 = 5 。在解码端可以根据y 把x 解码成陪集 中对y 的汉明距离最接近的那个码字。因此编码端在不明确知道y 信息的情况 下，也可以将x 压缩至2 比特，从而降低了传输的速率。 上面的例子可以映射到信道编码中熟悉的陪集和伴随式的形式： 1 1ln 3 h 表示速率为1 3 的重复信道码的校验矩阵，即h = i ：l ：用长为3 i l0l l 比特的二进制码字表示x ，则陪集互的序号j 表示为伴随式s = x h r ，伴随式j 将x 划分为4 个不相交的集合z 。用2 比特表示的伴随式j 代替原来需要用3 比特表示的x ，则得到的压缩率为3 ：2 。 在信道编码中，将满足s = x h7 1 条件的需要用3 比特表示的向量x 所在集合 称为由h 定义的线性信道码g ( s = x h7 = 0 0 ) 的陪集c 。，则每个陪集c 。对 应一个集合z 。，即集合z 。中的所有成员均为陪集c 。的码字，反之亦然。编码 效率为1 3 的线性重复信道码的码字间的汉明距特性与每个陪集c 。中的码 字的汉明距特性相同。解码端根据集合z 。的序号s ，即给定陪集c 。，再利用边 7 北京邮电人学硕上学位论文分布式信源编码理论基础 信息y 来选择确定c 中与之最近的码字，从而可以无差错的恢复x 。 将上面的例子扩展到更一般的情形： 假定x 和y 为等概率的f 2 。一1 l 比特( 正整数所3 ) 表示的二进制信源， x 和y 之间的相关性模型表示为d ( x ，y 1 朋。设刀= 2 脚一l ，七= 刀一历，则 h ( x ) = n ( r ) = 力比特，h ( xiy ) = 朋，h ( x ，y ) = 刀+ 坍。假定采用以比特对 y 进行编码，且在译码端可以知道y 的确切信息。对于输入的珂比特x ，采用 f k 1 二进制汉明信道码的坍刀的校验矩阵h 对x 进行s l e p i a n - w o l f 编码，得 到伴随式s = x h7 ，压缩率为刀：所，达到了s l e p i a n w r o l f 界。校验矩阵h 将x 的2 ”个二进制码字划分为2 朋个不相交的集合，伴随式s 则表示集合所对应的序 号，每个集合中有2 个元素，保留了码字的距离属性( 最小汉明距为历) ，因 此能够正确的恢复x 。 上面的例子说明了s l e p i a n w o l f 编码的可行性。尽管s l e p i a n - w o l f 编码是一 个信源编码的问题，但是这个问题实际上是和信道编码原理密切相关的。从上 面的例子中可以看出，问题的关键是信源码字空间的分割，把信源x 的输出划 分成了不同的组，称为陪集，这种划分使得在每一个陪集中的两个码字之间的 最小距离尽可能地达到最大，同时又保持了陪集间的对称性。编码器通过只传 输陪集的索引来达到数据压缩的目的。解码器通过存陪集中进行搜索得到与参 考信息( 即边信息) 距离最近的码字作为解码结果，可以看出陪集的这种特性 和信道码的特性十分相似，所以这种陪集的分割和伴随式的编码和解码可以利 用信道码来完成。 w y n e r 4 在1 9 7 4 年首先提出采用虚拟信道来模拟信源x 和边信息y 之间 相关性的方案。如果信源x 与边信息y 的相关性可以采用二进制信道来进行建 模，则w y n e r 提出的伴随式方案可拓展到任意的二进制线性信道码，对于逼近 仙农信道容量界的信道码如t u r b o 码和l d p c 码则可用来逼近s l e p i a n w o l f 界。 2 2 2 连续信源的w y n e r z i v 编码 在上一节，主要以解码端利用边信息对离散信源进行无损压缩为例讲述了 s l e p i a n w r o l f 编码。然而在无限传感器网络等实际应用场景中，经常需要处理的 信源是连续信源，这样在解码器端利用边信息来进行解码就会产生速率失真的 问题。假设边信息y 在解码端可知，而在编码端刁 ，j - i ，2 ，刀一k ，是检验节点q 的度： 6 ，嚣( 儡) r ，j - 1 ，2 ，n - k ，m = l ，2 ，r j 是来自( 到达) q 的第m 条边的以l o g 为底的概率。 在这里，可以看到译码中y 是二进制的，但是论文中采用的是高斯信道来 模拟信源x 与y 之间的相关性，因此二进制信源x 在经过高斯信道后得到的y 并不是二进制的，因此需要对y 进行判决来得到二进制形式的y 。并通过公式 ( 3 6 ) 得到x 与y 不等的概率。 肚争咖历 蜘， 首先设定： 旷1 0 9 鬻裂( 1 一驯0 9 警m k 唧丹睁小o 5 却7 ) 变量结点v i 第m 条边的l l r ： g ；：= q i ，。+ 记，m = l ，2 ，f = l ，2 ，l o 其中初始化粥= o 式( 3 - 8 ) 接下来g 篇分配给与之对应的f 易( f 州) 通过伴随子信息和“t a n h 规则 得到来自检验节点q 的第m 条边的l l r ： t o u t m t a n h ( 半) = ( 1 - 2 s j ) 兀t a n h ( 等) ，加= 1 2 ，o ，= 1 ，2 ，棚一k 式( 3 - 9 ) 接着让g 篇= 0 0 州u ，朋) 。通过下式来判定毫，然后重复除( 3 6 ) 、( 3 - 7 ) 外的以上 过程。 薯2 0 ，当研，。+ 蟊o 时 ? 刮式( 3 1 0 ) ， 、 7 1 ，当吼，。+ g 磊 o 时 朋= l 北京邮电人学颀_ 上学位论文低密度奇偶校验码 循环结束有两种情形，在初始化程序时设定有最大循环次数k 。结束的第 一种情形：正常结束，当循环次数小于k 且得到的量满足船r = z im o d 2 时循 环结束。第二种情形时：循环次数等于k 的情形，为非正常结束，但是可以近 似的看作已经满足k h 7 = z lm o d 2 。 3 3 3 仿真实现及结果分析 仿真是基于非规则的l d p c 码字，采用的仿真工具为m a t l a b 6 5 1 。在仿真 中信源的相关模型采用a w g n 信道模型。编译码算法采用的是上两小节中介绍 的编译码算法。在前文l d p c 码构造中的分析可知，在相同的条件下，非规则 l d p c 码的性能要优于规则l d p c 码。而且对于非规则码码长越长，性能越好， 也就是说误码越小。因此，本文对规则码与非规则码进行仿真分析，并对相同 码率不同码长，相同码长不同码率的非规则l d p c 码中进行仿真分析。但是由 于硬件条件的限制，在论文中只对码长为1 0 0 0 非规则码的进行了仿真。 3 3 3 1 规则码与非规则码l d p c 码仿真 分别对码长为t = 1 0 2 和刀= 1 0 3 的规则l d p c 与非规则l d p c 码进行仿真。 规则l d p c 码采用( 3 , 6 ) 码，对与非规则码采用的变量节点的度分布为 a ( 工) = 0 1 x 2 + 0 3 x 3 + 0 6 x 4 ，在译码过程中，对1 0 0 个码字，进行1 0 0 次消息 传递算法的迭代，计算出的误码率的平均值。误码曲线图如图3 7 所示： l d p c 误码牢r 口i ；6 ) i 巾1 2 ) + 0 3 西+ 母6 4 ) 嗓声的标准差 5 图3 - 7 规则码与非规则码误码率比较 通过观察图3 7 可以看到：整体上码长越长，译码性能越好，且非规则码 译码性能在整体上要优于规则码。这是与理论分析相一致的，因为描述同一元 酽 铲 铲 旷 铲 铲0 1 1 ， ， 1 l 囊皿碍非丑嗒 北京邮电大学硕士学位论文 低密度奇偶校验码 素空间，采用码字越长对应的码间距越大。在信道码中，码间距越大，纠错性 能越好。因此码长为1 0 0 0 的码字比码长为1 0 0 的码字纠错性能更好。 在使用l d p c 码作为分布式信源编码时，非规贝： l d p c 码的性能要优于规则 码；在l d p c 码作为信道码，l u b y 的模拟实验也得到了相同的结论：适当构造的 不规则码的性能优于规则码的性能【1 0 】。这一点也可从构成l d p c 码的二分图得 到直观性的解释，从信息节点的角度看，其度数越高越好，因为对它进行校验的 校验节点越多，提供的译码信息越准确，使得它能更快更准确地被译码；但是从 校验节点角度看，则是次数越低越好，这样它提供给与之相邻的比特节点的校验 信息就更准确。针对这一矛盾非规则l d p c 码比规则码能够更好地实现两者的平 衡。 3 3 3 21 2 码率下不同码长的仿真 采用的1 2 码率下度分布函数分别如下所示： 名( 工) = 0 2 3 4 0 2 9 x + 0 2 1 2 4 2 5 x 2 + 0 1 4 6 8 9 8 x 5 + 0 1 0 2 8 4 0 x 6 + 0 3 0 3 8 0 8 x 1 9 式( 3 11 ) p ( x ) = 0 7 1 8 7 5 x 7 + 0 2 8 1 2 5 x 3 式( 3 1 2 ) 分别对码长为n = 1 0 2 和n = 1 0 3 的不规则l d p c 码进行仿真。对l o 个码字， 进行4 0 次消息传递算法的迭代，而计算出的误码率的平均值。码率为0 5 时， 不同码长情形下能够正确译码时对应的噪声标准差临界值如表3 - 1 所示，仿真 误码曲线图如图3 - 8 所示。 表3 1 ，码率为o 5 时不同码长能够正确译码时的噪声标准差临界值 心 1 0 0 01 0 0 噪声标准差临界值0 6 0 40 4 9 对应的理论误码率0 0 4 8 8 9 80 0 2 0 6 3 5 在码率为0 5 时，对应的伴随子是码长的一半，在编码过程中，通过 z 。= x h7 来计算伴随子的长度。在码长为1 0 0 0 时，对应的伴随子为5 0 0 ；码长 为1 0 0 时，伴随子是5 0 。在传输的过程中，只传输了伴随子，因此达到了压缩 码字的目的。在码率相同的情况下，压缩比率都是0 5 。在译码端，利用伴随子 z l 和边信息y 采用前文提到的译码算法来得到j ，通过计算j 与x 不同的个 数来得到误码率。 北京邮电人学硬上学位论文低密度奇偶校验码 通过观察表3 - 1 ，可以看到在相同码率不同码长的情形下，不同码长所对 应的噪声标准差临界值是不一样的。通过对比可以清晰地看到，在码长为1 0 0 0 时，理论误码率为0 0 4 8 8 9 8 ，也就是说在1 0 0 0 个码字比特中，出现错误的比 特数约为4 9 个：码长为1 0 0 时，出错约2 个。在这种情况下，应用到d s c 中的 l d p c 码是能够正确译码的。 通过对比在相同码率不同码长的情况，可以得出这样的结论：码率相同的 情况下，码长越长，纠错性能越好，所对应的噪声标准差临界值越高，对信源 之问相关性的要求越弱。而且能够正确译码对应的噪声标准差的值并不是随码 长增加呈线性增长。 ：i 噪声的标准差 。； k，。 “l 图3 - 8 码率0 5 下的不同码长之间的误码率比较 通过观察图3 - 8 可以发现，虽然解码性能不是很理想，但是无论是码长为 1 0 0 0 还是码长为1 0 0 的l d p c 码应用到d s c 中都达到了一定的译码效果，起到 了一定的纠错作用。在图中的表现形式是码长为1 0 0 0 和1 0 0 的误码曲线都在理 论误码曲线的下方。这体现了l d p c 码纠错作用。通过比较可以看出码长为1 0 0 0 的码字更能够容忍噪声，即码长为1 0 0 0 的码字比1 0 0 的码字，纠错效果更好， 对应到信源方面就是对信源的相关性要求更弱。 这是与理论分析相一致的，因为描述同一元素空间，采用码长为1 0 0 0 的码 字比采用码长为1 0 0 的码字对应的码间距越大。存信道码中，码间距越大，纠 错性能越好。因此码长为1 0 0 0 的码字比码长为1 0 0 的码字纠错性能更好。 码长1 0 0 0 的性能较码长1 0 0 有所提高，但不是十分的明显，这和码字个数 及迭代次数都有一定的关系。因为硬件条件有限，只仿真了1 0 个码字月译码时 北京邮电大学硕士学位论文低密度奇偶校验码 的迭代次数只采用了4 0 次，这也是导致解码性能不是很理想的一个重要原因。 但是依然可以推断出，在相同码率的情况下，随着码长的增长，解码性能会越 好。这个结论在一定范围内成立的，观察图3 8 可以看到，在噪声比较大时， 三条曲线都趋向于一点。这是由于噪声太大，超过了l d p c 码的纠错能力所导 致的。 3 3 3 3 码长为1 0 0 0 的不同码率下的仿真 i 2 码率的度分布如上节所述。另外两种分别为码率为3 4 和7 8 的两种 非规则l d p c 码，其度分布为： 对r l = 0 2 5 名( x ) = 0 0 7 1 4 2 8 x + o 2 3 0 1 1 8 x 2 + 0 0 7 9 5 9 6 x 9 + 0 1 4 7 0 4 3 x m + 0 0 7 3 8 2 1 x 船+ 0 3 9 7 9 9 4 x 4 9 式( 3 1 3 ) p ( x ) = x 2 7 对r 2 = 0 1 2 5 名( x ) = o 0 3 4 4 8 2 x + 0 2 7 0 4 2 7 x 2 + o 0 2 7 7 1 9 x 9 + o 2 0 9 4 2 7 x l o + o 4 5 7 9 4 5 x 的式( 3 1 5 ) p ( x ) = x 5 7 式( 3 - 1 6 ) 对于这三种不同的码率( 1 2 ，3 4 ，7 8 ) ，选取的码长均为n = 1 0 3 ，码字数为 1 0 ，迭代次数为4 0 ，在码长为1 0 0 0 时，不同码率条件下能够正确译码时对应 的噪声标准差临界值如表3 - 2 所示：仿真误码曲线图如图3 - 9 所示。 表3 2 ，码长为1 0 0 0 时不同码率能够正确译码时的噪声标准差- 临界值 沁 0 50 7 50 8 7 5 噪声标准差临界值 0 6 0 4o 3 70 3 4 对应的理论误码率 0 0 4 8 8 9 80 0 0 3 4 3 8 90 0 0 1 6 3 4 8 在码长为1 0 0 0 的情况下，不同的码率对应的伴随子长度小一样，在码率为 北京邮电人学硕上学位论文 低密度奇偶校验码 0 5 时，对应的伴随子长为5 0 0 ，码率为0 7 5 时对应的伴随子长为2 5 0 ，码率 为0 8 7 5 时对应的伴随子长为1 2 5 。在编码过程中，通过z 。= 脚7 来计算伴随 子的长度。在传输的过程中，只传输了伴随子，达到了压缩码字的目的。而且 码率越大的情况下，压缩率越高。译码时利用伴随子z l 和边信息y 采用前文中 的译码算法来得到j ，通过计算j 与x 不同的个数来得到误码率。 通过观察表3 - 2 ，可以看到在相同码长不同码率的条件下，不同码率所对 应的噪声标准差临界值是不一样的。通过对比可以清晰地看到，在码率为o 5 时，理论误码率为0 0 4 8 8 9 8 ，也就是说在1 0 0 0 个码字比特中，出现错误的比 特数约为4 9 个；码率为0 7 5 时，出错约3 4 个；码率为0 8 7 5 时，出错约1 6 个。在这种情况下，应用到d s c 中的l d p c 码是能够正确译码的。 通过对比在相同码长不同码率的情况可以得出这样的结论：码长相同的 情况下，码率越低，所对应的噪声标准差越高，纠错性能也就越好，对信源相 关性的要求更弱。而且能够正确译码对应的噪声标准差的值并不是随码率增加 呈线性递减。 噪声的标准差 图3 - 9 码长为1 0 0 0 条件下不同码长之间的误码率比较 通过观察图3 - 9 可以发现，对于等长度仿真的d s c 编码，码率越低，译码 性能越好。在图中表现为码率低的误码曲线在码率高的误码曲线下方。即在相 同的码长下，码率越低，达到相同的误码率标准对应的噪声标准差越大，对噪 声的容忍性更好，在信源方面对应信源x 与y 之间的相关性越小。 这是与理论相一致的。在伴随子方面，码率越高对应的伴随子长度越小， 伴随子所能表示的信源x 与y 的相关性的信息越少，从而给解码带来更大的负 北京邮电人学硕士学位论文 低密度奇偶校验码 担，导致纠错性能的降低；在l d p c 码的校验矩阵方面，码率越高，对应的h 矩 阵中的检验节点越少，检验节点越少，在解码的过程中，提供有效信息越少， 从而降低了解码性能。因此可以推断出，在相同码长的情况下，码率越低，纠 错性能越好。这个结论在一定范围内成立的，观察图3 - 9 可以看到，在噪声比 较大时，三条曲线都趋向于一点。这是由于噪声太大，超过了l d p c 码的纠错能 力所导致的。 通过对以上两组仿真的分析，可以得到以下结论：增长码长，降低码率， 将有助于提高纠错译码的性能，从而更好地体现l d p c 与d s c 结合的优势。 3 4 图像压缩的应用实例 在图片数据中，相邻图片以及图片相邻行之间的数据相关性比较大，为了 验证分布式信源编码的有效性，可以采用前文所提到的使用l d p c 码的分布式信 源编码算法来对图像数据进行压缩。采用的系统框图如图3 - 1 0 所示： 图3 1 0d s c 在图像编码中的应用 3 4 1 编译码过程 1 利用图片的统计信息，结合校验矩阵的生成算法，得到需要的校验矩阵 h ： 2 将图片数据按行读入；每两行作为一个处理单元，进行相关信源的压缩 编码，即一行作为边信息不压缩，另一行通过校验矩阵得到伴随子： 3 边信息与伴随子均经过高斯信道进行有噪传输； 4 译码端首先对边信息y 译码，然后结合y 和校验子z 进行l d p c 迭代译 码； 5 还原图片。 北m 邮电学硕上学托论文 低密度奇偶枝验码 3 42 仿真结果 如图3 - 1 1 和图3 1 2 所示分别给出了原始图片和采用( 3 ，6 ) 规则l d p c 码进行分布式信源编码后的还原图片。图3 - 1 1 中，由于原始图片的两行间的相 关性较小使得d s c 的译码结果存