（模式识别与智能系统专业论文）现代纠错码及其在分布式视频编码中的应用.pdf

中文摘要 中文摘要 分布式信源编码( d i s t f i b u t c ds o u r c cc ( d i n g ，简称d s c ) 是一种新型通信框架， 主要特点是编码端简单，把复杂度转移到解码端，特别适合手机视频上传、传感 器网络等编码端运算能力不强的场合。目前分布式信源编码已得到学术界和工业 界越来越多的关注。 分布式视频编码( d i s t 抽u t c d d e oc o d i n g ，简称d v c ) 是分布式信源编码在 视频中的应用，通过在解码端消除视频帧间冗余来进行压缩，可以获得较低复杂 度的编码器。本文提出了一种分布式视频编码框架，实现了帧内编码、帧问解码 的结构，同时深入研究了现代纠错码t u r b 0 ，l o w d e n s i t yp a r i t y c h e c kc o d e s ( 简 称u ) p c ) 的编解码原理，并把它们分别引入到分布式视频编码系统中，在二进制 对称信道( b s c ) 中进行了系统仿真，取得了较好的性能。本文的主要工作和成果 如下： 1 提出了基于t u r b o 码的分布式视频编码系统，重新定义了r a t cc o m p a t i b l c p l l n c t u r c d l 、l f b oc o d e s ( 简称r c p t ) 打孔算法，实现了自适应可变码率，更好 的与视频帧间冗余度吻合。 2 提出了基于u ) p c 码的分布式视频编码系统，实现了自适应可变码率的r a t e c o m p a t i b l eu ) p cc o d e s ( 简称r g u ) p c ) ，用以动念匹配视频帧问冗余度。 3 从实验上证明了l d p c 比t u f b o 更适合于分布式视频编码。本文提出的分布式 视频编码框架优于h 2 6 3 + 全i 帧性能2 8 d b ，但是与基于运动补偿的帧问编码 还是存在一定的差距。当视频帧间运动量较大的时候，基于u ) p c 码的分布式 视频编码系统性能要比基于t u r b o 码高0 8 d b 。 关键词：分布式信源编码；分布式视频编码；t u r i ) o 码；l d p c 码 a b s t r a c t d i s t 抽u 伽s o u 嗽伽i n g ( d s c ) i san c wc o m m u n i c a t i o n cw h i c hh a sas i l l l p l e e n c o d e r fni se s p e d a l l yu s e f l i li l ip m c t i c c si nw h i c ht h e 锄c o d c rh 嬲l o wc o m p u t a t i a b i l i t i e s ，鲫c h 勰m o b i l ec a m e mp l l o n e s ，s e n rn e 呐o r k 粕d o n d s ch 鹊b e c n f e c c i v e dm u c hi l l t e r c s t 矗o mi n d u s t r i a la n da c a d c m i cf i e l d sa tp r c s e m d i s t r i b u t e dv i d c oc o d i n g( d v c ) i s 锄a p p l i c a t i o no fd s ci l lv d e oc o d i n g n e n a b l c sl o w c o m p l e x i t ye n c o d i n gb ys h i f t i n gt h eb u l ko ft h ec o m p u t a t i 伽t ot h ed c o o d e r t 1 1 j sl h e s i sp o p o s 鼯ad v cs c h 彻ew h j c hf c a 】j z c sv j d m p r e s s i 咖b yj n t 船一触m e e n c o d i n ga n di n t c r 仃锄ed e c o d i i l g 1 w om o d e me r i o rc o f r e c t i n g d e s ，t u r b o 柚du ) p ca s t u d i e da l l di n t r o d u c c dt o d v cu n d e rb i n a r ys y m m c t r i cc h 柚e l ( b s c ) t oi i i l p r o v ct h cq u a l i t yo ft h ew h o l e s y s t e m t h em a i nw o f ka i l da c h i c v e m e n t s 甜ea sf o u 0 w s ： 1 p f 叩。辩ad v cs c h 啪eb a s e do nh r b oc o d e s ，a n d 诈c s t m c tp u n 咖r i n gp a n 啪t o g c tr a t ec 眦n p a t i b l ep i l n c t l l r e dt u r b oc o d e s ( r c p d ，鲫c hp a t t e mm a k e st h e c o d er a t em a t c hi n t e r - 丘a m er e d u n d a n c yb e t t e r 2 p f o p 0 ad v cs c h e m eb a d 蛐u ) p cc o d e s ，柚dr e a l i z cr a t ec o m p a t i b l e p u n d u r c dl d p cc o d e s ( r c u ) p c ) l om a l c hj n t e f n 御瞳e 删u n d 彻c y 3 e x p e r i m e mr e s u l t ss h o wt h a tu d p ci sm o f es u i t a b l ef o rd v cf r a m et h 柚 t u r b o c o m p a r e dw i t hh 2 6 3 + ，o u fp r o p o s e ds y s t e m sp s n rv a l u ci s2 8 d b h i g h e rt h a ni n 仃a 劬m ee n c o d i n gb u tl o w e rt h a nt h ei n t e f - 劬m em o d e ib a s e d m o t i o nc o m p e n s a t i o n f b fv i d e os e q u e n c c sw i t hh i g hm o t i o n ，u ) p cp e r f o r n l s b e n e ri n 伽rd v cs y s t 锄a n dh a v ea b o u to 8d bi m p r 0 v e m e n ti np s n r c o m d a f e dw i t h1 u r b o k e y w o r d s ：d s c ；d v c ；t h r b 0 ；l d p c 致谢 本论文的工作是在我的导师赵耀教授的悉心指导下完成的，从选题到论文的 研究，从论文初稿的每一次修改到最后的完成，都凝聚了他的学术魅力。赵老师 科学的思维方式、严谨的治学态度和勤奋的工作精神给我留下极深刻的印象，使 我知道了要成为一名优秀的科研人员所应具备的素质，也为我树立了今后奋斗的 榜样，在此衷心感谢三年来赵老师对我的关心和指导。 感谢朱振峰老师、唐小芳老师在我硕士研究生期间给予的科研上的帮助以及 生活上的关心。 在实验室工作及撰写论文期间，王安红师姐、翁韶伟师姐、赵玉风师姐给予 很多有参考价值的意见，在此向她们表示感谢。张志远师兄、林春雨师兄对我平 时的研究工作给与了热情的帮助，在此向他们表达我的感激之情。 另外也感谢我的父母和哥哥多年来在学习和生活上给予我多方面的关心和帮 助，他们的鼓励和支持使我能够在学校专心完成我的学业，永远是我前进的动力。 感谢女友齐珊娜在我硕士期间给予的精神上的支持与鼓励，生活上的悉心照 顾和关怀。 结束之际，再次向赵老师、以及所有帮助过我的老师、同学和朋友表示最诚 挚的感谢! 引言 1 引言 随着通信技术的发展以及人们对多媒体信息需求的日益增加，多媒体通信技 术已经成为当今通信领域的研究重点和热点。为了满足多媒体传输的各项要求， 必须有一个好的编码传输系统对其进行支持。一个完整的编码传输系统包含信源 编码和信道编码两个部分，信源编码在保证质量的前提下，尽可能的将多媒体数 据进行压缩，然后送给信道编码部分。信道编码则负责给接收数据增加一定的冗 余，使其在一定的误码范围内能够正确译码，以此来保护己压缩的多媒体数据。 1 1 信源编码技术的发展 信源编码的任务即是对信源进行有效的描述，将信号在一定的保真度内进行 有效表示。这种有效描述可以通过减少信息冗余度来减少传输信源数据采样值所 占用的存储空间或频带宽度，降低系统的数掘速率，从而减少所需的系统资源。 数字通信的传统业务是电话，但随着通信技术的不断发展，信源信息已经不 单是语音或文字信息，而是融合了语音、图文、视频、音乐等多种数据的多媒体 信息，必须通过压缩以使之满足传输频带和存储空间的要求。多媒体从时间角度 上可分为离散媒体和连续媒体。离散媒体是指其内容与时日j 没关系，如：文本、 图像等。而连续媒体是指其所包含的信息量与时间有关，随着时日j 的改变而变化 的媒体，如：视频、音频等。这其中，对多媒体信息传输起着决定性作用的，是 时效性强、数据量大、带宽占用率高且同步性要求严格的连续媒体。从信息论的 观点来看，描述信源的数据是信息量( 信源熵) 和信息冗余量之和，信源编码的 主要目的就是数据压缩，保留信息量，而尽可能的减少信息冗余量。从这个角度 出发，编码压缩方法分为两大类：一种称为冗余度压缩方法，也称无损压缩、信 息保持编码或熵编码；另一种则称为信息量压缩方法，也称有损压缩、失真度编 码或熵压缩编码。 对于视频信号的压缩包括统计冗余度压缩、空间冗余度压缩、时问冗余度压 缩以及视觉冗余度的压缩，其编码方法由早期的差值脉冲编码逐渐发展为今天所 常用的d c t 变换编码、运动补偿、帧间、帧内预测编码等。信源编码经过多年 的发展有了很大的进步，可扩展编码( s c a l a b l ec o d i n 曲被认为是在无线网络、因特网 等异构的网络环境中传输视频的首选方案l l j 。可扩展编码又称为分层编码，是将视 频信息编码成多个不同性质的码流，其中包括一个基本层和多个增强层。2 0 0 1 年 m p e g 组织制定的m p e g 4 可精细扩展( f g s ，f i n cg r a n t i l a rs c a l a b i l i t y ) 编码标准 北京交通大学硕十论文 是可扩展编码中的一种f 2 l 。w u 等在m p e g 4 的基础上提出了渐进可精细扩展方 法p f g s ( p m g r c s s i v ef i n eg 埘m l a r i t ys c a l a b i i i t y ) 1 3 l o 该方法针对f g s 方法编码效 率不高的缺点，利用多个增强层进行预测以减少预测误差，提高了编码效率。这 种可扩展的编码方式越来越多得到实际的应用。2 0 0 1 年，ut v c e g 开始制定 h 2 6 l 标准，h 2 6 l 的压缩性能有了很大的突破，并最终形成了h 2 6 4 标准。其 压缩率为现有信源编码压缩标准中性能最优的，在3 0 3 5 d b 的解码质量范围内， 可以比m p e g 4 节省3 0 5 0 的码率。但h 2 6 4 获得优越性能的代价是计算复 杂度增加，编码的计算复杂度大约相当于h 2 6 3 的3 倍，解码复杂度大约相当于 h 2 6 3 的2 倍。 在传统的视频编码中，无论是m p e g 系列标准还是h 2 6 x 系列标准，它们 都在编码时运用了信源数据的统计特性，以此来压缩信源信息。为了充分运用信 源数据的统计特性，学者们想出了各种办法，利用帧内信息、帧间信息、运动矢 量等等，但这一切方法在压缩信源数据的同时，也大大增加了信源编码的复杂度。 为了保证编码效果，同时降低复杂度，一个很自然的想法就是将信源编码的复杂 度适当转移至解码端。早在上世纪七十年代，学者s l e p j a n 和w b l f 就提出了分布 式无损编码( d i s t 曲u t e dl o s s l e s sc o d i n g ) 理论1 4 】，随后学者w y i l e r 和z i v 给出 了分布式信源编码的率失真模型【”。从那以后，基于这些理论的编码方案被统称为 分命式信源编码( d i s t f i b u t e ds o u r c cc o d i n g ) 。 分布式信源编码指的是对两个( 或多个) 独立的，但是具有某种特殊关联的 随机序列进行编码，并且对于每一个序列采用一个独立的编码器的方法。每个编 码器发送独立的比特流到解码器中，该解码器可以对所有输入的比特流进行联合 解码从而利用其中的统计相关性。图1 1 是一个最简单的分布式编码示意图。图 中，相关的随机序列x 和y 分别进行信源编码，而在解码端则利用两序列问的 相关性进行联合解码。 国1 1 分布式编码框图 f i g 1 1d i s t 曲u t e dc o d i n gf r a 蟛 2 引言 对于统计相关的两个独立同分布随机序列x 和y ，在单独编码、单独解码的 情况下，可分别以码率尺，h ( x ) 和毋七日( y ) 单独进行无错编码，其中两0 和刖叼分别是序列x 和y 的熵。在单独编码、联合解码的情况下，如果在恢复石 和y 时可以容忍一定的错误概率，并且这个概率在编码序列足够长时可以变得任 意小( 但是一般不为0 ) ，则可以根据s l e p i 柚w b l f 理论采用码率r 。h ( x l l ，) ， b 乏日( y l x ) 来分别进行编码，此时需保证码率满足条件r ，+ 墨2 h ( x ，功，其 中各种熵的相应关系如图1 2 所示。可以看到，尽管x 和y 采用的是独立编码 器，码率仍然可以达到对x 和l ，采用联合编码所获得的联合熵h 陇，功。因此 通过在解码端运用相应技术来得到高压缩率，简化了编码复杂度。 所f 9 刀 压缩区 r x 图1 2 分布式压缩x 和y 可达码率范围 f 培1 2r a t er 柚g c0 f x 蛐dy i nd i s t r i b u t e ds 0 哪c o d i n g 下面举例来说明这个问题：假设有两个互相关的等概率分布的3 比特大小的信 源j ，、y ，它们相互关系为码距d 。( 工，l ，) 1 。如果l ，在编解码两端都是已知的， 那么可以编码x 成2 比特( 因为x 和l ，的模2 加只有4 种可能( o o o ) ，( 0 0 1 ) ，( 0 1 0 ) 和 ( 1 0 0 ) ，只用2 比特就可以表示) 。而当在编码端得不到y ，只能在解码端得到的时 候，仍然可以把x 压缩成2 比特。其根据为：如果已经知道x = 似柳或x = 口姐j ，那 么就没有必要再花费比特来区分这两个取值了，因为它们中只能有一个满足 d 。皤，y ) 1 。实际上，可以把x = ( 0 0 0 ) 和x = ( 1 1 1 ) 组成一个陪集。同理，把3 比特二 进制码字空间中的其他码字分割成另外3 个不同的陪集，使得每一个陪集中的两个 码字之间的汉明距离都大于等于2 。因为一共有4 个陪集，所以只需要2 个比特就可 以指明z 属于哪个陪集。这4 个陪集分别是： c o s e t l = ( 0 0 0 ，1 1 1 )映射为0 0 ； c o s c t 2 = ( 0 0 1 ，1 1o )映射为0 1 ； c o s e t 3 = ( 0 1 0 ，1 0 1 )映射为1 0 ； s e t 4 = ( 0 1 l ，1 0 0 1映射为1 1 。 3 北京交通大学硕十论文 在解码端可以根据l r 把x 解码成陪集中对y 的汉明距离最近的那个码字。因 此编码端不需要明确地知道y 的信息，也可以把x 压缩成2 比特。 例如，当j ，_ 0 0 1 ，l ，印1 1 时( 满足码矩d 。( x ，l ，) s1 ) ，把x 映射到陪集2 ，编码 为o l ，发送到解码端，解码端根据已经收到的y = 0 1 1 和d 。伍，y ) 蔓1 ，可以判断出 在陪集2 中只能是胜0 0 1 而不可能是壮1 1 0 。 上面的例子说明了s i e p i 孤w b l 编码的可行性，尽管s l c p i a n w o l f 编码是一个信 源编码的问题，但是这个问题实际上是和信道编码原理密切相关的。从上面的例 子中可以看出，这里面的关键问题是信源码字空间的分割，把信源x 的输出划分 成了不同的组，称之为陪集，这种划分使得在每一个陪集中的两个码字之间的最 小距离尽可能地达到最大，同时保持陪集问的对称性。编码器通过只传输陪集的 索引来达到数据压缩的目的。解码器通过在陪集中进行搜索得到与参考信息距离 最近的码字作为解码结果，可以看出陪集的这种特性和信道码的特性十分相似， 所以这种陪集的分割和伴随式的编码和解码可以利用信道码来完成。 根据s l e p i a i l 和w o i f 的工作，w y n e r 和z i v 建立了在解码端使用边信息( s i d e i n f o 啪a t i o n ) 的有损分布式编码率失真理论。w v l l e r _ z i v 理论认为，在有损压缩的 时候，如果只在解码端可以得到参考信息和在编解码端都能得到参考信息相比， 并没有编码效率的下降。即在有损压缩的时候，如果只在解码端可以得到参考信 息可以取得和在编解码端都能得到参考信息时相同的率失真。 在某种程度上，分布式信源编码可以看作是“纠错码”。考虑两个二进制序列x 和y ，假没序列“= x o y 。如果序列x 和l ，非常相似，则序列h 大部分数掘为0 ， 只有少部分为1 ，表示x ，y 不同的位置。为了“保护w 序列，对其进行系统码 的编码，但在传输时仅传送编码时生成的校验位。在解码端，利用x 、l ，序列的 统计特性，用该校验位与“边信息”y 进行“纠错”解码。如果x 和y 序列相似度非 常高，则仅需传送检验位很少的几位数据，从而压缩信源，得到较低码率。因此 信道编码方法都经修改后在分布式信源编码中得到了应用。需要强调的是这并不 是使用前向错误纠错( f e c ) 来防止信道传输所产生的错误，而是由一种通过计算x 与边信息y 相关性的虚拟“相关信道”来进行。 虽然分布式编码算法的信息理论建立在上个世纪7 0 年代，但是直到最近，一 些实用的分布式编码算法才开始出现，大多数的信源编码技术源于信道编码的思 想。最近一次代表性的工作在1 9 9 9 年由p r a 曲a n 和r 锄c h a n d r a n 实现1 6 j ，最初对于统 计独立的二进制和高斯信源采用不对称编码，即在解码端使用边信息。他们后来 考虑了对称情况l 0 】，对x 和】，进行相同速率编码。w a n g 和o r c h a r d 【1 1 l 使用一种嵌 入式网格结构对高斯信源进行不对称编码，效果明显的改进。 自此以后，更多的信道编码技术都被应用到分布式信源编码问题。这些技术要 4 引言 求迭代译码，例如b a v e s i 柚网络或者v i t e r b i 解码器。当编码端逐渐变得非常简单 的时候，计算被转移到解码端，在解码端研究信源之间的统计特性。g a r d a f r i 鹤 和z l l a o 【1 厶1 虬，b a l c s y 和m i t r 一1 4 。“，均独立提出使用t u r b o 码进行二值信源压缩 方案，已经被证明的是基于t u r l ) o 码的方案能被用于统计独立的非二进制符号的压 缩和高斯信源以及独立信源。迭代的信道编码也能够通过在解码端进行信源和信 道特性统计，从而达到联合信源信道解码。 后来，b e m dg i r o d 等人【1 6 l 提出了基于像素和基于变换的视频编码系统，并研 究了适用于实际情况下的分布式视频编码系统。基于变换的编码系统与基于像素 的系统相似，解码器使用之前的重建帧来产生边信息，而不用运动补偿l 埘。 图1 3 为本文所提出的分布式视频编码框图，可以看出这是一种基于像素域的 帧内编码器和帧问解码器系统结构。与基于运动补偿混合编码相比，基于像素的 编码的复杂程度要低的多。编码器不需要运动估值和预测，也不需要d c r 和l d c t 。 在待编码的图像序列中等间隔地抽取一组帧，称为关键帧k ，如x ：。，x ：；。这 些关键帧编码和解码都可以采用传统的8 x 8 d c t 变换帧内编码方式，如h 2 6 3 的帧 内编码技术。在本系统中，直接将关键帧传输到接收端，并且认为关键帧可以无 失真的在接收端得到。 帧内编码 ：帧问解码 图1 3 分布式视频编码框图 f i g 1 0d i s t d b u t e dv i d e oc ( ，d i n gf h 脚 在关键帧之问的其它帧，称为w y l l e r - z i v 帧，如x 这些帧则采用帧内编码 方式和帧问解码方式，图中虚线左边为帧内编码方式，虚线右边为帧间解码方式。 w ”e r - z i v 帧在编码时先进行格型矢量量化( i q ) ，然后使用s l e p i a i i w b l f 编码 器进行编码。解码时利用边信息进行解码，边信息k ；由i i i 后关键帧平均内插而成。 5 北京交通人学硕十论文 边信息e ，再经过u ，q 量化得到和w y n e r - z i v 帧量化后得到相同的码流格式， s l e p j 翘w b l f 解码器结合边信息量化后的码流和接收到的奇偶校验位来恢复视频 流。如果解码器不能可靠的解出原始信号，它将通过反馈从编码器缓冲器中请求 额外的校验位。“请求和解码”的过程会不断重复，直到错误率可以接受为止。然 后将解码输出值进行l v q 反量化，重构得到j 。完成一次编译码过程。 本文将采用基于t u r b 0 和u ) p c 的s i e 口j a n 、v o i f 编解码器来构造整个系统， 具体实现将在以下几章介绍。 1 2 信道编码技术的发展 当信号在信道中传输的时候，常会因为这样或那样的因素使得在接收端收到 的信号与发送端发送的信号不同，从而在译码时产生差错。常见的信道错误有随 机错误和突发错误两种。随机错误是指错误的出现是随机的，一般而言错误出现 的位置是随机分布的，即各个码元是否发生错误是互相独立的，通常不是成片地 出现错误。这种情况一般是由信道的加性随机噪声引起的，因此，一般将具有此 特性的信道称为随机信道。而对于突发错误，错误的出现是一连串出现的。通常 在一个突发错误持续时闻内，开头和末尾的码元总是错的，中问的某些码元可能 错也可能对，但错误的码元相对较多。这种情况如移动通信中信号在某一段时间 内发生衰落，造成串差错；汽车发动时电火花干扰造成的错误；光盘上的一条 划痕等等，这样的信道称之为突发信道。然而还有些信道情况比较复杂，既有 突发错误又有随机差错，这种信道称之为混合信道。 根掘信道的输入输出的取值连续与否可以将其分为离散信道、连续信道和离 散输入连续输出信道；根据信道统计特性是否随时问改变可以将其分为平稳信道 和非平稳信道；根据信道的输出之间是否具有相关性可将其分为记忆信道和无记 忆信道；根据信道的特性对输入端是否具有对称性可以将其分为对称信道和非对 称信道。下面给出三种最简单、最常用的信道模型 1 - 二进制对称信道( b s c ) ：输入为二值变量o ，1 ，输出也为二值变量o ，l ，传输 过程中发生错误的概率与输入无关，即输入为0 输出为1 ( p ( 1 o ) 。p ) 或输 入为1 输出为0 ( p ( 0 1 ) ；p ) 的概率与输入无关。 2 二进制删除信道( b e c ) ：输入为二值变量o ，l ，输出或为输入的二值变量o ， 1 ，或为删除e ，且通常传输过程中不同输入被删除的概率相同。 3 二进制输入高斯信道f b n w g n ) ：输入为二值变量，输出为连续变量，且信道 中的加性噪声为服从( o ，62 1 的高斯随机变量。 图1 - 4 给出了以上三种信道的模型图。 6 引言 ：裹。：塞 h l 1 ) b s c x 高斯噪声 均 b i a g w n b e c 图1 - 4 三种常用信道模型 f i g 1 - 4t h r e cc o m i nc h 枷c lm o d e k 在许多通信系统中的比特误码率并不能满足实际的需求，因此必须采用信道 编码( 即纠错码) 才能将比特误码率进一步降低，以满足系统指标要求。纠错码 的基本实现方法是在发送端传输的信息后附上一些监督码元，编码后增加的多余 码元与信息码元之间以某种确定的规则相互关联( 约束) 。接收端按照既定的规则校 验信息码元与监督码元之问的关系，一旦传输发生差错，则信息码元与监督码元 的关系就受到破坏，从而接收端可以发现错误乃至纠正错误。因此，研究各种编 码和译码方法就是纠错码所要解决的问题。 1 9 4 8 年，香农( s h 柚n o n )在他的开创性论文“am a t h e m a t i c a lt h e o r yo f c o m m u n i c a t i o n ”中【1 8 】，首次阐明了在有扰信道中实现可靠通信的方法，提出了著名 的有扰纠错码定理，奠定了纠错码的基石。自此以后汉明( h a m m i n 蓟、斯列宾 ( s l e p i a n ) 、普兰奇( p r a n g e ) 等人在5 0 年代仞，根据s h a n n o n 的思想，给出了一系 列设计好码和有效译码的方法。以后，纠错码受到了越来越多的通信和数学工作 者，特别是代数学家的重视，使纠错码无论在理论还是在实际中得到飞速发展。 信道编码可以分为两个研究领域，即波形编码( 或称信号设计) 和结构化序列( 或 称结构冗余) 。波形编码( w a v e f 0 咖d i n g ) ，即将波形转变成“更好的波形”以减少 错误对检波过程的影响，如i f 交( o n h o g o n a l ) 编码和双正交惭_ o n h o g o n a l ) 编码。 结构化序列( s t n l c t u r c ds e q u c n c e ) 使“数据序列”转变成“更好的序列”，它采用结构 冗余( 也即冗余比特) ，这些冗余比特可以用来检测错误和纠正错误，如分组码， 卷积码。无论波形编码还是结构化序列，都是为了使编码后的信号比未编码的信 号具有更好的距离特性。迄今，纠错码已有五十多年的历史，其发展过程大致可 以分为以下几个阶段。 5 0 年代至6 0 年代仞，学者们主要研究各种有效的编、译码方法，奠定了线 性分组码的理论基础，提出了著名的b c h 码编、译码方法以及卷积码的序列译 码，给出了纠错码的基本码限，还出版了纠错码的第一本专著。 自6 0 年代至7 0 年代初，这是纠错码发展过程中最为活跃的时期。不仅提 7 北京交通大学硕十论文 出了许多有效的编译码方法，如门限译码、迭代译码、软判决译码等，而且注意 到纠错码的实用化问题，讨论了与实用有关的各种问题，如码的重量分布、译码 错误概率和信道模型化等，为纠错码的实用打下了咯实的基础。 7 0 年代初至8 0 年代，在理论上以戈帕( g o p p a ) 为首的一批学者，构造了一类 g o p p a 码，其中一类子码能达到s h a 蚰o n 在信道编码定理中所提出的码一s h a n n 曲 码所能达到的性能，这在纠错码历史上具有划时代意义。 自8 0 年代初以来，戈帕等人从几何观点讨论分析码，利用代数曲线构造了 一类代数几何码。代数几何码是一类范围非常广的码，在理论上已经证明它具有 优越的性能。现在，对代数几何码的研究方兴未艾。 9 0 年代出现的n f b o 码1 1 删，使人们可以在很低的信噪比下而得到较高的通 信可信度。t u r b 0 码，又称并行级联卷积码，它巧妙地将卷积码和随机交织器结合 在一起，实现了随机编码的思想，同时，采用软输出迭代译码1 2 l l 来逼近最大似然 译码。它是一种实用的信道编码，其性能非常逼近s h a n n o n 的性能界。它的出现， 标志着纠错码理论与技术研究进入了一个崭新的阶段，具有里程碑的意义。 t u r l ) 0 码的出现，引起全世界广泛关注，正是人们对t u r b o 码的深入研究， 才发现它其实就是一种u ) p c 码。l d p c 码是g a l i a g e r1 2 2 l 于1 9 6 2 年提出的一种 基于稀疏校验矩阵的线性分组码。由于种种原因，在当时并没有得到正确的认识， 并且之后的几十年，对它的研究几乎是停止的。现在u ) p c 码所表现出的优异性 能，已经重新引起学者们的热切关注，成为新的研究热点。 u ) p c 码1 8 冽是目日订人们发现的纠错性能最好的一种码，下面对u ) p c 码和 t u r b o 码进行了简要比较。简单的说，u ) p c 码比t u r b o 码区别在于，u ) p c 码是 一种线性分组码，采用b p 迭代译码；而t u r b o 码采用的是卷积码，译码方法主要 有m a p 类的算法和软输出v i t e r b i 算法的迭代译码。u ) p c 码理论极限性能优于 t u r b 0 码，给定1 2 码率条件下，采用b p s k 调制的高斯信道中两种编码方法的 纠错性能比较，l d p c 码比t u r b o 码更接近香农限，目前最优u ) p c 码方案具有 的s h a i l n o n 限仅有o 0 0 4 5 d b 。相对于t u r b o 码而言，l d p c 码具有更低的误码平层， 其描述简单，对严格的理论分析具有可验证性，吐量大，极具高速译码潜力。而 且因为u ) p c 码采用了并行的迭代译码算法，以及由于l i ) p c 码具有随机码特 性，在与信源或者信道级联时，不需要额外加交织器，系统的复杂度和延时都比 t u r b o 码要低。 作为提高数字传输可靠性的技术之一，纠错码在数字通信中得到了广泛的应 用。如在移动通信系统中，g s m 系统采用了奇偶校验码和卷积码，a m p s 及t a c s 系统采用了b c h 码；在卫星通信系统中，i n t e l s 灯，m a 系统采用了扩充的 ( 1 2 8 ，1 1 2 ) b c h 码，m a r i 汛氏海事卫星系统采用了缩短的( 6 3 ，6 9 ) b c h 码，s c p c 8 引言 卫星通信系统采用了码率为1 ，2 的卷积码；在计算机通信中，采用了简单检错码 和循环码；在数字微波系统中，尤其是大容量数字微波系统，采用了高码率的自 正交卷积码。因此说，在许多通信系统中，假设没有纠错码的存在，就无法顺利 的完成通信任务。正因为纠错码在现代数字通信系统中占有重要地位，长期以来， 各国专家对其进行了深入的研究，得到了许多性能良好的纠错码。 本文是考虑在等效二进制对称信道中，利用信道转移概率信息，对信源编解 码器进行联合优化设计，并在视频传输上做出仿真结果。信道编码采用t u r b o ， l d p c 码进行编码，提高d s c d v c 系统性能。 1 3 论文安排 本论文得到了国家自然科学基金( 卜o 9 0 6 0 4 0 3 2 ，6 0 3 7 3 0 2 8 ) ，高等学校 博士点基金，新世纪优秀人才支持计划和北京交大十五重大专项基金的资助。本 文具体安排如下： 第一章回顾了信源信道编码技术的发展，介绍了分布式信源编码理论，纠错 码理论以及信道模型理论，引出了本文所采用的分布式视频编码基本框图，为全 文的展开提供必要的背景知识。 第二章首先对t u r b o 基本编解码原理进行了阐述，从其编解码基本结构入手， 分析了t u r b o 性能表现优异的原因，归纳了t u f b o 码的核心思想。随后，详细介 绍了u ) p c 码的编解码原理，给出了具体的迭代思想过程图，总结了u ) p c 码的 应用场合和迸一步需要研究的方向。 第三章分别实现了基于t u r b o 码的分布式信源编码和分布式视频编码，并采用 了r c p t ( r a t cc 0 m p a t i b i ep u n c t u r c dt u f b oc o d e ) 以达到自适应码率目的，表明分布 式编码与传统信源编码方法相比，其优势在于编码器简单，有一定的压缩效果， 更适合于移动或便携式视频采集终端。 第四章实现了基于u ) p c 码的分布式信源编码和分布式视频编码，引入了 r c u ) p c ( r a t cc o m p a t i b l e l d p cc o d e ) 来获取灵活可变的码率，具体分析了实验过 程与方法，并与t u 加码方案进行比较。实验结果表明，本文d v c 结构的率失真 性能优于全i 帧的h 2 6 3 + 编码方法，编码方案简单，而与h 2 6 3 + 帧间编码方法 相比，仍有一定的差距，同时表明在帧间运动量较大的时候使用u ) p c 会略优于 1 r u r b 0 。 第五章给出了全文总结和工作展望。 9 现代纠错码原理 2 现代纠错码原理 2 1t u r b o 码的基本原理 t u r b o 码i “捌一种并行级联递归系统卷积码伊a r a l l e lc o n c a t c n a t e dr e c u r s i v e s y s t c m a t i cc o n v o l u t i o n a lc o d e ) ，最早由b e n d u ，g l a v i e u x 和n t i m a j s h i m a 在1 9 9 3 年的i c c 国际会议上提出的，因为这种译码结构类似于涡轮机的工作原理，所以 称之为t u r b o 码。仿真结果表明：若采用( 3 7 ，2 1 ) 的递归系统卷积码作为编码单 元，长度为6 5 5 3 6 的伪随机交织器，编码码率为1 2 ，在加性高斯自噪声( a w g n ) 信道上传输，接收端在经过迭代1 8 次译码后，误码率性能与香农理论极限性能只 差0 7 d b 。这引起了立即引起信息与编码理论界的轰动。 t u r l ) o 码之所以有如此优异的性能，得益于其巧妙的结构设计及译码方法的选 取。下面主要针对t u r b o 码编译码的基本原理加以说明及分析。 2 1 1t u r b o 码编码原理 1 9 4 8 年s h a n n o n 在他的经典论文“a m a l h e m a t i c a lt h e o r yo f c o m m u n i c a t i o n 中首 次提出了著名的信道编码定理，即对于有干扰的信道，存在一定的信道容量c ，只 要信息传输的速率不超过信道容量c ，就定存在种编码方法，使得译码错误率 ( 即误码率) 为 只e 一“i ” ( 2 1 ) 其中尺为信息传输速率，l 是编码码长，( 尺) 为可靠性函数，是r 的函数， 当r o 。同时给出了证明：如果一种分组码的编码方式满足以下三个 条件： ( 1 ) 采用随机性编译码方式； ( 2 ) 编译长度一。，即分组的码组长度无限； ( 3 ) 译码采用最佳的最大似然译码法( m d l ) 。 那么，信息可以在有干扰的信道中实现无差错的传输。上述三个条件为日后 的信道编码研究指明了方向，而t u r b o 码在编译码中集中体现了这思想。 图2 1 所示为t u r b o 码的典型编码器结构，其中r s c l 、r s c 2 是两个完全相 同的递归系统卷积码( r s c ) 编码器，这里，称其为编码单元。从图中可以看到， t u r b o 码在编码端将两个编码器通过交织器相连，并行编码，然后再对三路信号进 行复用，进而传输。此处交织器的采用，消除了两个子编码器问的相关性，由此 实现了编码的随机性。 1 1 北京交通大学硕士论文 输入 信息 图2 - 1 1 、l r b o 码编码器 f i g 2 1t u f i me n c o d e f 递归系统卷积码( r s c ) 能更好的满足各分量码中的信息互相利用，总的码重 更集中于平均码重附近，被大多数的设计方案选用。综合研究表明，对于有相同 约束长度的系统码和非系统码来说，虽然两者具有相同的最小自由距离，但是在 较低信噪比的信道中，前者的误码性能要略好一些。而且经过打孔算法后，系统 卷积码比非系统码具有更好的重量谱分布和更佳的误码率特性，并且在码率越高、 信噪比越低时其优势越明显。 交织器在t u r i ) o 码编码器中的主要作用是在不增加输出码重的情况下使有效 自由距离最大化，以提高整体编码性能。通常交织器对t u r l ) o 码性能的影响与交 织长度成正比，增加交织器的长度会使t u r b o 码的性能提高，也可以说交织器的 长度越长，交织器的性能越好。这是因为交织长度越长，相邻反馈信号的相关性 就越低，在解码端能更好的实现迭代译码。t ur 1 ) o 码交织器的结构主要分为两类， 一类是规则交织器，按照一定的规则映射来实现交织，如分组交织器等。最简单 的分组交织器规则，即是按行写入按列读出，因此也称为“行一列”交织器。另一类 是随机交织器，对于输入长度有限的序列实现完全随机是不可能的，因此基于随 机型准则设计的交织器也常称为伪随机交织器。随机交织器将信息序列以随机( 但 是固定) 的顺序读给第二个编码器。随机交织器在写入第一个分量编码器时，以信 息序列的本来次序写进存储器，然后交织器以随机方式将其重新排列，要注意的 是每一个比特只能读一次。每个信息位在交织后的位置是随机产生的，所以叫做 随机交织器。在分组长度比较小时，块交织器的性能比随机交织器略好，而在分 组长度比较大时，随机交织器的性能好。 t u r b o 码的编码过程为： 1 将信息比特流分成多组长度恒定为的比特序列； 现代纠错码原理 2 每一组比特序列记为d 一 。，d 2 ，如) ，输入到第一个编码单元r s c l 进 行编码，得到相应校验序列c 1 一( c u ，c 1 ，2 ，c l ) ； 3 同时d 一“，d ：，d ) 通过交织器进行交织后进入第二个编码单元r s c 2 进行编码，得到相应校验序列c 2 一( c 2 j ，c 2 | 2 ，c 2 3 ，c 2 ) ； 4 把系统位信息d - “。，d ：，九) 与经过删余的校验序列进行复接，最后得 到t u r b o 码的编码输出序列s o 。，s ：，) ，其中j 。一 。，c 。) ， d 。，c 。 0 ，1 。 2 1 2t u r b o 码译码原理 t u f b 0 码的译码算法主要有两大类。一类是基于最大后验概率( m a p ， m a x i m 岫a - p 0 s t e r i 嘶p r o b a b i l i t y ) 的软输出算法，其简化算法有：基于符号的最 大后验概率译码( l o g 。m a p ) ，即把标准m a p 算法中的参量用它们的对数形式表 示，把繁琐的指数和乘除运算转化为加减运算，降低复杂度。通过对l o g m a p 算 法中分支路径度量计算的简化，就得到了更简单的m a b g - m a p 算法。另一类 t u f b o 译码算法是基于v i t c r b i 算法( 、，a ，v i t e f b i g 面t h m ) 的软输出算法，通 常称为软输出v i t e r b i 算法( s o 、，a ，s o f to u t p u tv i t e r b i 砧g o r i t h m ) 1 4 。总体来 说，从算法复杂度分析，s o 最简单，l o g - m a p 最复杂，m a x l o g - m a p 居中； 从性能角度分析l d 母m a p 最好，s o ，a 最差。 图2 2 为t u r b o 码译码器框图。由图可以看到，t u r b o 码的译码器有丽个相 同的s i s o 译码单元组成，两个译码单元之f b j 通过交织器与去解交织器级联起来， 构成了一个具有反馈回路的循环迭代的译码结构，并且通过在这两个分量译码器 图2 - 2 t u f b 0 码译码器 f i g 2 _ 2 t u f b od e 。o d e r 匕京交通人学硕士论文 之间进行迭代译码，逐步的降低误码率，下面将结合m a p 算法来说明t u r b o 码的 译码原理： 因两个译码单元采用相同的译码算法，在译码原理的分折过程中，仅以单元 译码器d e c l 为例。送入译码单元d e c l 的除了接收到的系统位x 。和校验位序列 y 。之外，还有每一传输比特的先验信息上。，该先验信息是迭代译码过程中上一 次循环译码时d e c 2 的软输出外信息经过解交织后的信息。在初始译码时，表示 为“l ”码和“0 ”码出现的先验概率比值的对数，即： p “d萱n 上哦，l 卅0 9 吾产看 (