《信息论与编码课件第四章优秀课件.ppt》由会员分享，可在线阅读，更多相关《信息论与编码课件第四章优秀课件.ppt（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息论与编码课件第四章第1页，本讲稿共35页第四章第四章 作业作业教材第教材第116116页页 117117页页 4.24.2，4.8(1)(3)4.8(1)(3)第2页，本讲稿共35页编码器编码器S=（s1，s2，sq）C=（W1，W2，Wq）X=（x1，x2，xr）信源信源符号符号码字码字码符号码符号编码器编码器 第3页，本讲稿共35页码：特定的符号集合。码：特定的符号集合。编码：建立在源符号与码符号或码符号组编码：建立在源符号与码符号或码符号组之间的变换。之间的变换。3 5 4 73 5 4 7011101100111011101100111信源编码：从信源输出符号序列到码符号信源编码：
2、从信源输出符号序列到码符号序列的一种映射，其逆映射称译码。序列的一种映射，其逆映射称译码。信源编码的目的：适合于信道传输，提高信源编码的目的：适合于信道传输，提高输出效率输出效率编码器编码器第4页，本讲稿共35页编码器编码器同价码同价码 非同价码非同价码非奇异码非奇异码奇异码奇异码不等长码不等长码等长码等长码信源符号si 出现概率pi 码 A 码 B码 Cs1p10000s2p20101s3p310100s4p4111011第5页，本讲稿共35页等长编码及其定理等长编码及其定理唯一可译码：一个码的任意一串有限长的码符号序列只唯一可译码：一个码的任意一串有限长的码符号序列只唯一可译码：一个码的任
3、意一串有限长的码符号序列只唯一可译码：一个码的任意一串有限长的码符号序列只 能被唯一地译成所对应的信源符号序列。能被唯一地译成所对应的信源符号序列。能被唯一地译成所对应的信源符号序列。能被唯一地译成所对应的信源符号序列。ak p(ak)码A 码B a1 0.5 00 00 a2 0.25 01 01 a3 0.125 10 00 a4 0.125 11 10等长非奇异码一定是唯一可译码等长非奇异码一定是唯一可译码等长非奇异码一定是唯一可译码等长非奇异码一定是唯一可译码第6页，本讲稿共35页对信源对信源对信源对信源S S的的的的N N次扩展信源次扩展信源次扩展信源次扩展信源S SN N进行等长编
4、码进行等长编码进行等长编码进行等长编码若若若若S S=s s1 1,s s2 2,s sq q，则，则，则，则N N N N次扩展信源次扩展信源次扩展信源次扩展信源S S N N=a a1 1,a a2 2,a aqNqN，共有，共有，共有，共有q qN N个符号序列。个符号序列。个符号序列。个符号序列。设码符号集为设码符号集为设码符号集为设码符号集为X X=x x1 1,x x2 2,x xr r，长度为，长度为，长度为，长度为l l 的码符号序列的码符号序列的码符号序列的码符号序列WWi i=(=(x xi i1 1 x xi i2 2 x xil il),),x xi i1 1,x xi
5、 i2 2,x xil ilX X。若要求编得的等长码是唯一可译码则必须满足若要求编得的等长码是唯一可译码则必须满足 q q Nr l l 等长编码及其定理等长编码及其定理第7页，本讲稿共35页对对对对 q Nr r l 两边取对数，则得两边取对数，则得两边取对数，则得两边取对数，则得N N loglogq q l l loglogr r 或或或或例例例例如如如如英英英英文文文文电电电电报报报报有有有有3232个个个个符符符符号号号号（2626个个个个英英英英文文文文字字字字母母母母加加加加上上上上6 6个个个个字字字字符符符符），即即即即q q =3232。若若若若r r =2 2，N N
6、=1=1(即即即即对对对对信信信信源源源源的的的的逐逐逐逐个个个个符符符符号号号号进进进进行行行行二二二二进进进进制制制制编编编编码码码码)，则，则，则，则等长编码及其定理等长编码及其定理第8页，本讲稿共35页定理定理4.14.1（等长信源编码定理）（等长信源编码定理）对于上述编码，对于任意对于上述编码，对于任意 ，只要，只要 N 充充分大，且满足不等式分大，且满足不等式则译码错误概率任意小（可以进行无失真编则译码错误概率任意小（可以进行无失真编码）。码）。反之，若反之，若则不可能进行无失真编码，且则不可能进行无失真编码，且N 充分大时，译充分大时，译码错误概率近似等于码错误概率近似等于1 1
7、。第9页，本讲稿共35页实现无失真编码实现无失真编码实现无失真编码实现无失真编码存在问题：存在问题：存在问题：存在问题：N N 充分大使存储和处理难度大。充分大使存储和处理难度大。充分大使存储和处理难度大。充分大使存储和处理难度大。解决办法：采用变长编码。解决办法：采用变长编码。解决办法：采用变长编码。解决办法：采用变长编码。等长信源编码定理的意义：等长信源编码定理的意义：等长信源编码定理的意义：等长信源编码定理的意义：信源的信息熵信源的信息熵信源的信息熵信源的信息熵是（是（是（是（信源冗余度的可压缩性）信源冗余度的可压缩性）信源冗余度的可压缩性）信源冗余度的可压缩性）无失无失无失无失真数据压
8、缩的理论极限。压缩到小于这个极限值，则真数据压缩的理论极限。压缩到小于这个极限值，则真数据压缩的理论极限。压缩到小于这个极限值，则真数据压缩的理论极限。压缩到小于这个极限值，则无失真做不到。无失真做不到。无失真做不到。无失真做不到。等长编码定理等长编码定理第10页，本讲稿共35页不等长编码及其定理不等长编码及其定理不等长编码的基本思想不等长编码的基本思想不等长编码的基本思想不等长编码的基本思想“量体裁衣量体裁衣量体裁衣量体裁衣”出现概率出现概率出现概率出现概率大大大大的信源符号用的信源符号用的信源符号用的信源符号用较短码较短码较短码较短码字表示，出现概率字表示，出现概率字表示，出现概率字表示，
9、出现概率小小小小的信源符的信源符的信源符的信源符号用号用号用号用较长码较长码较长码较长码字表示。这样平均每个信源符号所需的码符号数降低，字表示。这样平均每个信源符号所需的码符号数降低，字表示。这样平均每个信源符号所需的码符号数降低，字表示。这样平均每个信源符号所需的码符号数降低，提高编码效率。提高编码效率。提高编码效率。提高编码效率。唯一可译码：一个码的任意一串有限长的码符号序列唯一可译码：一个码的任意一串有限长的码符号序列唯一可译码：一个码的任意一串有限长的码符号序列唯一可译码：一个码的任意一串有限长的码符号序列 只能被唯一地只能被唯一地只能被唯一地只能被唯一地译成所对应的信源符号序列。译成
10、所对应的信源符号序列。译成所对应的信源符号序列。译成所对应的信源符号序列。即时码：唯一可译码，译码时无需参考后续的码符号就能立即作出译码即时码：唯一可译码，译码时无需参考后续的码符号就能立即作出译码即时码：唯一可译码，译码时无需参考后续的码符号就能立即作出译码即时码：唯一可译码，译码时无需参考后续的码符号就能立即作出译码判断。判断。判断。判断。异前缀码：码中没有码字是任意其他码字的前缀。可以在无延时的情况异前缀码：码中没有码字是任意其他码字的前缀。可以在无延时的情况异前缀码：码中没有码字是任意其他码字的前缀。可以在无延时的情况异前缀码：码中没有码字是任意其他码字的前缀。可以在无延时的情况下解码
11、。下解码。下解码。下解码。异前缀码等价于即时码异前缀码等价于即时码异前缀码等价于即时码异前缀码等价于即时码第11页，本讲稿共35页不等长编码及其定理不等长编码及其定理第12页，本讲稿共35页例：例：例：例：p(ap(ak k)码码码码A A 码码码码B B 码码码码C C 码码码码D D a a1 1 0.5 0 0 0 00.5 0 0 0 0 a a2 2 0.25 0 10 01 100.25 0 10 01 10 a a3 3 0.125 1 00 011 110 0.125 1 00 011 110 a a4 4 0.125 10 01 0111 11100.125 10 01 01
12、11 1110 码码码码A A：奇异，非唯一；：奇异，非唯一；：奇异，非唯一；：奇异，非唯一；码码码码B B：非奇异，非唯一；：非奇异，非唯一；：非奇异，非唯一；：非奇异，非唯一；码码码码C C：唯一，非异前缀；：唯一，非异前缀；：唯一，非异前缀；：唯一，非异前缀；码码码码D D：唯一，异前缀，即时码。：唯一，异前缀，即时码。：唯一，异前缀，即时码。：唯一，异前缀，即时码。不等长编码及其定理不等长编码及其定理第13页，本讲稿共35页 异前缀码是唯一可译码中的一类子码，易于构造。异前缀码是唯一可译码中的一类子码，易于构造。异前缀码是唯一可译码中的一类子码，易于构造。异前缀码是唯一可译码中的一类子
13、码，易于构造。异前缀码等价于即时码。异前缀码等价于即时码。异前缀码等价于即时码。异前缀码等价于即时码。即任何一种唯一可译码都可找到相应、同样有效的异即任何一种唯一可译码都可找到相应、同样有效的异即任何一种唯一可译码都可找到相应、同样有效的异即任何一种唯一可译码都可找到相应、同样有效的异前缀码。前缀码。前缀码。前缀码。不等长编码及其定理不等长编码及其定理树图法是构造即树图法是构造即树图法是构造即树图法是构造即时码（异前缀码）时码（异前缀码）时码（异前缀码）时码（异前缀码）的一种简单方法。的一种简单方法。的一种简单方法。的一种简单方法。220 221 22210 11 12 20 210一级节点一
14、级节点二级节点二级节点三级节点三级节点120树根树根中间节点不能中间节点不能作为码字的终点作为码字的终点第14页，本讲稿共35页定理定理定理定理4.2 4.2 设信源设信源设信源设信源S S=s s1 1,s s2 2,s sq q，码符号集，码符号集，码符号集，码符号集X X=x x1 1,x x2 2,x xr r，又设码字为（又设码字为（又设码字为（又设码字为（WW1 1，WW2 2，WWq q），其分别对应的码长为），其分别对应的码长为），其分别对应的码长为），其分别对应的码长为l l1 1，l l2 2，l lq q，则存在唯一可译码的充要条件为，则存在唯一可译码的充要条件为，则存在
15、唯一可译码的充要条件为，则存在唯一可译码的充要条件为KraftKraft不等式不等式 定理给出了码字长度的下界的限制。定理给出了码字长度的下界的限制。第15页，本讲稿共35页例：例：例：例：p(ap(ak k)码码码码A A 码码码码B B 码码码码C C 码码码码D D a a1 1 0.5 0 0 1 10.5 0 0 1 1 a a2 2 0.25 11 10 11 01 0.25 11 10 11 01 a a3 3 0.125 00 00 100 001 0.125 00 00 100 001 a a4 4 0.125 11 01 1010 00010.125 11 01 1010
16、0001r r2 2，码，码，码，码A A，码，码，码，码B B：l l1 1=1,=1,l l2 2=l l3 3=l l4 4=2,=2,这样码这样码这样码这样码A A，码，码，码，码B B不可能是唯一可译码。不可能是唯一可译码。不可能是唯一可译码。不可能是唯一可译码。r r2 2，码，码，码，码C C，码，码，码，码D D：l l1 1=1,=1,l l2 2=2,=2,l l3 3=3,=3,l l4 4=4,=4,码码码码C C不是唯一可译码，码不是唯一可译码，码不是唯一可译码，码不是唯一可译码，码D D是唯一可译码。是唯一可译码。是唯一可译码。是唯一可译码。第16页，本讲稿共35页
17、信源编码有关概念信源编码有关概念信源编码有关概念信源编码有关概念（1 1）平均码长）平均码长）平均码长）平均码长单位：码符号单位：码符号单位：码符号单位：码符号/信源符号信源符号信源符号信源符号意义：每个源符号平均需要的码符号数。意义：每个源符号平均需要的码符号数。意义：每个源符号平均需要的码符号数。意义：每个源符号平均需要的码符号数。编码后每个信源符号平均用编码后每个信源符号平均用编码后每个信源符号平均用编码后每个信源符号平均用 个码符号表示。个码符号表示。个码符号表示。个码符号表示。（2 2）信息传输率（平均每个码符号携带的信息量）信息传输率（平均每个码符号携带的信息量）信息传输率（平均每
18、个码符号携带的信息量）信息传输率（平均每个码符号携带的信息量）越短，信息传输率就越高。越短，信息传输率就越高。越短，信息传输率就越高。越短，信息传输率就越高。第17页，本讲稿共35页（3 3）最佳码（紧致码）最佳码（紧致码）最佳码（紧致码）最佳码（紧致码）最佳码：对于某一信源和某一码符号集，若有一唯一可最佳码：对于某一信源和某一码符号集，若有一唯一可最佳码：对于某一信源和某一码符号集，若有一唯一可最佳码：对于某一信源和某一码符号集，若有一唯一可 译码，其平均码长小于等于所有其他唯一可译译码，其平均码长小于等于所有其他唯一可译译码，其平均码长小于等于所有其他唯一可译译码，其平均码长小于等于所有其
19、他唯一可译 码的平均码长，则该码称为最佳码。码的平均码长，则该码称为最佳码。码的平均码长，则该码称为最佳码。码的平均码长，则该码称为最佳码。（最短唯一可译码）（最短唯一可译码）（最短唯一可译码）（最短唯一可译码）无失真信源编码的基本问题就是找到无失真信源编码的基本问题就是找到无失真信源编码的基本问题就是找到无失真信源编码的基本问题就是找到最佳码最佳码最佳码最佳码，最，最，最，最佳码的平均码长为理论极限。佳码的平均码长为理论极限。佳码的平均码长为理论极限。佳码的平均码长为理论极限。理论极限是多少呢？理论极限是多少呢？第18页，本讲稿共35页定理定理定理定理4.34.3（单符号信源的变长编码定理）
20、（单符号信源的变长编码定理）（单符号信源的变长编码定理）（单符号信源的变长编码定理）若若若若有有有有一一一一离离离离散散散散无无无无记记记记忆忆忆忆信信信信源源源源S S 具具具具有有有有熵熵熵熵HH（S S），并并并并有有有有r r个个个个码码码码符符符符号号号号的的的的符符符符号号号号集集集集X X=x x1 1,x x2 2,x xr r，则则则则总总总总可可可可以以以以找找找找到到到到一一一一种种种种无无无无失失失失真真真真编编编编码方法，构成唯一可译码，使其平均码长满足码方法，构成唯一可译码，使其平均码长满足码方法，构成唯一可译码，使其平均码长满足码方法，构成唯一可译码，使其平均码长
21、满足证明：证明：证明：证明：第19页，本讲稿共35页第20页，本讲稿共35页定理定理定理定理4.4 4.4 4.4 4.4（变长无失真信源编码定理（变长无失真信源编码定理（变长无失真信源编码定理（变长无失真信源编码定理-香农第一定理香农第一定理香农第一定理香农第一定理）离离离离散散散散无无无无记记记记忆忆忆忆信信信信源源源源S S S S的的的的N N N N次次次次扩扩扩扩展展展展信信信信源源源源S S S SN N N N=a a a a1 1 1 1,a a a a2 2 2 2,a a a aqNqNqNqN ，共共共共有有有有q q q qN N N N个个个个符符符符号号号号序序序
22、序列列列列，具具具具有有有有熵熵熵熵H H H H（S S S SN N N N），并并并并有有有有r r r r个个个个码码码码符符符符号号号号的的的的符符符符号号号号集集集集X X X X=x x x x1 1 1 1,x x x x2 2 2 2,x x x xr r r r 。若若若若对对对对信信信信源源源源S S S S N N N N（即即即即信信信信源源源源输输输输出出出出的的的的是是是是N N N N长长长长的的的的符符符符号号号号序序序序列列列列）进进进进行行行行编编编编码码码码，总总总总可可可可以以以以找找找找到到到到一一一一种种种种编编编编码码码码方方方方法法法法，构构构
23、构成成成成唯唯唯唯一一一一可可可可译译译译码码码码，使使使使信信信信源源源源S S S S中中中中每每每每个个个个信信信信源符号所需的码字平均长度满足源符号所需的码字平均长度满足源符号所需的码字平均长度满足源符号所需的码字平均长度满足香农第一定理香农第一定理第21页，本讲稿共35页由香农第一定理得到平均码长的理论极限：由香农第一定理得到平均码长的理论极限：由香农第一定理得到平均码长的理论极限：由香农第一定理得到平均码长的理论极限：HH(S S)/log)/logr r香农第一定理香农第一定理第22页，本讲稿共35页由香农第一定理得到平均码长的理论极限：由香农第一定理得到平均码长的理论极限：由香
24、农第一定理得到平均码长的理论极限：由香农第一定理得到平均码长的理论极限：HH(S S)/log)/logr r香农第一定理的物理意义香农第一定理的物理意义R R R R等于无噪无损信道的信道容量等于无噪无损信道的信道容量等于无噪无损信道的信道容量等于无噪无损信道的信道容量C C C C。无失真信源编码的实质无失真信源编码的实质无失真信源编码的实质无失真信源编码的实质：对离散信源进行适当的变换，使变：对离散信源进行适当的变换，使变：对离散信源进行适当的变换，使变：对离散信源进行适当的变换，使变换后新的码符号信源（信道的输入信换后新的码符号信源（信道的输入信换后新的码符号信源（信道的输入信换后新的
25、码符号信源（信道的输入信源）尽可能等概率分布，以使新信源的每个码符源）尽可能等概率分布，以使新信源的每个码符源）尽可能等概率分布，以使新信源的每个码符源）尽可能等概率分布，以使新信源的每个码符号平均所含的信息量达到最大，从而使信息传输号平均所含的信息量达到最大，从而使信息传输号平均所含的信息量达到最大，从而使信息传输号平均所含的信息量达到最大，从而使信息传输率率率率R R R R达到信道容量达到信道容量达到信道容量达到信道容量C C C C，实现信源与信道理想的统，实现信源与信道理想的统，实现信源与信道理想的统，实现信源与信道理想的统计匹配。计匹配。计匹配。计匹配。第23页，本讲稿共35页例例
26、例例4.14.1有一离散无记忆信源有一离散无记忆信源有一离散无记忆信源有一离散无记忆信源 其熵为其熵为其熵为其熵为HH(S S)=0.811)=0.811 比特比特比特比特/信源符号，用二进制符号信源符号，用二进制符号信源符号，用二进制符号信源符号，用二进制符号00，11来构来构来构来构造一个即时码。造一个即时码。造一个即时码。造一个即时码。s s1 10 0，s s2 21 1。码的效率为码的效率为码的效率为码的效率为1 1 1 1=0.811 0.811 信息传输率为信息传输率为信息传输率为信息传输率为R R R R1 1=0.811 =0.811 比特比特比特比特/二进制符号。二进制符号
27、。二进制符号。二进制符号。对信源对信源对信源对信源S S S S 的长为的长为的长为的长为2 2 2 2、3 3 3 3、4 4 4 4的符号序列的符号序列的符号序列的符号序列的符号序列的符号序列的符号序列的符号序列（即（即（即（即N N N N=2=2=2=2、3 3 3 3、4 4 4 4）分别进行变长编码。）分别进行变长编码。）分别进行变长编码。）分别进行变长编码。2 2 2 2=0.961=0.961=0.961=0.961 R R R R2 2 2 2=0.961 =0.961 =0.961 =0.961 比特比特比特比特/二进制符号二进制符号二进制符号二进制符号3 3 3 3=0.
28、985=0.985=0.985=0.985 R R R R3 3 3 3=0.985 =0.985 =0.985 =0.985 比特比特比特比特/二进制符号二进制符号二进制符号二进制符号4 4 4 4=0.991=0.991=0.991=0.991 R R R R4 4 4 4=0.991 =0.991 =0.991 =0.991 比特比特比特比特/二进制符号二进制符号二进制符号二进制符号可见编码复杂一些，使信息传输率提高。可见编码复杂一些，使信息传输率提高。可见编码复杂一些，使信息传输率提高。可见编码复杂一些，使信息传输率提高。第24页，本讲稿共35页变长变长码的编码方法码的编码方法 霍夫曼
29、霍夫曼霍夫曼霍夫曼(Huffman)(Huffman)码码码码HuffmanHuffman码是异字头码，是一种最佳码。码是异字头码，是一种最佳码。码是异字头码，是一种最佳码。码是异字头码，是一种最佳码。19521952年提出，应用于数据压缩，文件传输、语音处理、年提出，应用于数据压缩，文件传输、语音处理、年提出，应用于数据压缩，文件传输、语音处理、年提出，应用于数据压缩，文件传输、语音处理、图象处理。图象处理。图象处理。图象处理。费诺（费诺（费诺（费诺（FanoFano）码码码码FanoFano码不一定是最佳码，但有时也可能是最佳码。码不一定是最佳码，但有时也可能是最佳码。码不一定是最佳码，但
30、有时也可能是最佳码。码不一定是最佳码，但有时也可能是最佳码。第25页，本讲稿共35页霍夫曼码的编码方法霍夫曼码的编码方法二进制霍夫曼码的的编码方法，它的编码步骤如下：二进制霍夫曼码的的编码方法，它的编码步骤如下：二进制霍夫曼码的的编码方法，它的编码步骤如下：二进制霍夫曼码的的编码方法，它的编码步骤如下：（1 1 1 1）将）将）将）将q q q q个信源符号按概率值的大小以递减次序排列起来，设个信源符号按概率值的大小以递减次序排列起来，设个信源符号按概率值的大小以递减次序排列起来，设个信源符号按概率值的大小以递减次序排列起来，设 p p p p1 1 1 1 p p p p2 2 2 2p p
31、 p pq q q q（2 2 2 2）用用用用0 0 0 0和和和和1 1 1 1码码码码符符符符号号号号分分分分别别别别代代代代表表表表概概概概率率率率最最最最小小小小的的的的两两两两个个个个信信信信源源源源符符符符号号号号，并并并并将将将将这这这这两两两两个个个个概概概概率率率率最最最最小小小小的的的的信信信信源源源源符符符符号号号号合合合合并并并并一一一一个个个个符符符符号号号号，从从从从而而而而得得得得到到到到包包包包含含含含q q q q1 1 1 1个个个个符符符符号号号号的的的的新新新新信信信信源源源源-缩减信源缩减信源缩减信源缩减信源S S S S。（3 3 3 3）把把把把
32、缩缩缩缩减减减减信信信信源源源源S S S S 的的的的符符符符号号号号仍仍仍仍按按按按概概概概率率率率值值值值大大大大小小小小以以以以递递递递减减减减次次次次序序序序排排排排列列列列，再再再再将将将将其其其其最最最最后后后后二二二二个个个个概概概概率率率率最最最最小小小小的的的的符符符符号号号号合合合合并并并并成成成成一一一一个个个个符符符符号号号号，并并并并分分分分别别别别用用用用0 0 0 0和和和和1 1 1 1码码码码符符符符号号号号表表表表示示示示，这这这这样样样样又又又又得得得得到到到到q q q q2 2 2 2个符号的新缩减信源个符号的新缩减信源个符号的新缩减信源个符号的新缩
33、减信源S S S S。（4 4 4 4）依依依依次次次次继继继继续续续续下下下下去去去去，直直直直至至至至信信信信源源源源最最最最后后后后只只只只剩剩剩剩两两两两个个个个符符符符号号号号为为为为止止止止。将将将将这这这这最最最最后后后后两两两两个个个个信信信信源源源源符符符符号号号号分分分分别别别别用用用用0 0 0 0和和和和1 1 1 1码码码码符符符符号号号号表表表表示示示示。然然然然后后后后从从从从最最最最后后后后一一一一级级级级缩缩缩缩减减减减信信信信源源源源开开开开始始始始，向向向向前前前前返返返返回回回回，就就就就得出各信源符号所对应的码符号序列，即得到对应的码字。得出各信源符号
34、所对应的码符号序列，即得到对应的码字。得出各信源符号所对应的码符号序列，即得到对应的码字。得出各信源符号所对应的码符号序列，即得到对应的码字。第26页，本讲稿共35页缩减信源（辅助信源）缩减信源（辅助信源）缩减信源（辅助信源）缩减信源（辅助信源）设信源设信源设信源设信源S S，取值于集合，取值于集合，取值于集合，取值于集合 其概率分布其概率分布其概率分布其概率分布满足满足满足满足 ,码为码为码为码为 缩减信源缩减信源缩减信源缩减信源S S 码为码为码为码为第27页，本讲稿共35页例例例例：对下列离散无记忆稳恒信源进行对下列离散无记忆稳恒信源进行对下列离散无记忆稳恒信源进行对下列离散无记忆稳恒信
35、源进行HuffmanHuffman编码编码编码编码源字母源字母源字母源字母 概率概率概率概率 码字码字码字码字 编码过程编码过程编码过程编码过程a a1 1 0.4 0.4 a a2 2 0.2 0.2 a a3 3 0.20.2a a4 4 0.1 0.1a a5 5 0.10.1霍夫曼码编码举例霍夫曼码编码举例第28页，本讲稿共35页霍夫曼码编码举例霍夫曼码编码举例00010 01110101010 110010 0011 01100010101010第29页，本讲稿共35页霍夫曼码霍夫曼码说明：说明：说明：说明：（1 1）如果出现相同概率的情况，合并后的概率尽量安排处于最高）如果出现相同
36、概率的情况，合并后的概率尽量安排处于最高）如果出现相同概率的情况，合并后的概率尽量安排处于最高）如果出现相同概率的情况，合并后的概率尽量安排处于最高的位置，减少合并元素被重复编码的次数，使短码字充分利用。的位置，减少合并元素被重复编码的次数，使短码字充分利用。的位置，减少合并元素被重复编码的次数，使短码字充分利用。的位置，减少合并元素被重复编码的次数，使短码字充分利用。（2 2）不同编码后，平均码长相等，取码长偏离平均码长的方差较）不同编码后，平均码长相等，取码长偏离平均码长的方差较）不同编码后，平均码长相等，取码长偏离平均码长的方差较）不同编码后，平均码长相等，取码长偏离平均码长的方差较小的
37、，即小的，即小的，即小的，即 （3 3）缩减时源符号不够时，补零（概率）后编码。即：信源符号）缩减时源符号不够时，补零（概率）后编码。即：信源符号）缩减时源符号不够时，补零（概率）后编码。即：信源符号）缩减时源符号不够时，补零（概率）后编码。即：信源符号个数应满足个数应满足个数应满足个数应满足 q q=(r r 1)1)+r r 第30页，本讲稿共35页例例例例：对下列离散无记忆稳恒信源进行：对下列离散无记忆稳恒信源进行：对下列离散无记忆稳恒信源进行：对下列离散无记忆稳恒信源进行4 4进制进制进制进制HuffmanHuffman编码编码编码编码源字母源字母源字母源字母 概率概率概率概率 码字码
38、字码字码字 编码过程编码过程编码过程编码过程a a1 1 0.220.22a a2 2 0.20 0.20 a a3 3 0.180.18a a4 4 0.15 0.15a a5 5 0.100.10a a6 6 0.08 0.08 a a7 7 0.050.05a a8 8 0.020.02r 进制霍夫曼码编码举例进制霍夫曼码编码举例第31页，本讲稿共35页霍夫曼码的霍夫曼码的最佳性最佳性定定定定理理理理4.5 4.5 对对对对于于于于给给给给定定定定信信信信源源源源，存存存存在在在在有有有有最最最最佳佳佳佳唯唯唯唯一一一一可可可可译译译译二二二二元元元元码码码码，其其其其最最最最小小小小概
39、概概概率率率率的的的的两两两两个个个个码码码码字字字字WWq q-1-1和和和和WWq q的的的的长长长长度度度度最最最最大大大大且且且且相相相相等等等等，它它它它们们们们之之之之间间间间仅仅仅仅最最最最后后后后一一一一位码元取值不同（一个为位码元取值不同（一个为位码元取值不同（一个为位码元取值不同（一个为0 0，另一个为，另一个为，另一个为，另一个为1 1）。）。）。）。定定定定理理理理4.64.6 对对对对辅辅辅辅助助助助集集集集SS为为为为最最最最佳佳佳佳的的的的码码码码，对对对对原原原原始始始始消消消消息息息息符符符符号号号号集集集集S S 也也也也是是是是最最最最佳的。佳的。佳的。佳
40、的。第32页，本讲稿共35页费诺（费诺（FanoFano）码）码的编码方法的编码方法（1 1 1 1）将信源符号以概率递减次序排列起来）将信源符号以概率递减次序排列起来）将信源符号以概率递减次序排列起来）将信源符号以概率递减次序排列起来 p p p p1 1 1 1 p p p p2 2 2 2p p p pq q q q（2 2 2 2）将将将将排排排排列列列列好好好好的的的的信信信信源源源源符符符符号号号号划划划划分分分分成成成成两两两两大大大大组组组组，使使使使每每每每组组组组的的的的概概概概率率率率和和和和近近近近似似似似相同，并各赋于一个二进码符号相同，并各赋于一个二进码符号相同，并
41、各赋于一个二进码符号相同，并各赋于一个二进码符号“0 0 0 0”和和和和“1 1 1 1”。（3 3 3 3）将将将将每每每每一一一一大大大大组组组组的的的的信信信信源源源源符符符符号号号号再再再再分分分分成成成成两两两两级级级级，使使使使同同同同一一一一组组组组的的的的两两两两个个个个小小小小组组组组的的的的概概概概率率率率和和和和近近近近似似似似相相相相同同同同，并并并并又又又又各各各各赋赋赋赋于于于于一一一一个个个个二二二二进进进进码码码码符符符符号号号号“0 0 0 0”和和和和“1 1 1 1”。（4 4 4 4）如如如如此此此此下下下下去去去去，直直直直至至至至每每每每组组组组只
42、只只只剩剩剩剩下下下下一一一一个个个个信信信信源源源源符符符符号号号号为为为为止止止止。这这这这样样样样，信源符号所对应的码符号序列就为编得的码字。信源符号所对应的码符号序列就为编得的码字。信源符号所对应的码符号序列就为编得的码字。信源符号所对应的码符号序列就为编得的码字。第33页，本讲稿共35页例例例例：对下列离散无记忆稳恒信源进行：对下列离散无记忆稳恒信源进行：对下列离散无记忆稳恒信源进行：对下列离散无记忆稳恒信源进行FanoFano码码码码编码编码编码编码源字母源字母源字母源字母 概率概率概率概率 码字码字码字码字 编码过程编码过程编码过程编码过程a a1 1 0.4 0.4 a a2 2 0.2 0.2 a a3 3 0.20.2a a4 4 0.1 0.1a a5 5 0.10.1费诺（费诺（FanoFano）码）码编码举例编码举例第34页，本讲稿共35页掌握有关信源编码的概念（唯一可译码、异前缀掌握有关信源编码的概念（唯一可译码、异前缀码码）编码定理的意义（香农第一定理编码定理的意义（香农第一定理）编码方法（编码方法（Huffman码、码、Fano码）码）第四章第四章 小结小结第35页，本讲稿共35页