《近代信息论第三章优秀课件.ppt》由会员分享，可在线阅读，更多相关《近代信息论第三章优秀课件.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、近代信息论第三章第1页，本讲稿共25页主要内容第三节：平均码长界限定理第四节：无失真信源编码定理第五节 Huffman 编码第2页，本讲稿共25页第三节：平均码长界限定理定义1：平均码长含义：从平均意义上说，一个信源符号所需的平均码符号数。第3页，本讲稿共25页平均码长界限定理定义2 码率 code rate(码的信息传输率）含义：，每一个码符号所能携带的信息量。问题虽然R和平均码长和H(S)有关，但当信源固定（H(S)一定时），平均码长增大，R减小，有效性差。我们的目的：寻找平均码长尽可能小的码寻找平均码长尽可能小的码。手段：使得码长和概率相搭配（概率大的与码长小的相配）由“平均码长界限定理
2、”给出这个界。第4页，本讲稿共25页定理：定理：若一个离散无记忆信源S具有熵H(S)，并有r个码符号集X:a1，a2,ar,则总可以找到一种无失真编码，构成单义可译码，使平均码长满足：平均码长界限定理证明证明第5页，本讲稿共25页平均码长界限定理证明平均码长界限定理证明下界下界即：第6页，本讲稿共25页平均码长界限定理证明平均码长界限定理证明上界上界按上式选择码长构成的码满足Kraft不等式，则至少可构成单义可译码。第7页，本讲稿共25页平均码长界限定理证明平均码长界限定理证明上界上界注：按（按（1 1）式所构成的单义可译码，平均码长小于上界）式所构成的单义可译码，平均码长小于上界即：平均码长
3、小于上界时，单义可译码存在。即：平均码长小于上界时，单义可译码存在。但不意味着，平均码长大于上界就不能构成单义可译码。但不意味着，平均码长大于上界就不能构成单义可译码。第8页，本讲稿共25页平均码长界限定理推论推论1码率：定义定义1码的每秒信息传输率要无差错传输，必须使每秒所传要无差错传输，必须使每秒所传递的平均信息量递的平均信息量 小于小于 信道每信道每秒能通过的最大信息量。秒能通过的最大信息量。第9页，本讲稿共25页定义定义2平均码长界限定理信道每秒所能传递的信源符号数back第10页，本讲稿共25页第四节：无失真信源编码定理有界限定理可知平均码长有下界，问：能否达到下界？是否存在这样的码
4、？无失真信源编码定理：（Shannon第一定理）对于平均符号熵为对于平均符号熵为H(S)H(S)的离散平稳无记忆信源，的离散平稳无记忆信源，对对S S的的L L次扩展次扩展 进行编码，存在一种无失真编码，进行编码，存在一种无失真编码，使得：使得：(1)(2)第11页，本讲稿共25页无失真信源编码定理证明对对S S的的L L次扩展信源进行编码次扩展信源进行编码S S1 1，S S2 2,S,SL L,设用设用r r进制码进制码元元X:aX:a1 1，a a2 2,a,ar r 做变长编码。做变长编码。（1 1）由平均码长界限定理，存在单义可译码，）由平均码长界限定理，存在单义可译码，L L次扩次
5、扩展后平均码长满足：展后平均码长满足：第12页，本讲稿共25页（2）定义变长码编码速率 编码效率 无失真信源编码定理证明back第13页，本讲稿共25页第五节 Huffman 编码Shannon 编码Fano 编码Huffman 编码例第14页，本讲稿共25页Shannon编码码长满足码长满足计算出相应的码长，在码树上挑码。计算出相应的码长，在码树上挑码。例：例：则：则：第15页，本讲稿共25页Fano 编码概率r等份步骤：步骤：按概率大小次序排列；按概率大小次序排列；将消息分成近似于等概的将消息分成近似于等概的r r 个子集：个子集：aa1 1,a,a2 2,a,a3 3,a,a4 4,a,
6、a5 5,a,a9 9 分别与码树的一级节点对应；分别与码树的一级节点对应；同样各组分成等概子集同样各组分成等概子集第16页，本讲稿共25页P第一次划分第二次划分第三次划分码字码长01201201201200111212021220 221222122222333第17页，本讲稿共25页第18页，本讲稿共25页例例2P第一次划分第二次划分第三次划分第四次划分010.570.43010.200.37010.170.26010101第19页，本讲稿共25页由此例可见：由此例可见：Fano Fano 法，效率低，仍不尽人意法，效率低，仍不尽人意Fano 编码概率r等份Huffman 编码第20页，本
7、讲稿共25页Huffman 编码1.按概率大小排序；按概率大小排序；2.用码符号用码符号a a1 1，a a2 2,a,ar r分别代表概率最小的分别代表概率最小的r个符号并将这个符号并将这r个符个符号合并成一个符号，从而得到只有号合并成一个符号，从而得到只有q-r+1个符号的新信源，个符号的新信源，S1(一次缩减）一次缩减）3.又以概率大小对又以概率大小对S1排序，用码符号排序，用码符号a a1 1，a a2 2,a,ar r分别代表概率最分别代表概率最小的小的r个符号并将这个符号并将这r个符号合并成得到个符号合并成得到S2(二次缩减）二次缩减）4.按以上方法依次继续按以上方法依次继续5.当
8、缩减过程进行到第当缩减过程进行到第a次，次，Sa只含有只含有r个符号，则只剩最个符号，则只剩最后一步，将这后一步，将这r个符号用个符号用a a1 1，a a2 2,a,ar r表示。表示。6.逆次序分配码字逆次序分配码字7.如果第如果第a步时，步时，Sa中的符号数小于中的符号数小于r,则在原信源则在原信源S中增加中增加m=r-q-(r-1)a个概率为个概率为0的符号，重新开始。的符号，重新开始。步骤：步骤：第21页，本讲稿共25页例例1101010100.260.350.390.610101111001101000100010000Huffman编码优于Fano编码第22页，本讲稿共25页例例
9、2r=3,X:0,1,2当二次缩减后，当二次缩减后，S2S2中含符号数中含符号数q-(r-1)*2=23,q-(r-1)*2=23,需增加需增加1 1个个0 0。1020.221020.541020202122101112第23页，本讲稿共25页例例3码长方差码长方差合并后的概率和尽量处于高位，可减小方差0.20.40.61010101001110010101011100.2100.40.41010100001110111第24页，本讲稿共25页关于Huffman 编码可以证明可以证明Huffman Huffman 编码是最佳的。编码是最佳的。HuffmanHuffman编出的码不唯一。编出的码不唯一。HuffmanHuffman码字长参差，硬件实现困难，在理论上必须有无码字长参差，硬件实现困难，在理论上必须有无限大容量，才能达到按平均码长的信息率传输。限大容量，才能达到按平均码长的信息率传输。传输的过程中有误码传递。传输的过程中有误码传递。HuffmanHuffman编码表的缺省使用（双方均采用某一已知的概率分布。编码表的缺省使用（双方均采用某一已知的概率分布。自适应自适应HuffmanHuffman编码编码例：误传发送接后都译错back第25页，本讲稿共25页