信息論實習(xí)報告

信息論實習(xí)報告香農(nóng)編碼1.程序設(shè)計題目：對某一個信源Y用香農(nóng)編碼編成二元變長唯一可譯碼。例如：取信源Y=(y0,y1,y2,y3,y4,y5,y6,y7,y8).相應(yīng)的概率為P=（0.49,0.14,0.14,0.07,0.07,0.04,0.02,0.02,0.01）。2.程序設(shè)計方法：第一步：按概率從大到小的順序輸出信源Y。第二步：利用公式Li=「-㏒p(yi)」(「」取上整)確定碼長。第三步：為編成唯一可譯碼求p（yi）的累加概率P[i]。第四步：把P[i]化為二進制數(shù)，乘2取整。第五步：根據(jù)碼長Li確定第四步中for循環(huán)的次數(shù)，最終得到碼字。3.程序的設(shè)計中遇到的問題及解決辦法：本程序設(shè)計最關(guān)鍵在于碼長公式的C語言編碼實現(xiàn)和如何在編程中實現(xiàn)小數(shù)向二進制數(shù)的轉(zhuǎn)換。在一開始意識到-㏒p(yi)=-㏒p(yi)/㏒(2)的問題后，我在編程中首先遇到的問題是如何取整的問題。一開始因為對C語言編程的不熟悉在這句代碼中沒有對int加括號。4.程序中的主要函數(shù)：（1）主函數(shù)main().且香農(nóng)編碼的實現(xiàn)比較簡單所以沒有用到子函數(shù)。（2）求碼長的編程實現(xiàn)：（3）利用累加概率P[i]求的碼字的編程實現(xiàn)：5.流程圖：6.源程序如下：7.運行結(jié)果截圖：二、費諾碼1.程序設(shè)計題目：對某一個信源X用香農(nóng)編碼編成二元變長唯一可譯碼。例如：取信源X=(x0,x1,x2,x3,x4,x5,x6,x7,x8).相應(yīng)的概率為P=（0.14,0.49,0.07,0.04,0.14,0.02,0.07,0.02,0.01）。2.程序設(shè)計方法：第一步：將信源X發(fā)出的n個消息符號按其概率的遞減次序依次排列。第二步：將依次排列的信源符號依概率分成兩組，使兩個組的概率和近于相同，并對各組賦予一個二進制代碼符號“0”和“1”（編m進制碼就分成m組）。第三步：將每一個大組的信源符號進一步再分成兩組，使劃分后的兩個組的概率和近于相同，并又分別賦予兩組一個二進制符號“0”和“1”第四步：如此重復(fù)，直至每組值只剩下一個信源符號為止第五步：信源符號所對應(yīng)的碼符號序列即為費諾碼3.程序的設(shè)計中遇到的問題及解決辦法：在進行費諾編碼的過程中首先遇到的問題是如何進行分組，利用變量i從的值把信源符號分為兩組，前i個信源符號序列為一組進行概率求和s1,剩下的信源符號為一組進行概率求和s2。當(dāng)s1和s2之差的絕對值為最小的時候確定分組。前i個信源符號相應(yīng)的碼字在這一列上賦值為0，剩下的信源符號相應(yīng)的碼字在這一列上賦值為1。在進行費諾編碼的過程中遇到的最大的問題就是遞歸，在最初分為兩組后，調(diào)用子函數(shù)bianma（），確定第一組每個信源符號對應(yīng)的二元變長碼字第一位上是“0”，并且確定第二組每個信源符號對應(yīng)的二元變長碼字第一位上是“1”。再對兩個大組分別進行分組，重復(fù)前面的步驟，直到每一組只剩一個信源符號進行賦值后，輸出每個信源符號對應(yīng)的二元符號序列。從而得到相應(yīng)的費諾碼。4.程序中的主要函數(shù)：main()本函數(shù)實現(xiàn)的主要功能有：實現(xiàn)需要編碼符號的個數(shù)和相應(yīng)概率的的輸入；對輸入的概率進行降序排序；調(diào)用bianma（）函數(shù)對排序后的概率進行編碼并輸出編碼結(jié)果。bianma（）本函數(shù)實現(xiàn)對相應(yīng)的信源符號的分組，并且根據(jù)分組得到相應(yīng)的二元變長的編碼符號序列，在此函數(shù)中還會遞歸的用到bianma（）本身，直到每組只剩下一個信源符號，從而完成編碼。5.源程序運行結(jié)果截圖：6.流程圖：7.源程序如下：尾隨后綴的唯一可譯碼程序設(shè)計題目：利用Sardinas-Patterson算法將碼C中所有可能的尾隨后綴組成一個集合F，當(dāng)且僅當(dāng)集合F中沒有包含任一碼字，便可判斷碼C為唯一可譯碼。反之，碼C不是唯一可譯碼。程序設(shè)計思想方法：A.A.Sardinas和G.W.Patterson于1957年提出下述算法用于判斷碼C的唯一可譯性．此算法的原理如下所示：其中Ai,Bi都是碼字?？芍?dāng)且僅當(dāng)某個有限長的碼符號序列能譯成兩種不同的碼字序列時，此碼不是唯一可譯碼，此時B1一定是A1的前綴，而A1的尾隨后綴一定是另一碼字B2的前綴；而B2的尾隨后綴又是其他碼字的前綴．最后，碼符號序列的尾部一定是一個碼字。設(shè)C為碼字集合，按以下步驟構(gòu)造此碼的尾隨后綴集合F：(1)考查C中所有的碼字，若Wi是Wj的前綴，則將相應(yīng)的后綴作為一個尾隨后綴放入集合F0中；(2)考查C和Fi兩個集合，若Wj∈C是Wi∈Fi的前綴或Wi∈Fi是Wj∈C的前綴，則將相應(yīng)的后綴作為尾隨后綴碼放入集合Fi+1中；(3)F=∪Fi即為碼C的尾隨后綴集合；(4)若F中出現(xiàn)了C中的元素，則算法終止，返回假(C不是唯一可譯碼)；否則若F中沒有出現(xiàn)新的元素，則返回真。程序中的主要函數(shù):(1)main()本函數(shù)實現(xiàn)的主要功能有：實現(xiàn)需要碼字的個數(shù)和碼字集合的輸入；碼字集合本身是否含有重復(fù)碼字的檢驗，調(diào)用houzhui（）函數(shù)后綴集合F[i]。判斷F[i]和源碼字集合是否有相同元素，從而判斷原碼字集合是否為唯一可譯碼。(2)houzhui（）本函數(shù)實現(xiàn)對兩個碼字是否存在后綴的判斷，并且生成F[i]中的元素。4.流程圖：5.源程序如下：6.程序的設(shè)計中遇到的問題及解決辦法：在設(shè)計本程序的過程中遇到的最大的問題是尾隨后綴的