信息论与编码实验报告实验课程名称：赫夫曼编码（二进制与三进制编码）
专业信息与计算科学
班级信息与计算科学1班
学生姓名李林钟
学号 2013326601049
指导老师王老师
一、实验目的
利用赫夫曼编码进行通信可以大大提高通信利用率，缩短信息传输时间，降低传输成本。赫夫曼编码是信源编码中最基本的编码方法。
●
理解赫夫曼编码，无论是二进制赫夫曼编码，还是m 进制赫夫曼编码，都要理解其编码原理和编码步骤。 ● 回顾无失真信源编码定理，理解无失真编码的基本原理和常用编码方法。。 ●
掌握二进制赫夫曼编码和m 进制赫夫曼编码的基本步骤，能计算其平均码长，编码效率等。 ●
应用二进制赫夫曼编码或m 进制赫夫曼编码处理简单的实际信源编码问题。
二、实验环境与设备
1、操作系统与编程软件：windows 操作系统，cfree5.0， Visual C++ 6.0。
2、编程语言：C 语言以及C++语言 三、实验内容
1. 二进制赫夫曼编码原理及步骤： （1）信源编码的计算
设有N 个码元组成的离散、无记忆符号集，其中每个符号由一个二进制码字表示，信源符号个数n 、信源的概率分布P={p(s i )},i=1,…..,n 。且各符号xi 的以li 个码元编码，在变长字编码时每个符号的平均码长为∑==n
i li xi p L 1)( ；
信源熵为：)(log )()(1
xi p xi p X H n
i ∑=-= ；
唯一可译码的充要条件：11
≤∑=-n
i Ki m ；
其中m 为码符号个数，n 为信源符号个数，Ki 为各码字长度。 （2）二元霍夫曼编码规则
（1）将信源符号依出现概率递减顺序排序。
（2）给两个概率最小的信源符号各分配一个码位“0”和“1”，将两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含（n-1）个信源符号的新信源。称为信源的第一次缩减信源，用s1 表示。
（3）将缩减信源 s1 的符号仍按概率从大到小顺序排列，重复步骤(2)，得到只含（n-2）个符号的缩减信源s2。
(3).算法基本步骤描述
(4).编码及注解（见附页1） (5).验证截图:
得到信源得出信源序列个得出信源序列的计算信源符输
输
输
输
输
信源符号的赫弗曼码方
编码效
平均码
输
2. 三进制编码：
(1).三进制赫弗曼编码原理：
对于多进制赫夫曼编码，为了提高编码效率，就要是长码的符号数量尽量少、概率尽量小，所以信源符号数量最好满足n=(m-1)*k+r,其中m 为进制数，k 为缩减的次数。 设计步骤如下：
[1]将信源符号按概率从大到小的顺序排列，令 p(x1)≥ p(x2)≥…≥ p(xn)
[2]给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，或者在新添加一个信源符号，令其概率为0，则个分配一个码位“0”、“1”和“2”，将其合并，结果得到一个只包含(n －1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。
[3]将缩减信源S1的符号仍按概率从大到小顺序排列，此后每次合并3个信源符号，得到只含(n －3)个符号的缩减信源S2。
[4]重复上述步骤，直至最后，此时所剩符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。
(2).编码及注解（见附页2）
(3).例题：对如下单符号离散无记忆信源编三进制赫夫曼码。
这里：m =3，n =8
令k =3，m +k (m －1)=9，则 s =9－n =9－8=1 所以第一次取m －s =2个符号进行编码。 由计算可得： 平均码长为：
（3.1） 信息率为：
12345678,,,,,
()0.40.180.10.10.070.060.050.04X x x x x x x x x P X ????=????
????
5
11
()0.41(0.180.10.070.06)2(0.050.04)3 1.69(/)
i
i
i K p x k
===?++++?++?=∑比特符号
编码效率为：
（3.3）
(4).验证结果截图：
() 2.55
95.2%2.68
H X R η=
==
四.实验总结：
用C语言实现二进制赫夫曼编码对信源无失真编码。由于课本知识点的不太理解，一点都不知道编码的过程，后来通过阅读<<信息论与编码>>课本、网上查阅资料，最后才对本次设计有了一定的理解，详细理解了赫夫曼的具体编码过程。经过理解，发现这种编码其实挺简单的，最重要的是怎样用程序把他实现，这对我们的编程能力也是一次考验。设计要求中要求计算信源熵，这又考察了现代通信原理的知识。
以C++语言实现三进制赫夫曼编码来诠释多进制赫夫曼编码，其实不论是几进制的赫夫曼编码，只要掌握了编码的原理，是非常简单的。通过这次课程设计，我又重新的将信息论编码与设计的教材翻看了一遍，在网上也搜到了不少相关的知识，知识有提升不少。在这次课程设计中，最让人难懂的就是C++的编程，让我找了不少相关的书籍，上网查阅了不少的程序，对以前学过的编程又进一步巩固和提高了。在编程中，要涉及到编制赫夫曼树，平均码长，编码效率，信息率，信源熵。通过同学，网上查阅资料，终于得到解决，虽然仍有一些问题，但是大体上自己能编程出来，是对自己的考验。而且由网上得知：赫夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。赫夫曼编码在具体实用时，设备较复杂。在编码器中需要增加缓冲寄存器，因为每个信源符号所对应的码符号长度不一，负责会造成输入和输出不能保持平衡。
对于自己来说，编程能力尚有欠缺，自主编程能力较差，希望以后多加学习，掌握基础语言的编程基础。
附页1：
#include
#include
#include
#define MAX 100
//定义全局变量h存放信息熵
double h=0;
//定义结构体用于存放信源符号，数目及概率
typedef struct{
//不同的字符
char SOURCECODE;
//不同字符出现的次数
int NUM;
//不同字符出现的概率
double PROBABILITY;
//赫夫曼编码符号
int Code[MAX];
int start;
//赫夫曼树的父结点
int parent;
//赫夫曼树的左右子结点
int lchild;
int rchild;
//赫夫曼编码的长度
int lengthofhuffmancode;
}Hcode;
Hcode INFORMATION[MAX];
//该函数用来求信源所包含的符号，以及不同符号出现的次数和概率
int Pofeachsource(char informationsource[MAX],int a)
{
int i,j=1,m,flag=0;
char temp;
//预先存入第一个字符，便于与后面的字符进行比较
//统计不同的字符存入结构体数组中
//利用flag标签来标记每个字符是否出现过，若出现过标记为1，否则置为零INFORMATION[0].SOURCECODE=informationsource[0];
for(i=1;i flag=0; if(informationsource[m]==informationsource[i]){ flag=1; break; } } if(flag==1) continue; else INFORMATION[j++].SOURCECODE=informationsource[i]; } INFORMATION[j].SOURCECODE='\0'; printf("信源符号数为:%d\n",j); //统计相同的字符出现的次数 //每做一个字符出现次数的统计都将结构体数组里的NUM置为零 for(i=0;i for(m=0;m if(informationsource[m]==INFORMATION[i].SOURCECODE) INFORMATION[i].NUM++; } //统计每个字符出现的概率 for(i=0;i //将每个不同字符出现的次数概率都显示出来 for(i=0;i printf("The NUM and PROBABILITY of Code'%c'is %d and %.3f\n",INFORMATION[i].SOURCECODE,INFORMATION[i].NUM,INFORMATION[ i].PROBABILITY); return j; } //求信源符号的熵 void H(int a){ int i; for(i=0;i h+=((-1)*(INFORMATION[i].PROBABILITY)*(log(INFORMATION[i].PROBABI LITY)/log(2))); } } //赫夫曼编码函数 void Huffman(int a) { Hcode cd; int i,j,m=0,lm=0,p,c; double min,lmin; //顺序初始化每个信源父子结点为-1 for(i=0;i { INFORMATION[i].parent=-1; INFORMATION[i].lchild=-1; INFORMATION[i].lchild=-1; } //循环构造Huffman树 for(i=0;i { //min,lmin中存放两个无父结点且结点权值最小的两个结点 min=lmin=MAX; //找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 for (j=0;j { if((INFORMATION[j].PROBABILITY { lmin=min; lm=m; min=INFORMATION[j].PROBABILITY; m=j; } else if ((INFORMATION[j].PROBABILITY { lmin=INFORMATION[j].PROBABILITY; lm=j; } } //设置找到的两个子结点 m、lm 的父结点信息 INFORMATION[m].parent=a+i; INFORMATION[lm].parent=a+i; INFORMATION[a+i].PROBABILITY=INFORMATION[m].PROBABILITY+INFORMATION[l m].PROBABILITY; INFORMATION[a+i].parent=-1; INFORMATION[a+i].lchild=m; INFORMATION[a+i].rchild=lm; } for (i=0;i { cd.start=a-1; c=i; p=INFORMATION[c].parent; while(p!=-1) /* 父结点存在 */ { if(INFORMATION[p].lchild==c) cd.Code[cd.start]=1; else cd.Code[cd.start]=0; cd.start--; /* 求编码的低一位 */ c=p; p=INFORMATION[c].parent; /* 设置下一循环条件 */ } //保存求出的每个叶结点的赫夫曼编码和编码的起始位 for(j=cd.start+1;j { INFORMATION[i].Code[j]=cd.Code[j];} INFORMATION[i].start=cd.start; } } main() { //定义存放信源符号的数组 char informationsource[MAX]; int i,j,m; double averageofhuffmancode=0.0,Eita,cV=0.0; printf("please input the source of information:"); for(i=0;;i++){ scanf("%c",&informationsource[i]); if(informationsource[i]=='\n') break; } informationsource[i]='\0'; printf("信源序列为:"); //显示已输入的一串信源符号 puts(informationsource); //返回不同信源符号的数目 m=Pofeachsource(informationsource,i); //求信源的符号熵 H(m); printf("信源的符号熵:H(X)=%.3f(比特/符号)\n",h); Huffman(m); //输出已保存好的所有存在编码的赫夫曼编码 for(i=0;i { printf("%c's Huffman code is: ",INFORMATION[i].SOURCECODE); for(j=INFORMATION[i].start+1;j printf("%d",INFORMATION[i].Code[j]); INFORMATION[i].lengthofhuffmancode=m-INFORMATION[i].start-1; printf("\n"); } //求赫夫曼编码的平均码长和编码效率 for(i=0;i averageofhuffmancode+=INFORMATION[i].PROBABILITY*INFORMATION[i].l engthofhuffmancode; printf("赫夫曼编码的平均码长为:%lf(码元/信源符 号)\n",averageofhuffmancode); Eita=h/averageofhuffmancode; printf("赫夫曼编码的编码效率为:%lf\n",Eita); //求赫弗曼编码的码方差 for(i=0;i cV+=INFORMATION[i].PROBABILITY*INFORMATION[i].lengthofhuffmancode *INFORMATION[i].lengthofhuffmancode; cV-=averageofhuffmancode*averageofhuffmancode; printf("赫弗曼编码的码方差为：%lf\n",cV); } 附页2 #include #include #include #include #include #include using namespace std; ///vector属于std命名域，因此使用全局命名域方式 struct Huffman_InformationSource //信源类型 { char InformationSign[10]; //信源符号 double Probability; //概率 char Code[10]; //编码结果 int CodeLength; //码长 }; struct HuffNode //赫夫曼树的节点类型 { char InformationSign[10]; double Probability; HuffNode *LeftSubtree,*middleSubtree,*RightSubtree,*Next; char Code[10]; int CodeLength; }; class CHuffman_3 //三进制赫夫曼编码 { public: CHuffman_3() //初始化 { ISNumber=0; AvageCodeLength=0.0; InformationRate=0.0; CodeEfficiency=0.0; } ~CHuffman_3() { DestroyBTree(HuffTree); } void Huffman_Input(); //输入信息 void Huffman_Sort(); //排序 void Huffman_Tree(); //构造赫夫曼树 void Huffman_Coding(); //生成赫夫曼编码 void Huffman_CodeAnalyzing(); //结果分析 void Huffman_Display(); //显示结果信息 void DestroyBTree(HuffNode *TreePointer); //释放资源 private: vector int ISNumber; //符号个数 double AvageCodeLength; //平均码长 double InformationRate; //信息率 double CodeEfficiency; //编码效率 HuffNode * HuffTree; //赫夫曼树 private: void Huffman_Code(HuffNode *TreePointer); }; //输入信源信息如果需要添加信源信息在这里修改即可 void CHuffman_3::Huffman_Input() { Huffman_InformationSource temp1={"A",0.40,"",0}; ISarray.push_back(temp1); Huffman_InformationSource temp2={"B",0.18,"",0}; ISarray.push_back(temp2); Huffman_InformationSource temp3={"C",0.10,"",0}; ISarray.push_back(temp3); Huffman_InformationSource temp4={"D",0.10,"",0}; ISarray.push_back(temp4); Huffman_InformationSource temp5={"E",0.07,"",0}; ISarray.push_back(temp5); Huffman_InformationSource temp6={"F",0.06,"",0}; ISarray.push_back(temp6); Huffman_InformationSource temp7={"G",0.05,"",0}; ISarray.push_back(temp7); Huffman_InformationSource temp8={"H",0.04,"",0}; ISarray.push_back(temp8); ISNumber=ISarray.size(); } //按概率“从大到小”排序： void CHuffman_3::Huffman_Sort() { Huffman_InformationSource temp; int i,j; for(i=0;i for(j=i+1;j if(ISarray[i].Probability { temp=ISarray[i]; ISarray[i]=ISarray[j]; ISarray[j]=temp; } } //基于ISarray数组构造赫夫曼树 void CHuffman_3::Huffman_Tree() { int i; HuffNode *ptr1,*ptr2,*ptr3,*ptr4,*temp1,*temp2; //（1）：基于数组，创建单向链表 ptr1=new HuffNode; strcpy(ptr1->InformationSign,ISarray[0].InformationSign); ptr1->Probability=ISarray[0].Probability; strcpy(ptr1->Code,ISarray[0].Code); ptr1->LeftSubtree=NULL; ptr1->middleSubtree =NULL; ptr1->RightSubtree=NULL; ptr1->Next=NULL; HuffTree=ptr1; //赋给数据成员HuffTree for(i=1;i { ptr2=new HuffNode; strcpy(ptr2->InformationSign,ISarray[i].InformationSign); ptr2->Probability=ISarray[i].Probability; strcpy(ptr2->Code,ISarray[i].Code); ptr2->LeftSubtree=NULL; ptr2->middleSubtree =NULL; ptr2->RightSubtree=NULL; ptr2->Next=ptr1; ptr1=ptr2; } //结果：链表的表头为数组的最小元素。 HuffTree=ptr1; //使HuffTree指向链表头 //（2）：基于链表，构造赫夫曼树 int k; //树的层次 int s; //需要添加的无用符号的数目。 k=ceil((double)(ISNumber-3)/(3-1)); //“3”：表示三进制 //ceil函数：向上取整； //floor函数：向下取整s=3+k*(3-1)-ISNumber; if(s==1) //第一次取m-s=3-1=2个符号 { //合并概率最小的二个节点ptr1、ptr2，生成一个新节点ptr4： ptr2=ptr1->Next; ptr4=new HuffNode; strcpy(ptr4->InformationSign,"*"); //新节点的符号为“*” ptr4->Probability=ptr1->Probability+ptr2->Probability; //新节点的概率为二者之和 strcpy(ptr4->Code,""); ptr4->LeftSubtree =NULL; ptr4->middleSubtree=ptr1; //最小的节点ptr1成为ptr4的“中”子树，将来赋予码元“1” ptr4->RightSubtree=ptr2; //次小的节点ptr2成为ptr4的“右”子树，将来赋予码元“0” HuffTree=ptr2->Next; //指向下一个节点 //重新排序： temp1=HuffTree; while(temp1&&(ptr4->Probability>temp1->Probability)) { temp2=temp1; temp1=temp1->Next; } ptr4->Next=temp1; //插在当前节点temp1之前 if(temp1==HuffTree) HuffTree=ptr4; else temp2->Next=ptr4; //插在temp2节点之后ptr1=HuffTree; } while(ptr1->Next) { //合并概率最小的三个节点ptr1、ptr2，生成一个新节点ptr4： ptr2=ptr1->Next; ptr3=ptr2->Next; ptr4=new HuffNode; strcpy(ptr4->InformationSign,"*"); //新节点的符号为“*” ptr4->Probability=ptr1->Probability+ptr2->Probability +ptr3->Probability; //新节点的概率为三者之和 strcpy(ptr4->Code,""); ptr4->LeftSubtree=ptr1; //最小的节点ptr1成为ptr4的“左”子树，将来赋予码元“2” ptr4->middleSubtree=ptr2//次小的节点ptr2成为ptr4的“中”子树，将来赋予“1” ptr4->RightSubtree=ptr3;//次次小的节点ptr3成为ptr4的“右”子树，将来赋予“0” HuffTree=ptr3->Next; temp1=HuffTree; while(temp1&&(ptr4->Probability>temp1->Probability)) { temp2=temp1; temp1=temp1->Next; } ptr4->Next=temp1; //插在当前节点temp1之前 if(temp1==HuffTree) HuffTree=ptr4; else temp2->Next=ptr4; //插在temp2节点之后ptr1=HuffTree; } //释放： ptr1=NULL; ptr2=NULL; ptr3=NULL; ptr4=NULL; temp1=NULL; temp2=NULL; //设置根节点： strcpy(HuffTree->Code,""); HuffTree->CodeLength=0; } //生成赫夫曼码： void CHuffman_3::Huffman_Code(HuffNode *TreePointer) { if (TreePointer == NULL) return; char tempstr[10]=""; if(!TreePointer->LeftSubtree&&!TreePointer->middleSubtree &&!TreePointer->RightSubtree) { for(int i=0;i if(strcmp(ISarray[i].InformationSign,TreePointer->InformationSign )==0) { strcpy(ISarray[i].Code,TreePointer->Code); ISarray[i].CodeLength=TreePointer->CodeLength; return; } return; } if(TreePointer->LeftSubtree) { //生成左子树编码： strcpy(tempstr,TreePointer->Code); strcat(tempstr,"2"); strcpy(TreePointer->LeftSubtree->Code,tempstr); TreePointer->LeftSubtree->CodeLength=TreePointer->CodeLength+1; Huffman_Code(TreePointer->LeftSubtree); } if(TreePointer->middleSubtree) { //生成中子树编码： strcpy(tempstr,TreePointer->Code); strcat(tempstr,"1"); strcpy(TreePointer->middleSubtree->Code,tempstr); TreePointer->middleSubtree->CodeLength=TreePointer->CodeLength+1; Huffman_Code(TreePointer->middleSubtree); } if(TreePointer->RightSubtree) { //生成右子树编码： strcpy(tempstr,TreePointer->Code); strcat(tempstr,"0"); strcpy(TreePointer->RightSubtree->Code,tempstr); TreePointer->RightSubtree->CodeLength=TreePointer->CodeLength+1; Huffman_Code(TreePointer->RightSubtree); } } void CHuffman_3::Huffman_Coding() { Huffman_Code(HuffTree); } //编码结果分析 void CHuffman_3::Huffman_CodeAnalyzing() { //(1):平均码长 for(int i=0;i AvageCodeLength+=ISarray[i].Probability*ISarray[i].CodeLength; //(2):信息率 int L=1; //单符号时，L=1 int m=3; //三进制编码，m=3 InformationRate=AvageCodeLength/L*(log(m)/log(2)); //(3):编码效率 double Hx=0; for(int j=0;j Hx+=-ISarray[j].Probability*log(ISarray[j].Probability)/log(2); CodeEfficiency=Hx/InformationRate; } //显示结果 void CHuffman_3::Huffman_Display() { cout<<"编码结果："< for(int i=0;i { cout<<"\'"< "< } cout< cout<<"平均码长："< cout<<"信息率："< cout<<"编码效率："< } //释放资源 void CHuffman_3::DestroyBTree(HuffNode *TreePointer) { if (TreePointer!= NULL) { DestroyBTree(TreePointer->LeftSubtree); DestroyBTree(TreePointer->middleSubtree); DestroyBTree(TreePointer->RightSubtree); delete TreePointer; TreePointer = NULL; } } //主函数： void main() { CHuffman_3 YYY; YYY.Huffman_Input(); YYY.Huffman_Sort(); YYY.Huffman_Tree(); YYY.Huffman_Coding(); YYY.Huffman_CodeAnalyzing(); YYY.Huffman_Display(); } 实验五霍夫曼编码 一、实验目的 1、熟悉Matlab 工作环境及工具箱； 2、掌握霍夫曼编码的基本步骤； 3、利用MATLAB实现霍夫曼编码。 二、实验内容 （1）熟悉理解Huffman编码的过程 （2）将给定的数据进行Huffman编码 知识要点： 1、霍夫曼编码的基本原理。参照教材及参考书。 2、二进制霍夫曼编码方法。 1. 基本原理： 变长编码 不要求所有码字长度相同，对不同概率的信源符号或序列，可赋予不同长度的码字。变长编码力求平均码长最小，此时编码效率最高，信源的冗余得到最大程度的压缩。 1）几种常用变长编码方法： 霍夫曼编码 费若编码 香农编码。 2）霍夫曼编码： 二进制霍夫曼编码 r进制霍夫曼编码 符号序列的霍夫曼编码。 3）二进制霍夫曼编码的编码过程： 将信源中n个符号按概率分布的大小，以递减次序排列起来； 用0和1码分别分配给概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新符号，并用这两个最小概率之和作为新符号的概率，从而得到只包含n-1个符号的新信源，称为其缩减信源； 把缩减信源的符号仍按概率大小以递减次序排列，再将最后两个概率最小的符号合并 成一个新符号，并分别用0和1码表示，这样又形成一个新缩减信源； 依次继续下去，直到缩减信源最后只剩两个符号为止。再将最后两个新符号分别用0和1 码符号表示。最后这两个符号的概率之和为1，然后从最后一级缩减信源开始，依编码路径右后向前返回，就得到各信源符号所对应得码符号序列，即对应得码字。 r进制霍夫曼编码 由二进制霍夫曼编码可推广到r进制霍夫曼编码，只是每次求缩减信源时，改求r个最小概率之和，即将r个概率最小符号缩减为一个新符号，直到概率之和为1。但要注意，即缩减过程中可能到最后没有r个符号。为达次目的，可给信源添加几个概率为零的符号。 符号序列的霍夫曼编码 对信源编码除了对信源符号编码以外，也可对信源符号序列编码，一般来说，对序列编码比对单个符号更为有效。 2 数据结构与算法描述 1）变量及函数的定义 3 实验数据与实验结果（可用文字描述或贴图的方式进行说明） 1）测试数据 0.2 0.1 0.3 0.1 0.1 0.2 2）实验结果 《信息论与编码》实验指导书 信息与通信工程学院信息工程系 2014年6月 目录 实验一绘制信源熵函数曲线 (3) 实验二哈夫曼编解码 (6) 实验三离散信道容量 (10) 1实验一绘制信源熵函数曲线 一、实验目的 1.掌握离散信源熵的原理和计算方法。 2.熟悉matlab软件的基本操作，练习应用matlab软件进行信源熵函数曲 线的绘制。 3.理解信源熵的物理意义，并能从信源熵函数曲线图上进行解释其物理意 义。 二、实验原理 1.离散信源相关的基本概念、原理和计算公式 产生离散信息的信源称为离散信源。离散信源只能产生有限种符号。 假定X是一个离散随机变量，即它的取值范围R={x1，x2，x3，…}是有限或可数的。设第i个变量x i发生的概率为p i=P{X=x i}。则： 定义一个随机事件的自信息量I（x i）为其对应的随机变量x i出现概率对数的负值。即： I（x i）= -log2p(x i) 定义随机事件X的平均不确定度H（X）为离散随机变量x i出现概率的数学期望，即： ∑∑ - = = i i i i i i x p x p x I x p X H) ( log ) ( ) ( ) ( ) ( 2 单位为比特/符号或比特/符号序列。 平均不确定度H（X）的定义公式与热力学中熵的表示形式相同，所以又把平均不确定度H（X）称为信源X的信源熵。 必须注意一下几点： a)某一信源，不管它是否输出符号，只有这些符号具有某些概率特性， 必有信源的熵值；这熵值是在总体平均上才有意义，因而是个确定 值，一般写成H（X），X是指随机变量的整体（包括概率分布）。 b)信息量则只有当信源输出符号而被接收者收到后，才有意义，这就 是给与信息者的信息度量，这值本身也可以是随机量，也可以与接 信息论与编码 《信息论与编码》这门课程给我带了很深刻的感受。信息论是人类在通信工程实践之中总结发展而来的，它主要由通信技术、概率论、随机过程、数理统计等相结合而形成。它主要研究如何提高信息系统的可靠性、有效性、保密性和认证性，以使信息系统最优化。学习这门课程之后，我学到了很多知识，总结之后，主要有以下几个方面： 首先是基本概念。信息是指各个事物运动的状态及状态变化的方式。消息是指包括信息的语言、文字和图像等。信号是消息的物理体现，为了在信道上传输消息，就必须把消息加载到具有某种物理特性的信号上去。信号是信息的载荷子或载体。信息的基本概念在于它的不确定性，任何已确定的事物都不含有信息。信息的特征：（1）接收者在收到信息之前，对其内容是未知的。（2）信息是能使认识主体对某一事物的未知性或不确定性减少的有用知识。（3）信息可以产生，也可以消失，同时信息可以被携带、存储及处理。（4）信息是可以量度的，信息量有多少的差别。编码问题可分解为3类：信源编码、信道编 码、加密编码。= 理论上传输的最少信息量 编码效率实际需要的信息量。 接下来，学习信源，重点研究信源的统计特性和数学模型，以及各类离散信源的信息测度 —熵及其性质，从而引入信息理论的一些基本概念和重要结论。本章内容是香农信息论的基础。重点要掌握离散信源的自信息，信息熵（平均自信息量），条件熵，联合熵的的概念和求法及其它们之间的关系，离散无记忆的扩展信源的信息熵。另外要记住信源的数学模型。通过学习信源与信息熵的基本概念，了解了什么是无记忆信源。信源发出的序列的统计性质与时间的推移无关，是平稳的随机序列。当信源的记忆长度为m+1时，该时刻发出的符号与前m 个符号有关联性，而与更前面的符号无关，这种有记忆信源叫做m 阶马尔可夫信源。若上述条件概率与时间起点无关，则信源输出的符号序列可看成齐次马尔可夫链，这样的信源叫做齐次马尔可夫信源。之后学习了信息熵有关的计算，定义具有概率为 () i p x 的符号i x 的自信息量为：()log ()i i I x p x =-。自信息量具有下列特性：（1） ()1,()0i i p x I x ==（2）()0,()i i p x I x ==∞（3）非负性（4）单调递减性（5）可加 性。信源熵是在平均意义上来表征信源的总体特征，它是信源X 的 函数，一般写成H （X ）。信源熵：()()log ()i i i H X p x p x =-∑，条件熵：(|)(,)log (|) i j i j ij H X Y p x y p x y =-∑联合 熵(|)(,)log (,)i j i j ij H X Y p x y p x y =-∑，联合熵 H(X,Y)与熵H(X)及条件熵H(Y|X)的关系： (,)()(|)()(|)H X Y H X H Y X H X H X Y =+=+。互信息: ,(|)(|)(;)(,)log ()(|)log () () j i j i i j i j i ij i j j j p y x p y x I X Y p x y p x p y x p y p y = = ∑ ∑ 。熵的性质：非负性，对称性，确定 性，极值性。 接下来接触到信道，知道了信道的分类，根据用户数可以分为，单用户和多用户；根 本科生实验报告 实验课程信息论与编码 学院名称信息科学与技术学院 专业名称通信工程 学生姓名 学生学号 指导教师谢振东 实验地点6C601 实验成绩 二〇一五年十一月二〇一五年十一月 实验一：香农（Shannon ）编码 一、实验目的 掌握通过计算机实现香农编码的方法。 二、实验要求 对于给定的信源的概率分布，按照香农编码的方法进行计算机实现。 三、实验基本原理 给定某个信源符号的概率分布，通过以下的步骤进行香农编码 1、将信源消息符号按其出现的概率大小排列 )()()(21n x p x p x p ≥≥≥ 2、确定满足下列不等式的整数码长K i ； 1)(l o g )(l o g 22+-<≤-i i i x p K x p 3、为了编成唯一可译码，计算第i 个消息的累加概率 ∑ -== 1 1 )(i k k i x p p 4、将累加概率P i 变换成二进制数。 5、取P i 二进制数的小数点后K i 位即为该消息符号的二进制码。 四、源程序： #include int i,j; for(i=0;i 《信息论与编码》教学大纲 一课程简介 课程编号：04254002 课程名称：信息论与编码Informatics & Coding 课程类型：基础课必修课 学时：32 学分：2 开课学期：第六学期 开课对象：通信、电子专业 先修课程：概率论与数理统计、信号与系统、随机信号原理。 参考教材：信息论与编码，陈运，周亮，陈新，电子工业出版社，2002年8月 二课程性质、目的与任务 信息论在理论上指出了建立最佳编码、最佳调制和最佳接收方法的最佳系统的理论原则，它对通信体制和通信系统的研究具有指导意义。提高信息传输的可靠性和有效性始终是通信工作所追求的目标。因此，信息论与编码是从事通信、电子系统工程的有关工程技术人员都必须掌握的基本理论知识。 内容提要：本课程包括狭义相对论和提高通信可靠性的差错控制编码理论。信息论所研究的主要问题是在通信系统设计中如何实现有效性和可靠性。 三教学基本内容与基本要求 本课程总学时为32。其中理论教学为28，实验学时为4。 主要的理论教学内容包括：离散信源和连续信源的熵、条件熵、联合熵和平均互信息量的概念及性质；峰值功率受限和平均功率受限下的最大熵定理和连续信源熵的变换；变长码的霍夫曼编码方法，熟悉编码效率和平均码长的计算；最大后验概率准则和最大似然译码准则等。 实验内容主要包括：离散无记忆信道容量的迭代算法，循环码的编译码。 四教学内容与学时分配 第3章离散信源无失真编码 第6章网络信息论 （教学要求：A—熟练掌握；B—掌握；C—了解） 五实习、实验项目及学时分配 1．离散无记忆信道容量的迭代算法2学时 要求用Matlab编写计算离散信道容量的实用程序并调试成功，加深对信道容量的理解。 2．循环码的编译码2学时 要求用Matlab编写程序，用软件完成循环码的编译码算法。 六教学方法与手段 常规教学与多媒体教学相结合。 《信息论与编码》课程教学大纲、课程基本信息 二、课程内容及基本要求 第一章绪论 课程内容： 1 ?信息论之父--香农；信息论与香农信息论的形成与发展；香农信息论的中心 问题及其局限性； 2．信息、消息、信号、信息的本质、信息的广义性； 3．通信系统基本模型：信源、信宿、信道、干扰、噪声、信源编码、信道编码。基本要求：1．了解信息论之父---Shannon（香农）和香农信息论的基本思想及其局限性；了解信息论的形成与发展过程；了解香农信息论的基本思想（中心问题）及其适用范围；2．理解消息、信息与信号的含义；理解消息、信息与信号之间的联系与区别；3．熟悉通信系统的基本模型及各模块的主要功能。 本章重点香农信息论的中心问题、通信系统模型 本章难点：信息、消息与信号的联系与区别；香农信息论的局限性第二章信源、信息量和信息熵 课程内容： 1．无记忆信源与有记忆信源、离散信源与连续信源、离散序列信源、马尔可夫信源、离散无记忆信源、离散无记忆序列信源； 2．非平均信息量、信源熵、条件信息量、条件熵、噪声熵、损耗熵、联合熵、非平均互信息、平均互信息； 3．熵的性质、离散无记忆信源的序列熵、离散有记忆信源的序列熵；4．数据处理中信息的变化、连续信源熵；5．凸函数、互信息量的凸性，冗余度。 基本要求： 1．了解并掌握信源的分类与特点； 2．理解并掌握非平均信息量、信源熵、互信息量、条件熵、联合熵、非平均互信息量、平均互信息的概念，计算；理解并掌握信源熵、信宿熵、噪声熵、损耗熵、平均 互信息之间的关系； 3．理解马尔可夫信源的概念、理解离散序列信源熵的概念； 4．理解熵的性质、熵的唯一性原理；理解连续信源的熵及连续熵的性质； 5．理解凸函数的含义和性质；了解凸函数在信息论中的应用。 本章重点：非平均自信息量、条件信息量、互信息量、条件互信息量、熵、条件熵、熵的性质 本章难点：平均互信息量、熵、离散序列信源熵、马尔可夫信源、条件熵、噪声熵、损耗熵第三章信源编码 课程内容： 1．编码的定义与分类；奇异码与非奇码；唯一可译码与非唯一可译码；即时码与非即时码；克拉夫特不等式；码树；平均码长的计算；信息传输速率；2．无失真信源编码；定长码与定长编码定理；变长码与变长编码定理；最佳变长码编码定理；香农编码及其过程；费诺编码及其过程；哈夫曼编码及其过程；3．限失真信源编码；常用信源编码--- 游程编码、算术编码、预测编码、变换编码。 基本要求： 1．理解并掌握编码的分类及特点；掌握平均码长的计算；掌握码树的使用； 2．理解无失真信源编码的含义；掌握定长码的特点与编码原理；掌握不定长编 码的特点与编码原理； 3．掌握离散无记忆信源的等长编码及不等长编码；掌握香农编码原理、掌握费 诺编码原理；掌握哈夫曼编码原理； 4．了解常用限失真信源编码方法—算术编码、游程编码、预测编码及变换编码的编码原理。 实验报告 课程名称：信息论与编码姓名： 系：专 业：年 级：学 号：指导教 师：职 称： 年月日 目录 实验一信源熵值的计算 (1) 实验二Huffman 信源编码. (5) 实验三Shannon 编码 (9) 实验四信道容量的迭代算法 (12) 实验五率失真函数 (15) 实验六差错控制方法 (20) 实验七汉明编码 (22) 实验一信源熵值的计算 、实验目的 1 进一步熟悉信源熵值的计算 2 熟悉Matlab 编程 、实验原理 熵(平均自信息)的计算公式 q q 1 H(x) p i log2 p i log2 p i i 1 p i i 1 MATLAB实现：HX sum( x.* log2( x))；或者h h x(i)* log 2 (x(i )) 流程：第一步：打开一个名为“ nan311”的TXT文档，读入一篇英文文章存入一个数组temp，为了程序准确性将所读内容转存到另一个数组S，计算该数组中每个字母与空格的出现次数( 遇到小写字母都将其转化为大写字母进行计数) ，每出现一次该字符的计数器+1；第二步：计算信源总大小计算出每个字母和空格出现的概率；最后，通过统计数据和信息熵公式计算出所求信源熵值(本程序中单位为奈特nat )。 程序流程图： 三、实验内容 1、写出计算自信息量的Matlab 程序 2、已知：信源符号为英文字母(不区分大小写)和空格输入：一篇英文的信源文档。输出：给出该信源文档的中各个字母与空格的概率分布，以及该信源的熵。 四、实验环境 Microsoft Windows 7 五、编码程序 #include"stdio.h" #include 《信息论与编码》课程论文 ——通过信息论对已有知识产生的新认识 马赛 1143031014 《信息论与编码》课程是通信专业的一门基础课。其讲述的理论——香农信息论是当今信息科学的基础，可以说没有信息论的理论支持，就没有当今的信息化社会。 通过对于信息论的学习，我认识到，信息论的贡献就是解释了什么是“信息”，同时使用数学工具，对信息及伴随它产生的各种事物概念进行了解析。近代科学的重大飞跃往往都是因人类对于一个事物有了强有力的分析工具而产生的。有了信息论这一近乎完备（存在一些缺陷）的解析理论，人类才得以驾驭信息，社会才有了长足的进步。 在学习时，我习惯于把正在学习的知识和自己已经掌握的知识进行联系。通过这种方法，可以增进对正在学习知识的理解，同时对已掌握的知识也有新的认识。下文中，列举了两个问题，同时使用信息论的角度去进行解释。 一、计算机的存储容量与信息量的联系 当今的计算机已经十分普及。存储容量，无论内存还是外存，都是判定一台计算机性能的重要指标。现在的个人计算机硬盘容量已经达到了TB级别，而在20年前，几百MB的硬盘都十分罕见。在追求更高的存储容量时，我们是否思考过存储的东西是什么？KB、MB、GB等单位究竟代表的含义是什么？ 这是计算机科学的基本知识：“8 bit = 1 byte”。bit即“位”，这是计算机存储单元最基本的单位；而信息论中也将信息量——用于衡量信息的量的单位称为bit，这两个概念有什么联系吗？ 在课程讲解时提到过这个问题，幻灯片上的答案如是解释：两者代表着不同的概念，信息论中的bit代表着信息量；而计算机中的bit代表着计算机中的二元数字1和0。 我认为两者是同一种概念，都代表信息量，而计算机中的bit是更为细化的概念，单指计算机中的信息量。信息的一种解释是：对于不确定性的消除。信息量是对信息的一种衡量手段，描述对事件不确定性消除的程度。而描述事件不确定性的量就是这个事件发生的概率，因此一个事件发生的概率与事件包含的信息量具有对应的关系。这是香农信息论对于信息量的定义。 计算机存储的依然是信息，只是信息的存储形式是01二进制数字。如果说计算机中的bit只是二元数字的话，那么这个单位就丧失了“信息”这个定义了。 用户通过互联网下载各种资料，下载的资料需要占用本地的存储空间，这是一个众所周知的例子。其实这个过程就是一个消除不确定性的过程。我们一般常识中的“空”硬盘，实际上是没有存储信息，而空间就在那里，空间中的信息有不确定，有不确定度；写入信息，实际上就是在消除不确定性，让空间中的信息确定，让其有序。这就是一种典型的信息传递过程。 计算机是2元存储结构，一个二进制符号代表1bit，根据实际计算，一个二进制符号的最大信息量即H0(X) = log22 = 1bit，这是一个将符号等同于无记忆的，每个符号之间没有联系，达到了信息量的最大值。这是最为简化的处理结果，也是最为可行的处理结果。如果严格按照信息论的角度去分析，其实每个符号之间是有联系的——各种编码、指令，如果01只是随机出现，那么只是一盘散沙。当然这是严格的理论解释，如果实际应用到存储信息的计量，那么将是不可行，计算机界的先驱是非常有远见的。 二、关于称硬币问题的思考 《信息论与信源编码》实验报告 1、实验目的 (1) 理解信源编码的基本原理； (2) 熟练掌握Huffman编码的方法； (3) 理解无失真信源编码和限失真编码方法在实际图像信源编码应用中的差异。 2、实验设备与软件 (1) PC计算机系统 (2) VC++6.0语言编程环境 (3) 基于VC++6.0的图像处理实验基本程序框架imageprocessing_S (4) 常用图像浏览编辑软件Acdsee和数据压缩软件winrar。 (5) 实验所需要的bmp格式图像（灰度图象若干幅） 3、实验内容与步骤 (1) 针对“图像1.bmp”、“图像2.bmp”和“图像3.bmp”进行灰度频率统计（即计算图像灰度直方图），在此基础上添加函数代码构造Huffman码表，针对图像数据进行Huffman编码，观察和分析不同图像信源的编码效率和压缩比。 (2) 利用图像处理软件Acdsee将“图像1.bmp”、“图像2.bmp”和“图像 3.bmp”转换为质量因子为10、50、90的JPG格式图像（共生成9幅JPG图像），比较图像格式转换前后数据量的差异，比较不同品质因素对图像质量的影响； (3) 数据压缩软件winrar将“图像1.bmp”、“图像2.bmp”和“图像3.bmp”分别生成压缩包文件，观察和分析压缩前后数据量的差异； (4) 针对任意一幅图像，比较原始BMP图像数据量、Huffman编码后的数据量（不含码表）、品质因素分别为10、50、90时的JPG文件数据量和rar压缩包的数据量，分析不同编码方案下图像数据量变化的原因。 4、实验结果及分析 (1)在VC环境下，添加代码构造Huffman编码表，对比试验结果如下： a.图像1.bmp： 中南大学 《信息论与编码》实验报告 题目信源编码实验 指导教师 学院 专业班级 姓名 学号 日期 目录 一、香农编码 (3) 实验目的 (3) 实验要求 (3) 编码算法 (3) 调试过程 (3) 参考代码 (4) 调试验证 (7) 实验总结 (7) 二、哈夫曼编码 (8) 实验目的 (8) 实验原理 (8) 数据记录 (9) 实验心得 (10) 一、香农编码 1、实验目的 （1）进一步熟悉Shannon 编码算法； （2）掌握C 语言程序设计和调试过程中数值的进制转换、数值与字符串之间 的转换等技术。 2、实验要求 （1）输入：信源符号个数q 、信源的概率分布p ； （2）输出：每个信源符号对应的Shannon 编码的码字。 3、Shannon 编码算法 1：procedure SHANNON(q,｛Pi ｝) 2: 降序排列｛Pi ｝ 3: for i=1 q do 4: F(i s ) 5：i l 2 []log 1/()i p s 6：将累加概率F(i s )（十进制小数）变换成二进制小数。 7：取小数点后i l 个二进制数字作为第i 个消息的码字。 8：end for 9：end procedure ------------------------------------------------------------------------------------------------------------------ 4、调试过程 1、fatal error C1083: Cannot open include file: 'unistd.h': No such file or directory fatal error C1083: Cannot open include file: 'values.h': No such file or directory 原因：unistd.h 和values.h 是Unix 操作系统下所使用的头文件 纠错：删去即可 2、error C2144: syntax error : missing ')' before type 'int' error C2064: term does not evaluate to a function 原因：l_i(int *)calloc(n,sizeof(int)); l_i 后缺少赋值符号使之不能通过编译 纠错：添加上赋值符号 1 1 ()i k k p s -=∑ 实验一 绘制二进熵函数曲线（2个学时） 一、实验目的： 1. 掌握Excel 的数据填充、公式运算和图表制作 2. 掌握Matlab 绘图函数 3. 掌握、理解熵函数表达式及其性质 二、实验要求： 1. 提前预习实验，认真阅读实验原理以及相应的参考书。 2. 在实验报告中给出二进制熵函数曲线图 三、实验原理： 1. Excel 的图表功能 2. 信源熵的概念及性质 ()()[] ()[]())(1)(1 .log )( .) ( 1log 1log ) (log )()(10 , 110)(21Q H P H Q P H b n X H a p H p p p p x p x p X H p p p x x X P X i i i λλλλ-+≥-+≤=--+-=-=≤≤? ?????-===??????∑ 单位为 比特/符号 或 比特/符号序列。 当某一符号xi 的概率p(xi)为零时，p(xi)log p(xi) 在熵公式中无意义，为此规定这时的 p(xi)log p(xi) 也为零。当信源X 中只含有一个符号x 时，必有p(x)=1，此时信源熵H （X ）为零。 四、实验内容： 用Excel 和Matlab 软件制作二进熵函数曲线。根据曲线说明信源熵的物理意义。 （一） Excel 具体步骤如下： 1、启动Excel 应用程序。 2、准备一组数据p 。在Excel 的一个工作表的A 列（或其它列）输入一组p ，取步长为0.01，从0至100产生101个p （利用Excel 填充功能）。 3、取定对数底c，在B列计算H(x) ,注意对p=0与p=1两处，在B列对应位置直接输入0。Excel中提供了三种对数函数LN(x),LOG10(x)和LOG(x,c)，其中LN(x)是求自然对数，LOG10(x)是求以10为底的对数，LOG(x,c)表示求对数。选用c=2,则应用函数LOG(x,2)。 在单元格B2中输入公式：=-A2*LOG(A2,2)-(1-A2)*LOG(1-A2,2) 双击B2的填充柄，即可完成H(p)的计算。 4、使用Excel的图表向导，图表类型选“XY散点图”，子图表类型选“无数据点平滑散点图”，数据区域用计算出的H(p)数据所在列范围，即$B$1:$B$101。在“系列”中输入X值(即p值)范围，即$A$1:$A$101。在X轴输入标题概率，在Y轴输入标题信源熵。 （二）用matlab软件绘制二源信源熵函数曲线 p = 0.0001:0.0001:0.9999; h = -p.*log2(p)-(1-p).*log2(1-p); plot(p,h) 五、实验结果 一填空题（本题20分，每小题2分） 1、平均自信息为 表示信源的平均不确定度，也表示平均每个信源消息所提供的信息量。 平均互信息 表示从Y获得的关于每个X的平均信息量，也表示发X前后Y的平均不确定性减少的量，还表示通信前后整个系统不确定性减少的量。 2、最大离散熵定理为：离散无记忆信源，等概率分布时熵最大。 3、最大熵值为。 4、通信系统模型如下： 5、香农公式为为保证足够大的信道容量，可采用（1）用频带换信噪比；（2）用信噪比换频带。 6、只要，当N足够长时，一定存在一种无失真编码。 7、当R＜C时，只要码长足够长，一定能找到一种编码方法和译码规则，使译码错误概率无穷小。 8、在认识论层次上研究信息的时候，必须同时考虑到形式、含义和效用三个方面的因素。 9、1948年，美国数学家香农发表了题为“通信的数学理论”的长篇论文，从而创立了信息论。 按照信息的性质，可以把信息分成语法信息、语义信息和语用信息。 按照信息的地位，可以把信息分成客观信息和主观信息。 人们研究信息论的目的是为了高效、可靠、安全地交换和利用各种各样的信息。 信息的可度量性是建立信息论的基础。 统计度量是信息度量最常用的方法。 熵是香农信息论最基本最重要的概念。 事物的不确定度是用时间统计发生概率的对数来描述的。 10、单符号离散信源一般用随机变量描述，而多符号离散信源一般用随机矢量描述。 11、一个随机事件发生某一结果后所带来的信息量称为自信息量，定义为其发生概率对 数的负值 。 12、自信息量的单位一般有 比特、奈特和哈特 。 13、必然事件的自信息是 0 。 14、不可能事件的自信息量是 ∞ 。 15、两个相互独立的随机变量的联合自信息量等于 两个自信息量之和 。 16、数据处理定理：当消息经过多级处理后，随着处理器数目的增多，输入消息与输出消息之间的平均互信息量 趋于变小 。 17、离散平稳无记忆信源X 的N 次扩展信源的熵等于离散信源X 的熵的 N 倍 。 18、离散平稳有记忆信源的极限熵，=∞H )/(lim 121-∞→N N N X X X X H 。 19、对于n 元m 阶马尔可夫信源，其状态空间共有 nm 个不同的状态。 20、一维连续随即变量X 在[a ，b]区间内均匀分布时，其信源熵为 log2（b-a ） 。 21、平均功率为P 的高斯分布的连续信源，其信源熵，Hc （X ）=eP π2log 21 2。 22、对于限峰值功率的N 维连续信源，当概率密度 均匀分布 时连续信源熵具有最大值。 23、对于限平均功率的一维连续信源，当概率密度 高斯分布 时，信源熵有最大值。 24、对于均值为0，平均功率受限的连续信源，信源的冗余度决定于平均功率的限定值P 和信源的熵功率P 之比 。 信息论与编码实验报告-标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII 实验一关于硬币称重问题的探讨 一、问题描述： 假设有N 个硬币，这N 个硬币中或许存在一个特殊的硬币，这个硬币或轻 或重，而且在外观上和其他的硬币没什么区别。现在有一个标准天平，但是无刻度。现在要找出这个硬币，并且知道它到底是比真的硬币重还是轻，或者所有硬币都是真的。请问： 1）至少要称多少次才能达到目的； 2）如果N=12，是否能在3 次之内将特殊的硬币找到；如果可以，要怎么称？ 二、问题分析： 对于这个命题，有几处需要注意的地方： 1）特殊的硬币可能存在，但也可能不存在，即使存在，其或轻或重未知； 2）在目的上，不光要找到这只硬币，还要确定它是重还是轻； 3）天平没有刻度，不能记录每次的读数，只能判断是左边重还是右边重，亦或者是两边平衡； 4）最多只能称3 次。 三、解决方案： 1.关于可行性的分析 在这里，我们把称量的过程看成一种信息的获取过程。对于N 个硬币，他们 可能的情况为2N+1 种，即重（N 种），轻（N 种）或者无假币（1 种）。由于 这2N+1 种情况是等概率的，这个事件的不确定度为： Y=Log(2N+1) 对于称量的过程，其实也是信息的获取过程，一是不确定度逐步消除的过程。 每一次称量只有3 种情况：左边重，右边重，平衡。这3 种情况也是等概率 的，所以他所提供的信息量为： y=Log3 在K 次测量中，要将事件的不确定度完全消除，所以 K= Log(2N+1)/ Log3 根据上式，当N=12 时，K= 2.92< 3 所以13 只硬币是可以在3 次称量中达到 信息理论与编码实验指导书 实验一离散信源信息熵 一、实验目的 1、理解自信息量和信息熵的基本含义； 2、熟练掌握自信息量和信息熵的计算； 3、熟悉MATLAB 开发环境的使用； 二、实验仪器 计算机、Matlab 仿真软件 三、实验原理 自信息是一个随机变量,它是指某一信源发出某一消息所含有的信息量。所发出的消息不同，它们所含有的信息量也就不同。任何一个消息的自信息量都代表不了信源所包含的平均自信息量，不能作为整个信源的信息测度，因此，定义自信息量的数学期望为信源的平均自信息量： 称为信息熵。信息熵的意义：信源的信息熵H是从整个信源的统计特性来考虑的。它是从平均意义上来表征信源的总体信息测度的。对于某特定的信源，其信息熵是一个确定的数值。不同的信源因统计特性不同，其熵也不同。 四、实验内容 1、根据书本习题2.5和习题2.7，建立离散信源的概率空间； 2、按照题目要求，用matlab实现离散信源自信息量和信息熵的计算； 3、将程序在计算机上仿真，验证其计算结果与实际运算结果相符否。 五、实验要求 1、提前预习实验，认真阅读实验原理以及相应的参考书。 2．简要说明信源熵的含义及信源熵的计算 3、写出信源熵的计算过程，并画出信源熵计算的程序流程图 4、给出信源熵计算的matlab源程序 5、分析软件仿真或计算结果 实验二 离散信道容量 一、实验目的 1、理解信道转移概率矩阵及其特点； 2、理解信道容量的定义和最佳输入概率分布； 3、掌握信道容量和平均互信息的计算步骤； 4、用 MATLAB 进行简单地编程 二、实验仪器 计算机、Matlab 仿真软件 三、实验原理 1、平均互信息 平均互信息代表接收到输出符号后平均每个符号获得的关于输入符号的信息量。定义为 I(X;Y)=H(X)-H(X|Y) 其中，H （X ）代表接收到输出符号以前关于输入变量X 的平均不确定性，H(X|Y)代表接收到输出符号后关于输入变量X 的平均不确定性。 2、信道容量 对于一个固定的信道，总存在一种信源，使传输每个符号平均获得的信息量最大。也就是每个固定信道都有一个最大的信息传输率。我们把这个最大的信息传输率定义为信道容量，即 信息容量是完全描述信道特性的参量，是信道能够传输的最大信息量。它与输入信源的概率分布无关，只与信道的统计特性有关。 离散信道中有一类特殊的信道，它具有很强的对称性。信道矩阵P 中每一行都是由同一集合{p1’, p2’,…, ps ’}中的诸元素不同排列组成；每一列也都是由{q1’, q2’,…, qr ’} 中的诸元素不同排列组成。对于这类信道，它的容量为 四、实验内容 1、建立教材106页习题3.9所要求的数学模型。 2、写出数学模型的Matlab 程序。 3、将程序在计算机上仿真实现。 4、验证程序的正确性。 五、实验要求 1、提前预习实验，认真阅读实验原理以及相应的参考书。 2．简要说明信道容量的含义和特点，并计算信道容量 3、写出信道容量的计算过程，并画出程序流程图 4、给出信道容量计算的matlab 源程序 )};({max )(Y X I C X P =（比特/符号） )/()',...,','(log 21symbol bit p p p H s C s -= 《信息论与编码》课程小结 《信息论与编码》课程小结信息论是应用概率论、随机过程和数理统计和近代代数等方法，来研究信息的存储、传输和处理中一般规律的学科。它的主要目的是提高通信系统的可靠性、有效性和安全性，以便达到系统的最优化。 关于信息论的基本理论体系，1948年，香农在贝尔系统技术杂志 上发表“通信的数学理论”。在文中，他用概率测度和数理统计的方法系统地讨论了通信的基本问题，得出了几个重要而带有普遍意义的结论，并由此奠定了现代信息论的基础。香农理论的核心是：揭示了在通信系统中采用适当的编码后能够实现高效率和高可靠地传输信息，并得出了信源编码定理和信道编码定理。然而，它们给出了编码的性能极限，在理论上阐明了通信系统中各种因素的相互关系，为寻找最佳通信系统提供了重要的理论依据。 对信息论的研究内容一般有以下三种理解： (1) 狭义信息论，也称经典信息论。它主要研究信息的测度、信道容量以及信源和信道编码理论等问题。这部分内容是信息论的基础理论，又称香农基本理论。 (2) 一般信息论，主要是研究信息传输和处理问题。除了香农理论以外，还包括噪声理论、信号滤波和预测、统计检测与估计理论、调制理论、信息处理理论以及保密理论等。后一部分内容以美国科学家维纳为代表，其中最有贡献的是维纳和苏联科学家柯尔莫哥洛夫。 (3) 广义信息论。广义信息论不仅包括上述两方面的内容，而且包括所有与信息有关的自然和社会领域，如模式识别、计算机翻译、心理学、遗传学、神经生理学、语言学、语义学甚至包括社会学中有关信息的问题，是新兴的信息科学理论。 信息论已经成为现代信息科学的一个重要组成部分，它是现代通信和信息技术的理论基础。现代信息论又是数学概率论下的一个分支，与遍历性理论、大偏差理论以及统计力学等都有密切关系。 关于信息论与编码课程的特点，信息论课程中运用了大量的数学知识。例如：在讨论纠错编码中生成矩阵和一致校验矩阵的关系时，需要用到矩阵的运算和性质；在讨论连续信源熵时，需要对连续信源概率密度进行积分运算；在讨论离散信源熵的最大值或信道容量的最大值时，要计算多元函数的条件极值。此外，信息论与编码中很多定理都伴随着复杂的数学证明，其中最明显的就是香农三定理（无失真信源编码定理、有 信息论与编码实验报告 课程名称：信息论与编码 实验名称：霍夫曼编码 班级： 学号： 姓名： 实验目的 1、熟练掌握Huffman编码的原理及过程，并熟练运用； 2、熟练运用MATLAB应用软件，并实现Huffman编码过程。 一、实验设备 装有MATLAB应用软件的PC计算机。 二、实验原理及过程 原理： 1、将信源符号按概率从大到小的排列，令P （X1）>=P(X2)>=P(X3)......P(Xn) 2、给两个概率最小的信源符号P（Xn-1）和P（Xn）各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含（n-1）个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。 3、将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含（n-2）个符号的缩减信源S2. 4、重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。 过程： 用MATLAB编写代码实现Huffman编码其程序为： %哈夫曼编码的MA TLAB实现（基于0、1编码）： clc; clear; A=[0.3,0.2,0.1,0.2,0.2];信源消息的概率序列 A=fliplr(sort(A));%按降序排列 T=A; [m,n]=size(A); B=zeros(n,n-1);%空的编码表（矩阵） for i=1:n B(i,1)=T(i);%生成编码表的第一列 end r=B(i,1)+B(i-1,1);%最后两个元素相加 T(n-1)=r; T(n)=0; T=fliplr(sort(T)); t=n-1; for j=2:n-1%生成编码表的其他各列 for i=1:t B(i,j)=T(i); end K=find(T==r); B(n,j)=K(end);%从第二列开始，每列的最后一个元素记录特征元素在 信息论与编码实验指导书 1 课程实验目的 本课程是一门实践性很强的专业课和核心课程，根据课程理论教学的需要安排了6学时的配套实验教学，主要内容涉及信息度量的计算方法、典型信源编码方法、典型信道容量计算方法和数据压缩方法四个实验，这四个实验的开设一方面有助于学生消化、巩固课程理论教学的知识，另一方面又可培养学生实践动手能力，同时为后续课程做好准备。 2 课程实验要求 课程实验准备要求 （1）课程实验主要为设计性实验，要求学生熟悉掌握在VC环境下编写和调试C++程序的方法。 （2）要求学生在实验前复习实验所用到的预备知识。可以查阅教材或者相关的参考资料，这需要学生有自主的学习意识和整理知识的能力。 （3）根据实验项目，设计相关的数据结构和算法，再转换为对应的书面程序，并进行静态检查，尽量减少语法错误和逻辑错误。上机前的充分准备能高效利用机时，在有限的时间内完成更多的实验内容。 课程实验过程要求 （1）生成源代码。将课前编写好的书面代码，利用VC自带的编辑器尽快输入为转换为源代码； （2）程序调试和软件测试。要求学生熟练掌握调试工具，调试正确后，认真整理源程序和注释，给出带有完整注释且格式良好的源程序清单和结果。 （3）完成实验报告。根据实验内容和完成情况，按照附件1给定的格式完成课程实验报告的编写。 课程实验报告要求 在每次课程实验后要及时进行总结和整理，并编写课程实验报告。报告格式按江西蓝天学院实验报告纸格式填写。 实验一二维随机变量信息熵的计算 [实验目的] 掌握二变量多种信息量的计算方法。 [实验学时] 2学时 [实验准备] 1．熟悉二变量多种信息量的计算方法，设计实验的数据结构和算法； 2．编写计算二维随机变量信息量的书面程序代码。 [实验内容及步骤] 离散二维随机变换熵的计算 说明： （1）利用random函数和归一化方法构造一个二维离散随机变量（X，Y）； （2）分别计算X与Y的熵、联合熵、条件熵：H（X）、H（Y）、H（X,Y）H（X|Y）、I（X|Y）； （3）对测试通过的程序进行规范和优化； （4）编写本次实验的实验报告。信息论与编码实验
信息论与编码实验指导书
信息论与编码课程总结
信息论与编码实验报告.
《信息论与编码》教学大纲
信息论与编码教学大纲
信息论与编码实验报告材料
信息论与编码课程论文
《信息论与信源编码》实验报告
香农编码实验报告
信息论与编码实验报告
信息论与编码试题集与答案(新)
信息论与编码实验报告
信息论与编码技术 实验指导书
《信息论与编码》课程小结
信息论霍夫曼编码
信息论与编码实验指导书
相关主题
文本预览