實驗1道容量的迭代算法

1、信息論基礎實驗指導老師:賀正蕓 班級：信息工程081姓名：盧慈榮學號：08401400103湖南工業(yè)大學電氣與信息工程學院實驗一 信道容量的迭代算法程序設計一、實驗目的（1）進一步熟悉信道容量的迭代算法；（2）學習如何將復雜的公式轉(zhuǎn)化為程序；（3）掌握C語言數(shù)值計算程序的設計和調(diào)試技術。二、實驗要求（1）已知：信源符號個數(shù)r、信宿符號個數(shù)s、信道轉(zhuǎn)移概率矩陣P。（2）輸入：任意的一個信道轉(zhuǎn)移概率矩陣。信源符號個數(shù)、信宿符號個數(shù)和每個具體的轉(zhuǎn)移概率在運行時從鍵盤輸入。（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("信源處信息的個數(shù)："); 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("信道數(shù)據(jù)有誤！n"); void print() int i,j,k; printf("nntt運行結(jié)果nn最大的信息容量是:%lf.n",Now_C); printf("n迭代次數(shù)是%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; /前后兩次迭代的容量進行比較，達到一定的精確度時退出循環(huán)，進行輸出 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; 五、實驗結(jié)果實驗二 唯一可譯碼判決準則一、實驗目的（1） 進一步熟悉唯一可譯碼判決準則；（2） 掌握C語言字符串處理程序的設計和調(diào)試技術。二、實驗要求（1）

10、已知：信源符號個數(shù)q、碼字集合C。（2） 輸入：任意的一個碼。碼字個數(shù)和每個具體的碼字在運行時從鍵盤輸入。（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;/輸入待檢測碼的個數(shù)in

16、t Cnum;cout<<"輸入待檢測碼的個數(shù):"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.輸入、輸出結(jié)果：例1：輸入： 唯一可譯碼的判斷!輸入待檢測碼的個數(shù):5輸入待檢測碼1 ：xx2 ：xz3 ：y4 ：zz5 ：

19、xyzC :xxxzyzzxyzF :是唯一可譯碼碼組!Press any key to continue 實驗三 Huffman 編碼方案程序設計一、實驗目的 （1）進一步熟悉Huffman編碼過程； （2）掌握C語言遞歸程序的設計和調(diào)試技術。二、實驗要求 （1）輸入：信源符號個數(shù)r、信源的概率分布P； （2）輸出：每個信源符號對應的Huffman編碼的碼字。三、算法 1、從鍵盤輸入組成信源C的字符個數(shù)N； 2、從鍵盤輸入信源C和組成信源的字符所對應的概率數(shù)組P； 3、用函數(shù)來對信源進行二進制編碼；先對P按從大到小進行排序，與此同時要把C中相應的字符的位置做相應的調(diào)換；用數(shù)組來記錄編碼：在進

20、行記錄編碼時是從數(shù)組的最后一個開始存儲的，而且，每進行一次編碼所記錄下來的兩個編碼是按從數(shù)組的最后一個元素開始服從countm-k-j、countm-k-j-1，其中k表示編碼所進行的次數(shù)，j表示每次編碼都只有;最后用函數(shù)來輸出編碼。四、代碼#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、/動態(tài)分配數(shù)組存儲哈夫曼樹 typedef char *HuffmanCode; /動態(tài)分配數(shù)組存儲哈夫曼編碼表 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)，構(gòu)造哈夫曼樹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哈夫曼樹的構(gòu)造過程如下所示："); printf("HT初態(tài):n 結(jié)點 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(" 按任意鍵，繼續(xù) ."); getchar(); for (i=n+1; i<=m; i+) / 建哈夫曼樹 / 在HT1.i-1中選擇parent為0且weight最小的兩個結(jié)點， / 其序號分別為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(" 結(jié)點 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(" 按任意鍵，繼續(xù) ."); getchar(); /-無棧非遞歸遍歷哈夫曼樹，求哈夫曼編碼 cd = (char *)malloc(n*sizeof(char); / 分配求編碼的工作空間 p = m; cdlen = 0; for (i=1; i<=m; +i) / 遍歷哈夫曼樹時用作結(jié)點狀態(tà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) / 登記葉子結(jié)點的字符的編碼 HCp = (char *)malloc(c