中南大學《信息論與編碼》試驗匯報題目信源編碼試驗指導教師學院專業班級姓名學號曰期目錄一、香農編碼……….....3試驗目的.................................................................................3試驗規定.................................................................................3編碼算法.................................................................................3調試過程.................................................................................3參照代碼.................................................................................4調試驗證.................................................................................7試驗總結.................................................................................7二、哈夫曼編碼……….8試驗目的.................................................................................8試驗原理.................................................................................8數據記錄.................................................................................9試驗心得................................................................................10一、香農編碼1、試驗目的（1）深入熟悉Shannon編碼算法；（2）掌握C語言程序設計和調試過程中數值的進制轉換、數值與字符串之間的轉換等技術。2、試驗規定（1）輸入：信源符號個數q、信源的概率分布p；（2）輸出：每個信源符號對應的Shannon編碼的碼字。3、Shannon編碼算法1：procedureSHANNON(q,｛｝)2:降序排列｛｝3:fori=1qdo4:F()5：6：將累加概率F()（拾進制小數）變換成二進制小數。7：取小數點後個二進制數字作為第i個消息的碼字。8：endfor9：endprocedure------------------------------------------------------------------------------------------------------------------調試過程1、fatalerrorC1083:Cannotopenincludefile:'unistd.h':NosuchdirectoryfatalerrorC1083:Cannotopenincludefile:'values.h':Nosuchdirectory原因：unistd.h和values.h是Unix操作系統下所使用的頭文獻糾錯：刪去即可2、errorC2144:syntaxerror:missing')'beforetype'int'errorC2064:termdoesnotevaluatetoafunction原因：l_i(int*)calloc(n,sizeof(int));l_i後缺乏賦值符號使之不能通過編譯糾錯：添加上賦值符號errorC:unknowncharacter'0xa1'原因：有不能被識別的符號糾錯：在錯誤處將不能識別的符號改為符合C語言規范的符號errorC:expectedexponentvalue,not''原因：if(fabs(sum-1.0)>DELTA);這一行中DELTA宏定義不對的糾錯：#defineDELTA0.000001errorC2143:syntaxerror:missing';'before'}'原因：少寫了“;”號糾錯：在對應位置添加上“;”號參照代碼#include<stdio.h>#include<math.h>#include<stdlib.h>#include<string.h>#defineDELTA0.000001/*精度*/voidsort(float*,int);/*排序*/intmain(void){registerinti,j;intn;/*符號個數*/inttemp;/*中間變量*/float*p_i;/*符號的概率*/float*P_i;/*累加概率*/int*l_i;/*碼長*/char**C;/*碼集合*//*用sum來檢查數據，用p來緩存了中間數據*/floatsum,p;/*輸入符號數*/fscanf(stdin,"%d",&n);/*分派內存地址*/p_i=(float*)calloc(n,sizeof(float));P_i=(float*)calloc(n,sizeof(float));l_i=(int*)calloc(n,sizeof(int));/*存儲信道傳播的概率*/for(i=0;i<n;i++)fscanf(stdin,"%f",&p_i[i]);/*確認輸入的數據*/sum=0.0;for(i=0;i<n;i++)sum+=p_i[i];if(fabs(sum-(1.0))>DELTA)fprintf(stderr,"Invalidinputdata\n");fprintf(stdout,"Starting…\n\n");/*以降序排列概率*/sort(p_i,n);/*計算每個符號的碼長*/for(i=0;i<n;i++){p=(float)(-(log(p_i[i])))/log(2.0);l_i[i]=(int)ceil(p);}/*為碼字分派內存地址*/C=(char**)calloc(n,sizeof(char*));for(i=0;i<n;i++){C[i]=(char*)calloc(l_i[i]+1,sizeof(char));C[i][0]='\0';}/*計算概率累加和*/P_i[0]=0.0;for(i=1;i<n;i++)P_i[i]=P_i[i-1]+p_i[i-1];/*將概率和轉變為二進制編碼*/for(i=0;i<n;i++){for(j=0;j<l_i[i];j++){ /*乘2後的整數部分即為這一位的二進制碼元*/P_i[i]=P_i[i]*2;temp=(int)(P_i[i]);P_i[i]=P_i[i]-temp; /*整數部分不小于0為1，等于0為0*/if(temp==0)C[i]=strcat(C[i],"0");elseC[i]=strcat(C[i],"1");}}/*顯示編碼成果*/fprintf(stdout,"Theoutputcodingis:\n");for(i=0;i<n;i++)fprintf(stdout,"%s",C[i]);fprintf(stdout,"\n\n");/*釋放內存空間*/for(i=n-1;i>=0;i--)free(C[i]);free(C);free(p_i);free(P_i);free(l_i);exit(0);}/*冒泡排序法*/voidsort(float*k,intm){inti=1;/*外層循環變量*/intj=1;/*內層循環變量*/intfinish=0;/*結束標志*/floattemp;/*中間變量*/while(i<m&&!finish){finish=1;for(j=0;j<m-i;j++){ /*將小的數後移*/if(k[j]<k[j+1]){temp=k[j];k[j]=k[j+1];k[j+1]=k[j];finish=0;}i++;}}}調試驗證：程序成果：試驗總結1949年香農在《有噪聲時的通信》一文中提出了信道容量的概念和信道編碼定理，為信道編碼奠定了理論基礎。無噪信道編碼定理（又稱香農第一定理）指出，碼字的平均長度只能不小于或等于信源的熵。有噪信道編碼定理（又稱香農第二定理）則是編碼存在定理。它指出只要信息傳播速率不不小于信道容量，就存在一類編碼，使信息傳播的錯誤概率可以任意小。伴隨計算技術和數字通信的發展，糾錯編碼和密碼學得到迅速的發展。香農編碼定理雖然指出了理想編碼器的存在性，不過并沒有給出實用碼的構造及構造措施，編碼理論正是為了處理這一問題而發展起來的科學理論。編碼的目的是為了優化通信系統。香農編碼是碼符號概率大的用短碼表達，概率小的是用長碼表達，程序中對概率排序，最終求得的碼字就依次與排序後的符號概率對應。哈夫曼編碼1、試驗目的和任務1、理解信源編碼的意義；2、熟悉MATLAB程序設計；3、掌握哈夫曼編碼的措施及計算機實現；４、對給定信源進行香農編碼，并計算編碼效率；2、試驗原理簡介1、把信源符號按概率大小次序排列，并設法按逆次序分派碼字的長度；2、在分派碼字長度時，首先將出現概率最小的兩個符號的概率相加合成一種概率；3、把這個合成概率當作是一種新組合符號地概率，反復上述做法直到最終只剩余兩個符號概率為止；4、完畢以上概率次序排列後，再反過來逐漸向前進行編碼，每一次有二個分支各賦予一種二進制碼，可以對概率大的賦為零，概率小的賦為1；5、從最終一級開始，向前返回得到各個信源符號所對應的碼元序列，即對應的碼字。3、試驗內容和環節對如下信源進行哈夫曼編碼，并計算編碼效率。計算該信源的信源熵，并對信源概率進行排序首先將出現概率最小的兩個符號的概率相加合成一種概率，把這個合成概率與其他的概率進行組合，得到一種新的概率組合，反復上述做法，直到只剩余兩個概率為止。之後再反過來逐漸向前進行編碼，每一次有兩個分支各賦予一種二進制碼。對大的概率賦“1”，小的概率賦“0”。（3）從最終一級開始，向前返回得到各個信源符號所對應的碼元序列，即對應的碼字。（4）計算碼字的平均碼長得出最終的編碼效率。4、試驗數據記錄>>clearall>>p=[0.200.180.150.170.190.100.01];l=0;H=0;N=length(p);fori=1:NH=H+(-p(i)*log2(p(i)));endfprintf('信源信息熵：\n');disp(H);fori=1:N-1forj=i+1:Nifp(i)<p(j)m=p(j);p(j)=p(i);p(i)=m;endendendfori=1:N-1c(i,:)=blanks(N*N);endc(N-1,N)='0';c(N-1,2*N)='1';fori=1:N-1%對字符數組c碼字賦值過程，記下沿途徑的“1”和"0";c(N-i,1:N-1)=c(N-i+1,N*(find(m(N-i+1,:)==1))-(N-2):N*(find(m(N-i+1,:)==1)));c(N-i,N)='0';c(N-i,N+1;2*N-1)=c(N-i,1:N-1);c(N-i,2*N)='1';forj=1:i-1c(N-i,(j+1)*N+1:(j+2)*N)=c(N-i+1,N*(find(m(N-i+1,:)==j+1)-1)+1:N*find(m(N-i+1,:)==j+1));endendfori=1:Nh(i,1:N)=c(1,N*(find(m(1,:)==i)-1)+1:find(