信息论实验报告 姓名 胡小辉 班级 电子信息工程 0902 学号 ********** 1 . 实验目的 1、掌握哈夫曼编码、费诺编码、汉明码原理; 2、熟练掌握哈夫曼树的生成方法; 3、学会利用 matlab、C 语言等实现 Huffman 编码、费诺编码以及 hamming 编码。 2 . 实验原理 Huffman 编码: 哈夫曼树的定义:假设有 n 个权值,试构造一颗有 n 个叶子节点的二叉树,每个叶子带权值为 wi,其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树; 实现 Huffman 编码原理的步骤如下: 1. 首先将信源符号集中的符号按概率大小从大到小排列。 2. 用 0 和 1 表示概率最小的两个符号。可用 0 表示概率小的符 号,也可用 1 表示概率小的符号,但整个编码需保持一致。 3. 将这两个概率最小的符号合并成一个符号,合并符号概率为 最小概率之和,将合并后的符号与其余符号组成一个 N-1 的新信源符号集,称之为缩减符号集。 4. 对缩减符号集用步骤 1,2 操作 5. 以此类推,直到只剩两个符号,将 0 和 1 分别赋予它们。 6. 根据以上步骤,得到 0,1 赋值,画出 Huffman 码树,并从最 后一个合并符号回朔得到 Huffmaan 编码。 费诺编码: 费诺编码的实现步骤: 1、将信源消息符号按其出现的概率大小依次排列: 。 2、将依次排列的信源符号按概率值分为两大组,使两个组的概率之和近似相同,并对各组赋予一个二进制码元“0”和“1”。 3、将每一大组的信源符号再分为两组,使划分后的两个组的概率之和近似相同,并对各组赋予一个二进制符号“0”和“1”。 4、如此重复,直至每个组只剩下一个信源符号为止。 5、信源符号所对应的码字即为费诺码。 hamming 编码: 若一致监督矩阵 H 的列是由不全为0 且互不相同的所有二进制m(m≥2 的正整数)重组成,则由此 H 矩阵得到的线性分组码称为[2m-1,2m-1-m,3]汉明码。 我们通过(7,4)汉明码的例子来说明如何具体构造这种码。设分组码(n,k)中,k = 4,为能纠正一位误码,要求r≥3。现取r=3,则n=k+r=7。我们用a0ala2a3a4a5a6表示这7个码元,用S1、S2、S3表示由三个监督方程式计算得到的校正子,并假设三位S1、S2、S3校正子码组与误码位置的对应关系如表1所示。 S1S2S3 错码位置 S1S2S3 错码位置 001 a0 101 a4 010 al 110 a5 100 a2 111 a6 011 a3 000 无错码 表1 校正子和错码位置关系 由表可知,当误码位置...