信息论与编码.docx

1、信息论与编码信息论与编码实验报告 学生姓名： 李俊 班号： 11611125 班 号： 20111003660 指导教师： 黄鹰 中国地质大学（武汉）信息工程学院2013 年 7月实验1 Huffman 编码Huffman 编码原理：将信源符号按概率从大到小的顺序排列，令 p(x1) p(x2) p(xn) 给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率， 结果得到一个只包含(n1)个信源符号的新信源。称为信源的第一次缩减信源， 用S1表示。 将缩减信源S1的符号仍按概率从大到小顺序排列

2、，重复步骤2，得到只含(n2)个符号的缩减信源S2。 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各 信源符号所对应的码字。 Huffman 树的编码步骤： 步骤1： 将各个符号及其出现频率分别作为不同的小二叉树（目前每棵树只有根节点） 步骤2： 在步骤1中得到的树林里找出频率值最小的两棵树，将他们分别作为左、右子树连成一棵大一些的二叉树，该二叉树的频率值设为两棵子树频率值 之和。 步骤3：对上面得到的树林重复步骤2的做法，直到所有符号都连入树中为止。 数据结构定义typedef struct unsign

3、ed long weight; int parent, lchild, rchild; HTNode, *HuffmanTree; typedef char* HuffmanCode; / 指向存放数组指针的数组即二维数组 包含的函数：（1）void Select(HuffmanTree &HT,int n,int*s1,int*s2)，实现从HT1.n中选出权值最小的两个节点（2）void CreateHuffmanTree(HuffmanTree&HT,float*w,int n)，创造huffman树（3）void HuffmanCoding(HuffmanTree HT,Huffman

4、Code &HC,int n)，对信源符号进行编码（4）void OutputHuffCode(HuffmanCode HC,char*ch,float*w,int n)，输出编码函数的实现：void Select(HuffmanTree &HT,int n,int*s1,int*s2) int i; float p,q; p=q=1.0; for (i=1;i=n;i+) if(HTi.parent=0 & (HTi.weightp | HTi.weightq) if(pq) q=HTi.weight; *s2=i; else p=HTi.weight; *s1=i; if (*s2*s1)

5、/指针s1存放权值较小的节点 i=*s1; *s1=*s2; *s2=i; void CreateHuffmanTree(HuffmanTree&HT,float*w,int n) int i,m; int s1,s2; HuffmanTree t; if(n=1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for (t=HT,i=1;iweight=*w; t-parent=0; t-lchild=0; t-rchild=0; for(;iweight=0; t-parent=0; t-lchild=0; t-r

6、child=0; for (i=n+1;i=m;+i) Select(HT,i-1,&s1,&s2); HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n) int i,p,q,start; char*cd; HC=(HuffmanCode)malloc(n+1)*sizeof(char*); cd=(char*)malloc(n*sizeof(

7、char); cdn-1=0;/编码结束符 for (i=1;i=n;+i) start=n-1;/ 编码结束位置 for (p=i,q=HTi.parent;q!=0;p=q,q=HTq.parent)/从叶节点到根节点 逆向求编码 if (HTq.lchild =p) start-; cdstart=0;/左孩子编码为0 else start-; cdstart=1;/ 左孩子编码为1 HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart);/将编码从cd复制到HC中 free(cd);void OutputHuffCod

8、e(HuffmanCode HC,char*ch,float*w,int n) printf(huffman编码?为a：on); for (int i=1;i=n;i+) printf(%ct%ft,chi-1,wi-1); puts(HCi); printf(n);结果显示：学习心得： 本次实验，熟悉了课堂上的信源编码的一种，即huffman编码，加深了对知识的理解，通过编程简单实现了编码，但是我的程序存在一些缺陷，即在我的程序中需要手工输入信源符号的概率，我觉得可以输入一串字符串，统计每个字符出现的概率，这样更加方便，另外从HT1.n中选出权值最小的两个节点可以通过最小堆来实现，效率更高一

9、些。附录：文件huffman.h：#ifndef HUFFMANCODE_H#define HUFFMANCODE_H#include #include #include typedef struct float weight; int parent, lchild, rchild; HTNode,*HuffmanTree;typedef char* HuffmanCode;void Select(HuffmanTree &HT,int n,int*s1,int*s2) int i; float p,q; p=q=1.0; for (i=1;i=n;i+) if(HTi.parent=0 &

10、(HTi.weightp | HTi.weightq) if(pq) q=HTi.weight; *s2=i; else p=HTi.weight; *s1=i; if (*s2*s1) i=*s1; *s1=*s2; *s2=i; void CreateHuffmanTree(HuffmanTree&HT,float*w,int n) int i,m; int s1,s2; HuffmanTree t; if(n=1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for (t=HT,i=1;iweight=*w;

11、t-parent=0; t-lchild=0; t-rchild=0; for(;iweight=0; t-parent=0; t-lchild=0; t-rchild=0; for (i=n+1;i=m;+i) Select(HT,i-1,&s1,&s2); HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n) int i,p,q,start;

12、 char*cd; HC=(HuffmanCode)malloc(n+1)*sizeof(char*); cd=(char*)malloc(n*sizeof(char); cdn-1=0; for (i=1;i=n;+i) start=n-1; for (p=i,q=HTi.parent;q!=0;p=q,q=HTq.parent); if (HTq.lchild =p) start-; cdstart=0; else start-; cdstart=1; HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); free(c

13、d);void OutputHuffCode(HuffmanCode HC,char*ch,float*w,int n) printf(huffman编码?为a：on); for (int i=1;i=n;i+) printf(%ct%ft,chi-1,wi-1); puts(HCi); printf(n);#endifmain函数：int _tmain(int argc, _TCHAR* argv) HuffmanTree HT; HuffmanCode HC; int n,i; float sum=0; char *ch; float*w; coutn; w=(float*)malloc(

14、n*sizeof(float); ch=(char*)malloc(n*sizeof(char); cout请?输?入?字?符?和每?个?字?符?发生的?概?率：oendl; for (i=0;ichiwi; sum+=wi; cout剩余概?率为a1.0-sum!endl; for (i=0;in;i+) CreateHuffmanTree(HT,w,n); HuffmanCoding(HT,HC,n); OutputHuffCode(HC,ch,w,n); free(w); free(ch); return 0; 实验2 CRC 校验码编码实验 本实验中，是对（7,4）循环码的编码。实验原

15、理：CRC 校验的基本思想是利用线性编码理论，在发送端根据要传送的k 位二进制码序列，以一定的规则产生一个校验用的监督码（CRC 码）r 位，并附在信息后边，构成一个新的二进制码序列数共 (k+r) 位，最后发送出去。在接收端，则根据信息码和CRC 码之间所遵循的规则进行检验，以确定传送中是否出错。数据结构： 定义生成多项式为g（x）=x3+x2+1, 因此采用数组 int a4=1,1,0,1来表示该多项式。主要函数：void code(int a1,int b1) int c7; int i,j; for (i=0;i7;i+)/把所有的信息位左移三位 if (i4) ci=b1i; el

16、se ci=0; for (i=0;i4;i+) for (j=0;j4;j+) ci+j=ci+ja1j; for(i=0;i7;i+) if(i4) ci=b1i; coutci; 实验结果：实习体会 通过这个实验，我熟悉了按位计算CRC码，但是我的算法不具有普遍性和通用性，针对是特点情况，另外我在网上还看到了其他几种方式来计算CRC码，如按字节计算CRC码，按半字节计算CRC码，但是按字节计算CRC码需要很大的空间，按位计算CRC码需要较长的时间，而按半字节计算CRC码就均衡了上面的两种方式。代码附录：#include using namespace std;void code(int

17、a1,int b1) int c7; int i,j; for (i=0;i7;i+)/把所有的信息位左移三位 if (i4) ci=b1i; else ci=0; for (i=0;i4;i+) for (j=0;j4;j+) ci+j=ci+ja1j; for(i=0;i7;i+) if(i4) ci=b1i; coutci; int _tmain(int argc, _TCHAR* argv) int a4=1,1,0,1; int b4; cout本程序是实现（7,4）循-环码?，生成多项式为个g（x）=x3+x2+1！endl; cout请输入4位的信息位?：; for (int i=0;ibi; cout7位编码为：; code(a,b); coutendl; return 0;