哈夫曼编码

《哈夫曼编码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、SchoolofInformationandMathematics哈夫曼编码邹健回顾：通信系统模型SchoolofInformationandMathematics信源：产生消息和消息序列的来源。信源编码器：将信源的输出进行适当的变换，以提高信息传输的有效性。回顾：信源编码定理SchoolofInformationandMathematics信源编码定理（定理2.4.1）设X1，X2…为无记忆信源，服从共同分布p(x)，则当码率时，存在码率为R的编码，使得当n→∞时，误差码率Pe→0.最优码的存在性如何构造最优码？回顾：最优码的构造SchoolofInformation

2、andMathematics等长码：每个码字的码长相等变长编码：每个码字的码长可以不相等引例—色子游戏SchoolofInformationandMathematics顺序编码是否最优？引例—色子游戏SchoolofInformationandMathematics点数出现的频率引例—色子游戏SchoolofInformationandMathematics按概率编码引例—莫尔斯电报码SchoolofInformationandMathematics莫尔斯电报码：按照英文字母出现的概率编码，在英文中，e的出现概率很高，而z的出现概率则最低。思考：国际求救信号SOS哈夫曼

3、编码SchoolofInformationandMathematics1952年，DavidA.Huffman在麻省理工攻读博士时发表了《一种构建极小多余编码的方法》（AMethodfortheConstructionofMinimum-RedundancyCodes）一文，提出Huffman编码算法。哈夫曼编码(HuffmanCoding)是可变长编码(VLC)的一种哈夫曼编码SchoolofInformationandMathematics哈夫曼编码(HuffmanCoding)基本思想完全依据字符出现概率进行编码出现概率高的字符使用较短的编码出现概率低的字符使用较

4、长的编码编码后平均码字长最短哈夫曼编码SchoolofInformationandMathematics哈夫曼编码算法：(1)信源符号按概率分布大小，以递减次序排列；(2)取两个最小的概率，分别赋以“0”,“1”;然后把这两个概率值相加，作为新概率值与其他概率重新排序(3)按重排概率值，重复(2)…,直到概率和达到1为止(4)由后向前排列码序，即得哈夫曼编码例题SchoolofInformationandMathematics例题：设一个信源变量X服从以下概率分布设计二进哈夫曼编码X:p(x)~(0.4,0.2,0.2,0.1,0.1)例题SchoolofInforma

5、tionandMathematics方法一：x10.4x20.2x30.2x40.1x50.10.20.40.61.00101010101100000100011合并后概率下放例题SchoolofInformationandMathematics方法二：合并后概率上放010.20.40.61.001010100x10.410x20.211x30.2010x40.1011x50.1＊两法平均码长相同，故信息率R、冗余度相同；例题SchoolofInformationandMathematics两种方法的比较码方差平均码长例题SchoolofInformationandMa

6、thematics可见：第二种