信息論上機實習報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)信息論上機實習報告姓名：夏勇 學院：數(shù)學與物理學院 專業(yè)號： 學號：目錄 TOC o 1-3 h z u 判斷唯一可譯碼題目分析問題描述編一個程序判斷一組碼是不是唯一可譯碼.基本要求 利用薩德納斯和彼特森的判斷思想來編輯程序.算法分析算法原理B1B2B3BmA1A2A3Am由圖可知，B1一定是A1的前綴，而A1的尾隨后綴一定是另一碼字B2的前綴；又B2的尾隨后綴又是其他碼字的前綴。最后，若碼符號序列的尾部是碼字，則其是非唯一可譯碼。算法設計和思想首先，由于在比較前綴時，

2、碼字的長度也是一個重要的量，所以需要設計一個結構體來存放碼字和其長度。然后首先判斷源碼字中的所有的尾隨后綴，運用了兩個for循環(huán)來實現(xiàn)，使得每個源碼字都作為前綴和所有的其他碼字比較，找出所有的尾隨后綴及其長度，放在對象f中。具體判斷時，如果作為前綴的碼字的長度大于其他的，則剔除，判斷下一個。接著，我們比較源碼字和f中的碼字，在這里，源碼字和f中的碼字都要作為前綴和其他的碼字比較，找出尾隨后綴碼及其長度放入f中，判斷方法和前面的相同。最后，比較f中的碼字是否有和源碼字相同的，若有，則其不是唯一可譯碼，否則，其是唯一可譯碼。設計中遇到的問題及其解決方法在起初設計中，一直不知道應該怎么比較碼字來找出

3、尾隨后綴，后來仔細分析后，明白了在比較的時候牽扯到了碼字的長度，既然有多個變量，那么就運用結構體變量。然后在比較的時候，就可以根據(jù)它的長度來劃分它的尾隨后綴碼，其的長度也就知道了。在具體編程時，要避免變量在多處運用。因為如果你忘記了初始化就會導致錯誤，而且很難找出來，所以盡量不要多處使用，如果你一定要用的話，那就在它的后面加上標注。另外，在設計當中從老師那里學會了一種檢錯方法，就是一步一步的調(diào)試，雖然有點麻煩，但是效果相當不錯。調(diào)試結果源代碼#include#include#include#define N 1typedef structint a20;/數(shù)據(jù)int len;/碼字長度Code

4、;main()int i,j,z=0,n,b,count=0,flag=0,flag1=0,sum=0,h,m;char c20,*p;/過渡，接收每個碼字Code d100,f100;printf(按次序依次輸入每個碼字: n);gets(c);p=c;while(*p!=0) if(*p= ) p+;else i=0;while(*(p+i)!= &*(p+i)!=0)i+;for(j=0;ji;j+)dz.aj=pj-0;dz.len=i;z+;n=z;/碼字個數(shù)p=p+i;/*for(i=0;in;i+)for(j=0;jdi.len;j+)printf(%d,di.aj);print

5、f(n);*/檢驗碼字是否正確輸入數(shù)組for(i=0;in;i+)for(j=i+1;jn;j+)if(di.len=dj.len)for(z=0;zdi.len;z+)if(di.az=dj.az)sum+;if(sum=di.len) break;else sum=0;if(sum=di.len)break;if(sum!=0) printf(此碼組不是唯一可譯碼組!n);else for(i=0;in;i+)/前綴for(j=0;jn;j+)if(dj.lendi.len|di.a0!=dj.a0|dj.len=di.len)continue;b=di.len;while(b) b-;i

6、f(di.ab=dj.ab) flag=1;elseflag=0;break;b=di.len;if(flag!=0)for(z=0;z(dj.len-di.len);z+)fcount.az=dj.ab+z;fcount.len=dj.len-di.len;count+;/f中碼字的個數(shù)/在源碼字里找前綴m=count;for(h=0;hN;h+)/使得f最終收斂for(i=0;in;i+)for(j=0;jfj.len)b=fj.len;flag=0;while(b) b-;if(di.ab=fj.ab) flag=1;elseflag=0;break;b=fj.len;if(flag!=

7、0)for(z=0;z(di.len-fj.len);z+)fcount.az=di.ab+z;fcount.len=di.len-fj.len;count+;elseb=di.len;flag=0; while(b)b-;if(di.ab=fj.ab) flag=1;elseflag=0;break;b=di.len;if(flag!=0)for(z=0;z(fj.len-di.len);z+)fcount.az=fj.ab+z;fcount.len=fj.len-di.len;count+;for(i=0;in;i+)/作比較，看f中是否有源碼字for(j=0;jcount;j+)if(d

8、i.len=fj.len)for(z=0;zdi.len;z+)if(di.az=fj.az) flag1=1;elseflag1=0;break;if(flag1=1) printf(此碼組不是唯一可譯碼組!n);break;if(flag1=1) printf(此碼組不是唯一可譯碼組!n);break;if(flag1=0) printf(此碼組是唯一可譯碼組!n);香農(nóng)編碼題目分析問題描述用香農(nóng)方法編一個程序來對各符號編碼?；疽笮枰孟戕r(nóng)編碼方法。算法分析算法原理首先將輸入的概率按遞減的次序排列，然后計算累加概率Fi=k=1i-1pk，接著計算每個符號的碼字的長度li，它應該是不小于

9、log2pi的最小整數(shù)。最后將每個符號對應的累加概率轉變成二進制的數(shù)，碼字就取其二進制數(shù)的前l(fā)i位。這樣就得到了每個符號的碼字。算法設計思想array函數(shù)用來把輸入的概率按遞減的次序排列好，用的方法是先找最大的放第一個，再找次大的放第二個，如此反復。chang函數(shù)用來把累加函數(shù)由十進制變到二進制，在函數(shù)中，一位一位的比較，比較了一位，就用累加函數(shù)值減去此位的數(shù)0或1的2i倍，i表示是第幾位。算法中遇到的問題及解決方法由于香農(nóng)編碼比較的簡單，所以在編碼時基本上沒有什么問題，只要把chang函數(shù)編好就行。調(diào)試結果源代碼#include#include#includeint k100;int c10

10、0;void array(double a,int n)/排序int i,j;double m;for(i=0;in;i+)for(j=i;jn;j+)if(aiaj)m=ai;ai=aj;aj=m;void chang(double p,int l)int i,j=0,z=2; for(i=0;i100;i+)/初始化ci=-1;if(p=0)for(i=0;il;i+)ci=0;elsefor(i=0;i=1.0/z) cj+=1;p-=1.0/z;z*=2;else cj+=0;z*=2;main()double a100,b100,sum=0.0,m;int n,i,j;printf(

11、請輸入信源符號的個數(shù): n);scanf(%d,&n);doprintf(請依次輸入各信源符號的概率: n);for(i=0;in;i+)scanf(%lf,&ai);for(i=0;in;i+)sum+=ai;while(sum!=1);/檢驗概率和是否是1array(a,n); b0=0.0;for(i=1;in;i+)bi=bi-1+ai-1;/累加for(i=0;ij&m=j+1)ki=j+1;break;for(i=0;i100;i+)/初始化ci=-1;printf(按概率降序排列碼字依次為: );for(i=0;in;i+)printf(%.3f ,ai);printf(n);f

12、or(i=0;in;i+)printf(該碼字對應累加概率為: %.3f 該碼字碼長為: %d ,bi,ki);chang(bi,ki);printf(碼字為: );for(j=0;jki;j+)printf(%d,cj);printf(n);費諾編碼題目分析問題描述對于給定的概率，按照費諾編碼方法編碼?；疽蟀凑召M諾編碼方法編碼。算法分析算法基本原理首先，將信源符號以概率遞減的次序排列起來，將排列好的信源符號劃分成兩大組，使每組的概率和近于相同，并各賦予一個二元碼符號“0”，“1”。然后，將每一大組的信源符號再分成兩組，使同一組的兩個小組的概率和近于相同，并又分別賦予一個二元碼符號。依次下

13、去，直到每小組只剩一個信源符號為止。這樣，信源符號所對應的碼符號序列則為編得的碼字。算法設計思想首先，也要編一個array函數(shù)來排列概率，這與上面的香農(nóng)編碼相同。在這個設計中，主要是運用了一個遞歸算法來劃分概率組，先定義起點和終點，然后按照概率相近的要求來劃組，再把上面一部分賦予“0”，下面一部分賦予“1”，這都是存在一個二維數(shù)組中，其每一行對應一個概率的碼字，接著再遞歸這兩個小組。算法設計中遇到的問題和解決方法在費諾編碼中，主要的難題就是怎么來劃分組。這有點類似于我們學數(shù)據(jù)結構時需要編的遍歷算法。所以我就運用了遞歸算法，這大大簡便了算法設計，因為它的劃分組的方法是一樣的，不用遞歸算法，那么你

14、就是一直在重復編寫相同的劃分程序，其中改變了一些變量值。所以遞歸在這里是一個好的方法。運行結果 源代碼#include#include#includechar p100100;void array(double f,int n)/排序int i,j;double m;for(i=1;i=n;i+)for(j=i;j=n;j+)if(fifj)m=fi;fi=fj;fj=m;void F(int m,int n,double f)/遞歸算法int i,k; double sum=0.0,s=0.0,s1,a20; if(m=n) return; for(i=1;i=n;i+) ai=fi; for(i=m;i=n;i+) sum=sum+ai;k=m; while(s=sum-s) s1=s;s=s+fk+;if(sum-2*s1)=(2*s-sum) k-;for(i=m;ik;i+) strcat(pi,0);/編碼上面的為0for(i=k;i=n;i+) strcat(pi,1);/編碼下面的為1F(m,k-1,f);F(k,n,f); main()double sum=0.0,f100;int n,i;printf(請輸入信源符號的個數(shù): n);scanf(%d,&n);d