信息論—— - 副本

《信息論—— - 副本》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、周鵬版權所有，違者必究版權所有，違者必究版權所有，違者必究版權所有，違者必究版權所有，違者必究版權所有，違者必究版權所有，違者必究版權所有，違者必究版權所有，違者必究版權所有，違者必究版權所有，違者必究版權所有，違者必究唯一可譯碼判決準則一、實驗內容編程實現唯一可譯碼的判決準則―――Sardinas－Patterson算法二、實驗環(huán)境1.計算機2.Windows73.VC++6.0三、實驗目的1.進一步熟悉唯一可譯碼判決準則；1.掌握VC開發(fā)環(huán)境的使用；2.掌握C語言編程（尤其是字符串處理）四、實驗要求1.提前預習實驗，認真閱讀實

2、驗原理。2.認真高效的完成實驗，實驗過程中服從實驗室管理人員以及實驗指導老師的管理。3.認真填寫實驗報告。五、關于唯一可譯碼1、唯一可譯變長碼判別準則A.A.Sardinas和G.W.Patterson于1957年提出下述算法用于判斷碼C的唯一可譯性．此算法的原理如下所示：其中Ai,Bi都是碼字?？芍斍覂H當某個有限長的碼符號序列能譯成兩種不同的碼字序列時，此碼不是唯一可譯碼，此時B1一定是A1的前綴，而A1的尾隨后綴一定是另一碼字B2的前綴；而B2的尾隨后綴又是其他碼字的前綴．最后，碼符號序列的尾部一定是一個碼字。將碼C中所有

3、可能的尾隨后綴組成一個集合F，當且僅當集合F中沒有包含任一碼字，便可判斷此碼C為唯一可譯變長碼六、實現唯一可譯碼的判決準則過程1、Sardinas－Patterson算法設C為碼字集合，按以下步驟構造此碼的尾隨后綴集合F：(1)考查C中所有的碼字，若Wi是Wj的前綴，則將相應的后綴作為一個尾隨后綴放入集合F0中；(2)考查C和Fi兩個集合，若Wj∈C是Wi∈Fi的前綴或Wi∈Fi是Wj∈C的前綴，則將相應的后綴作為尾隨后綴碼放入集合Fi+1中；(3)F=∪Fi即為碼C的尾隨后綴集合；(4)若F中出現了C中的元素，則算法終止，返

4、回假(C不是唯一可譯碼)；否則若F中沒有出現新的元素，則返回真。輸入碼字集合X0for所有Wi，Wj∈X0if碼字Wi是碼字Wj的前綴，即將相應的后綴作為一個尾隨后綴放入新集合X1endifendforfor所有Wi∈X0for所有Wj∈Xn－1ifWi是Wj的前綴，即將相應的后綴作為一個尾隨后綴放入新集合Xn中elseifWj是Wi的前綴，即將相應的后綴作為一個尾隨后綴放入新集合Xn中endifendforendfor構造尾隨后綴集合X←Xiif有碼字Wi∈X0，Wi∈X，則非唯一可譯碼2、算法流程1.算法流程六、實驗設計1、

5、數據結構本實驗所需設計的程序中，碼字可用如下結構體表示：2、關鍵算法3、函數調用關系圖七、實驗結果3、關鍵算法（判斷前綴形成Fi）intjudge(char**C,intnum,int*l){intt=0,p=-1;inttemp=-1;int*k=newint[num-1];//F中第i+1行有k[i]個字符char**F;F=newchar*[num-1];for(inti=0;i<=num-1;i++){//F0形成F[i]=newchar[100];for(intj=i+1;j

6、],C[j])==0)return0;//C中有相同碼字elseif(l[i]>l[j]){if(strncmp(C[i],C[j],l[j])==0){k[++p]=l[i]-l[j];t=l[i]-l[j];post(C,F,i,t,p,num);}}else{if(strncmp(C[i],C[j],l[i])==0){k[++p]=l[j]-l[i];t=l[j]-l[i];post(C,F,j,t,p,num);}}}}4、函數調用關系圖判斷前綴形成Fi調用judge（）主函數main（）比較C和F中有無相同項post（

7、）七、用戶手冊首先根據提示輸入碼字集合中碼字的個數，然后分別輸入碼字六、實驗結果輸入6個碼字：0、10、1100、1110、1011、1101，并判斷出該碼字集合不是唯一可譯碼輸入5個碼字：xx、xz、y、zz、xyz，判斷出該碼字集合是可譯碼。六、源程序（C++）#include#include#include//usingnamespacestd;intjudge(char**C,intnum,int*l);voidpost(char**C,char**F,intb

8、,intt,intp,intnum);voidmain(){intz;char**C;//碼字集合intnum;//n行cout<<"請輸入碼字集合中碼字個數"<>num;//輸入行數int*l=newint[num];//C中