信息論實驗(共11頁)

1、信息論與編碼(bin m)實驗實驗(shyn)一 唯一可譯碼判別(pnbi)準(zhǔn)則1.實驗?zāi)康模?）進一步熟悉唯一可譯碼判決準(zhǔn)則；（2）掌握C語言字符串處理程序的設(shè)計和調(diào)試技術(shù)。2.實驗要求 （1）已知：信源符號個數(shù)q、碼字集合C；（2）輸入：任意的一個碼，碼字個數(shù)和每個碼字在運行時從鍵盤輸入；（3）輸出：判決（是唯一可譯碼/不是唯一可譯碼）。3.實驗原理 其中Ai和Bi都是碼字。可知，當(dāng)且僅當(dāng)某個有限長的碼符號序列能被譯碼成兩種不同的碼字序列時，此碼不是唯一可譯碼，此時B1一定是A1的前綴，而A1的尾隨后最一定是另一碼字B2的前綴；而B2的尾隨后綴又是其他碼字的后綴。最后，碼符號序列的尾部一定

2、是一個碼字。設(shè)C是碼字集合(jh)，尾隨后綴集合F： （1）考察(koch)C中所有(suyu)的碼字，若Wi是Wj的前綴，則將相應(yīng)的后綴作為一個尾隨后綴碼放入集合F1中；（2）考察C和Fi兩個集合，若WiC是WjFi的前綴或者WiFi是WjC的前綴，則將相應(yīng)的后綴作為尾隨后綴碼放入集合Fi+1中；（3）F=iFi即為碼C的尾隨后綴集合；（4）若F中出現(xiàn)C中的元素，則算法終止，返回假（C不是唯一可譯碼）；否則若F中沒有出現(xiàn)新的元素，則返回真。4.實驗環(huán)境軟件：DevC+ 編程語言：C語言5.實驗程序 #include#include#define num 20#define row 20 ch

3、ar cnumrow;char fnumrow;int N,sum=0; int flag; void weiyima(char c,char d) /檢測尾隨后綴 int i,j,k; for(i=0;i+) if(ci=0&di=0)/2字符串一樣，跳出 break; if(ci=0) /d比c長，將d的尾隨后綴放入f中 for(j=i;dj!=0;j+) fsumj-i=dj; fsumj-i=0; for(k=0;ksum;k+) if(strcmp(fsum,fk)=0) /*查看當(dāng)前生成的尾隨后綴在f集合中是否存在*/ sum-;break; sum+; break; if(di=

4、0) /c比d長，將c的尾隨后綴放入f中 for(j=i;cj!=0;j+) fsumj-i=cj; fsumj-i=0; for(k=0;ksum;k+) if(strcmp(fsum,fk)=0) /*查看當(dāng)前(dngqin)生成的尾隨后綴在f集合中是否(sh fu)存在*/ sum-;break; sum+; break; if(ci!=di)/字符不一樣(yyng)了也退出 break; /*主函數(shù)*/main()char loop;loop = y;while(loop=y) int i,j,init; flag = 0; printf(請輸入碼字的個數(shù):n);/輸入碼得個數(shù) sca

5、nf(%d,&N); for(init=0;initN;init+) finitinit= ; printf(請分別輸入碼字（每個碼字長度小于50個字符）:n); for(i=0;iN;i+) scanf(%s,&ci); for(i=0;iN-1;i+)/判斷如果碼本身是否重復(fù) for(j=i+1;jN;j+) if(strcmp(ci,cj)=0) flag=1;break; if(flag=1)/如果碼本身有重復(fù)，就可以斷定它不是唯一可譯碼 printf(這不是唯一可譯碼。n); else for(i=0;iN-1;i+) /*此處是根據(jù)原始編碼生成的尾隨后綴集合s1放入f中*/ for

6、(j=i+1;jN;j+) weiyima(ci,cj); for(i=0;i+) /根據(jù)(gnj)原始碼與si生成(shn chn)si+1也放入fi int s=0; for(j=0;jN;j+) /*判斷(pndun)si+1中的字符串是否與si中一樣 ，重復(fù)的則不再添加*/ if(i=sum) s=1;break; else weiyima(fi,cj); if(s=1)break; for(i=0;isum;i+) /判斷f和c中是否有相同的元素，有則是不唯一的 for(j=0;jN;j+) if(strcmp(fi,cj)=0) flag=1; break; printf(判斷結(jié)果

7、：); if(flag=1) printf(這不是唯一可譯碼。n); else printf(這是唯一可譯碼。n); /loop = getchar(); printf(是否繼續(xù) :); scanf(%s,&loop); 6.實驗結(jié)果實驗結(jié)果(ji gu)分析：（1）3個碼字0,01,010：不是(b shi)唯一可譯碼 C的后綴(huzhu)集合F： F1=1,10,0 其中F1中的“0”和C中的“0”重復(fù)，因此不是唯一可譯碼。 例如：010可以譯碼為010或者01,0（2）3個碼字1,10,100：是唯一可譯碼 C的后綴集合F： F1=0,00 C的元素不是F1的前綴，F(xiàn)1中的元素也不是C

8、的前綴，F(xiàn)1中沒有與C相同的元素，因此該碼字是唯一可譯碼。 （3）4個碼字101,10010,0110,01：不是唯一可譯碼 C的后綴集合F： F1=10； F2=1,010； F3=01,0010 F3中的元素(yun s)在C中有，因此不是(b shi)唯一可譯碼。 如：0110101可被譯碼成01,101,01或者(huzh)0110,1017.實驗體會 通過這次實驗，熟悉了判別是否是唯一可譯碼的方法，學(xué)會使用C語言進行字符串處理程序的設(shè)計和調(diào)試，并使用輸入循環(huán)。 實驗二 Huffman編碼1.實驗?zāi)康?（1）進一步熟悉Huffman編碼過程；（2）掌握C語言遞歸程序的設(shè)計和調(diào)試技術(shù)。2

9、.實驗要求 （1）輸入：信源符號個數(shù)r、信源的概率分布P； （2）輸出：每個信源符號對應(yīng)的Huffman編碼的碼字。3.實驗原理 （1）首先將q個信源符號按照概率大小遞減排列p（s1）p（s2）p（sq）； （2）用“0”“1”碼符號分別代表概率最小的兩個信源符號，并將這兩個概率最小的信源符號合并成一個，從而得到只包含q-1個符號的新信源，成為縮減信源S1； （3）把縮減信源S1的符號仍按概率大小遞減次序排列，再將其最后兩個概率最小的信源符號分別用“0”和“1”碼符號表示，并且合并成一個符號，這樣有行程q-2個信源符號的縮減信源S2； （4）依次繼續(xù)下去，直至信源最后只剩下兩個信源符號為止，將

10、這最后兩個信源符號分別用二元碼符號“0”和“1”表示； （5）最后(zuhu)從最后一級縮減信源開始，進行回溯，就得到各信源符號所對應(yīng)的碼符號序列，即相應(yīng)的碼字。4.實驗(shyn)環(huán)境軟件(run jin)：DevC+ 編程語言：C語言5.實驗程序#include #define maxnum 20#define max_v 10000#define max_le 30#define max_no max_le*2 -1typedef struct int bitmaxnum; int start; HCodeType; /* 編碼結(jié)構(gòu)體 */typedef struct float wei

11、ght; int parent; int lchild; int rchild; HNodeType; /* 結(jié)點結(jié)構(gòu)體 */* 構(gòu)造一顆哈夫曼樹 */void HuffmanTree (HNodeType HuffNodemax_no, int n) int i, j, MinSeq1, MinSeq2; float MinValue1,MinValue2; / 初始化存放哈夫曼樹數(shù)組 HuffNode 中的結(jié)點 for (i=0; i2*n-1; i+) HuffNodei.weight = 0; HuffNodei.parent =-1; HuffNodei.lchild =-1; Hu

12、ffNodei.lchild =-1; /* end for */ /* 輸入 n 個葉子結(jié)點的權(quán)值 */ printf(請輸入碼字的概率：n); for (i=0; in; i+) / printf (輸入葉子節(jié)點 %d: n, i); scanf (%f, &HuffNodei.weight); /* end for */ /* 循環(huán)構(gòu)造 Huffman 樹 */ for (i=0; in-1; i+) MinValue1=MinValue2=max_v; /* MinValue1、MinValue2中存放兩個無父結(jié)點且結(jié)點權(quán)值最小的兩個結(jié)點 */ MinSeq1=MinSeq2=0; /

13、* 找出所有結(jié)點中權(quán)值最小、無父結(jié)點的兩個(lin )結(jié)點，并合并之為一顆二叉樹 */ for (j=0; jn+i; j+) if (HuffNodej.weight MinValue1 & HuffNodej.parent=-1) MinValue2=MinValue1; MinSeq2=MinSeq1; MinValue1=HuffNodej.weight; MinSeq1=j; else if (HuffNodej.weight MinValue2 & HuffNodej.parent=-1) MinValue2=HuffNodej.weight; MinSeq2=j; /* end

14、for */ /* 設(shè)置找到的兩個(lin )子結(jié)點 MinSeq1、MinSeq2 的父結(jié)點(ji din)信息 */ HuffNodeMinSeq1.parent = n+i; HuffNodeMinSeq2.parent = n+i; HuffNoden+i.weight = HuffNodeMinSeq1.weight + HuffNodeMinSeq2.weight; HuffNoden+i.lchild = MinSeq1; HuffNoden+i.rchild = MinSeq2; / printf (n); /* end for */ /* end HuffmanTree */

15、main(void)char loop;loop = y;while(loop=y) HNodeType HuffNodemax_no; /* 定義一個結(jié)點結(jié)構(gòu)體數(shù)組 */ HCodeType HuffCodemax_le, cd; /* 定義一個編碼結(jié)構(gòu)體數(shù)組， 同時定義一個臨時變量來存放求解編碼時的信息 */ int i, j, c, p, n; printf (請輸入碼字個數(shù) n:n); scanf (%d, &n); HuffmanTree (HuffNode, n); for (i=0; i n; i+) cd.start = n-1; c = i; p = HuffNodec.pa

16、rent; while (p != -1) /* 父結(jié)點存在 */ if (HuffNodep.lchild = c) cd.bitcd.start = 1; else cd.bitcd.start = 0; cd.start-; /* 求編碼(bin m)的低一位 */ c=p; p=HuffNodec.parent; /* 設(shè)置下一循環(huán)(xnhun)條件 */ /* end while */ /* 保存求出的每個葉結(jié)點的哈夫曼編碼(bin m)和編碼的起始位 */ for (j=cd.start+1; jn; j+) HuffCodei.bitj = cd.bitj; HuffCodei.

17、start = cd.start; /* end for */ printf(霍夫曼編碼為:n); /* 輸出已保存好的所有存在編碼的哈夫曼編碼 */ for (i=0; in; i+) printf(%.2f : ,HuffNodei.weight); / printf (%d s Huffman code is: , i); for (j=HuffCodei.start+1; j n; j+) printf (%d, HuffCodei.bitj); printf (n); / getchar(); / return 0; printf(是否繼續(xù)?:); scanf(%s,&loop);

18、6.實驗結(jié)果0實驗(shyn)結(jié)果分析010.20 0.20 0.26 0.35 0.39 0.61 10010.19 0.19 0.20 0.26 0.35 0.390110.18 0.18 0.19 0.20 0.2610.17 0.17 0.18 0.1900.15 0.15 0.1710.10 0.110.01則各碼字的Huffman編碼(bin m)：0.20 : 100.19 : 110.18 : 0000.17 : 0010.15 : 0100.10 : 01100.01 : 01110第二個碼字概率(gil)0010.20 0.40 0.40 0.60 1 0110.20 0.20 0.4