1、信息論基礎(chǔ)實驗指導(dǎo)老師:賀正蕓 班級：信息工程081姓名：盧慈榮學(xué)號：湖南工業(yè)大學(xué)電氣與信息工程學(xué)院實驗一 信道容量的迭代算法程序設(shè)計一、實驗?zāi)康模?）進(jìn)一步熟悉信道容量的迭代算法；（2）學(xué)習(xí)如何將復(fù)雜的公式轉(zhuǎn)化為程序；（3）掌握C語言數(shù)值計算程序的設(shè)計和調(diào)試技術(shù)。二、實驗要求（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：initial

2、ize:信源分布=1/r，相對誤差門限，C=3：repeat4：5：6：C 7：until 8：output P*= ,C9：end procedure -四、實驗代碼/*問題：初始最大容量的設(shè)定exp的精確求解 */#include#include#include#include#include#define R 1000#define S 1000#define delta 1e-2#define inf 1e6 using namespace std; double P_iR,P_jiSR,Thi_ijRS; double Pre_C,Now_C; int r,s,Num; double

3、 _log2(double a) return log(a)/log(2); double _exp(double a) return pow(2.9045 ,a); int eps( double a) if(adelta|a-delta) return 1; return 0; void scan() int i,j,k; int flag=0; double t; freopen(信道信息.txt,r,stdin); printf(本次信道信息如下：（若要更改信道信息，請終止程序運行后，改變文件信道信息.txt中的信息）n); printf(信源處信息的個數(shù)：); scanf(%d,&r

4、); printf(%dnn,r); printf(信道接收處信息的種類：); scanf(%d,&s); printf(%dnn,s); printf( 信道的分配（每一行表示信源處的一個信息對接收端一處信息的概率分布）:n); for(i=0;ir;i+) t=0.0; for(j=0;js;j+) scanf(%lf,&P_jiji); if(P_jiji0) flag=1; t+=P_jiji; if(eps(t-1.0) flag=1; for(i=0;ir;i+) for(j=0;js;j+) printf(%lf ,P_jiji); printf(n); if(flag) pri

5、ntf(信道數(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;ir;i+) printf(%.6lf ,P_ii); printf(nn); printf(后驗概率分布是(每一行表示接收端一種信息的來源概率分布):n); for(j=0;js;j+) for(i=0;ir;i+) printf(%.6lf ,Thi_ijij); printf(n); void run() int i,j,k;

6、 double P_j,sum; for(i=0;ir;i+) /初始化P_i P_ii=1.0/r; Now_C=0; Num=0; while(1) Num+; for(j=0;js;j+) /求Thi_ij P_j=0.0; for(i=0;i=delta) for(i=0;ir;i+) Thi_ijij=P_ii*P_jiji/P_j; else for(i=0;ir;i+) Thi_ijij=0.0; sum=0.0; /求P_i for(i=0;ir;i+) P_ii=0.0; for(j=0;jdelta) P_ii+=P_jiji*_log2(Thi_ijij); P_ii=_

7、exp(P_ii); sum+=P_ii; if(fabs(sum)=delta) for(i=0;ir;i+) P_ii/=sum; else for(i=0;ir;i+) P_ii=0.0; Pre_C=Now_C; /前后兩次迭代的容量進(jìn)行比較，達(dá)到一定的精確度時退出循環(huán)，進(jì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é)果實驗二 唯一可譯碼判決準(zhǔn)則一、實驗?zāi)?/p>

8、的（1） 進(jìn)一步熟悉唯一可譯碼判決準(zhǔn)則；（2） 掌握C語言字符串處理程序的設(shè)計和調(diào)試技術(shù)。二、實驗要求（1） 已知：信源符號個數(shù)q、碼字集合C。（2） 輸入：任意的一個碼。碼字個數(shù)和每個具體的碼字在運行時從鍵盤輸入。（3） 輸出：判決（是唯一可譯碼/不是唯一可譯碼）。3. 程序設(shè)計代碼：#include #include #include struct strings char *string; struct strings *next;struct strings Fstr, *Fh, *FP;/輸出當(dāng)前集合void outputstr(strings *str)docoutstringne

9、xt;while(str);coutb?b:a; inline int MAX(int a, int b) return ab?a:b; #define length_a (strlen(CP)#define length_b (strlen(tempPtr)/判斷一個碼是否在一個碼集合中，在則返回0，不在返回1int comparing(strings *st_string,char *code)while(st_string-next)st_string=st_string-next;if(!strcmp(st_string-string,code)return 0;return 1;/判

10、斷兩個碼字是否一個是另一個的前綴，如果是則生成后綴碼void houzhui(char *CP,char *tempPtr)if (!strcmp(CP,tempPtr)cout集合C和集合F中有相同碼字:endlCPendl不是唯一可譯碼碼組!next=NULL;cp_temp-string=new charabs(length_a-length_b)+1; char *longstr;longstr=(length_alength_b ? CP : tempPtr);/將長度長的碼賦給longstr/取出后綴for (int k=MIN(length_a,length_b); kstrin

11、gk - 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()/功能提示和程序初始化準(zhǔn)備couttt唯一可譯碼的判斷!nstring=new charstrlen(c); strcpy(Ch-string, c); Ch-next=NULL; char f=F :; Fh-string=new charstrl

12、en(f); strcpy(Fh-string, f); Fh-next=NULL;/輸入待檢測碼的個數(shù)int Cnum;coutCnum;cout輸入待檢測碼endl;for(int i=0; iCnum; i+) couti+1tempstr; CP-next=new (struct strings);CP=CP-next;CP-string=new charstrlen(tempstr) ;strcpy(CP-string, tempstr);CP-next = NULL; outputstr(Ch); CP=Ch; while(CP-next-next) CP=CP-next;temp

13、Ptr=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是唯一可譯碼碼組!next) CP=CP-next;tempPtr=Fbegin;for(;)tempPtr=tempPtr-next;houzhui(CP-string,tempPtr-string);if(tempPtr = Fend)break;outputstr(

14、Fh);/輸出F集合中全部元素 4.輸入、輸出結(jié)果：例1：輸入： 唯一可譯碼的判斷!輸入待檢測碼的個數(shù):5輸入待檢測碼1 ：xx2 ：xz3 ：y4 ：zz5 ：xyzC :xxxzyzzxyzF :是唯一可譯碼碼組!Press any key to continue 實驗三 Huffman 編碼方案程序設(shè)計一、實驗?zāi)康?（1）進(jìn)一步熟悉Huffman編碼過程； （2）掌握C語言遞歸程序的設(shè)計和調(diào)試技術(shù)。二、實驗要求 （1）輸入：信源符號個數(shù)r、信源的概率分布P； （2）輸出：每個信源符號對應(yīng)的Huffman編碼的碼字。三、算法 1、從鍵盤輸入組成信源C的字符個數(shù)N； 2、從鍵盤輸入信源C和組

15、成信源的字符所對應(yīng)的概率數(shù)組P； 3、用函數(shù)來對信源進(jìn)行二進(jìn)制編碼；先對P按從大到小進(jìn)行排序，與此同時要把C中相應(yīng)的字符的位置做相應(yīng)的調(diào)換；用數(shù)組來記錄編碼：在進(jìn)行記錄編碼時是從數(shù)組的最后一個開始存儲的，而且，每進(jìn)行一次編碼所記錄下來的兩個編碼是按從數(shù)組的最后一個元素開始服從countm-k-j、countm-k-j-1，其中k表示編碼所進(jìn)行的次數(shù)，j表示每次編碼都只有;最后用函數(shù)來輸出編碼。四、代碼#include #include #include int m,s1,s2; typedef struct unsigned int weight; unsigned int parent,lc

16、hild,rchild; HTNode,*HuffmanTree; /動態(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 HTi.weight)&(!HTi.parent)&(s2!=i)s1=i; for(j = 1;j HTj

17、.weight)&(!HTj.parent)&(s1!=j)s2=j; void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC, int *w, int n) / 算法6.13 / w存放n個字符的權(quán)值(均0)，構(gòu)造哈夫曼樹HT， / 并求出n個字符的哈夫曼編碼HC int i, j; char *cd; int p; int cdlen; if (n=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); / 0號單元未用 for (i=1; i=n; i

18、+) /初始化 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é)點 weight parent lchild rchild); for (i=1; i=m; i+) printf(n%4d%8d%8d%8d%8d,i,HTi.weight, HTi.parent,HTi.lchild, H

19、Ti.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 = 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é)點 w

20、eight parent lchild rchild); for (j=1; j=i; j+) printf(n%4d%8d%8d%8d%8d,j,HTj.weight, HTj.parent,HTj.lchild, HTj.rchild); printf( 按任意鍵，繼續(xù) .); getchar(); /-無棧非遞歸遍歷哈夫曼樹，求哈夫曼編碼 cd = (char *)malloc(n*sizeof(char); / 分配求編碼的工作空間 p = m; cdlen = 0; for (i=1; i=m; +i) / 遍歷哈夫曼樹時用作結(jié)點狀態(tài)標(biāo)志 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(cdlen+1) * sizeof(char); cdcdlen =0; strcpy(HCp, cd); / 復(fù)制編碼(串) else if (HTp