信息工程专业课程实验指导书一、 信息论与编码课程实验指导书；实验1 Huffman 编码（4 学时） 一、实验目的 1复习C+程序基本编写方法，熟悉VC 编程环境。 2会用VC 调试Huffman 编码程序。 二、实验内容 1复习C+代码基本语法（结构体、树等数据结构定义） 2根据Huffman 编码源代码，学习算法实现流程，培养自己动手能力，在C+编译器下按步调试跟踪算法。 三、实验仪器、设备 1计算机系统最低配置 256M 内存、P4 CPU 。 2C+ 编程软件 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”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。 将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n2)个符号的缩减信源 S2。 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各 信源符号所对应的码字。 2Huffman 树的编码原理： 步骤1： 将各个符号及其出现频率分别作为不同的小二叉树（目前每棵树只有根节点） 步骤2： 在步骤1中得到的树林里找出频率值最小的两棵树，将他们分别作为左、右子树连成一棵大一些的二叉树，该二叉树的频率值设为两棵子树频率值 之和。 步骤3：对上面得到的树林重复步骤2的做法，直到所有符号都连入树中为止。 五、实验步骤 1VC 环境下，建一个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 开始索引数组，HT0.weight 的大小设为0xffffffffL 。为了输出二进制 Huffman 码，程序最后对每个符号进行深度优先搜索，得到该符号的二进制字符，然后进行字符串拷贝，直到最后输出。实验二 CRC 校验码编码实验（4 学时） 一、实验目的 1学习CRC 编码基本流程, 学会调试循环冗余校验码编码程序。 2掌握CRC 校验码的编码原理，重点掌握按字节（Byte）编码方法。 二、实验内容 1根据实验原理掌握CRC 校验码编码/解码基本流程。 2在C+编译器下能够调试编码算法每一个步骤，重点掌握按字节编码的过程。三、实验仪器、设备 1计算机系统最低配置 256M 内存、P4 CPU 。 2C+ 编程软件 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 位（乘以216）后，再除以一个多项式，最后所得到的余数既是CRC 码。求CRC 码所采用模2 加减运算法则，既是不带进位和借位的按位加减，这种加减运算实际上就是逻辑上的异或运算，加法和减法等价，乘法和除法运算与普通代数式的乘除法运算是一样，符合同样的规律。接收方将接收到的二进制序列数（包括信息码和CRC 码）除以多项式，如果余数为0，则说明传输中无错误发生，否则说明传输有误。 2按位计算CRC 一个二进制序列数可以表示为 求此二进制序列数的CRC 码时，先乘以216后（左移16位），再除以多项式G(X) ， 所得的余数就是所要求的CRC 码。 可以设： 其中Q n (X) 为整数， R n (X) 为16位二进制余数，将上式代入前式得：再设：其中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 校验码。实验三 典型信道容量计算方法实现实验目的掌握用递推算法计算典型信道的容量的方法。实验学时2 学时实验准备1熟悉二进信道的概率转移矩阵表示，掌握信道容量的递推算法，设计用递推算法计算二进信道容量的数据结构和算法；2编写用递推算法计算二进信道容量的书面程序代码。实验内容及步骤用递推算法计算二进信道的容量说明：（1）构造各种二进信道的概率转移矩阵；（2）用递推算法计算各种二进信道的容量；（3）不断调整误差精度对系统进行测试，并进行对比分析；（4）编写本次实验的实验报告。二、 信息网络系统课程实验指导书；实验一网络简单观察实验一、实验目的1. 观察了解网卡、线缆、集线器等设备；2. 了解 WINDOWS 中的网络组成及参数；3. 了解通过 TCP/IP 协议连接上网的方法；4. 了解 Ethereal 软件的作用，以及利用 Ethereal 软件捕获、查看网络数据包的方法。二、原理概述Ethereal 是一个免费的网络协议分析软件，支持 Linux、Windows 等多种平台。由于网络上产生的数据包很多，通常我们只对其中一部分数据包感兴趣，因此在捕捉具体的数据包之前需要定义一个过滤器（filter） ，以滤除不需要的信息。一个过滤器实质上是一组规则，只有收到的数据满足规则时才保存，否则丢弃。过滤器通常可以是多个规则的逻辑组合。在 Ethereal 中捕捉数据包前,首先要选择要监听的接口。点击菜单中“Capture” “Interface”，此处选择接口“NDIS5 Driver”。在捕捉前还要设置一些参数，如过滤器。点击“prepare” ，出现设置窗口，在“Capture Filter”一栏中填写感兴趣的数据包对应规则（见使用手册） 。点击“Start”按钮开始捕捉。打开浏览器访问一些站点后，然后关闭浏览器，最后点击“Stop”按钮，结束数据包的捕捉。所有捕捉的数据包都显示在主窗口中。窗口中上面的列表框为所有捕获数据包（帧）的列表，记录了这些数据包的捕获时间、来源、目的地、协议等信息。中间的文本框为当前选中的捕获帧经 Ethereal 解释后的协议信息。屏幕最下面的窗口中以二进制形式显示当前选中的数据包的原始内容。如果需要保存所捕获的数据，可选择菜单“File”中的“Save as”进行保存。Ethereal 支持多种文件格式。三、实验内容1. 了解网卡的配置情况；2. 了解对等网的相关数据；3. 了解 TCP/IP 协议的相关参数配置；4. 阅读 Ethereal 软件的相关使用手册。四、实验方法1. 实验原理本实验是是在实验室的基于 WINDOWS 的网络上，观察网络的硬件软件，和相关的网络参数，并可以进行进一步的上网和共享硬盘等网络应用。见下图。2. 实验步骤步骤 1： 实验前准备在实验前已经建立计算机网络，并已经设定好网络设备参数及相关协议，如：TCP/IP 等。步骤 2：读取网络相关数据 网络组件打开计算机电源，启动 WINDOWS 操作系统，右击“我的电脑” “属性 ”“硬件” “设备管理器”“网络适配器”的顺序，了解网卡类型、中断请求、内存范围、输入输