信息论与编码实验报告.doc

本科生实验报告实验课程 信息理论与编码 学院名称 信息科学与技术学院 专业名称 学生姓名 学生学号 指导教师 实验地点 实验成绩 二一六 年 九 月-二一六 年 十一 月填写说明1、 适用于本科生所有的实验报告（印制实验报告册除外）；2、 专业填写为专业全称，有专业方向的用小括号标明；3、 格式要求： 用A4纸双面打印（封面双面打印）或在A4大小纸上用蓝黑色水笔书写。 打印排版：正文用宋体小四号，1.5倍行距，页边距采取默认形式（上下2.54cm，左右2.54cm，页眉1.5cm，页脚1.75cm）。字符间距为默认值（缩放100%，间距：标准）；页码用小五号字底端居中。 具体要求：题目（二号黑体居中）； 摘要（“摘要”二字用小二号黑体居中，隔行书写摘要的文字部分，小4号宋体）；关键词（隔行顶格书写“关键词”三字，提炼3-5个关键词，用分号隔开，小4号黑体)； 正文部分采用三级标题；第1章 (小二号黑体居中，段前0.5行)1.1 小三号黑体（段前、段后0.5行）1.1.1小四号黑体（段前、段后0.5行）参考文献（黑体小二号居中，段前0.5行），参考文献用五号宋体，参照参考文献著录规则（GB/T 77142005）。实验一：香农（Shannon）编码一、实验目的掌握通过计算机实现香农编码的方法。二、实验要求对于给定的信源的概率分布，按照香农编码的方法进行计算机实现。三、实验基本原理 给定某个信源符号的概率分布，通过以下的步骤进行香农编码1.将信源消息符号按其出现的概率大小排列 2确定满足下列不等式的整数码长Ki ； 3为了编成唯一可译码，计算第i个消息的累加概率4将累加概率Pi变换成二进制数。5取Pi二进制数的小数点后K i 位即为该消息符号的二进制码。四、实验内容1.对给定信源进行二进制香农编码。2.对给定信源进行二进制香农编码。3.自已选择一个例子进行香农编码。五、实验设备 PC计算机 ，C+六、实验报告要求 1、画出程序设计的流程图，2、写出程序代码，3、写出在调试过程中出现的问题 ，4、对实验的结果进行分析。七、流程图八、程序代码/ test.cpp : 定义控制台应用程序的入口点。/#include stdafx.h#include #include using namespace std;int _tmain(int argc, _TCHAR* argv)int test;int N; coutN; cout请输入各符号的概率：endl; double *X=new doubleN; /离散无记忆信源 int i,j; for(i=0;iN;i+) coutXi+1Xi;/由小到大排序 for(i=0;iN;i+) for(j=i+1;jN;j+) if(XiXj) double temp=Xi;Xi=Xj;Xj=temp; int *K=new intN; /确定码长 for(i=0;iN;i+) Ki=int(-(log(Xi)/log(2.0)+1; /确认码长为 1-log2(p(xi) if(Ki=(-(log(Xi)/log(2.0)+1)/当Ki=-log2(p(xi)时，Ki- Ki-; /累加概率 double *pa=new doubleN;pa0=0.0; double *p=new doubleN;p0=0.0; for(i=1;iN;i+)pai=pai-1+Xi-1;pi=pai; /将累加概率转换为二进制 string *code=new stringN;for(i=0;iN;i+) for(j=0;j=1) /累加概率乘2大于1,对应码字加1,累加概率自身取余 codei+=1; pai=pai*2-1; else /累加概率乘2小于1时,对应码字加0,累加概率自身取余 codei+=0; pai*= 2; for(i=0;iN;i+) codei= codei.substr(0,Ki); /求码字 /输出码字 coutsetw(12)信源setw(12)概率p(x)setw(12)累加概率 Pa(x)setw(8)码长 Ksetw(8)码字endl; for(i=0;iN;i+)coutsetw(12)i+1setw(12)Xisetw(12)pisetw(8) Kisetw(8)data()test; return 0;实验二：费诺编码一、实验目的掌握通过计算机实现费诺编码。二、实验要求对于给定的信源的概率分布,按照费诺编码的方法进行计算机实现。三、实验基本原理 费诺编码的步骤: 1.将概率按从大到小的顺序排列；2.按编码进制数将概率分组，使每组概率和尽可能接近或相等；3.给每组分配一位码元；4.将每一分组再按同样原则划分，重复2和3，直到概率不再可分为止。四、实验内容1.对给定信源进行二进制费诺编码。2.对给定信源进行二进制费诺编码。3.自已选择一个例子进行费诺编码。五、实验设备PC计算机 ，C+ 六、实验报告要求 1、画出程序设计的流程图，2、写出程序代码，3、写出在调试过程中出现的问题 ，4、对实验的结果进行分析。七、流程图八、程序代码/feinuo.cpp : 定义控制台应用程序的入口点。/#include stdafx.h#include #include #include#includeusing namespace std;/int _tmain(int argc, _TCHAR* argv)int n;string *sign;double *p;string *code;void fano(int a,int b) /费诺编码函数if(b-a)=1) /判断该组中符号个数是否大于2 double sum=0; for(int i=a;i=b;i+) sum+=pi; /计算该组概率累加和 double s1=0, *s=new double10; for(int i=a;i=b;i+) s1+=pi;si=fabs(2*s1-sum)/sum; double min=sa; int c; for(int i=a;i=b;i+) if(si=min) min=si; c=i; /定位使两组概率和尽可能相近或相等的位置c for(int i=a;i=b;i+) if(i=c) codei+=0; /码字加0 else codei+=1; /码字加1 /判断分组点位置，进而分情况自身调用 if(c=a) fano(c+1,b); else if(c=b-1) fano(a,c); else fano(a,c);fano(c+1,b); void main()int feinuo; coutn; p=new doublen; sign=new stringn; code=new stringn; cout请输入信源符号: ; for(int i=0;isigni; cout请输入信源符号的概率: ; for(int i=0;ipi; for(int i=0;in;i+) for(int j=i+1;jn;j+) if(pipj) double temp=pi;pi=pj;pj=temp; string m=signi; signi= signj; signj=m; fano(0,n-1); /费诺编码 coutsetw(8)信源符号setw(8)概率setw(8) 码字setw(8)码长 endl; for(int i=0;in;i+)coutsetw(8)signisetw(8)pisetw(8)codeisetw(8)codei.length()feinuo;实验三：霍夫曼编码一、实验目的掌握通过计算机实现霍夫曼编码 二、实验要求对于给定的信源的概率分布，按照霍夫曼编码的方法进行计算机实现。三、实验基本原理 霍夫曼编码的步骤:(1). 把信源符号按概率大小顺序排列， 并设法按逆次序分配码字的长度。(2). 在分配码字长度时，首先将出现概率 最小的两个符号的概率相加合成一个概率(3). 把这个合成概率看成是一个新组合符号地概率，重复上述做法直到最后只剩下两个符号概率为止。(4). 完成以上概率顺序排列后，再反过来逐步向前进行编码，每一次有二个分支各赋予一个二进制码，可以对概率大的赋为0，概率小的赋为1。四、实验内容1.对给定信源进行二进制霍夫曼编码。2.对给定信源进行二进制霍夫曼编码。3.自已选择一个例子进行霍夫曼编码。五、实验设备 PC计算机，C+ 六、实验报告要求1、画出程序设计的流程图，2、写出程序代码，3、写出在调试过程中出现的问题 ，4、对实验的结果进行分析。七、流程图八、程序代码#include #include #include #include #include /-typedef struct unsigned int weight;unsigned int parent,lchild,rchild; HTNode,*HuffmanTree;typedef char *HuffmanCode;typedef struct unsigned int s1;unsigned int s2; MinCode;void Error(char *message);HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n);MinCode Select(HuffmanTree HT,unsigned int n);void Error(char *message) system(cls); fprintf(stderr,Error:%s,message); exit(1);HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n) unsigned int i,s1=0,s2=0; HuffmanTree p; char *cd; unsigned int f,c,start,m; MinCode min; if(n=1) Error(Code too small!); m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT,i=0;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; for(;iweight=0; p-parent=0; p-lchild=0; p-rchild=0; for(i=n+1;i=m;i+) min=Select(HT,i-1); s1=min.s1; s2=min.s2; HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; printf(HT List:n); printf(Numberttweightttparentttlchildttrchildn); for(i=1;i=m;i+) printf(%dtt%dtt%dtt%dtt%dn, i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild); 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(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start=0; else cd-start=1; HCi=(char *)malloc(n-start)*sizeof(char *); strcpy(HCi,&cdstart); free(cd); return HC;MinCode Select(HuffmanTree HT,unsigned int n) unsigned int min,secmin; unsigned int temp; unsigned int i,s1,s2,tempi; MinCode code; s1=1;s2=1; for(i=1;i=n;i+) if(HTi.parent=0) min=HTi.weight; s1=i; break; tempi=i+; for(;i=n;i+) if(HTi.weightmin&HTi.parent=0) min=HTi.weight; s1=i; for(i=tempi;i=n;i+) if(HTi.parent=0&i!=s1) secmin=HTi.weight; s2=i; break; for(i=1;i=n;i+) if(HTi.weights2) temp=s1; s1=s2; s2=temp; code.s1=s1; code.s2=s2; return code;void main() HuffmanTree HT=NULL; HuffmanCode HC=NULL; unsigned int *w=NULL; unsigned int i,n; system(cls); printf(Input n:); scanf(%d,&n); w=(unsigned int *)malloc(n+1)*sizeof(unsigned int *); w0=0; printf(Enter weight:n); for(i=1;i=n;i+) printf(w%d=,i); scanf(%d,&wi); HC=HuffmanCoding(HT,HC,w,n); printf(HuffmanCode:n); printf(NumberttWeightttCoden); for(i=1;i0。 ； 置迭代序号k+1k，转向； 输出的结果； 结束。可以证明，平均互信息具有收敛性，即，所以迭代算法最终能求出任意精度的解。算法的收敛速度与信源初始概率分布的选择有很大的关系，初始分布选择越接近最佳分布，则收敛的速度越快，若初始分布选的正好是最佳分布，则一步就可以求得信道容量。四 实验内容1. 信道转移矩阵为，求信道容量及最佳的概率分布。2. 信道转移矩阵为，求信道容量及最佳的概率分布。3. 信道转移矩阵为，求信道容量及最佳的概率分布。4. 自己选择一个例子求信道容量及最佳的概率分布。五、实验设备 PC计算机 ，C+六、实验报告要求 1画出设计流程图，写出设计思路，方法，原理等。 2画出程序设计的流程图。 3写出或关于实现信道容量迭代计算法的代码。 3写出在调试过程中出现的问题。4 对实验的结果进行分析。七、流程图八、实验代码#include #include #include using namespace std;int main()/=/确定输入及输出符号的个数/因为一般先验概率是取等概率，所以为1/num_in/= int num_in,num_out; int i,j; cout输入符号的个数为：num_in; cout输出符号的个数为：num_out; cout输入概率为：endl; float *P_in; P_in=new floatnum_in; /输入的符号的概率 float *P_out; P_out=new floatnum_out; /输出的符号的概率 for (i=0;inum_in;i+) P_ini=1.0/(float)num_in; coutP_ini ; coutendl;/=/再输入信道转移概率矩阵/注意进行判断，某行如果总概率大于1，则出现错误应从新输入/= cout输入转移概率：endl; float *p_ji; /转移条件概率 p_ji=new float *num_in; for (i=0;inum_in;i+) p_jii=new floatnum_out; for (i=0;inum_in;i+) for (j=0;jp_jiij; for (i=0;inum_in;i+) float validate=0.0; for (j=0;j1.000001|validate0.999999) cout输入数据有误，请检查后再次输入。endl; exit(-1); float *p_ij; /反条件概率 p_ij=new float *num_in; for (i=0;inum_in;i+) p_iji=new floatnum_out; float C_Pre,C; /当前信道容量和前一次循环信道容量 C=10.0; double Pe=0.000001; /两次信道容量相差的阈值 int r=0; /迭代次数 float *p_up; /计算第r+1次循环输入分布p_in分子 p_up=new floatnum_in; float p_down; /计算第r+1次循环输入分布p_in分母 do r+;/=/求第r次循环反条件概率p_ij/= for (j=0;jnum_out;j+) P_outj=0.0; for (i=0;i=0.000001) for (i=0;inum_in;i+) p_ijij=P_ini*p_jiij/P_outj; else for (i=0;inum_in;i+) p_ijij=0.0; /=/求第r+1次循环输入分布p_in/= p_down=0.0; for (i=0;inum_in;i+) p_upi=0.0; for (j=0;j=0.000001) p_upi+=p_jiij*log(p_ijij)/log(2.0); p_upi=pow(2.0,p_upi); p_down+=p_upi; for (i=0;inum_in;i+) P_ini=p_upi/p_down; /=/求C(r+1)/= C_Pre=C; C=log(p_down)/log(2.0); cout第r次的容量为：CPe); cout迭代的次数为：rendl;实验结果如下1.2.3.4.实验五：循环码编码一、实验目的:掌握通过计算机实现系统循环码编码 二、实验要求: 对于给定的消息序列,按照循环码编码的方法进行计算机实现. 三、实验基本原理循环码的编码步骤: 循环码的系统码构造的步骤为： 1）消息多项式乘x n-k 2) x n-km(x)/g(x)=q(x) +r(x)/g(x) 其中：q(x)是商，r(x)是余数 3）C(x)= xn-km(x)+r(x) 四、实验内容1.GF(2)中(7,4)循环码，生成多项式g(x)=x3+x+1，对信息组(1101)进行编码。2.GF(2)中(15,7)循环码，生成多项式g(x)=x8+x7+x6+x4+1，对信息组(1101011)进行编码。3.自己选择一个例子进行编码。五、实验设备 PC计算机，C+ 六、实验报告要求 1、画出程序设计的流程图， 2、写出程序代码， 3、写出在调试过程中出现的问题 ， 4、对实验的结果进行分析。 七、流程图八、程序代码/C言实现循环码系统与非系统编码#include stdio.h #include #define N 10 /系统编码实现void X(int gN,int cN,int r,int n) int degg,degc,i,k,t,j,e,u,sum=0; int dN2*N=0,CN,RN,aN2*N,qN; degg=r; /求信息多项式的次幂 for(i=0;i=n-r-1;i+) if(ci!=0) degc=n-i-1; break; for(i=0;iN;i+) qi=gi; Ri=ci; k=degc-degg; e=k; /二进制除法实现 for(j=0;jN;j+) for(i=0;i=e;i-) t=qi;qi=qi-e;qi-e=t; for(i=0;i=n-1;i+) ci=(ci+qn-1-i)%2; for(i=0;i=n-1;i+) if(ci!=0) degc=n-i-1; break; e=degc-degg; u=j; if(e0)break; for(i=0;i=n-1;i+) Ci=(Ri+ci)%2; /输出 printf(系统编码的结果为:n); printf(t); for(j=0;j=n-1;j+) printf(%d ,Cj); printf(n); /非系统编码实现void UX(int gN,int cN,int r,int n) int aN2*N,xN; int i,j,k,sum=0; /二进制乘法 for(j=0;j=n-r-1;j+) for(i=0;ij;i+) aji=0; for(i=0;i=n-1;i+) aji+j=cj*gi; for(k=i+j;k=2*n-r-2;k+) ajk=0; for(j=0;j=2*n-r-2;j+) sum=0; for(i=0;i=n-r-1;i+) sum=(aij+sum)%2; xj=sum; /输出 printf(非系统编码的结果：n); printf(t); for(j=0;j=n-1;j+) printf(%d ,xj); printf(n); void main() int i,n,m,t,r; int gN=0,cN=0; printf(*循环码编码方法（码长n=10)*n); printf(t输入码长n:); scanf(%d,&m); n=m; switch(n) case 1 :printf(输入校验位r=%d:,n-1); scanf(%d,&r); switch(r) case 0:g0=1;break; break; case 2 :printf(输入校验位r=%d:,n-1); scanf(%d,&r); switch(r) case 0:g0=1;break; case 1:g0=1;g1=1;break; break; case 3 :printf(输入校验位r=%d:,n-1); scanf(%d,&r); switch(r) case 0:g0=1;break; case 1:g0=1;g1=1;break; case 2:g0=1;g1=1;g2=1;break; break; case 4 :printf(输入校验位r=%d:,n-1); scanf(%d,&r); switch(r) case 0:g0=1;break; case 1:g0=1;g1=1;break; case 2:g0=1;g1=0;g2=1;break; case 3:g0=1;g1=1;g2=1;g3=1;break; break; case 5 :printf(输入校验位r=0,1,4:); scanf(%d,&r); switch(r) case 0:g0=1;break; case 1:g0=1;g1=1;break; case 4:g0=1;g1=1;g2=1;g3=1;g4=1;break; break; case 6 :printf(输入校验位r=%d:,n-1); scanf(%d,&r); switch(r) case 0:g0=1;break; case 1:g0=1;g1=1;break; case 2:g0=1;g1=1;g2=1;break; case 3:g0=1;g1=0;g2=0;g3=1;break; case 4:g0=1;g1=0;g2=1;g3=0;g4=1;break; case 5:g0=1;g1=1;g2=1;g3=1;g4=1;g5=1;break; break; case 7 :printf(输入校验位r=0,1,3,4,6:); scanf(%d,&r); switch(r) case 0 :g0=1;break; case 1 :g0=1;g1=1;break; case 3 :g0=1;g1=1;g2=0;g3=1;break; case 4 :g0=1;g1=1;g2=1;g3=0;g4=1;break; case 6 :g0=1;g1=1;g2=1;g3=1;g4=1;g5=1; g6=1;break; break; case 8 :printf(输入校验位r=%d:,n-1); scanf(%d,&r); switch(r) case 0 :g0=1;break; case 1 :g0=1;g1=1;break; case 2 :g0=1;g1=0;g2=1;break; case 3 :g0=1;g1=1;g2=1;g3=1;break; case 4 :g0=1;g1=0;g2=0;g3=0;g4=1;break; case 5 :g0=1;g1=1;g2=0;g3=0;g4=1;g5=1;break; case 6 :g0=1;g1=0;g2=1;g3=0;g4=1;g5=0; g6=1;break; case 7 :g0=1;g1=1;g2=1;g3=1;g4=1;g5=1;g6=1; g7=1;break; break; case 9 :printf(输入校验位r=%d:,n-1); scanf(%d,&r); switch(r) case 0 :g0=1;break; case 1 :g0=1;g1=1;break; case 2 :g0=1;g1=0;g2=1;break; case 3 :g0=1;g1=0;g2=0;g3=1;break; case 4 :g0=1;g1=0;g2