信息論實(shí)習(xí)報(bào)告

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