第五章无失真信源编码13ppt课件_第1页
第五章无失真信源编码13ppt课件_第2页
第五章无失真信源编码13ppt课件_第3页
第五章无失真信源编码13ppt课件_第4页
第五章无失真信源编码13ppt课件_第5页
已阅读5页,还剩46页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、信源编码器信源编码器 信源发出的消息符号集输出的码字集合输出的码字集合C C代码组)代码组)qSSSS,.,21qWWWC,.,21 信道的基本符号集合qxxxX,.,21ix信源符号信源符号Si Si 码码1 1 码码2 2 码码3 3 码码4 4 S1 00 0 0 0 S1 00 0 0 0 S2 01 01 11 S2 01 01 11 1010 S3 10 001 00 00 S3 10 001 00 00 S4 11 111 11 10 S4 11 111 11 10)()()()(43214321spspspspssssPSNNCSCS 码信源)11,01(),(21CSSS一个

2、分组码若对任意有限的整数一个分组码若对任意有限的整数N,N,其其N N次扩展码均为非奇异码,次扩展码均为非奇异码,则称为唯一可译码。则称为唯一可译码。 或每个信源符号序列映射成一个固定的码字,并且代码组中每或每个信源符号序列映射成一个固定的码字,并且代码组中每个码字只能唯一地被译成所对应的信源符号序列。个码字只能唯一地被译成所对应的信源符号序列。)1111,1101,0111,0101(),(221221112CSSSSSSSSS无需考虑后续的码符号即可从码符号序列中译出码字,这样无需考虑后续的码符号即可从码符号序列中译出码字,这样的唯一可译码称为即时码,又称非延时码。的唯一可译码称为即时码,

3、又称非延时码。树根树根一阶节点一阶节点二阶节点二阶节点 三阶节点(终端节点)A00011010111001000111110101100011010001码。码。 有一离散无记忆信源输出为N长符号序列,信道基本符号r个,信源输出符号个数为q,则存在唯一可译码的充要条件为: 为码字的长度lqrNl,rqNlqrNllog/logrqNLloglog由52log/32loglog/logrqNlqrNl)()()(2121qqNpppPS进行长度为进行长度为 的定长编码,的定长编码,rxxxX,21NS对对用码元集用码元集设离散无记忆信源设离散无记忆信源)()()(2121qqSpSpSpSSSP

4、S的熵为的熵为H(S)H(S),其,其N N次扩展次扩展对于对于, 0, 0只要满足只要满足)(logSHrNl( (正定理正定理) )则当则当N N足够大时,几乎可实现无失真信源编码,此时译码差错足够大时,几乎可实现无失真信源编码,此时译码差错小于小于。反之,假设反之,假设2)(logSHrNl则当则当N N足够大时,译码错误概率趋于足够大时,译码错误概率趋于1(1(编码误差任意大编码误差任意大) )(逆定理)(逆定理)l信源为信源为symbolbitXH/5)(symbolbitXH/4 . 1)(1log)(次扩展代码组的熵次扩展信源的熵lNrlSNH)(log, 1)()(SHrNlS

5、HSH此时最佳编码时,2iSIDN 2221 SHSIDNiiSID为自信息的方差为自信息的方差如果为最佳编码,那么如果为最佳编码,那么414321SSPS96. 0510求信源序列的长度。求信源序列的长度。允许错误概率允许错误概率7222212222222222221013. 4)1 ()()(4715. 0)()(log )(2)()( )()(2)()( )()(2)()( )()(2)()()()()(/811. 0)(NSHSIDNSHppSHSHSIESIESHSHSIESHSIESHSIESHSISHSIESHSIESIDSHiiiiiiiiiiiii则根据符号比特解:第三节第三

6、节 离散无记忆信源的变长编码离散无记忆信源的变长编码 设信源符号集为设信源符号集为),(21qSSSS不等式)kraftrqili(11其分别对应码长为其分别对应码长为l1,l2,lql1,l2,lq,则即时码存在的充要条件,则即时码存在的充要条件是:是:),(21qwwwW对信源进行编码,相应的码字集为对信源进行编码,相应的码字集为),(21rxxxX码符号集为码符号集为不等式)McMillanrqili(11 在满足kraft不等式的条件下,唯一可译码存在的充要条件是: 设设S0S0为原始码字的集合。再构造一系列集合为原始码字的集合。再构造一系列集合S1,S2,SnS1,S2,Sn。构造构

7、造S1,S2, SnS1,S2, Sn的方法:的方法: 1 1、首先考察、首先考察S0S0中所有的码字。若码字中所有的码字。若码字WjWj是码字是码字WiWi的前缀,的前缀,即即Wi = WjAWi = WjA,则将后缀,则将后缀A A列为列为S1S1中的元素,中的元素,S1S1就是由所有具就是由所有具有这种性质的有这种性质的A A构成的集合。构成的集合。 2 2、当、当n1n1,则将,则将S0S0于于Sn-1Sn-1比较,看是否比较,看是否S0S0中的码字是中的码字是Sn-1Sn-1的前缀,如果是,则取后缀为的前缀,如果是,则取后缀为SnSn中元素,且看中元素,且看Sn-1Sn-1中码字中码

8、字是否为是否为S0S0中码字的前缀,如果是,则取后缀为中码字的前缀,如果是,则取后缀为SnSn中元素,中元素,如此构成集合如此构成集合SnSn。 S0 S1 S2 S3 S4 S5 S6 S7 S8 S0 S1 S2 S3 S4 S5 S6 S7 S8 a d eb de b ad d eb 0 a d eb de b ad d eb 0 c bb cde bcde c bb cde bcde ad ad abb abb bad bad deb deb bbcde bbcde,7654321aaaaaaa,bbcdedebbadabbadca信源符号码元/)(1qiiilspl平均每个码元载荷

9、的信息量平均每个码元载荷的信息量 = = 信道的信息传输率信道的信息传输率R R码符号比特/)(lSHR 秒比特信道的信息传输速率/)(tlSHRt 信源编码目的:提高信道信息传输率R,充分利用信道= = 信道中平均每个符号所能传送的信息量信道中平均每个符号所能传送的信息量l 对于某一信源和某一码元集,若有一种唯一可译码,其平对于某一信源和某一码元集,若有一种唯一可译码,其平均长度均长度 小于所有其他的唯一可译码,则称此码为最佳码小于所有其他的唯一可译码,则称此码为最佳码(紧致紧致码码)。NrSHNLrSHN1log)(log)(则总可以找到一种编码方法构成唯一可译码,使信源则总可以找到一种编

10、码方法构成唯一可译码,使信源S S中的每中的每个信源符号所需的码字与平均长度满足个信源符号所需的码字与平均长度满足 有一离散无记忆信源S=Si(i=1,2,q),输出符号为q个,其熵为H(S),它的N次扩展信源),.,2 , 1(NiNqiS)()(SNHSHNNS其熵其熵, ,若用若用r r个码元对个码元对信源进行编码信源进行编码其中,其中, 为为 中每个信源符号序列中每个信源符号序列 编码所对应的码字的平编码所对应的码字的平均码长。均码长。NLNSiNqiiiiiNpL1,)(所对应的码字的长度为所对应的平均码长中每个信源符号离散无记忆信源iNSSNL:NLN)(log)(SHrSHr变长

11、编码定理说明:若编码的平均码长变长编码定理说明:若编码的平均码长小于信源的熵则唯一可译码不存在。同时指出:要做到无失真的信源编码,变换每个信源符号平均所需要最少的r进制码符号数,就是原始信源的熵值以r为底的);如果编码的平均码长小于原始信源的熵值,则唯一可译码不存在,此时,译码必然带来失真。 )(SHrrRlog当平均码长为时,编码后的信道的信息传输率此时有: 比特/符号信道的信息传输率R=无损信道的信道容量C 可知此时:R达到最大值,实现信源与信道的统计匹配。 变长编码定理还表明:在无失真信源编码中,采用扩展信源的手变长编码定理还表明:在无失真信源编码中,采用扩展信源的手段,虽然可以减少每一

12、个信源符号所需要的平均码符号数,使编段,虽然可以减少每一个信源符号所需要的平均码符号数,使编码的有效性提高,但无论如何扩展,其有效性是有限度的,其极码的有效性提高,但无论如何扩展,其有效性是有限度的,其极限值即是信源的熵值。限值即是信源的熵值。rlSHlSHrlog)()(码的剩余度码的剩余度=1-=1-414321SSPSsymbolbitSH/811. 0)(1, 021SS21/1)(iiillSpl信源符号码元则811. 0)()(2lSHlSHr编码效率码元信道信息传输率/811. 0)(bitlSHR解解:(1) :(1) 用用00,11对之进行编码,有对之进行编码,有 16116

13、3163169221221112 SSSSSSSSPS111110100用树图构造即时码为信源序列码元/332116271611631631692l信源符号码元 /32/272/2 ll961. 0811. 0)(3227lSHr编码效率码元信道信息传输率/961. 0)(bitlSHR为了编成唯一可译码,首先计算第为了编成唯一可译码,首先计算第i i个消息的累加概率个消息的累加概率11)(iKKiSpp1)(log)(logiiiSplSp11100. 090. 01011. 070. 00110. 040. 0000. 004321pppp信源符号码符号编码的平均码长/40.2)(41ii

14、ilSpl码符号比特信道的信息传输率/796.0)(lSHR796.0log)(rlSH编码效率用用0 0,1 1码符号分别代表概率最小的两个信源符号,并将这两码符号分别代表概率最小的两个信源符号,并将这两个概率最小的信源符号合并成一个,从而得到只包含个概率最小的信源符号合并成一个,从而得到只包含q-1q-1个符个符号的新信源号的新信源S1,S1,称为缩减信号源。称为缩减信号源。编码对其进行二元HuffmanSSSSSPS1 . 01 . 02 . 02 . 04 . 054321信源符号信源符号Si Si 概率概率p(Si) p(Si) 编码过程编码过程 码字码字Wi Wi 码码长长lili

15、 S1 S1 S2 S3S2 S3 S1 0.4 S1 0.4 S2 0.2 S2 0.2 S3 0.2 S3 0.2 S4 0.1 S4 0.1 S5 0.1 S5 10101001451/2 . 2)(iiilSpl信源符号码元则平均码长0A01001110100000100011信源符号比特/123. 2)(log)()(51iiiSpSpSH码符号比特信道的信息传输率/965. 0)(lSHR965. 0)(lSHr编码效率 码字码字Wi Wi 码长码长l l i i S1 0.4 0.4 S1 0.4 0.4 0.4 0.6 00 20.4 0.6

16、 00 2 S2 0.2 0.2 S2 0.2 0.2 0.4 0.4 10 20.4 0.4 10 2 S3 0.2 0.2 S3 0.2 0.2 0.2 11 20.2 11 2 S4 0.1 0.2 S4 0.1 0.2 010 3010 3 S5 0.1 S5 0.1 011 3011 301010101A00111000101101010011965. 0/2 . 2编码效率信源符号码元平均码长l比第一种好。由此可见,第二种质量差现在讲的哈夫曼码的方差先前讲的哈夫曼码的方16. 036. 1)()(22211222LLqiiiLllSplliE结论:当进行哈夫曼编码时,为了得到质量好

17、结论:当进行哈夫曼编码时,为了得到质量好的码,应使合并的信源符号位于缩减信源序列的码,应使合并的信源符号位于缩减信源序列尽可能高的位置,这样可充分利用短码。尽可能高的位置,这样可充分利用短码。同,用码方差表示:而他们的质量不完全相和编码效率码长两种编码有相同的平均l r r元哈夫曼码可由二元哈夫曼码的编码方法推广得到。只元哈夫曼码可由二元哈夫曼码的编码方法推广得到。只是编码过程中构成缩减信源时,每次将是编码过程中构成缩减信源时,每次将r r个概率最小的符号合个概率最小的符号合并,并分别用并,并分别用0 0,1 1,r-1r-1码元表示。码元表示。 为了充分利用短码,使哈夫曼码的平均码长最短,必

18、须为了充分利用短码,使哈夫曼码的平均码长最短,必须是最后一个缩减信源有是最后一个缩减信源有r r个信源符号。因此,对于个信源符号。因此,对于r r元哈夫曼码,元哈夫曼码,信源信源S S的符号个数的符号个数q q必须满足必须满足为非负整数表示信源缩减的次数,其中rrq) 1( 如果信源S的符号个数q不满足上式,则增补一些概率为0的信源符号。025. 0025. 005. 02 . 03 . 04 . 0654321SSSSSSPS码元集码元集X=(0,1,2)X=(0,1,2),对,对S S进行进行3 3元哈夫曼编码。元哈夫曼编码。0)(72323) 1(77SpSqqrrrq则增补信源符号信源

19、符号 概率概率 编码过程编码过程 码字码字Wi Wi 码长码长li li Si p(Si) S1 Si p(Si) S1 S2 Wi li S2 Wi li S1 0.4 0.4 S1 0.4 0.4 0.4 0 10.4 0 1 S2 0.3 0.3 S2 0.3 0.3 0.3 2 10.3 2 1 S3 0.2 0.2 S3 0.2 0.2 0.3 10 20.3 10 2 S4 0.05 0.05 S4 0.05 0.05 12 212 2 S5 0.025 0.05 S5 0.025 0.05 110 3110 3 S6 0.025 S6 0.025 111 3111 3 S7 0

20、S7 0 112 3112 321021021061/35. 1)(iiilSpl信源符号码元其平均码长霍夫曼编码的特点:霍夫曼编码的特点: 1由于霍夫曼编码总是以最小概率相加的方法来缩减参与皮埃对的概率个数,因此概率越小,对缩减的贡献越大,其对应消息的码字也越长。2最小概率相加的方法使得编码不具有唯一性,尤其是碰到存在几个消息符号有着相同概率的情况,将会有多种路径选择,即既具有多种可能的代码组集合。3尽管对同一信源存在着多种结果的霍夫曼编码,但它们的平均码长几乎都是相等的,因为每一种路径选择都是使用最小概率相加的方法,其实质都是遵循最佳编码的原则,因此霍夫曼编码是最佳编码。 霍夫曼编码存在的

21、问题:霍夫曼编码存在的问题: 1霍夫曼编码要求信源消息概率已知或可估计。由于初始信源不可能总是统计好了概率,为此编码之前必须先估算信源的统计特性。在信源具有记忆性能并用霍夫曼编码来表示信源的扩展输出时,概率的估计很耗费时间。2霍夫曼编码是建立在编码器和译码器都知道码树结构的基础上的,如果信源消息数目变大,则树型结构的大小和算法的复杂性会呈指数规律增加。 例例5-105-10:待编码的字符序列为:待编码的字符序列为:abaaaabaabaaabbbbbbbabbbbbaababaababa.,abaaaabaabaaabbbbbbbabbbbbaababaababa.,试用试用Lemple-Le

22、mple-ZivZiv方法给出编码结果。方法给出编码结果。 编码结果0a0b1a3b4a4b2b7b1b8b5b11b地址123456789101112码段内容abaaaabaabaaabbbbbbbabbbbbaababaababa由此可知:Lemple-Ziv编码利用了已编码信息进行当前的编码,编码结果是等长码,编码过程就是建立码地址和将待编码消息序列分段的过程,所有的码段内容都是不同的。 2 .08 .0)(21sssps1 104. 016. 016. 064. 0)(2212211122sssssssssps信源符号二元符号符号序列二元符号/78. 0/56. 12ll008. 00

23、32. 0032. 0032. 0128. 0128. 0128. 0512. 0)(22212221211222112121111133sssssssssssssssssssssssssps信源符号二元符号符号序列二元符号/728. 0/184. 23ll一一. .游程编码游程编码1.1.游程编码的基本原理游程编码的基本原理 游程编码是哈夫曼编码的一种改进和应用,游程编码是哈夫曼编码的一种改进和应用,主要用于黑白二值文件的传真。主要用于黑白二值文件的传真。 表示背景白色时像素为码元表示背景白色时像素为码元“0”0”,表,表示内容黑字像素为码元示内容黑字像素为码元“1”1”。 对大量出现的连对

24、大量出现的连“0 0或连或连“1”1”(黑或白(黑或白像素序列在传输时,可通过像素类别黑、白像素序列在传输时,可通过像素类别黑、白像素加重复次数的方式来加以表示,由此思像素加重复次数的方式来加以表示,由此思路构成的一种编码方式即是游程编码路构成的一种编码方式即是游程编码RLCRLC)。)。重复出现的同类像素的长度称为游程长度重复出现的同类像素的长度称为游程长度RunLengthRunLength)。)。规定第一个游程为白游程。规定第一个游程为白游程。 第五节第五节 实用的信源编码方法实用的信源编码方法 MH MH码是国际电话电报咨询委员会提出的文件、传真类一维数据压缩码是国际电话电报咨询委员会

25、提出的文件、传真类一维数据压缩编码的国际标准,是由游程编码和哈夫曼编码相结合而成的一种改进型编码的国际标准,是由游程编码和哈夫曼编码相结合而成的一种改进型哈夫曼码哈夫曼码. .其具体编码规则为:其具体编码规则为: 游程长度在游程长度在0 06363之间时,码字直接由相应的终止码之间时,码字直接由相应的终止码表示。表示。 游程长度在游程长度在646417281728之间时,码字由一个形成组之间时,码字由一个形成组合合) )码加上一个终止码构成。码加上一个终止码构成。 每行必须以白游程开始,以一个同步码每行必须以白游程开始,以一个同步码EOLEOL结束,且结束,且每页文件也必须以同步码每页文件也必

26、须以同步码EOLEOL开始用以清洗系统,开始用以清洗系统,防止误差扩散)。防止误差扩散)。 每行游程总和必须为每行游程总和必须为17281728个像素,否则该行出现错个像素,否则该行出现错误。误。 为了达成同步操作,每行编码的传输时间最短为为了达成同步操作,每行编码的传输时间最短为20ms20ms,最长为,最长为5s5s;不足;不足20ms20ms的行,需的行,需EOLEOL码之前填入码之前填入足够的足够的“0 0码元。码元。 连续连续6 6个个EOLEOL表示文件页传输的结束。表示文件页传输的结束。按编码规则,一页文件传真编码的最终格式如图所示。按编码规则,一页文件传真编码的最终格式如图所示

27、。 页首填充码页尾tTtTTTEOLEOLEOLEOL6个EOL数据数据数据数据数据其中,其中,EOLEOL是行同步码,其码字为是行同步码,其码字为00000000000010000000000001,在正常的,在正常的游程编码数据中不可能出现连游程编码数据中不可能出现连1111个个0 0,故,故EOLEOL能够在出现突发能够在出现突发差错时,重新建立行同步,控制差错不扩散到下一行,同时差错时,重新建立行同步,控制差错不扩散到下一行,同时每一页结束时,转回控制每一页结束时,转回控制RTCRTC由由6 6个个EOLEOL组成。组成。白游程白游程黑游黑游程程白游程白游程黑游程黑游程白游程白游程黑游

28、程黑游程 码是一种改进码,与前面介绍的哈夫曼码存在的两点差异: 码的编码表是由各类文件的平均统计特性指标得到的,并且固定不变,因而多数情况下,码并非紧致码最佳码)。 游程的码字由形成码和终止码组成,可使码字大大缩短。具体编码过程如下:具体编码过程如下: 从信源符号全序列出发,将各信源序列依累积概率分布从信源符号全序列出发,将各信源序列依累积概率分布函数的大小映射到函数的大小映射到,区间区间,将将,区间分成许多区间分成许多互不重叠的小区间。此时每个符号序列均有一个小区间与之互不重叠的小区间。此时每个符号序列均有一个小区间与之对应,因而可在小区间内取点来代表该符号序列。对应,因而可在小区间内取点来代表该符号序列。)(1logplilil)(sPs)()(),(spsPsPssr

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论