实验课程：信息论与编码理论专业：信息与计算科学班级：09070241
学号：0907024101
姓名：孙秋月
中北大学理学院
实验二 哈夫曼编码
一、实验目的
1. 掌握哈夫曼编码的原理及编码步骤
2. 练习matlab 中哈夫曼编码函数的调用及通信工具箱的使用
二、实验原理
哈夫曼编码的具体步骤归纳如下：
1. 统计n 个信源消息符号，得到n 个不同概率的信息符号。

2. 将这n 个信源信息符号按其概率大小依次排序：
p (x 1) ≥ p (x 2)≥ …≥ p (x n )
3. 取两个概率最小的信息符号分别配以0和1两个码元，并将这两个概率相加作为一个新的信息符号的概率，和未分配的信息符号构成新的信息符号序列。

4. 将剩余的信息符号，按概率大小重新进行排序。

5. 重复步骤3，将排序后的最后两个小概论相加，相加和与其他概率再排序。

6. 如此反复重复n-2次，最后只剩下两个概率。

7. 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字，构成霍夫曼编码字。

编码结束。

三、实验内容
为某一信源进行哈夫曼编码。

该信源的字符集为X={x 1, x 2, … x 6 }，相应的概率矢量为：P =(0.30,0.25,0.21,0.10,0.09,0.05)，即X ，P 的概率空间为：
123456 0.300.250.210.100.090.05X x x x x x x P ⎡⎤⎡⎤=⎢⎥⎢⎥⎣⎦⎣⎦
根据哈夫曼编码算法对该信源进行哈夫曼编码。

并计算其平均码长和编码效率。

调用matlab 哈夫曼编码函数进行哈夫曼编码，与人工编码结果做比较。

1. huffmandict 函数： 为已知概率分布的信源模型生成哈夫曼编解码索引表。

调用方法如下：
[dict，avglen] = huffmandict (symbols, p)
[dict，avglen] = huffmandict (symbols, p, N)
[dict，avglen] = huffmandict (symbols, p, N, variance)
【实验方法和步骤】
symbols = [1:6];
p = [.30 .25 .21 .10 .09 .05];
[dict,avglen] = huffmandict(symbols,p)
samplecode1= dict{1,2}
samplecode2= dict{2,2}
samplecode3= dict{3,2}
samplecode4= dict{4,2}
samplecode5= dict{5,2}
samplecode6= dict{6,2}
h=-0.30.*log2(0.30)-0.25.*log2(0.25)-0.21.*log2(0.21)-0.10.*log2(0.10)-0.09. *log2(0.09)-0.05.*log2(0.05)
n=h./avglen
【运行结果】
dict =
[1] [1x2 double]
[2] [1x2 double]
[3] [1x2 double]
[4] [1x3 double]
[5] [1x4 double]
[6] [1x4 double]
avglen =
2.3800
samplecode1 =
0 0
samplecode2 =
0 1 samplecode3 =
1 1 samplecode4 =
1 0 1 samplecode5 =
1 0 0 0 samplecode6 =
1 0 0 1
h =
2.3549
n =
0.9894。