霍夫曼编码的 matlab 实现
一、实验内容:
用 Matlab 语言编程实现霍夫曼( Huffman)编码。
二、实验原理及编码思想 :
霍夫曼( Huffman)编码算法是满足前缀条件的平均二进制码长最短
的编- 源输出符号, 而将较短的编码码字分配给较大概率的信源输出。
算法是:在信源符号集合中, 首先将两个最小概率的信源输出合并为
新的输出,其概率是两个相应输出符号概率之和。 这一过程重复下去,
直到只剩下一个合并输出为止, 这个最后的合并输出符号的概率为 1。
这样就得到了一张树图, 从树根开始, 将编码符号 1 和0 分配在同一
节点的任意两分支上, 这一分配过程重复直到树叶。 从树根到树叶途
经支路上的编码最后就构成了一组异前置码,就是霍夫曼编码输出。
以本教材 P36例题3-2 信源为例:
离散无记忆信源:
U u1 u2 u3 u4 u5
P(U) = 0.4 0.2 0.2 0.1 0.1
解:
码字 Wi
信符 s
i
概率
P(s i )
编码过程
第一次 第二次 第三次