實(shí)驗(yàn)二哈弗曼編碼

信息論與編碼技術(shù)實(shí)驗(yàn)報(bào)告姓名:學(xué)號(hào):專業(yè)班級(jí):學(xué)院:聯(lián)系方式:Huffman編碼軟件實(shí)現(xiàn)實(shí)驗(yàn)報(bào)告一、實(shí)驗(yàn)?zāi)康倪M(jìn)一步熟悉Huffman編碼過(guò)程；掌握Matlab程序的設(shè)計(jì)和調(diào)試技術(shù)。二、實(shí)驗(yàn)要求輸入：信源符號(hào)個(gè)數(shù)r、信源的概率分布P；輸出：每個(gè)信源符號(hào)對(duì)應(yīng)的Huffman編碼的碼字，編碼效率。三、實(shí)驗(yàn)原理：1.二進(jìn)制Huffman編碼的基本原理設(shè)信源S={ss,...s}，其中對(duì)應(yīng)的概率分布為P(s)={pp,...p}，則其編碼步1,2qi1,2q驟如下：將q個(gè)信源符號(hào)按概率遞減的方式排列。用0、1碼符號(hào)分別表示概率最小的兩個(gè)信源符號(hào)，并將這兩個(gè)概率最小的信源符號(hào)合并成一個(gè)新的符號(hào)，從而的得到的只含q-1個(gè)符號(hào)的新信源，稱為S信源的縮減信源S1將縮減信源s中的符號(hào)仍按概率大小以遞減次序排列，在將其最后兩個(gè)概率1最小的符號(hào)合并成一個(gè)符號(hào)，并分別用0、1碼符號(hào)表示，這樣由形成了由q-2個(gè)符號(hào)構(gòu)成的縮減信源s2重復(fù)(2)(3)兩步驟，直至縮減信源只剩下兩個(gè)符號(hào)為止，將這最后兩個(gè)符號(hào)分別用0、1碼字表示。從最后一級(jí)縮減信源開(kāi)始，向前返回，沿信源縮減過(guò)程的反方向取出所編的碼元，得出各信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即為對(duì)應(yīng)信源符號(hào)的碼字。2.二進(jìn)制Huffman編碼程序設(shè)計(jì)的原理(編碼步驟)(1)程序的輸入：以一維數(shù)組的形式輸入要進(jìn)行Huffman編碼的信源符號(hào)的概率，在運(yùn)行該程序前，顯示文字提示信息，提示所要輸入的概率矢量；然后對(duì)輸入的概率矢量進(jìn)行合法性判斷，原則為：如果概率矢量中存在小于0的項(xiàng)，則輸入不合法，提示重新輸入；如果概率矢量的求和大于1，則輸入也不合法，提示重新輸入。(2)Huffman編碼具體實(shí)現(xiàn)原理：<1>在輸入的概率矩陣p正確的前提條件下，對(duì)p進(jìn)行排序，并用矩陣L記錄p排序之前各元素的順序，然后將排序后的概率數(shù)組p的前兩項(xiàng)，即概率最小的兩個(gè)數(shù)加和，得到新的一組概率序列，重復(fù)以上過(guò)程，最后得到一個(gè)記錄概率加和過(guò)程的矩陣p以及每次排序之前概率順序的矩陣a。<2>新生成一個(gè)n-1行n列，并且每個(gè)元素含有n個(gè)字符的空白矩陣，然后進(jìn)行Huffman編碼：將c矩陣的第n-1行的第一和第二個(gè)元素分別令為0和1(表示在編碼時(shí)，根節(jié)點(diǎn)之下的概率較小的元素后補(bǔ)0，概率較大的元素后補(bǔ)1，后面的編碼都遵守這個(gè)原則)然后對(duì)n-i-1的第一、二個(gè)元素進(jìn)行編碼，首先在矩陣a中第n-i行找到值為1所在的位置，然后在c矩陣中第n-i行中找到對(duì)應(yīng)位置的編碼(該編碼即為第n-i-1行第一、二個(gè)元素的根節(jié)點(diǎn))，則矩陣c的第n-i行的第一、二個(gè)元素的n-1的字符為以上求得的編碼值，根據(jù)之前的規(guī)則，第一個(gè)元素最后補(bǔ)0，第二個(gè)元素最后補(bǔ)1，則完成該行的第一二個(gè)元素的編碼，最后將該行的其他元素按照“矩陣c中第n-i行第j+1列的值等于對(duì)應(yīng)于a矩陣中第n-i+1行中值為j+1的前面一個(gè)元素的位置在c矩陣中的編碼值”的原則進(jìn)行賦值，重復(fù)以上過(guò)程即可完成Huffman編碼。<3>計(jì)算信源熵和平均碼長(zhǎng)，其比值即為編碼密碼效率。部分偽代碼(算法知識(shí))：節(jié)點(diǎn)信息結(jié)構(gòu)體structHuffNode{intweight;〃信源符號(hào)的概率intparent;intlchild;intrchild;};算法voidHuffman(intweight[],intn,HuffNodehn[],HuffCodehc[]){for(i=0;i!=2*n-1;++i)//createHuffmanNode,step1{}for(i=0;i!=n-1;++i)//createHuffmanNode,step2{for(j=0;j!=n+i;j++){if(hn[j].weight<min1&&hn[j].parent==0){}elseif(hn[j].weight<min2&&hn[j].parent==0){}else;}}在此逆序存儲(chǔ)Huffman編碼inttemp[maxlen];for(i=0;i!=n;++i){intparent=hn[i].parent;while(hn[child].parent!=0){}Huffman編碼方法的特征★它是一種分組碼，各個(gè)信源符號(hào)都被映射成一組固定次序的馬符號(hào)?！锼且环N唯一可解的碼，任何符號(hào)序列只能以一種方式譯碼?！锼且环N即時(shí)碼：由于代表信源符號(hào)的節(jié)點(diǎn)都是終端節(jié)點(diǎn)，因此其編碼不可能是其他終端節(jié)點(diǎn)對(duì)應(yīng)的編碼的前綴，即Huffman編碼所得的碼字為即時(shí)碼?！颒uffman碼的譯碼：對(duì)接受到的哈弗曼碼序列可通過(guò)從左到右檢查各個(gè)符號(hào)進(jìn)行譯碼?！锕蚵幋a過(guò)程中，當(dāng)縮減信源的概率分布重新排列時(shí)，應(yīng)使合并得到的概率和盡量處于高的位置，這樣可使合并的元素重復(fù)編碼次數(shù)減少，使短碼得到充分利用。四、實(shí)驗(yàn)內(nèi)容對(duì)離散無(wú)記憶信源5=*'S3S4'進(jìn)行Huffman編碼。P(s)0.40.20.20.10.1—i—II——畫出Huffman編碼的程序流程圖(如下)2.寫出Huffman編碼的源程序(如下)p=input('pleaseinputanumber:')n=length(p);fori=1:nifp(i)<0fprintf('\nTheprobabilitiesinhuffmancannotlessthan0!\n');p=input('pleaseinputanumber:，)%若輸入的概率數(shù)組中有小于0的值，則重新輸入概率數(shù)組endendifabs(sum(p)-1)>0fprintf('\nThesumoftheprobabilitiesinhuffmancanmorethan1!\n');p=input('pleaseinputanumber：')%如果輸入的概率數(shù)組總和大于1,則重新輸入概率數(shù)組endq=p;a=zeros(n-1,n);%生成一個(gè)n-1行n列的數(shù)組fori=1:n-1[q,l]=sort(q)%對(duì)概率數(shù)組q進(jìn)行從小至大的排序，并且用l數(shù)組返回一個(gè)數(shù)組，該數(shù)組表示概率數(shù)組q排序前的順序編號(hào)a(i,:)=[l(1:n-i+1),zeros(1,i-1)]%由數(shù)組l構(gòu)建一個(gè)矩陣，該矩陣表明概率合并時(shí)的順序，用于后面的編碼q=[q⑴+q(2),q(3:n),1上％將排序后的概率數(shù)組q的前兩項(xiàng)，即概率最小的兩個(gè)數(shù)加和，得到新的一組概率序列endc(i,l.n*n)=blanks(n*n),%生成一個(gè)n-1行n列，并且每個(gè)元素的的長(zhǎng)度為n的空白數(shù)組，c矩陣用于進(jìn)行huffman編碼，并且在編碼中與a矩陣有一定的對(duì)應(yīng)關(guān)系endc(n-1,n)=0；%由于a矩陣的第n-1行的前兩個(gè)元素為進(jìn)行huffman編碼加和運(yùn)算時(shí)所得的最后兩個(gè)概率，因此其值為0或1，在編碼時(shí)設(shè)第n-1行的第一個(gè)空白字符為0,第二個(gè)空白字符1。c(n-1,2*n)='1';fori=2:n-1c(n-i,1:n-1)=c(n-i+1,n*(find(a(n-i+1,:)==1))-(n-2):n*(find(a(n-i+1,:)==1)))%矩陣c的第n-i的第一個(gè)元素的n-1的字符賦值為對(duì)應(yīng)于a矩陣中第n-i+1行中值為1的位置在c矩陣中的編碼值c(n-i,n)='0'%根據(jù)之前的規(guī)則，在分支的第一個(gè)元素最后補(bǔ)0c(n-i,n+1:2*n-1)=c(n-i,1:n-1)%矩陣c的第n-i的第二個(gè)元素的n-1的字符與第n-i行的第一個(gè)元素的前n-1個(gè)符號(hào)相同，因?yàn)槠涓?jié)點(diǎn)相同c(n-i,2*n)=1%根據(jù)之前的規(guī)則，在分支的第一個(gè)元素最后補(bǔ)1forj=1:i-1c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(a(n-i+1,:)==j+1)-1)+1:n*find(a(n-i+1,:)==j+1))%矩陣c中第n-i行第j+1列的值等于對(duì)應(yīng)于a矩陣中，第n-i+1行中值為j+1的前面一個(gè)元素的位置在c矩陣中的編碼值endend%完成huffman碼字的分配fori=1:nendh(i,1:n)=c(1,n*(find(a(1,:)==i)-1)+1:find(a(1,:)==i)*n)%用h表示最后的huffman編碼，矩陣h的第i行的元素對(duì)應(yīng)于矩陣c的第一行的第i個(gè)元素ll(i)=length(find(abs(h(i，:))~=32))%計(jì)算每一個(gè)huffman編碼的長(zhǎng)度endl=sum(p.*ll);%計(jì)算平均碼長(zhǎng)fprintf('\nhuffmancode:\n');hhh=sum(p.*(-log2(p)));%計(jì)算信源熵fprintf('\nthehuffmaneffciency:\n');t=hh/l3.運(yùn)行源程序后，實(shí)驗(yàn)過(guò)程中的測(cè)試結(jié)果p=0.40000.20000.20000.10000.1000q=0.10000.10000.20000.20000.4000q=0.20000.20000.20000.40001.0000q=0.20000.40000.40001.00001.0000q=0.40000.60001.00001.00001.0000ll=13244huffmancode:h=01111011001101thehuffmaneffciency:t=0.96454.實(shí)驗(yàn)結(jié)果分析信源(sssss)的碼字長(zhǎng)度分別為13244；12345所對(duì)應(yīng)的碼字為01111011001101；編碼效率為0.9645。五、總結(jié)實(shí)驗(yàn)過(guò)程遇到的問(wèn)題及解決方法在實(shí)驗(yàn)過(guò)程中，遇到以下幾個(gè)問(wèn)題：信源縮減不知怎么表示；不知如何運(yùn)用矩