信息論課程設(shè)計(jì)報(bào)告

1、成績：2016-2017 學(xué)年第 1 學(xué)期信息論課程設(shè)計(jì)學(xué)院名稱：班級學(xué)號：學(xué)生姓名：教師姓名：2016 年 12 月一、判定唯一可譯碼1. 任務(wù)說明輸入：任意的一個碼 （ 即已知碼字個數(shù)及每個具體的碼字 ）輸出：判決結(jié)果（是 / 不是）輸入文件 : ，含至少 2 組碼，每組的結(jié)尾為” $”符輸出文件 : ，對每組碼的判斷結(jié)果說明：為了簡化設(shè)計(jì)，可以假定碼字為 0，1 串2. 實(shí)現(xiàn)原理判斷方法：將碼 C中所有碼字可能的尾隨后綴組成一個集合F,當(dāng)且僅當(dāng)集合F中沒有包含任一碼字，則可判斷此碼 C為唯一可譯變長碼。構(gòu)成集合F:首先觀察碼C中最短的碼字是否是其他碼字的前綴。若是，將其所有可能的尾隨后綴

2、排列出。就是將其他碼字序列中截去與其最短碼字相同的前綴部分，將余下的序列為尾隨后綴。而這些尾隨后綴又可能是某些碼字的前綴，或者最短碼字又仍是這些尾隨后綴的前綴，再將由這些尾隨后綴產(chǎn)生的新的尾隨后綴列出。然后再觀察這些新的尾隨后綴是否是某些碼字的前綴，或觀察有否其他碼字是這些新的尾隨后綴的前綴，再將產(chǎn)生的尾隨后綴列出，依次下去，直至沒有一個尾隨后綴是碼字的前綴或沒有新的尾隨 后綴產(chǎn)生為止。這樣，首先獲得的是由最短碼字能引起的所有尾隨后綴。接著，按照上述步驟將次短的碼字、 所有碼字可能產(chǎn)生的尾隨后綴前部 列出。由此得到由碼 C的所有可能的尾隨后綴組成的集合F。參考算法偽代碼:For all Wi,

3、Wj C doif W、是Wj的前綴then將相應(yīng)的后綴作為一個尾隨后綴放入集合F0中End ifEnd forLoopFor all Wi C doFor all Wj Fn doif Wi 是 Wj 的前綴 then將相應(yīng)的后綴作為一個尾隨后綴放入集合Fn 1中Else if Wj 是 W 的前綴 then將相應(yīng)的后綴作為一個尾隨后綴放入集合Fn 1中End ifEnd forEnd forIfWiF,Wi C thenReturn falseElse if F中未出現(xiàn)新的元素 the nRetur n trueEnd if實(shí)現(xiàn)源碼#inelude <iostream>#inc

4、lude <fstream>#include <>#include <>using namespace std;#pragma warning (disable :4996)char c10050;運(yùn)行結(jié)果輸入文件：說明：輸入文件中第一個數(shù)字表示碼的組數(shù)，第二個數(shù)字表示一組碼碼字的個數(shù)，一組 碼結(jié)束以“ $”符號結(jié)尾；“$”符號后的數(shù)字表示下一組碼的碼字個數(shù)。此例以兩組碼輸入 為例，多組碼判斷同上。輸出文件：結(jié)果分析：程序首先讀取第一組碼，進(jìn)行是否唯一可譯碼的判斷，在輸出文件第一行輸 出判斷結(jié)果，在第二行輸出該碼字產(chǎn)生的尾隨后綴集合(若只是輸出是否唯一可譯碼

5、的判斷結(jié)果，不能完全說明程序的正確性，可能存在偶然性；若是輸出的尾隨后綴集合是正確的， 則能說明程序的正確性，由于選取的兩組數(shù)據(jù)來自課本，可以準(zhǔn)確的知道尾隨后綴集合是否正確，則可驗(yàn)證此程序的正確性，即可用于判斷碼是否為唯一可譯碼)。5.設(shè)計(jì)體會通過此實(shí)驗(yàn)的設(shè)計(jì)，進(jìn)一步加深了我對唯一可譯碼判別方法的理解。此實(shí)驗(yàn)在設(shè)計(jì)完成 的過程中出現(xiàn)兩大難點(diǎn)， 第一點(diǎn)就是， 作為此程序的核心， 兩個碼字生成尾隨后綴的函數(shù)編 寫，選取兩個字符數(shù)組保存碼字和后綴， 通過碼字長度和單個字符比較來生成尾隨后綴； 第 二個難點(diǎn)是碼字的文件讀取， 起初考慮的是整個碼字一起讀取， 發(fā)現(xiàn)實(shí)現(xiàn)過程較為復(fù)雜， 經(jīng) 過修改， 改為單

6、個字符讀取能簡化程序的設(shè)計(jì)。 其他部分按照唯一可譯碼的判斷方法進(jìn)行設(shè) 計(jì)，關(guān)鍵部分調(diào)用尾隨后綴生成函數(shù)即可， 再將判斷結(jié)果輸出到輸出文件。 此實(shí)驗(yàn)總體而言 較為簡單，實(shí)現(xiàn)時(shí)注意細(xì)節(jié)、沒有邏輯誤區(qū)即可。二、游程編碼 +Huffman 碼1. 任務(wù)說明要求：一無記憶二元信源， 0 符號的出現(xiàn)概率為 1/4, 1 符號的出現(xiàn)概率為 3/4 ?，F(xiàn)要求 對該信源連續(xù)出現(xiàn)的 n 個符號序列，先進(jìn)行游程編碼，再對結(jié)果進(jìn)行 Huffman 編碼。然后，再進(jìn)行 Huffman 譯碼和游程譯碼。假定，連續(xù)出現(xiàn)的 0或 1 序列 的長度不超過 16，n 不小于 256。輸入：長為 n 的 0/1 串輸出： 1. 游

7、程編碼結(jié)果， 2. Huffman 編碼結(jié)果， 3. Huffman 譯碼結(jié)果 4. 游程譯碼結(jié) 果輸入文件 : ，含至少兩組輸入輸出文件 : ，對每組輸入的處理結(jié)果2. 實(shí)現(xiàn)原理游程編碼：信源輸出的字符序列中各種字符連續(xù)地重復(fù)出現(xiàn)而形成一段一段的字符串，這種字符串的長度稱為游程。游程編碼（RLC就是將信源輸出的這種字符序列映射成由串的字符， 串的長度和串的位置三個標(biāo)志組成的標(biāo)志序列。 知 道了串的字符、 串的長度和串的位置的標(biāo)志序列， 就可以完全恢復(fù)出原來的 字符序列。在二元序列中，只有兩種符號，即“ 0”和“ 1”，這些符號可連續(xù)出現(xiàn)，連“ 0”這一段稱為“ 0”游程，連“ 1”這一段稱為

8、“ 1”游程。它們的長度分 別稱為游程長度 L(0) 和 L(l) ?！?0”游程和“ l ”游程總是交替出現(xiàn)的。如 果規(guī)定二元序列是以“ 0”開始，第一個游程是“ 0”游程，第二個必為“ 1”游 程，第三個又是“ 0”游程等等。對于隨機(jī)的二元序列，各游程長度將是隨 機(jī)變量，其取值可為 1，2，3， ?，直到無限。Huffman碼：(1 )將q個信源符號按概率分布 P (si )的大小，以遞減次序排列起來，設(shè) p1>=p2>=p3>=.>=p q( 2)用 0 和 1 碼符號分別分配給概率最小的兩個信源符號，并將這兩個概率最小的信源符號合并成一個信服好，并用這兩個最小概

9、率之和 作為新符號的概率，從而得到只包含 q-1 個服啊后的新信源，稱為 S信源的縮減信源 S1。(3)把縮減信源Si的符號仍按概率大小以遞減次序排列，再將其最后兩 個概率最小的符號合并成一個新符號， 并分別用 0和 1 碼符號表示， 這樣又形成了 q-2 個符號的縮減信源 S2。( 4)依次繼續(xù)下去，直至縮減信源最后只剩兩個符號為止。將這最后兩 個符號分別用 0 和 1 碼符號表示。最后這兩個符號的概率之和必為1。然后從最后一級縮減信源開始， 依編碼路徑由后向前返回， 就得出各信源符號所對應(yīng)的碼符號序列，即得對應(yīng)的碼字。Huffman 碼參考算法偽代碼：if q=2 thenReturns0

10、0,s11Else降序排序 pi縮減信源：創(chuàng)建一個符號s'以取代Sq 1,Sq 2，其概率P' Pq 2 Pq 1遞歸調(diào)用Huffman算法以得到恥3，$ 3,s的編碼WoW.Wq 3,w (相應(yīng)的概率分 布為 p0， p1 ,，pq 3 , p)ReturnSoWo,S,Wi,.,Sq3Wq3,Sq2w'0,Sq1w'1End if3. 實(shí)現(xiàn)源碼#include <iostream>#include <string>#include <>#include <>#include <fstream>#pr

11、agma warning (disable :4996)#define N 100#define M 2*N-1typedef char * HuffmanCode2 * M; = chi; |CW*p.weight = 1;for (k = i + 1; chk !='0' k+)if (chi = chk)CW*p.weight+;eight = wi.weight;hti.pare nt = 0;hti. LChild = 0;hti.RChild = 0;for (i = n + 1; i <= 2 * n - 1; i+)hti.weight = 0;hti.p

12、are nt = 0;hti. LChild = 0;hti.RChild = 0;for (i = n + 1; i <= 2 * n - 1; i+)for (j = 1; j <= i - 1; j+)if (!htj.pare nt)break ;s1 = j; arent)s1 = hts1.weight>htj.weight j : s1; |hts1.pare nt = i;hti. LChild = s1;for (j = 1; j <= i - 1; j+)if (!htj.pare nt)break ;s2 = j; arent)s2 = hts2.

13、weight>htj.weight j : s2;|hts2.pare nt = i;hti.RChild = s2;hti.weight = hts1.weight + hts2.weight;are nt;Child = c)are nt;weighty.num = n - start; 中查找與 chi相等的下標(biāo) K*/if (chi = weightk.c)break ;hci = ( char *)malloc(weightk.num)*sizeof (char);strcpy(hci, hk); Child;elsep = htp.RChild;printf( "%

14、c", wp.c); /*打印原信息 */out << wp.c;i+;out << en dl;/* 釋放 huffman 編碼內(nèi)存 */void FreeHuffma nCode(Huffma nCode h, Huffma nCode hc, int n, int m) int i;for (i = 1; i <= n; i+);printf("nWeight ");for (i = 1; i <= n; i+)printf( "%d ", weighti.weight);CreateHuffmanTr

15、ee(ht, weight, n);/*產(chǎn)生 Huffman 樹*/printf( "n*HuffamnTreelnformation*n");printf( "titweighttparenttLChildtRChildn");for (i = 1; i <= 2 * n - 1; i+) eight, hti.parent, hti.LChild,hti .RChild);CrtHuffmanNodeCode(ht, ch, h, weight, m, n);/*葉子結(jié)點(diǎn)的編碼 */printf(” *NodeCode*n" ); /

16、* 打印葉子結(jié)點(diǎn)的編碼 */for (i = 1; i <= n; i+)printf( "t%c:" , weighti.c);printf( "%sn" , hi);CrtHuffmanCode(ch, h, hc, weight, n, m);/*所有字符的編碼 */printf( "Huffman編碼后");/*打印字符串的編碼 */for (i = 0; i < m; i+)printf( "%s", hci);strcpy(&y i, hci);system( "pause

17、");void huffma nyi ma()printf( "huffman 譯碼后：");TrsHuffmanTree(ht, weight, hc, n, m);/*解碼 */FreeHuffma nCode(h, hc, n, m);system( "pause");int mai n() char s100;if (!()cout << "Error opening file" ; exit(1);while (!() (s, 100);cout << s << en dl;yo

18、uche ngbia nm a(s);out << "游程編碼后："<< x << endl;huffma nbm(x);out << "Huffman 編碼后：” << y << endl;out << "huffman 譯碼后：”；huffma nyima();youche ngyima(x);();();return 0;4. 運(yùn)行結(jié)果輸入文件：結(jié)果分析：對 n 個符號序列進(jìn)行游程編碼后輸出“ 0”游程長度和“ 1”游程長度，再對 結(jié)果進(jìn)行霍夫曼編碼， 得到游程編碼

19、結(jié)果的霍夫曼碼。 然后進(jìn)行譯碼， 首先的是霍夫曼譯碼， 得到游程編碼結(jié)果， 再進(jìn)行游程譯碼， 得到原符號序列。 第二組符號序列編碼譯碼過程相同。5. 設(shè)計(jì)體會游程編碼相對簡單， 首先計(jì)算每次連續(xù)相同字符的個數(shù)， 然后將每次連續(xù)相同的字符及 個數(shù)保存起來， 再使用霍夫曼編碼。 霍夫曼編碼用概率匹配方法進(jìn)行信源編碼， 有兩個明顯 的特點(diǎn)： 一是霍夫曼碼的編碼方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長嗎，充分利用了短碼； 二是縮減信源的最后兩個碼字總是最后一位不同， 從而保證霍夫曼編 碼是即時(shí)碼。 完成哈夫曼的編碼首先建立哈夫曼樹， 定義當(dāng)前節(jié)點(diǎn)的字符， 當(dāng)前節(jié)點(diǎn)的左子、 右子和父親指針

20、， 之后對所有字符根據(jù)權(quán)重進(jìn)行編碼 （先在所有可能出現(xiàn)的字符中篩選出當(dāng) 前權(quán)重最小的兩個字符，將這兩個字符分別作為新節(jié)點(diǎn)的左子和右子建立一個小的二叉樹， 并將兩個字符的權(quán)重之和賦值給新節(jié)點(diǎn)， 將新二叉樹放入篩選字符中， 再將篩選過的兩個字 符從篩選列表中淘汰掉。 依次對列表中剩下的字符進(jìn)行權(quán)重最小的篩選，直到根節(jié)點(diǎn)） ，最 后再對文件內(nèi)容進(jìn)行編碼。三、算術(shù)編碼的編碼與譯碼1. 任務(wù)說明要求：輸入字符集為 a,b, 且 p（a）=1/4,p（2）=3/4. 對長度 L<=30 的序列進(jìn)行算術(shù)編碼 , 并進(jìn) 反向譯碼輸入文件 : ，含至少兩組輸入，每組為滿足要求的串輸出文件 : ，對每組輸入的編碼和譯碼結(jié)果2. 實(shí)現(xiàn)原理算術(shù)編碼用到兩個基本的參數(shù)： 符號的概率和它的編碼間隔。 信源符號的概率決定壓縮 編碼的效率， 也決定編碼過程中信源符號的間隔， 而這些間隔包含在 0到 1 之間。編碼過程 中的間隔決定了符號壓縮后的輸出。給定事件序列的算術(shù)編碼步驟如下：（1）編碼器在開始時(shí)將“當(dāng)前間隔” L ， H） 設(shè)置為0 ，1）。（2）對每一事件，編碼器按步驟（a）和（b）進(jìn)行處理(a) 編碼器將“當(dāng)前間隔”分為子間隔，每一個事件一個。(b) 一