信息論實(shí)驗(yàn)報(bào)告

1、前 言信息論是現(xiàn)代通信與信息工程的理論基礎(chǔ)。作為電子信息科學(xué)與技術(shù)專業(yè)本科生的學(xué)科基礎(chǔ)課，本課程主要講授：信息的定義和測(cè)度、信源和信息熵、連續(xù)熵和信息變差、信道和互信息、平均互信息和信道容量、數(shù)據(jù)處理和信息測(cè)量理論、無(wú)失真信源編碼理論和編碼方法等內(nèi)容。本課程按“單符號(hào)離散信息系統(tǒng)”、“多符號(hào)離散信息系統(tǒng)”、“連續(xù)信息系統(tǒng)”三個(gè)“系統(tǒng)”層面，逐步深入展開(kāi)，以嚴(yán)密的數(shù)學(xué)分析貫串始終。通過(guò)教學(xué)，使學(xué)生掌握信息理論的基本概念和信息分析方法，為今后進(jìn)一步研究信息科學(xué)和信息技術(shù)打下堅(jiān)實(shí)的理論基礎(chǔ)。實(shí)驗(yàn)一：唯一可譯碼判斷實(shí)驗(yàn)學(xué)時(shí)：3實(shí)驗(yàn)類型：（演示、驗(yàn)證、綜合、設(shè)計(jì)、研究）實(shí)驗(yàn)要求：（必修、選修）一、實(shí)驗(yàn)?zāi)?/p>

2、的通過(guò)本次試驗(yàn)了解唯一可譯碼地判斷原理；實(shí)現(xiàn)用c語(yǔ)言編寫(xiě)判斷唯一可譯碼地程序二、實(shí)驗(yàn)內(nèi)容編程實(shí)現(xiàn)唯一可譯碼的判決準(zhǔn)則sardinaspatterson算法三、實(shí)驗(yàn)原理、方法和手段sardinaspatterson算法描述： 設(shè)c為碼字集合，按以下步驟構(gòu)造此碼的尾隨后綴集合f： (1) 考查c中所有的碼字，若wi是wj的前綴，則將相應(yīng)的后綴作為一個(gè)尾隨后綴放入集合f0中； (2) 考查c和fi兩個(gè)集合，若wjc是wifi的前綴或wifi 是wjc的前綴，則將相應(yīng)的后綴作為尾隨后綴碼放入集合fi+1中； (3)f=fi即為碼c的尾隨后綴集合； (4) 若f中出現(xiàn)了c中的元素，則算法終止，返回假(c

3、不是唯一可譯碼)；否則若f中沒(méi)有出現(xiàn)新的元素，則返回真。在我們?cè)O(shè)計(jì)的算法中，需要注意的是我們需要的是先輸出所有尾隨后綴的集合，然后再判斷該碼是否是唯一可譯碼，即如f中出現(xiàn)了c中的元素，則c不是唯一可譯碼，否則若f中沒(méi)有出現(xiàn)新的元素，則c為唯一可譯碼。而不是f中出現(xiàn)c中的元素就終止，這也是在本題的要求中需要注意的問(wèn)題。1、 概要設(shè)計(jì)：由于需要判斷尾隨后綴，所以我們需要反復(fù)的比較c和f中的碼字。1） 首先我們用一個(gè)b3030的數(shù)組來(lái)存放所有的尾隨后綴的集合；用q記錄所有尾隨后綴的個(gè)數(shù)；2） 用數(shù)組a3030來(lái)存放輸入的碼字，l30來(lái)存放碼字的長(zhǎng)度；通過(guò)一個(gè)雙重循環(huán)并調(diào)用houzhui（ai,aj,

4、li,lj）函數(shù)來(lái)找到a3030中的為隨后綴，即：for(i=0;in-1;i+) for(j=0;jn;j+) if(i!=j&lilj) huozhui(ai,aj,li,lj); 3） 通過(guò)判斷q是否大于0，如果不大于0，即b3030中沒(méi)有碼字，也就是不存在尾隨后綴，那么可判斷a3030是唯一可譯碼，否則進(jìn)行如下操作；4） 計(jì)算b3030中尾隨后綴的長(zhǎng)度，用k1表示；并調(diào)用huozhui(bi,aj,k1,lj)其中k1lj來(lái)a3030中所存在的后綴，并加入到b3030中，通過(guò)一個(gè)循環(huán)，找到a3030中所有尾隨后綴；即 for(i=0;iq;i+) k1=strlen(bi); for(

5、j=0;jn;j+) if(k1lj;通過(guò)循環(huán)調(diào)用即可找到b3030中的所有尾隨后綴，最后再將他們分別存放在b3030中；即通過(guò) for(i=0;in;i+) for(j=0;jli) huozhui(ai,bj,li,k2); 6） 在反復(fù)調(diào)用huozhui(ai,aj,li,lj)函數(shù)中如果b3030中有重復(fù)出現(xiàn)的，即尾隨后綴相同的不用再次放入b3030中。7） 在調(diào)用函數(shù)中所需要注意的問(wèn)題就是一個(gè)比較的問(wèn)題，也就是實(shí)現(xiàn)6）中所提到的。四，實(shí)驗(yàn)數(shù)據(jù)源1： 10,0.1002: 10,110，1110五、實(shí)驗(yàn)組織運(yùn)行要求以學(xué)生自主訓(xùn)練為主的開(kāi)放模式組織教學(xué)六、實(shí)驗(yàn)條件1. 計(jì)算機(jī)2. win

6、dows xp3. vc+ 6.0七、實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)源程序#include #include #include struct strings char *string; struct strings *next;struct strings fstr, *fh, *fp;/輸出當(dāng)前集合void outputstr(strings *str)docoutstringnext;while(str);coutb?b:a; inline int max(int a, int b) return ab?a:b; #define length_a (strlen(cp)#define length_b (s

7、trlen(tempptr)/判斷一個(gè)碼是否在一個(gè)碼集合中，在則返回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;/判斷兩個(gè)碼字是否一個(gè)是另一個(gè)的前綴，如果是則生成后綴碼void houzhui(char *cp,char *tempptr)if (!strcmp(cp,tempptr)cout集合c和集合f中有相同碼字:endlcpendl不是唯

8、一可譯碼碼組!next=null;cp_temp-string=new charabs(length_a-length_b)+1; char *longstr;longstr=(length_alength_b ? cp : tempptr);/將長(zhǎng)度長(zhǎng)的碼賦給longstr/取出后綴for (int k=min(length_a,length_b); kstringk - min(length_a,length_b)=longstrk;cp_temp-stringabs(length_a-length_b)=null;/判斷新生成的后綴碼是否已在集合f里，不在則加入f集合if(compari

9、ng(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 charstrlen(f); strcpy(fh-string, f); fh-next=null;/輸入待檢測(cè)碼的個(gè)數(shù)int cnum;coutcnum;cout輸入待檢測(cè)碼endl;for(int i=0; icnum; i+) couti+1

10、tempstr; 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;tempptr=cp;dotempptr=tempptr-next;houzhui(cp-string,tempptr-string);while(tempptr-next); outputstr(fh);struct strings *f

11、begin,*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(fh);/輸出f集合中全部元素 流程框圖數(shù)據(jù)測(cè)試（）輸入10,0,100(2)輸入10,110，1110八，實(shí)驗(yàn)心得1.更深入理解了唯一可譯碼地判斷原則2.學(xué)會(huì)了用sardinaspatterson算法實(shí)現(xiàn)編碼判斷3.掌握用c編程實(shí)

12、現(xiàn)唯一可譯碼判斷實(shí)驗(yàn)二： huffman編碼的實(shí)現(xiàn)實(shí)驗(yàn)學(xué)時(shí)：3實(shí)驗(yàn)類型：（演示、驗(yàn)證、綜合、設(shè)計(jì)、研究）實(shí)驗(yàn)要求：（必修、選修）一、 實(shí)驗(yàn)?zāi)康睦斫夂驼莆説uffman編碼的基本原理和方法，實(shí)現(xiàn)對(duì)信源符號(hào)的huffman編碼。二、 實(shí)驗(yàn)內(nèi)容1. 理解和掌握huffman編碼的基本原理和方法2. 通過(guò)matlab編程實(shí)現(xiàn)對(duì)單信源符號(hào)的huffma編碼3. 計(jì)算信源的信息熵、平均碼長(zhǎng)以及編碼效率三、 實(shí)驗(yàn)原理1 huffman編碼按信源符號(hào)出現(xiàn)的概率而編碼，其平均碼長(zhǎng)最短，所以是最優(yōu)碼。2 無(wú)失真信源編碼定理：對(duì)于熵為h(x)的離散無(wú)記憶的平穩(wěn)信源，必存在一種無(wú)失真編碼，使每符號(hào)的平均碼長(zhǎng)滿足不等式

13、：3 二元huffman編碼：若將編碼設(shè)計(jì)為長(zhǎng)度不等的二進(jìn)制編碼，即讓待傳字符串中出現(xiàn)概率大的字符采用盡可能短的碼字，而把長(zhǎng)的碼字分配給概率小的信源符號(hào)。構(gòu)造方法如下：（a） 將信源概率分布按大小以遞減次序排列；合并兩概率最小者，得到新信源；并分配0/1符號(hào)。（b） 新信源若包含兩個(gè)以上符號(hào)返回（a），否則到（c）。（c） 從最后一級(jí)向前按順序?qū)懗雒啃旁捶?hào)所對(duì)應(yīng)的碼字。4huffman編碼算法procedure huffman(si ,pi ) if q=2then return s0 0, s1 1else 降序排序pi縮減信源:創(chuàng)建一個(gè)符號(hào)s以取代sq-2 ,sq -1 ,其概率為p=p

14、q-2+ pq-1 遞歸調(diào)用huffman算法以得到s0 ,sq-3 ,s的編碼:w0 ,wq-3 ,w,相應(yīng)的概率分布為p0 ,pq -3 ,p returns 0 w0,sq-3 wq-3 ,sq-2 w0,sq-1 w1 end ifend procedure四、 實(shí)驗(yàn)數(shù)據(jù)源1 2 五、實(shí)驗(yàn)組織運(yùn)行要求以學(xué)生自主訓(xùn)練為主的開(kāi)放模式組織教學(xué)六、實(shí)驗(yàn)條件4. 計(jì)算機(jī)5. windows 6. vc+ 6.0七、實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)源程序#include #define maxbit 100#define maxvalue 10000#define maxleaf 30#define maxnode

15、maxleaf*2 -1typedef struct int bitmaxbit; int start; hcodetype; /* 編碼結(jié)構(gòu)體 */typedef struct int weight; int parent; int lchild; int rchild; hnodetype; /* 結(jié)點(diǎn)結(jié)構(gòu)體 */* 構(gòu)造一顆哈夫曼樹(shù) */void huffmantree (hnodetype huffnodemaxnode, int n) /* i、j： 循環(huán)變量，m1、m2：構(gòu)造哈夫曼樹(shù)不同過(guò)程中兩個(gè)最小權(quán)值結(jié)點(diǎn)的權(quán)值， x1、x2：構(gòu)造哈夫曼樹(shù)不同過(guò)程中兩個(gè)最小權(quán)值結(jié)點(diǎn)在數(shù)組中的序號(hào)

16、。*/ int i, j, m1, m2, x1, x2; /* 初始化存放哈夫曼樹(shù)數(shù)組 huffnode 中的結(jié)點(diǎn) */ for (i=0; i2*n-1; i+) huffnodei.weight = 0; huffnodei.parent =-1; huffnodei.lchild =-1; huffnodei.lchild =-1; /* end for */ /* 輸入 n 個(gè)葉子結(jié)點(diǎn)的權(quán)值 */ for (i=0; in; i+) printf (please input weight of leaf node %d: n, i); scanf (%d, &huffnodei.we

17、ight); /* end for */ /* 循環(huán)構(gòu)造 huffman 樹(shù) */ for (i=0; in-1; i+) m1=m2=maxvalue; /* m1、m2中存放兩個(gè)無(wú)父結(jié)點(diǎn)且結(jié)點(diǎn)權(quán)值最小的兩個(gè)結(jié)點(diǎn) */ x1=x2=0; /* 找出所有結(jié)點(diǎn)中權(quán)值最小、無(wú)父結(jié)點(diǎn)的兩個(gè)結(jié)點(diǎn)，并合并之為一顆二叉樹(shù) */ for (j=0; jn+i; j+) if (huffnodej.weight m1 & huffnodej.parent=-1) m2=m1; x2=x1; m1=huffnodej.weight; x1=j; else if (huffnodej.weight m2 & hu

18、ffnodej.parent=-1) m2=huffnodej.weight; x2=j; /* end for */ /* 設(shè)置找到的兩個(gè)子結(jié)點(diǎn) x1、x2 的父結(jié)點(diǎn)信息 */ huffnodex1.parent = n+i; huffnodex2.parent = n+i; huffnoden+i.weight = huffnodex1.weight + huffnodex2.weight; huffnoden+i.lchild = x1; huffnoden+i.rchild = x2; printf (x1.weight and x2.weight in round %d: %d, %

19、dn, i+1, huffnodex1.weight, huffnodex2.weight); /* 用于測(cè)試 */ printf (n); /* end for */ /* end huffmantree */int main(void) hnodetype huffnodemaxnode; /* 定義一個(gè)結(jié)點(diǎn)結(jié)構(gòu)體數(shù)組 */ hcodetype huffcodemaxleaf, cd; /* 定義一個(gè)編碼結(jié)構(gòu)體數(shù)組， 同時(shí)定義一個(gè)臨時(shí)變量來(lái)存放求解編碼時(shí)的信息 */ int i, j, c, p, n; printf (please input n:n); scanf (%d, &n); huffmantree