信息論課程設計報告

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

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

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

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

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

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

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

8、“ 1”游程。它們的長度分 別稱為游程長度 L(0) 和 L(l) ?！?0”游程和“ l ”游程總是交替出現的。如 果規(guī)定二元序列是以“ 0”開始，第一個游程是“ 0”游程，第二個必為“ 1”游 程，第三個又是“ 0”游程等等。對于隨機的二元序列，各游程長度將是隨 機變量，其取值可為 1，2，3， ?，直到無限。Huffman碼：(1 )將q個信源符號按概率分布 P (si )的大小，以遞減次序排列起來，設 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。然后從最后一級縮減信源開始， 依編碼路徑由后向前返回， 就得出各信源符號所對應的碼符號序列，即得對應的碼字。Huffman 碼參考算法偽代碼：if q=2 thenReturns0

10、0,s11Else降序排序 pi縮減信源：創(chuàng)建一個符號s'以取代Sq 1,Sq 2，其概率P' Pq 2 Pq 1遞歸調用Huffman算法以得到恥3，$ 3,s的編碼WoW.Wq 3,w (相應的概率分 布為 p0， p1 ,，pq 3 , p)ReturnSoWo,S,Wi,.,Sq3Wq3,Sq2w'0,Sq1w'1End if3. 實現源碼#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相等的下標 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 編碼內存 */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);/*產生 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);/*葉子結點的編碼 */printf(” *NodeCode*n" ); /

16、* 打印葉子結點的編碼 */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. 運行結果輸入文件：結果分析：對 n 個符號序列進行游程編碼后輸出“ 0”游程長度和“ 1”游程長度，再對 結果進行霍夫曼編碼， 得到游程編碼

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

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