近代信息论第三章精选文档.ppt
近代信息论第三章本讲稿第一页，共二十五页主要内容第三节：平均码长界限定理第四节：无失真信源编码定理第五节 Huffman 编码本讲稿第二页，共二十五页第三节：平均码长界限定理定义1：平均码长含义：从平均意义上说，一个信源符号所需的平均码符号数。本讲稿第三页，共二十五页平均码长界限定理定义2 码率 code rate(码的信息传输率）含义：，每一个码符号所能携带的信息量。问题虽然R和平均码长和H(S)有关，但当信源固定（H(S)一定时），平均码长增大，R减小，有效性差。我们的目的：寻找平均码长尽可能小的码寻找平均码长尽可能小的码。手段：使得码长和概率相搭配（概率大的与码长小的相配）由“平均码长界限定理”给出这个界。本讲稿第四页，共二十五页定理：定理：若一个离散无记忆信源S具有熵H(S)，并有r个码符号集X:a1，a2,ar,则总可以找到一种无失真编码，构成单义可译码，使平均码长满足：平均码长界限定理证明证明本讲稿第五页，共二十五页平均码长界限定理证明平均码长界限定理证明下界下界即：本讲稿第六页，共二十五页平均码长界限定理证明平均码长界限定理证明上界上界按上式选择码长构成的码满足Kraft不等式，则至少可构成单义可译码。本讲稿第七页，共二十五页平均码长界限定理证明平均码长界限定理证明上界上界注：按（按（1 1）式所构成的单义可译码，平均码长小于上界）式所构成的单义可译码，平均码长小于上界即：平均码长小于上界时，单义可译码存在。即：平均码长小于上界时，单义可译码存在。但不意味着，平均码长大于上界就不能构成单义可译码。但不意味着，平均码长大于上界就不能构成单义可译码。本讲稿第八页，共二十五页平均码长界限定理推论推论1码率：定义定义1码的每秒信息传输率要无差错传输，必须使每秒所传递的平要无差错传输，必须使每秒所传递的平均信息量均信息量 小于小于 信道每秒能通过的最大信道每秒能通过的最大信息量。信息量。本讲稿第九页，共二十五页定义定义2平均码长界限定理信道每秒所能传递的信源符号数back本讲稿第十页，共二十五页第四节：无失真信源编码定理有界限定理可知平均码长有下界，问：能否达到下界？是否存在这样的码？无失真信源编码定理：（Shannon第一定理）对于平均符号熵为对于平均符号熵为H(S)H(S)的离散平稳无记忆信源，对的离散平稳无记忆信源，对S S的的L L次次扩展扩展 进行编码，存在一种无失真编码，使得：进行编码，存在一种无失真编码，使得：(1)(2)本讲稿第十一页，共二十五页无失真信源编码定理证明对对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次扩展次扩展后平均码长满足：后平均码长满足：本讲稿第十二页，共二十五页（2）定义变长码编码速率 编码效率 无失真信源编码定理证明back本讲稿第十三页，共二十五页第五节 Huffman 编码Shannon 编码Fano 编码Huffman 编码例本讲稿第十四页，共二十五页Shannon编码码长满足码长满足计算出相应的码长，在码树上挑码。计算出相应的码长，在码树上挑码。例：例：则：则：本讲稿第十五页，共二十五页Fano 编码概率r等份步骤：步骤：按概率大小次序排列；按概率大小次序排列；将消息分成近似于等概的将消息分成近似于等概的r r 个子集：个子集：aa1 1,a,a2 2,a,a3 3,a,a4 4,a,a5 5,a,a9 9 分别与码树的一级节点对应；分别与码树的一级节点对应；同样各组分成等概子集同样各组分成等概子集本讲稿第十六页，共二十五页P第一次划分第二次划分第三次划分码字码长01201201201200111212021220221222122222333本讲稿第十七页，共二十五页本讲稿第十八页，共二十五页例例2P第一次划分第二次划分第三次划分第四次划分010.570.43010.200.37010.170.26010101本讲稿第十九页，共二十五页由此例可见：由此例可见：Fano Fano 法，效率低，仍不尽人意法，效率低，仍不尽人意Fano 编码概率r等份Huffman 编码本讲稿第二十页，共二十五页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.当缩减过程进行到第当缩减过程进行到第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的符号，重新开始。的符号，重新开始。步骤：步骤：本讲稿第二十一页，共二十五页例例1101010100.260.350.390.610101111001101000100010000Huffman编码优于Fano编码本讲稿第二十二页，共二十五页例例2r=3,X:0,1,2当二次缩减后，当二次缩减后，S2S2中含符号数中含符号数q-(r-1)*2=23,q-(r-1)*2=23,需增加需增加1 1个个0 0。1020.221020.541020202122101112本讲稿第二十三页，共二十五页例例3码长方差码长方差合并后的概率和尽量处于高位，可减小方差0.20.40.61010101001110010101011100.2100.40.41010100001110111本讲稿第二十四页，共二十五页关于Huffman 编码可以证明可以证明Huffman Huffman 编码是最佳的。编码是最佳的。HuffmanHuffman编出的码不唯一。编出的码不唯一。HuffmanHuffman码字长参差，硬件实现困难，在理论上必须有无限码字长参差，硬件实现困难，在理论上必须有无限大容量，才能达到按平均码长的信息率传输。大容量，才能达到按平均码长的信息率传输。传输的过程中有误码传递。传输的过程中有误码传递。HuffmanHuffman编码表的缺省使用（双方均采用某一已知的概率分布。编码表的缺省使用（双方均采用某一已知的概率分布。自适应自适应HuffmanHuffman编码编码例：误传发送接后都译错back本讲稿第二十五页，共二十五页
