压缩技术实验编码
- 格式：doc
- 大小：93.50 KB
- 文档页数：5
实验一 统计编码
一、 实验目的
1. 熟悉统计编码的原理
2. 掌握元编码的方法；
3. 了解编码效率及冗余度的计算；
二、 实验原理
霍夫曼编码, 又称最佳编码，根据字符出现概率来构造平均长度最短的变长编码。
编码步骤：
()(,…)按出现概率的值由大到小的顺序排列；
()对两个概率最小的符号分别分配以“”和“”，然后把这两个概率相加作为一个新的辅助符号的概率；
()
()
()用线将符号连接起来，从而得到一个码树，树的个端点对应个信源符号；
()从最后一个概率为的节点开始，沿着到达信源的每个符号，将一路遇到的二进制码“”或“”顺序排列起来，就是端点所对应的信源符号的码字。
以上是二元霍夫曼编码。如果是元霍夫曼编码，则应该如何做呢？
在编码方案中，为出现概率较小的信源输出分配较长的码字，而对那些出现可能性较大的信源输出分配较短的码字。为此，首先将个最小可能的信源输出合并成为一个新的输出，该输出的概率就是上述的个输出的概率之和。重复进行该过程直到只剩下一个输出为止。信源符号的个数与必须满足如下的关系式：
() 为整数
如果不满足上述关系式，可通过添加概率为零的信源符号来满足。这样就生成了一个树，从该树的根节点出发并将、 ……分别分配给任何个来自于相同节点的分支，生成编码。可以证明用这种方法产生的编码在前向树类编码中具有最小的平均长度。
举例：对于取值为{}其相应的概率为{，，，，，}的信源，试设计一个元码，求出码子的平均长度与编码效率。
注：因为是元编码，所以每次个概率值相加。
码字的平均长度
××××××
信源的熵
（） (×() ×() ×() ×() 0. ×() ×()
编码效率
用实现该编码的方法可用下面的矩阵来说明：
① ② ⑤ ⑤ ③ ①
② ⑥ ④ ④ ② ③
③ ⑤ ③ ③ ① ②
④ ① ② ①
⑤ ④ ① ②
⑥ ③
. ⑦ ⑦
注：每次个数加完后，重新按序分配编号，在按概率值重新排序，再进行下次加数。
注：中每一行为按概率值重新排序后的编号列，一共三次概率值排序；单箭头表示两次排序中的概率值并未参加加数，未改变；多箭头表示箭头所指向的多项概率值相加后得到箭头源的概率值。
注：为编码矩阵，从最后一行开始，因为是元编码，故按、、开始编码。根据中的箭头，单箭头不变，多箭头根据箭头源每上一层则箭头源编码后再加一位，同一层中加的位数按、、顺序添加。
矩阵第（>）行中的‘’记录了合并后的信源符号在新信源中的位置。
三、 实验步骤
1． 输入初始概率分布和码元数；
2． 检查是否满足 () （为输入信源的个数），如果不满足则补零使之满足；
3． 排序得矩阵
4． 根据矩阵获得矩阵
5． 从矩阵中取出最后的码字矩阵并计算平均码长和编码效率。
四、 实验仪器
计算机；
程序；
移动式存储器（软盘、盘等）；
记录用的笔、纸。
五、 实验报告内容
