实验1道容量的迭代算法

1、信息论基础实验指导老师:贺正芸 班级：信息工程081姓名：卢慈荣学号：08401400103湖南工业大学电气与信息工程学院实验一 信道容量的迭代算法程序设计一、实验目的（1）进一步熟悉信道容量的迭代算法；（2）学习如何将复杂的公式转化为程序；（3）掌握C语言数值计算程序的设计和调试技术。二、实验要求（1）已知：信源符号个数r、信宿符号个数s、信道转移概率矩阵P。（2）输入：任意的一个信道转移概率矩阵。信源符号个数、信宿符号个数和每个具体的转移概率在运行时从键盘输入。（3）输出：最佳信源分布P*，信道容量C。三、信道容量迭代算法 1：procedure CHANNEL CAPACITY(r,s,

2、()2：initialize:信源分布=1/r，相对误差门限，C=3：repeat4：5：6：C ß 7：until 8：output P*= ,C9：end procedure -四、实验代码/*问题：初始最大容量的设定exp的精确求解 */#include<stdio.h>#include<iostream>#include<math.h>#include<string.h>#include<stdlib.h>#define R 1000#define S 1000#define delta 1e-2#define in

3、f 1e6 using namespace std; double P_iR,P_jiSR,Thi_ijRS; double Pre_C,Now_C; int r,s,Num; double _log2(double a) return log(a)/log(2); double _exp(double a) return pow(2.718281828459045 ,a); int eps( double a) if(a>delta|a<-delta) return 1; return 0; void scan() int i,j,k; int flag=0; double t;

4、 freopen("信道信息.txt","r",stdin); printf("本次信道信息如下：（若要更改信道信息，请终止程序运行后，改变文件信道信息.txt中的信息）n"); printf("信源处信息的个数："); scanf("%d",&r); printf("%dnn",r); printf("信道接收处信息的种类："); scanf("%d",&s); printf("%dnn",s);

5、printf( "信道的分配（每一行表示信源处的一个信息对接收端一处信息的概率分布）:n"); for(i=0;i<r;i+) t=0.0; for(j=0;j<s;j+) scanf("%lf",&P_jiji); if(P_jiji<0) flag=1; t+=P_jiji; if(eps(t-1.0) flag=1; for(i=0;i<r;i+) for(j=0;j<s;j+) printf("%lf ",P_jiji); printf("n"); if(flag) p

6、rintf("信道数据有误！n"); void print() int i,j,k; printf("nntt运行结果nn最大的信息容量是:%lf.n",Now_C); printf("n迭代次数是%d.n",Num); printf("n信源信息概率分布为:n"); for(i=0;i<r;i+) printf("%.6lf ",P_ii); printf("nn"); printf("后验概率分布是(每一行表示接收端一种信息的来源概率分布):n"

7、); for(j=0;j<s;j+) for(i=0;i<r;i+) printf("%.6lf ",Thi_ijij); printf("n"); void run() int i,j,k; double P_j,sum; for(i=0;i<r;i+) /初始化P_i P_ii=1.0/r; Now_C=0; Num=0; while(1) Num+; for(j=0;j<s;j+) /求Thi_ij P_j=0.0; for(i=0;i<r;i+) P_j+=P_ii*P_jiji; if(fabs(P_j)>=

8、delta) for(i=0;i<r;i+) Thi_ijij=P_ii*P_jiji/P_j; else for(i=0;i<r;i+) Thi_ijij=0.0; sum=0.0; /求P_i for(i=0;i<r;i+) P_ii=0.0; for(j=0;j<s;j+) if(fabs(Thi_ijij)>delta) P_ii+=P_jiji*_log2(Thi_ijij); P_ii=_exp(P_ii); sum+=P_ii; if(fabs(sum)>=delta) for(i=0;i<r;i+) P_ii/=sum; else fo

9、r(i=0;i<r;i+) P_ii=0.0; Pre_C=Now_C; /前后两次迭代的容量进行比较，达到一定的精确度时退出循环，进行输出 Now_C=-_log2(sum); if(fabs(Pre_C-Now_C)/Now_C)<=delta) print(); break; int main() scan(); run(); while(1); system("pause"); return 0; 五、实验结果实验二 唯一可译码判决准则一、实验目的（1） 进一步熟悉唯一可译码判决准则；（2） 掌握C语言字符串处理程序的设计和调试技术。二、实验要求（1）

10、已知：信源符号个数q、码字集合C。（2） 输入：任意的一个码。码字个数和每个具体的码字在运行时从键盘输入。（3） 输出：判决（是唯一可译码/不是唯一可译码）。3. 程序设计代码：#include <iostream.h>#include <stdlib.h>#include <string.h>struct strings char *string; struct strings *next;struct strings Fstr, *Fh, *FP;/输出当前集合void outputstr(strings *str)docout<<str-&

11、gt;string<<endl;str = str->next;while(str);cout<<endl;inline int MIN(int a, int b) return a>b?b:a; inline int MAX(int a, int b) return a>b?a:b; #define length_a (strlen(CP)#define length_b (strlen(tempPtr)/判断一个码是否在一个码集合中，在则返回0，不在返回1int comparing(strings *st_string,char *code)whi

12、le(st_string->next)st_string=st_string->next;if(!strcmp(st_string->string,code)return 0;return 1;/判断两个码字是否一个是另一个的前缀，如果是则生成后缀码void houzhui(char *CP,char *tempPtr)if (!strcmp(CP,tempPtr)cout<<"集合C和集合F中有相同码字:"<<endl<<CP<<endl<<"不是唯一可译码码组!"<&

13、lt;endl;exit(1);if (!strncmp(CP, tempPtr, MIN(length_a,length_b)struct strings *cp_temp;cp_temp=new (struct strings);cp_temp->next=NULL;cp_temp->string=new charabs(length_a-length_b)+1; char *longstr;longstr=(length_a>length_b ? CP : tempPtr);/将长度长的码赋给longstr/取出后缀for (int k=MIN(length_a,len

14、gth_b); k<MAX(length_a,length_b); k+)cp_temp->stringk - MIN(length_a,length_b)=longstrk;cp_temp->stringabs(length_a-length_b)=NULL;/判断新生成的后缀码是否已在集合F里，不在则加入F集合if(comparing(Fh,cp_temp->string)FP->next=cp_temp;FP=FP->next;void main()/功能提示和程序初始化准备cout<<"tt唯一可译码的判断!n"<

15、;<endl;struct strings Cstr, *Ch, *CP,*tempPtr; Ch=&Cstr;CP=Ch; Fh=&Fstr;FP=Fh;char c="C :" Ch->string=new charstrlen(c); strcpy(Ch->string, c); Ch->next=NULL; char f="F :" Fh->string=new charstrlen(f); strcpy(Fh->string, f); Fh->next=NULL;/输入待检测码的个数in

16、t Cnum;cout<<"输入待检测码的个数:"cin>>Cnum;cout<<"输入待检测码"<<endl;for(int i=0; i<Cnum; i+) cout<<i+1<<" ："char tempstr10;cin>>tempstr; CP->next=new (struct strings);CP=CP->next;CP->string=new charstrlen(tempstr) ;strcpy(CP->

17、;string, tempstr);CP->next = NULL; outputstr(Ch); CP=Ch; while(CP->next->next) CP=CP->next;tempPtr=CP;dotempPtr=tempPtr->next;houzhui(CP->string,tempPtr->string);while(tempPtr->next); outputstr(Fh);struct strings *Fbegin,*Fend; Fend=Fh; while(1) if(Fend = FP)cout<<"

18、;是唯一可译码码组!"<<endl;exit(1);Fbegin=Fend;Fend=FP;CP=Ch;while(CP->next) CP=CP->next;tempPtr=Fbegin;for(;)tempPtr=tempPtr->next;houzhui(CP->string,tempPtr->string);if(tempPtr = Fend)break;outputstr(Fh);/输出F集合中全部元素 4.输入、输出结果：例1：输入： 唯一可译码的判断!输入待检测码的个数:5输入待检测码1 ：xx2 ：xz3 ：y4 ：zz5 ：

19、xyzC :xxxzyzzxyzF :是唯一可译码码组!Press any key to continue 实验三 Huffman 编码方案程序设计一、实验目的 （1）进一步熟悉Huffman编码过程； （2）掌握C语言递归程序的设计和调试技术。二、实验要求 （1）输入：信源符号个数r、信源的概率分布P； （2）输出：每个信源符号对应的Huffman编码的码字。三、算法 1、从键盘输入组成信源C的字符个数N； 2、从键盘输入信源C和组成信源的字符所对应的概率数组P； 3、用函数来对信源进行二进制编码；先对P按从大到小进行排序，与此同时要把C中相应的字符的位置做相应的调换；用数组来记录编码：在进

20、行记录编码时是从数组的最后一个开始存储的，而且，每进行一次编码所记录下来的两个编码是按从数组的最后一个元素开始服从countm-k-j、countm-k-j-1，其中k表示编码所进行的次数，j表示每次编码都只有;最后用函数来输出编码。四、代码#include<string.h> #include<stdlib.h> #include<stdio.h> int m,s1,s2; typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree;

21、/动态分配数组存储哈夫曼树 typedef char *HuffmanCode; /动态分配数组存储哈夫曼编码表 void Select(HuffmanTree HT,int n) int i,j; for(i = 1;i <= n;i+) if(!HTi.parent)s1 = i;break; for(j = i+1;j <= n;j+) if(!HTj.parent)s2 = j;break; for(i = 1;i <= n;i+) if(HTs1.weight>HTi.weight)&&(!HTi.parent)&&(s2!=i

22、)s1=i; for(j = 1;j <= n;j+) if(HTs2.weight>HTj.weight)&&(!HTj.parent)&&(s1!=j)s2=j; void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC, int *w, int n) / 算法6.13 / w存放n个字符的权值(均>0)，构造哈夫曼树HT， / 并求出n个字符的哈夫曼编码HC int i, j; char *cd; int p; int cdlen; if (n<=1) return; m = 2

23、* n - 1; HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); / 0号单元未用 for (i=1; i<=n; i+) /初始化 HTi.weight=wi-1; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; for (i=n+1; i<=m; i+) /初始化 HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; puts("n哈夫曼树的构造过程如下所示："); printf("HT初态:n 结点 wei

24、ght parent lchild rchild"); for (i=1; i<=m; i+) printf("n%4d%8d%8d%8d%8d",i,HTi.weight, HTi.parent,HTi.lchild, HTi.rchild); printf(" 按任意键，继续 ."); getchar(); for (i=n+1; i<=m; i+) / 建哈夫曼树 / 在HT1.i-1中选择parent为0且weight最小的两个结点， / 其序号分别为s1和s2。 Select(HT, i-1); HTs1.parent =

25、 i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; printf("nselect: s1=%d s2=%dn", s1, s2); printf(" 结点 weight parent lchild rchild"); for (j=1; j<=i; j+) printf("n%4d%8d%8d%8d%8d",j,HTj.weight, HTj.parent,HTj.lchild, HTj.r

26、child); printf(" 按任意键，继续 ."); getchar(); /-无栈非递归遍历哈夫曼树，求哈夫曼编码 cd = (char *)malloc(n*sizeof(char); / 分配求编码的工作空间 p = m; cdlen = 0; for (i=1; i<=m; +i) / 遍历哈夫曼树时用作结点状态标志 HTi.weight = 0; while (p) if (HTp.weight=0) / 向左 HTp.weight = 1; if (HTp.lchild != 0) p = HTp.lchild; cdcdlen+ ='0' else if (HTp.rchild = 0) / 登记叶子结点的字符的编码 HCp = (char *)malloc(c