信息論與編碼實習(xí)報告

本文格式為Word版，下載可任意編輯——信息論與編碼實習(xí)報告

信息論與編碼實習(xí)報告

試驗一唯一可譯碼判決準(zhǔn)則

一、試驗內(nèi)容

編程實現(xiàn)唯一可譯碼的判決準(zhǔn)則―――Sardinas－Patterson算法二、試驗環(huán)境

1.計算機(jī)

2.Windows2000或以上3.VC++6.0三、試驗?zāi)康?/p>

1.進(jìn)一步熟悉唯一可譯碼判決準(zhǔn)則；2.把握VC開發(fā)環(huán)境的使用；

3.把握C語言編程（特別是字符串處理）；四、試驗要求

1.提前預(yù)習(xí)試驗，認(rèn)真閱讀試驗原理。

2.認(rèn)真高效的完成試驗，試驗過程中聽從試驗室管理人員以及試驗指導(dǎo)老

師的管理。3.認(rèn)真填寫試驗報告。五、試驗原理

1.唯一可譯碼判決準(zhǔn)則的原理參考書1的153頁。其原理可簡介如下：

將源碼組C中所有可能的尾隨后綴組成一個集合F，當(dāng)且僅當(dāng)集合F中沒有包含任一碼字，便可判斷此碼C為唯一可譯變長碼。

2.算法流程

輸入碼字集合XW，W∈Xfor所有if碼字W是碼字W的前綴，即將相應(yīng)的后綴作為一個尾隨后綴放入新集合Xendifendforfor所有W∈Xfor所有W∈XifW是W的前綴，即將相應(yīng)的后綴作為一個尾隨后綴放入新集合X中elseifW是W的前綴，即將相應(yīng)的后綴作為一個尾隨后綴放入新集合X中endifendforendfor構(gòu)造尾隨后綴集合X←Xif有碼字W∈X，W∈X，則非唯一可譯碼0ji0ij1i0jn－1ijnjinii0i六、試驗設(shè)計1、數(shù)據(jù)結(jié)構(gòu)

本試驗所需設(shè)計的程序中，碼字可用如下結(jié)構(gòu)表示：charc[100][50]尾隨后綴用如下結(jié)構(gòu)表示:charf[300][50]

2、關(guān)鍵算法

本程序的關(guān)鍵算法是用來求尾隨后綴的Sardinas－Patterson算法。

其算法流程圖如下：

假使c[i]=d[i]=’Y’/0NY

假使c[i]=’/0’,將d的剩余部分放入尾隨后綴集合開始輸入兩個要計算尾隨后綴的字符i=0比較c[i]、d[i]NY

假使d[i]=’/0’,將c的剩余部分放入尾隨后綴集合N假使c[i]=d[i]NY

voidpatterson(charc[],chard[])//檢測尾隨后綴

{

inti,j,k;

for(i=0;;i++)

i++；break{

if(c[i]=='\\0'

if(c[i]=='\\0')//d比c長，將d的尾隨后綴放入f中{

for(j=i;d[j]!='\\0';j++)f[sum][j-i]=d[j];f[sum][j-i]='\\0';

for(k=0;k

用戶手冊:

1.依照提醒先輸入隨后將輸入字符串的總個數(shù)

2.依次輸入個字符串3.得出結(jié)果總結(jié)：

本次編程試驗中進(jìn)一步加深了對尾隨后綴集合算法的理解，運用C語言將其實現(xiàn)。在程序中設(shè)置了一個相互比較兩個字符串是否為對方前綴的函數(shù)，以求得尾隨后綴。

程序大體寫完后，又在原程序的基礎(chǔ)上增加了它的魯棒性。附源代碼：

#include#includecharc[100][50];charf[300][50];

intN,sum=0;//N為輸入碼字的個數(shù)，sum為尾隨后綴集合中碼字的個數(shù)intflag;//判斷是否唯一可譯標(biāo)志位

voidpatterson(charc[],chard[])//檢測尾隨后綴{

inti,j,k;

for(i=0;;i++){

if(c[i]=='\\0'

if(c[i]=='\\0')//d比c長，將d的尾隨后綴放入f中{

for(j=i;d[j]!='\\0';j++)f[sum][j-i]=d[j];f[sum][j-i]='\\0';

for(k=0;k100){printf(\輸入碼字個數(shù)過大，請輸入小于100的數(shù)\\n\printf(\請輸入碼字的個數(shù)（小于100）:\scanf(\}

flag=0;

printf(\請分別輸入碼字（每個碼字長度小于50個字符）:\\n\for(i=0;i

Y終止本次循環(huán)把最終一個字符設(shè)為’/0’

for(i=0;i=1){

sb[i].m[j]='1';p=p-1;}

elsesb[i].m[j]='0';}

sb[i].m[sb[i].l]='\\0';}

3、函數(shù)調(diào)用關(guān)系圖

僅有main()函數(shù)。概率排序、求累加概率、自信息量、碼字長度、碼字的

函數(shù)均包含在main()函數(shù)內(nèi)。九、用戶手冊及總結(jié)用戶手冊:

1.依照提醒先輸入信源的總個數(shù)

2.依次輸入各信源的名稱3.再按上序輸入信源的概率4.得出結(jié)果總結(jié)：

本次編程中沒有用到特別繁雜的算法。依照香農(nóng)編碼的編碼方法依次實現(xiàn)各模塊即可。在編程中要注意的是數(shù)字的類型，利用log函數(shù)時求得的值是double型。附源代碼：

#include#include#include

typedefstructsymbol{

chars[50];

doublepa,pb,h;//分別為符號概率，累加概率，自信息量intl;//碼字長度charm[100];//碼字}symbol;

intN;

voidmain(){

inti,j;

symbolsb[100];

printf(\請輸入符號的個數(shù):\scanf(\

printf(\請依次輸入消息符號:\\n\for(i=0