成都理工大学信息理论与编码实验指导书.docx

《成都理工大学信息理论与编码实验指导书.docx》由会员分享，可在线阅读，更多相关《成都理工大学信息理论与编码实验指导书.docx（39页珍藏版）》请在三一办公上搜索。

1、成都理工大学信息理论与编码实验指导书1 实验一：香农编码 一、 实验目的 掌握通过计算机实现香农编码的方法。 二、实验要求 对于给定的信源的概率分布，按照香农编码的方法进行计算机实现。 三、实验基本原理 给定某个信源符号的概率分布，通过以下的步骤进行香农编码 1. 将信源消息符号按其出现的概率大小排列 p(x1)p(x2)Lp(xn) -log2p(xi)Ki-log2p(xi)+1 i-12确定满足下列不等式的整数码长Ki ； 3为了编成唯一可译码，计算第i个消息的累加概率 pi=p(xk) k=14将累加概率Pi变换成二进制数。 5取Pi二进制数的小数点后K i 位即为该消息符号的二进制码

2、。 四 实验内容 x2x3x4x5x6x7Xx11 对给定信源进行二进=q(X)0.20.190.180.170.150.10.01制香农编码。 x2x3x4x5x6Xx12 对给定信源进行二进制=q(X)0.250.250.200.150.100.05香农编码。 3 自已选择一个例子进行香农编码。 五、实验设备 PC计算机 ，C+ 六、实验报告要求 2 1、画出程序设计的流程图， 2、写出程序代码， 3、写出在调试过程中出现的问题 ， 4、对实验的结果进行分析。 七、参考程序(仅供参考) /香农编码参考程序 int main int N; coutN; cout”请输入各符号的概率：”end

3、l； double *X=new doubleN; /离散无记忆信源 int i,j; for(i=0;iN;i+) cout”X”i+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)+1; /确认码长为 1-log2(p(xi) if(Ki=(-(log(Xi)/log(2)+1)/当Ki=-log2(p(xi)时，Ki- Ki-; 3 /累加概率 do

4、uble *Pa=new doubleN;pa0=0.0; for(i=1;iN;i+) pai=pai-1+Xi-1; /将累加概率转换为二进制 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)”

5、信源”setw(12)”概率p(x)”setw(12)”累加概率 Pa(x)”setw(8)”码长 K”setw(8)”码字”endl; for(i=0;iN;i+) coutsetw(12)i+1setw(12)Xisetw(12)Pai”setw(8) Kisetw(8)codei=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; dou

6、ble 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” 7 /判断分组点位置，进而分情况自身调用 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 coutn; p=new doublen; sign=new strin

7、gn; 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; 8 fano(0,n-1); /费诺编码 coutendlendlsetw(8)”信源符号”setw(8)”概率”setw(8)” 码字”setw(8)”码长 ” endl

8、; for(int i=0;in;i+) coutsetw(8)signisetw(8)pisetw(8)codei.lengthendl; delete p; delete sign; delete code; /*费诺编码参考程序2* #include #include using namespace std; class DATA/数据类,采用双向表 public:/初始化PXi=1是为了在排序迭代时方便 DATAnext=NULL;pre=NULL;r=NULL;PXi=1;key0=0;key1=0;key2=0;key3=0;key4=0;key5=0; key6=0;key7=0

9、;key8=0;key9=0;key10=0; char Xi;/信源符号 double PXi;/信源概率 char key11;/码字 DATA *next,*pre,*r;/地址 ; DATA *head=new DATA,*p=head; int k=(-1);/编码函数用 void encoding(DATA * pp);/编码函数声明 DATA * sort(DATA * pp);/排序函数声明 DATA *HEAD=new DATA,*tt=HEAD,*T;/排序函数用 9 void input /输入数据 double l,sum=0; int n,i; char L; cou

10、tn; for(i=0;in;i+) cout请输入一个字符的信源符号: L; cout请输入概率: l; p-Xi=L; p-PXi=l; sum=sum+p-PXi; p-next=new DATA; p-next-pre=p;/对新创建结点赋值 p-r=p-next; p=p-next; if(sum!=1) cout所输入的概率之和是sum不为1，请重新输入next=T;/由于迭代产生的链表格式不规范，以下句用来整理sort函数的返回结果 tt-next-pre=tt; tt=tt-next; tt-next=new DATA; 10 tt-next-pre=tt;/对新创建结点赋值

11、tt=tt-next; HEAD-next-next-pre=NULL; HEAD=HEAD-next-next; cout对输入信源排序结果如下：next!=NULL;p=p-next)/排序输出 coutXi:PXiendl; cout对输入信源编码结果如下：endl; encoding(HEAD); /*编码*/ void encoding(DATA * pp)/定义递归函数 double y=1;/y定义为1是因为概率最多为1 k+;/递归自增值，用于字符数组定位 DATA *head1=pp,*head2; int o=1; while(1)/分01组 double l=0,z=0;

12、 for(int i=1;inext=NULL) break; l=l+pp-PXi; pp=pp-next; head2=pp-pre;/从这里分01段 for(;pp-next!=NULL;pp=pp-next) z=z+pp-PXi; 11 if(yfabs(l-z)/判断两组值之差是否最小 y=fabs(l-z); pp=head1; o+; continue; else if(z=0&i=2)/z=0,i1表示只有一个概率了 coutXi:keynext!=head2-next;u=u-next) u-keyk=0;/为字符串赋值 for(DATA * h=head2;h-next!

13、=NULL;h=h-next) h-keyk=1; head2-pre-next=new DATA;/分段：标记head2为上一段结束位置 head2-pre-next-pre=head2-pre; encoding(head1);/递归 encoding(head2); break; k-;/迭代还原到上一个数组位置 DATA * sort(DATA * pp) /函数递归后头变到HEAD-next-next.返回值得到最后个head2没有与tt相连，需另设得不到结尾为空的地址 DATA *head1=pp,*head2=pp; 12 if(pp-next=NULL) return pp;/

14、当pp是最后一个值时 for(;pp-next!=NULL;pp=pp-next) if(1-pp-PXi=1-head2-PXi) /两个以上的值时,由于最后一个pxi为1，所以每次都会有个最小值 head2=pp; if(head2-pre=NULL)/当pp是第一个值时 head2-next-pre=NULL; head1=head1-next; else /当pp是最后一个值及中间的值时 head2-pre-next=head2-next; head2-next-pre=head2-pre; tt-next=sort(head1);/递归，先得第一个，再得下一个 tt-next-pre

15、=tt; tt=tt-next; return head2; void main cout*费诺编码*endl; input; coutendlendltttttttendl; 13 实验三 霍夫曼编码 一、实验目的 掌握通过计算机实现霍夫曼编码 二、实验要求 对于给定的信源的概率分布，按照霍夫曼编码的方法进行计算机实现。 三、实验基本原理 霍夫曼编码的步骤: (1). 把信源符号按概率大小顺序排列， 并设法按逆次序分配码字的长度。 (2). 在分配码字长度时，首先将出现概率 最小的两个符号的概率相加合成一个概率 (3). 把这个合成概率看成是一个新组合符号地概率，重复上述做法直到最后只剩下两

16、个符号概率为止。 (4). 完成以上概率顺序排列后，再反过来逐步向前进行编码，每一次有二个分支各赋予一个二进制码，可以对概率大的赋为0，概率小的赋为1。 四 实验内容 x2x3x4x5x6x7Xx11 对给定信源进行二进=q(X)0.20.190.180.170.150.10.01制霍夫曼编码。 x2x3x4x5x6Xx12 对给定信源=0.250.250.200.150.100.05进行二进制q(X)霍夫曼编码。 3 自已选择一个例子进行霍夫曼编码。 五、实验设备 PC计算机，C+ 六、实验报告要求 14 1、画出程序设计的流程图， 2、写出程序代码， 3、写出在调试过程中出现的问题 ， 4

17、、对实验的结果进行分析。 七、参考程序(仅供参考) /第一段参考代码 #include #include #include /for setw using namespace std; /= typedef struct int weight; int parent; int lchild; int rchild; hnodetype; /霍夫曼树节点 typedef struct int bit10; int position; char sign; hcodetype; /霍夫曼编码表 /= void Huffman(int m,int n); /函数声明 int main 15 int

18、i=0,n=8; int m10=40,18,10,10,7,6,5,4; char sign10=hufmcode; coutsetw(12)各个字符为：; for(i=0;in;i+) coutsetw(12)signi; coutsetw(12)字符加权为：; for(i=0;in;i+) float f=( float)mi/100; coutsetw(12)f; coutendlendl各字符的霍夫曼码为：endl; Huffman(m,n); getch; return 0; /= void Huffman(int m,int n) int i,j,m1,m2,x1,x2,c,p;

19、 hnodetype *huffnode=new hnodetype 2*n-1; /一共2n-1个节点 hcodetype *huffcode=new hcodetypen,temp; for(i=0;i2*n-1;i+) /初始化霍夫曼树 huffnodei.weight=0; huffnodei.parent =0; huffnodei.lchild=1; huffnodei.rchild=1; 16 for(i=0;in;i+) /节点赋初值 huffnodei.weight=mi; huffcodei.sign =signi; /对n到2n-1节点编码 for(i=0;in;i+)

20、m1=m2=100; x1=x2=0; for(j=0;jn+i;j+) /查找最小的两个节点x1和x2 if(huffnodej.weight=m1& huffnodej. parent=0) m2=m1; x2=x1; m1= huffnodej.weight; x1=j; else if(huffnodej.weight=m2& huffnodej. parent=0) m2= huffnodej.weight; x2=j; huffnodex1. parent=n+i; /定义x1和x2的父节点为n+i huffnodex2. parent=n+i; huffnoden+i.weigh

21、t=huffnodex1.weight+huffnodex2.weight; huffnoden+i.lchild=x1; /新节点的左、右孩子分别为x1、x2 huffnoden+i.rchild=x2; 17 /从叶子到根逆向求每个字符的霍夫曼编码 for(i=0;in;i+) temp.position=n-1; c=i; p= huffnodec. parent; while(p!=0) /如果p节点不是根节点则一直向上编码 if(huffnodep. lchild =c) /如果p节点的左孩子是c，则码字加1 temp.bittemp.position=1; else /否则则码字加

22、0 temp.bittemp.position=0; temp.position-; /记录当前码字存储位置 c=p;p= huffnodec. parent; /从新定义c和p的指向 cout huffcodei. sign:; for(j= temp.position+1;jn;j+) /输出码字 huffcodei.bitj=temp.bitj; cout temp.bitj; coutendl; deletehuffcode; deletehuffnode; /第二段参考代码 #include #include 18 #include #include #include /- type

23、def 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 HC,unsigned int *w,unsigned int n); MinCode Select(HuffmanTree

24、 HT,unsigned int n); void Error(char *message) clrscr; fprintf(stderr,Error:%s,message); exit(1); HuffmanCode HuffmanCoding(HuffmanTree HC,unsigned int *w,unsigned int n) unsigned int i,s1=0,s2=0; HuffmanTree p; char *cd; unsigned int f,c,start,m; HT,HuffmanCode HT,HuffmanCode 19 MinCode min; if(n=1

25、) 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

26、.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; printf(HT List:); 20 printf(Numberttweightttparentttlchildttrchild); for(i=1;i=m;i+) printf(%dtt%dtt%dtt%dtt%d, 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

27、(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

28、int i,s1,s2,tempi; MinCode code; s1=1;s2=1; for(i=1;i=n;i+) if(HTi.parent=0) min=HTi.weight; 21 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

29、; s1=s2; s2=temp; code.s1=s1; 22 code.s2=s2; return code; void main HuffmanTree HT=NULL; HuffmanCode HC=NULL; unsigned int *w=NULL; unsigned int i,n; clrscr; printf(Input n:); scanf(%d,&n); w=(unsigned int *)malloc(n+1)*sizeof(unsigned int *); w0=0; printf(Enter weight:); for(i=1;i=n;i+) printf(w%d=

30、,i); scanf(%d,&wi); HC=HuffmanCoding(HT,HC,w,n); printf(HuffmanCode:); printf(NumberttWeightttCode); for(i=1;i=n;i+) printf(%dtt%dtt%s,i,wi,HCi); /第三段参考代码 #include #include 23 #include #include #include using namespace std; #define MAXVALUE 10000 /*权值最大值*/ #define MAXLEAF 30 /*叶子最多个数*/ #define MAXNO

31、DE MAXLEAF*2-1 /* 结点数的个数*/ #define MAXBIT 50 /*编码的最大位数*/ typedef struct node /*结点类型定义*/ char letter; int weight; int parent; int lchild; int rchild; HNodeType; typedef struct /*编码类型定义*/ char letter; int bitMAXBIT; int start; HCodeType; typedef struct /*输入符号的类型*/ char s; int num; lable; 24 void Huffm

32、anTree(HNodeType HuffNode,int n,lable a) int i,j,m1,m2,x1,x2,temp1; char temp2; for (i=0;i2*n-1;i+) /*结点初始化*/ HuffNodei.letter=0; HuffNodei.weight=0; HuffNodei.parent=-1; HuffNodei.lchild=-1; HuffNodei.rchild=-1; for (i=0;in-1;i+) for (j=i+1;jai.num) temp1=ai.num; ai.num=aj.num; aj.num=temp1; temp2=ai.s; ai.s=aj.s; aj.s=temp2; for (i=0;in;i+) HuffNodei.weight=ai.num; HuffNodei.letter=ai.s; 25 for (i=0;in-1;i+) /*构造huffman树*/ m1=m2=MAXVAL