《信息论与编码基础》课件 15单符号变长码

§6.1单符号变长编码§6压缩编码方法1.Morse码2.Shannon码3.Fano码4.Huffman码5.简要讨论6.规范码§6.1单符号变长编码不等概：变长码1.Morse码§6.1单符号变长编码1.Morse码SamuelF.B.Morse1791.

4.27--1872.4.21832:开始研究1838:Morse码表1844:电报,从WashingtonDC到Baltimore§6.1单符号变长编码§6.1单符号变长编码1.Morse码变长码，提高了编码效率不是唯一可译码§6.1单符号变长编码1.Morse码问题：如何构造好的码，使得平均码长最短？Huffman,1952惟一可译，异字头码§6.1单符号变长编码三种异字头码Shannon码Fano码Huffman码§6.1单符号变长编码2.Shannon码ClaudeShannon

1916.4.30--2001.2.24享年85岁§6.1单符号变长编码步骤1）将信源符号的发生概率（降序）排序；2）计算各信源符号的自信息量；3）各信源符号编码码长：自信息量取整；4）排序后的信源符号，计算累加概率；5）累加概率二进制化，取给定码长，得到编码码字；2.Shannon码§6.1单符号变长编码2.Shannon码例子§6.1单符号变长编码2.Shannon码0.200.190.180.170.150.100.0133333473.14bits/symbol2.61/3.14=0.83效率§6.1单符号变长编码3.Fano码RobertMarioFano1917§6.1单符号变长编码3.Fano码1）将信源符号的发生概率排序；2）尽可能等概划分子集；3）子集以符号“0”或“1”标识；4）如此以往，直到最终各子集都只包含一个符号；步骤§6.1单符号变长编码3.Fano码消息符号si消息概率P(si)s10.20s20.19s30.18s40.17s50.15s60.10s70.01第一次分组01第二次分组0101第三次分组0101第四次分组01码字码长0020103011310211031110411114§6.1单符号变长编码3.Fano码2.74bit/symbol2.61/2.74=0.95效率§6.1单符号变长编码DavidA.Huffman

卒于1999.10.7

享年74岁4.Huffman码编码步骤1、将q个符号si按概率Pi递减排序。2、用码符号0,1分别表示S中概率最小的两个符号，并将二者概率相加，合二为一，得到缩减后的新信源S1含q-1个符号。3、将S1重新排序，再将最后两个符号以码符号0,1代表并合并，得到S2。4、依此类推最后剩两个符号，分别标以码符号0,1。5、将信源中各符号历次分配码符倒序串起，得到码字。4.Huffman码§6.1单符号变长编码§6.1单符号变长编码消息符号si消息概率P(si)s10.20s20.19s30.18s40.17s50.15s60.10s70.0101010001010101码长码字210211300030013010401104011111000001010110110.110.260.350.394.Huffman码§6.1单符号变长编码4.Huffman码2.72bit/symbol2.61/2.74=0.96效率§6.1单符号变长编码5.简要讨论（1）编码效率：Huffman码最佳码；（2）编码原理性思路；（3）Shannon码的讨论。§6.1单符号变长编码5.简要讨论（1）编码效率§6.1单符号变长编码5.简要讨论（1）编码效率信源熵H：4.121bits/symbolShannon码码长3~11，平均码长4.602bits/symbol，效率0.895Fano码码长3~11，平均码长4.168bits/symbol，效率0.989Huffman码码长3~10，平均码长4.156bits/symbol，效率0.992§6.1单符号变长编码5.简要讨论（1）编码效率：Huffman码最佳码；（2）编码原理性思路；（3）Shannon码的讨论。§6.1单符号变长编码5.简要讨论（2）编码原理性思路Fano码：等概分割Huffman码：概率最小的符号开始Shannon码：自信息量§6.1单符号变长编码5.简要讨论（1）编码效率：Huffman码最佳码；（2）编码原理性思路；（3）Shannon码的讨论。§6.1单符号变长编码5.简要讨论（3）Shannon码A码长：A.1存在唯一可译码；A.2平均码长不会太坏；B码字：B.1异字头特性；B.2编码的改变、改进；A.3扩展信源编码；§6.1单符号变长编码消息序号Si消息概率P(Si)-logP(Si)代码组长度li累加概率Pi二进制代码组S10.202.3430000S20.192.4130.2001S30.182.4830.39011S40.172.5630.57100S50.152.7430.74101S60.103.3440.891110S70.016.6670.991111110Shannon码的改进§6.1单符号变长编码Shannon码的改进§6.1单符号变长编码6.规范码（1）编码1、已知信源符号的最佳编码码长；2、对信源符号进行编码，从短码开始，到长码结束2.1第一个码字，编码为0…02.2后继码字，为前一码字的值加1，并依照编码码字的码长，在码字后适当添加0。§6.1单符号变长编码6.规范码（1）编码§6.1单符号变长编码6.规范码（2）解码快速解码1、取各等长子码组的最后一个码字的值，作为界限值（等长码组中最大的码字值）2、由短及长，比较界限值，快速确定码长3、根据码字值和界限值之差，快速确定信源符号§6.1单符号变长编码6.规范码（2）解码假设对s6s2s5…编码，形成码流111001110…§6.1单符号变长编码6.规范码（2）解码快速解码1、取各