哈夫曼编码

SchoolofInformationandMathematics哈夫曼编码邹健回顾：通信系统模型SchoolofInformationandMathematics信源信源编码器信道编码器调制器信道解调器信宿信源译码器信道译码器干扰源编码信道信源信源编码器信道编码器调制器信道解调器信宿信源译码器信道译码器干扰源编码信道信源：产生消息和消息序列的来源。信源编码器：将信源的输出进行适当的变换，以提高信息传输的有效性。回顾：信源编码定理SchoolofInformationandMathematics信源编码定理（定理2.4.1）设X1，X2…为无记忆信源，服从共同分布p(x)，则当码率时，存在码率为R的编码，使得当n→∞时，误差码率Pe→0.1log()RMHXn最优码的存在性如何构造最优码？回顾：最优码的构造SchoolofInformationandMathematics等长码：每个码字的码长相等变长编码：每个码字的码长可以不相等引例—色子游戏SchoolofInformationandMathematics顺序编码是否最优？引例—色子游戏SchoolofInformationandMathematics点数出现的频率引例—色子游戏SchoolofInformationandMathematics按概率编码引例—莫尔斯电报码SchoolofInformationandMathematics莫尔斯电报码：按照英文字母出现的概率编码，在英文中，e的出现概率很高，而z的出现概率则最低。思考：国际求救信号SOS哈夫曼编码SchoolofInformationandMathematics1952年，DavidA.Huffman在麻省理工攻读博士时发表了《一种构建极小多余编码的方法》（AMethodfortheConstructionofMinimum-RedundancyCodes）一文，提出Huffman编码算法。哈夫曼编码(HuffmanCoding)是可变长编码(VLC)的一种哈夫曼编码SchoolofInformationandMathematics哈夫曼编码(HuffmanCoding)基本思想•完全依据字符出现概率进行编码•出现概率高的字符使用较短的编码•出现概率低的字符使用较长的编码•编码后平均码字长最短哈夫曼编码SchoolofInformationandMathematics哈夫曼编码算法：(1)信源符号按概率分布大小，以递减次序排列；(2)取两个最小的概率，分别赋以“0”,“1”;然后把这两个概率值相加，作为新概率值与其他概率重新排序(3)按重排概率值，重复(2)…,直到概率和达到1为止(4)由后向前排列码序，即得哈夫曼编码例题SchoolofInformationandMathematics例题：设一个信源变量X服从以下概率分布设计二进哈夫曼编码X:p(x)~(0.4,0.2,0.2,0.1,0.1)例题SchoolofInformationandMathematics方法一：x10.4x20.2x30.2x40.1x50.10.20.40.61.00101010101100000100011合并后概率下放例题SchoolofInformationandMathematics方法二：合并后概率上放010.20.40.61.001010100x10.410x20.211x30.2010x40.1011x50.1＊两法平均码长相同，故信息率R、冗余度相同；例题SchoolofInformationandMathematics两种方法的比较511()0.410.220.230.140.142.2iiiLPsl521()0.420.220.220.130.132.2iiiLPsl码方差2221[()]()()qiiiiElLPslL522111()()1.36iiiPslL522221()()0.16iiiPslL平均码长例题SchoolofInformationandMathematics可见：第二种编码方法的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。第一种方法编出的5个码字有4种不同的码长；第二种方法编出的码长只有两种不同的码长；显然，第二种编码方法更简单、更容易实现，所以更好。结论SchoolofInformationandMathematics结论：在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。结论SchoolofInformationandMathematics定理：在变长编码中，若各码字长度严格按照所对应符号出现概率的大小逆序排列，则其平均长度为最小。结论：哈夫曼编码方法，它完全依据字符出现概率来构造平均长度最短的异字头码字，有时称之为最佳编码。哈夫曼编码的应用SchoolofInformationandMathematics无损压缩在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。实际上，哈夫曼编码是传真图像的压缩标准。哈夫曼编码的缺点SchoolofInformationandMathematics单个字母编码时编码效率不高信源字母集大时不易实现（香农-费诺码可解决）硬件实现时需要缓冲寄存器（变长码固有的缺陷）差错扩散（可增加信道校验码）必须知道信源的统计特性（通用信源编码不需要）谢谢各位老师！