信息论与编码实验.doc

数据库系统课程设计

学生姓名： 马 进 孝
学 号： 20101000479
班 号： 116102-02
指导教师： 黄 鹰

中国地质大学（武汉）信息工程学院
2012/5/15年 2 月 25 日

实验一 Huffman 编码（2 学时）
一、实验目的
1．复习C++程序基本编写方法，熟悉VC 编程环境。
2．会用VC 调试Huffman 编码程序。
二、实验内容
1．复习C++代码基本语法（结构体、树等数据结构定义）
2．根据Huffman 编码源代码，学习算法实现流程，培养自己动手能力，在
C++编译器下按步调试跟踪算法。
三、实验仪器、设备
1．计算机－系统最低配置 256M 内存、P4 CPU。
2．C++ 编程软件－ Visual C++ 7.0 （Microsoft Visual Studio 2003）
Visual C++ 8.0 （Microsoft Visual Studio 2005）
四、实验原理
1． Huffman 编码原理：
①将信源符号按概率从大到小的顺序排列，令
p(x1)≥ p(x2)≥…≥ p(xn)
②给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这
两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，

结果得到一个只包含(n－1)个信源符号的新信源。称为信源的第一次缩减信源，

用S1表示。
③将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含

(n－2)个符号的缩减信源S2。

④重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概
率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各
信源符号所对应的码字。
2．Huffman 树的编码原理：
步骤1： 将各个符号及其出现频率分别作为不同的小二叉树（目前每棵树只
有根节点）
步骤2： 在步骤1中得到的树林里找出频率值最小的两棵树，将他们分别作
为左、右子树连成一棵大一些的二叉树，该二叉树的频率值设为两棵子树频率值
之和。
步骤3：对上面得到的树林重复步骤2的做法，直到所有符号都连入树中为止。
五、实验步骤
1．VC 环境下，建一个C++控制台应用程序，并把源代码考到该程序目录
下。
2．项目文件中含有一个预编译头文件，一个主函数入口文件和Huffman 编
码算法文件。
3．在入口文件中，输入任一个离散信源进行编码调试。
4．设置好程序断点，仔细分析Huffman 树每步的建立过程。
5．输出离散信源中每个符号的Huffman 编码，并与手工运算的结果进行比
较。
六、实验报告要求

1． 按照实验一附 3 中实验报告样式书写本次实验报告。
2． 总结 C++语言学习心得，并结合Huffman 编码实验总结自己的得失，
指出今后自己要练习改进之处。根据自己实验情况，对本实验写出建议。
七、实验注意事项
1．指针数据结构定义
typedef struct
{
unsigned long weight;
int parent, lchild, rchild;
} HTNode, *HuffmanTree;
typedef char** HuffmanCode; // 指向存放数组指针的数组即二维数组

2．二叉树生成操作放在数组中（节点n 和数组大小m 关系为：m=2*n-1）。
每次在树中找到两颗最小子树，其函数为Select(HuffmanTree HT, int n, int *s1, int
*s2)，实际实现的是在数组中找到最小两个元素。另外注意C++的数组起始索引
是0，Matlab 起始索引是1；程序中为了方便从1 开始索引数组，HT[0].weight
的大小设为0xffffffffL。为了输出二进制Huffman 码，程序最后对每个符号进行
深度优先搜索，得到该符号的二进制字符，然后进行字符串拷贝，直到最后输出。
3哈夫曼是一种编码手段。也就是说保证将来的编码是最小长度的，最终生成最小的哈夫曼编码树，又称哈夫曼最小树。

它的原理是将一段文本中出现的字符按出现的频率决定其编码。然后按其最终的
编码生成一段明文。知道了这个原理，编码还是很简单的。
首先，要实现字符的频度表。也就是说，这18个字符中出现次数最多的一个记作
01，然后按其出现的频率，分别生成最小树就可以了！保证哈夫曼最小树的生成！

至于树的生成，可以先生成一个双链表，分别表示左子树，数据，右子树。

#include<iostream>
　　#include<string>
　　using namespace std;
　　typedef struct TreeNode
　　{
　　char c;
　　int w;
　　int parent;
　　int right;
　　int left;
　　int tag;
　　char * code;
　　}Node;
　　void Find(Node * tree, int n, int & m1, int & m2)
　　{
　　m1 = -1;
　　while(tree[++ m1].tag != 0);
　　m2 = m1;
　　while(tree[++ m2].tag != 0);
　　for(int i = m2 + 1; i < n; i ++)  // 找到最小的两个元素的权值
　　{
　　if(tree[i].tag == 0)  // 只搜索没有标记过的元素
　　{
　　if(tree[i].w < tree[m1].w || tree[i].w < tree[m2].w)
　　{
　　if(tree[m2].w < tree[m1].w)
　　m1 = m2;
　　m2 = i;
　　}
　　}
　　}
　　}
　　void Huffman(Node * tree, int n)//建立Huffman树
　　{
　　int min1, min2;
　　for(int i = 0; i < n - 1; i ++)
　　{
　　Find(tree, n + i, min1, min2);//找出权值最小的两个顶点为min1,min2
　　tree[n + i].w = tree[min1].w + tree[min2].w;//新的顶点的权值为顶点min1,min2的权值的和
　　tree[n + i].left = min1;//n+i的两个孩子结点分别为min1,min2,一个为左孩子，一个为右孩子
　　tree[n + i].right = min2;
　　tree[n + i].tag = 0;//父亲顶点tag=0表示该顶点未访问过
　　tree[n + i].parent = 0;
　　tree[min1].parent = n + i;//把找的权值最小的两个顶点的父亲指针指向n+i
　　tree[min2].parent = n + i;
　　tree[min1].tag = 1;//已经找过的就不用找了
　　tree[min2].tag = 1;
　　}
　　}
　　void HuffmanCoding(Node * tree, int n)// Huffman编码函数
　　{
　　char * code = new char[n];
　　char * t = code + n - 1; // 指针t指向code的末尾
　　int m;
　　for(int i = 0; i < n; i ++)
　　{
　　int k = i;
　　code = t;
　　*code= '\0';
　　while(tree[k].parent != 0)
　　{
　　int p = tree[k].parent;
　　if(tree[p].left == k)
　　*(-- code) = '0';//左孩子编码为0
　　else
　　*(-- code) = '1';//右孩子编码为1
　　k = p;
　　}
　　tree[i].code = new char[strlen(code) + 1];
　　m=strlen(code);
　　cout<<tree[i].c<<"  "<<m<<endl;
　　}
　　}
　　int main()
　　{
　　int n;
　　while(cin>>n)
　　{
　　Node * tree = new Node[2 * n - 1];
　　for(int i = 0; i < n; i ++)
　　{
　　cin>>tree[i].c>>tree[i].w;
　　tree[i].tag = 0;
　　}
　　Huffman(tree, n);//建立Huffman树
　　HuffmanCoding(tree, n);//调用Huffman编码函数
　　}
　　return 0;
　　}

实验二 CRC 校验码编码实验（2 学时）
一、实验目的
1．学习CRC 编码基本流程, 学会调试循环冗余校验码编码程序。
2．掌握CRC 校验码的编码原理，重点掌握按字节（Byte）编码方法。
二、实验内容
1．根据实验原理掌握CRC 校验码编码/解码基本流程。
2．在C++编译器下能够调试编码算法每一个步骤，重点掌握按字节编码的
过程。
三、实验仪器、设备
1．计算机－系统最低配置 256M 内存、P4 CPU。
2．C++ 编程软件－ Visual C++ 7.0 （Microsoft Visual Studio 2003）
Visual C++ 8.0 （Microsoft Visual Studio 2005）
四、实验原理
1． CRC 校验码介绍
CRC 校验的基本思想是利用线性编码理论，在发送端根据要传送的k 位二
进制码序列，以一定的规则产生一个校验用的监督码（CRC 码）r 位，并附在
信息后边，构成一个新的二进制码序列数共 (k+r) 位，最后发送出去。在接收端，
则根据信息码和CRC 码之间所遵循的规则进行检验，以确定传送中是否出错。
16 位的CRC 码产生的规则是先将要发送的二进制序列数左移16 位（乘以
16
模2 加减运算法则，既是不带进位和借位的按位加减，这种加减运算实际上就是
逻辑上的异或运算，加法和减法等价，乘法和除法运算与普通代数式的乘除法运
算是一样，符合同样的规律。接收方将接收到的二进制序列数（包括信息码和
CRC 码）除以多项式，如果余数为0，则说明传输中无错误发生，否则说明传输
有误。
2．按位计算CRC
一个二进制序列数可以表示为

求此二进制序列数的CRC 码时，先乘以216后（左移16位），再除以多项式G(X) ，
所得的余数就是所要求的 CRC 码。

可以设：

其中 Q n (X) 为整数， R n (X) 为 16 位二进制余数，将上式代入前式得：

2 ）后，再除以一个多项式，最后所得到的余数既是CRC 码。求CRC 码所采用

再设：

其中 Qn-1(X) 为整数， Rn-1(X) 为 16 位二进制余数，继续代入前式，多次迭代
得到：

根据 CRC 的定义，很显然，十六位二进制数 R0(X) 即是要求的 CRC 码。
3．按字节计算CRC
对于一个二进制序列数可以按字节表示为下式，其中Bn(X) 为一个字节(共8
位)：

求此二进制序列数的CRC码时，先乘以216后（左移16位），再除以多项式G(X)，
所得的余数即是所要求的CRC 码。

可以设：

其中Qn(X) 为整数， Rn(X) 为16位二进制余数，将上式代入前式得：

由于：

其中RnH8(X) 是Rn(X)的高八位， RnL8(X)是Rn(X)的低八位，代入前式得到：

显然，十六位二进制数R0(X)即是要求的CRC码。
五、实验步骤
项目文件建立步骤同实验二，下面列出对给定字符串 CRC 校验主要步骤：
步骤 1：从主函数入口输入一个字符串，并且确定按字节32 位CRC 校验编
码，编码多项式采用CCITT 标准形式多项式。
步骤 2：调用编码函数，依次读入字符串每个自己，进行模2 除法运算。
步骤 3：将原来字符串左移32 位，将除法最后的余式追加到字符串的后32
位中去，得到该字符串CRC 校验编码结果。
步骤 4：如果要解码，首先确认编码多项式，然后将接收字符串除以编码多
项式。如果能够整除，说明字符串在传输或存储中没有发生错误；否则，表明字
符串在传输或存储中产生错误，导致CRC 校验失败。
六、实验报告要求
1． 按照实验一附 3 中实验报告样式提交本次实验报告。
2． 要求写出 CRC 校验编码学习心得，最好是能够结合硬件设计谈一下校验编
码的设计体会。根据自己实验情况，写出自己的做实验中遇到的具体问题，对本
实验提出建议。
七、实验注意事项
1．几个重要概念在实验前一定搞清楚：
1） 模 2 加减法 = 异或（XOR）。
2） 多项式的表示方法。
3） CRC 校验的基本理论
a 可以参考前面文中的推导。
b 自己通过一个除法运算推导。
4） 常用的两种方法：
a Bit 长度运算
b Byte 长度运算（可以将字节除法余式表保存下来，通过查表，计算
比较快）
2. 程序设计时注意内容：
1） 注意检查字节输入顺序与多项式的关系
a 高字节前，低字节后，采用通常理论推导公式编写程序。
b 低字节前，高字节后，采用向右移位方式。（这是数据通信中常用方
式，多项式采用反转多项式，添加余式时注意低位在前，高位在后）
2） 注意寄存器初始值选择
CCITT 和CRC32 如果用在通信中，常采用初始值为0xffff 或0xffffffffL，可
以开始纠正数字通信中几个bit 连续为0 的情况。为保持其输出和采用初始值为

0xffff 或0xffffffffL 一致，最后CRC 校验值要与0xffff 或0xffffffffL 进行异或运
算（XOR）得到最终CRC 校验码。

CRC校验码实验要求：编写出CRC码的编码和解码程序。
(1)实验框架：CRC编码－信道传输－CRC解码。
(2)CRC编码将原始数据按照既定的生成多项式进行编码；
(2)信道传输中实现模拟信道，某些位数据随机发生差错；
(3)CRC解码要能准确判断是否有差错，无差错要恢复出原始数据。

设计感言:

这次课程设计历时二个星期多左右，通过课程设计，发现自己的很多不足，
自己知识的很多漏洞，看到了自己的实践经验还是比较缺乏，理论联系实际的能
力还急需提高。大学里一年的相处还赶不上这十来天的实习，我感觉我和同学们
之间的距离更加近了。
    对我而言，知识上的收获重要，精神上的丰收更加可喜。让我知道了学无止
境的道理。我们每一个人永远不能满足于现有的成就，人生就像在爬山，一座山峰
的后面还有更高的山峰在等着你。挫折是一份财富，经历是一份拥有。这次课程设
计必将成为我人生旅途上一个非常美好的回忆！