信息編碼實(shí)驗(yàn)

《信息論與編碼》實(shí)驗(yàn)指導(dǎo)書目錄TOC\o"1-5"\h\z實(shí)驗(yàn)一 信息熵與圖像熵計(jì)算 1實(shí)驗(yàn)二 Huffman編碼實(shí)驗(yàn) 6實(shí)驗(yàn)三 算術(shù)編碼實(shí)驗(yàn) 11實(shí)驗(yàn)四 CRC校驗(yàn)編碼實(shí)驗(yàn) 17-1-實(shí)驗(yàn)一信息熵與圖像熵計(jì)算(2學(xué)時(shí))一、實(shí)驗(yàn)?zāi)康?．復(fù)習(xí)MATLAB的基本命令，熟悉MATLAB下的基本函數(shù)。2．復(fù)習(xí)信息熵基本定義,能夠自學(xué)圖像熵定義和基本概念。二、實(shí)驗(yàn)內(nèi)容1．能夠?qū)懗鯩ATLAB源代碼，求信源的信息熵。2．根據(jù)圖像熵基本知識(shí)，綜合設(shè)計(jì)出MATLAB程序，求出給定圖像的圖像熵三、實(shí)驗(yàn)儀器、設(shè)備1?計(jì)算機(jī)一系統(tǒng)最低配置256M內(nèi)存、P4CPU。2．Matlab仿真軟件－7.0/7.1/2006a等版本Matlab軟件。四、實(shí)驗(yàn)原理MATLAB中數(shù)據(jù)類型、矩陣運(yùn)算、圖像文件輸入與輸出知識(shí)復(fù)習(xí)。利用信息論中信息熵概念，求出任意一個(gè)離散信源的熵(平均自信息量)。自信息是一個(gè)隨機(jī)變量,它是指某一信源發(fā)出某一消息所含有的信息量。所發(fā)出的消息不同，它們所含有的信息量也就不同。任何一個(gè)消息的自信息量都代表不了信源所包含的平均自信息量。不能作為整個(gè)信源的信息測(cè)度，因此定義自信息量的數(shù)學(xué)期望為信源的平均自信息量：1()1()[log]()log()iniipaiHEpEXpa===信息熵的意義：信源的信息熵H是從整個(gè)信源的統(tǒng)計(jì)特性來考慮的。它是從平均意義上來表征信源的總體特性的。對(duì)于某特定的信源，其信息熵只有一個(gè)。不同的信源因統(tǒng)計(jì)特性不同，其熵也不同。學(xué)習(xí)圖像熵基本概念，能夠求出圖像一維熵和二維熵。圖像熵是一種特征的統(tǒng)計(jì)形式，它反映了圖像中平均信息量的多少。圖像的一維熵表示圖像中灰度分布的聚集特征所包含的信息量，令Pi表示圖像中灰度值為i的像素所占的比例，則定義灰度圖像的一元灰度熵為：2550logiiipp==YH-2-圖像的一維熵可以表示圖像灰度分布的聚集特征，卻不能反映圖像灰度分布的空間特征，為了表征這種空間特征，可以在一維熵的基礎(chǔ)上引入能夠反映灰度分布空間特征的特征量來組成圖像的二維熵。選擇圖像的鄰域灰度均值作為灰度分布的空間特征量，與圖像的像素灰度組成特征二元組，記為(i,j)，其中i表示像素的灰度值(0<=i<=255)，j表示鄰域灰度(0<=j<=255),2(,)/ijpfijN=上式能反應(yīng)某像素位置上的灰度值與其周圍像素灰度分布的綜合特征，其中f(i,j)為特征二元組(i,j)出現(xiàn)的頻數(shù)，N為圖像的尺度，定義離散的圖像二維熵為：2550logijijipp==YH構(gòu)造的圖像二維熵可以在圖像所包含信息量的前提下，突出反映圖像中像素位置的灰度信息和像素鄰域內(nèi)灰度分布的綜合特征.五、實(shí)驗(yàn)步驟1．求解信息熵過程：輸入一個(gè)離散信源，并檢查該信源是否是完備集。去除信源中符號(hào)分布概率為零的元素。根據(jù)平均信息量公式，求出離散信源的熵。2．圖像熵計(jì)算過程：輸入一幅圖像，并將其轉(zhuǎn)換成灰度圖像。統(tǒng)計(jì)出圖像中每個(gè)灰度階象素概率。統(tǒng)計(jì)出圖像中相鄰兩象素的灰度階聯(lián)合分布矩陣。根據(jù)圖像熵和二階熵公式，計(jì)算出一幅圖像的熵。六、實(shí)驗(yàn)報(bào)告要求1．按照本節(jié)內(nèi)容后實(shí)驗(yàn)報(bào)告形式書寫。2．實(shí)驗(yàn)總結(jié)和心得要詳細(xì)，可以根據(jù)自己實(shí)驗(yàn)情況，寫出建議。七、實(shí)驗(yàn)注意事項(xiàng)1．Matlab語言課下多復(fù)習(xí)，盡量采用模塊化編程方法，通過函數(shù)調(diào)用形式運(yùn)行程序。2．仔細(xì)理解、體會(huì)圖像熵的概念，能夠?qū)⑵渎?lián)合熵的概念理解透徹。-3-八、思考題舉例說明圖像熵、信息熵在現(xiàn)實(shí)中有何實(shí)踐指導(dǎo)意義？附1：信息熵計(jì)算源代碼函數(shù)源程序CalEntropy.m%InformationShannonEntropycalculation%jma@,22/08/2007 %array:DiscreteProbabilitiesSet%H:OutputShannonEntropyfunctionH=CalEntropy(array)%Vectornumbernum=length(array);%Checkprobabilitiessumto1:ifabs(sum(array)-1)>.00001,error('Probablitiesdon''tsumto1.')end%%Removeanyzeroprobabilities%%zeroProbs=find(array<eps);if~isempty(zeroProbs),array(zeroProbs)=[];%disp('Removedzeroornegativeprobabilities.')End%%ComputetheentropyH=-sum(array.*log2(array));%單位bit/symbol附2：圖像熵計(jì)算源代碼函數(shù)源程序ImgEntropy.m%%%%%%%ImageEntropycalculation%%%%%%%%%jma@,22/08/2007%img:inputimagedata%H1,H2 :Output1&2orderentropyfunction[H1,H2]=ImgEntropy(img)%colorimagetransformationI=imread(img);img=rgb2gray(I);imview(I),imview(img);-4-[ix,iy]=size(img);%computeprobsforeachscalelevelinimageP1=imhist(img)/(ix*iy);temp=double(img);%fortheindexofimagepiexltemp=[temp,temp(:,1)];%correlationprobmatrixbetween[0...255]graylevels CoefficientMat=zeros(256,256);forx=1:ixfory=1:iyi=temp(x,y);j=temp(x,y+1);CoefficientMat(i+1,j+1)=CoefficientMat(i+1,j+1)+1; endend%computetheprobofmatrixP2=CoefficientMat./(ix*iy);H1=0;H2=0;fori=1:256%calculate1ordimageentropyifP1(i)~=0H1=H1-P1(i)*log2(P1(i));end%compute2ordimageentropyforj=1:256ifP2(i,j)~=0H2=H2-P2(i,j)*log2(P2(i,j));endendendH2=H2/2; %meanentropy/symbolsprintf('1ordimageentropyis:%d',H1)sprintf('2ordimageentropyis:%d',H2)函數(shù)調(diào)用實(shí)例test.m-5%InformationTheoryexperimenttestingfile%jma@,22/08/2007%testingDiscreteShannonEntropy%discreteprobabilitiessetprobSet=[0.150.25];%callCalEntropyfunctionH=CalEntropy(probSet);sprintf('ShannonEntropyis:%d',H)%calculatetheImageentropy[H1,H2]=ImgEntropy('lena.jpg');附3：實(shí)驗(yàn)報(bào)告固定樣式實(shí)驗(yàn)報(bào)告班級(jí)：姓名：學(xué)號(hào)：組別：同組人：課程名稱：實(shí)驗(yàn)室：實(shí)驗(yàn)時(shí)間：(使用實(shí)驗(yàn)報(bào)告紙的，以上內(nèi)容可按照實(shí)驗(yàn)報(bào)告紙格式填寫)實(shí)驗(yàn)一信息熵與圖像熵計(jì)算一、實(shí)驗(yàn)?zāi)康模憾?shí)驗(yàn)內(nèi)容與原理：三、實(shí)驗(yàn)器材(設(shè)備、元器件、軟件工具、平臺(tái))：四、實(shí)驗(yàn)步驟：五、實(shí)驗(yàn)數(shù)據(jù)及結(jié)果分析：六、實(shí)驗(yàn)結(jié)論：七、思考題八、其他：實(shí)驗(yàn)總結(jié)、心得體會(huì)及對(duì)本實(shí)驗(yàn)方法、手段及過程的改進(jìn)建議等。-6-實(shí)驗(yàn)二Huffman編碼(2學(xué)時(shí))一、實(shí)驗(yàn)?zāi)康膹?fù)習(xí)C++程序基本編寫方法，熟悉VC編程環(huán)境。2．會(huì)用VC調(diào)試Huffman編碼程序。二、實(shí)驗(yàn)內(nèi)容復(fù)習(xí)C++代碼基本語法(結(jié)構(gòu)體、樹等數(shù)據(jù)結(jié)構(gòu)定義)根據(jù)Huffman編碼源代碼，學(xué)習(xí)算法實(shí)現(xiàn)流程，培養(yǎng)自己動(dòng)手能力，在C++編譯器下按步調(diào)試跟蹤算法。三、實(shí)驗(yàn)儀器、設(shè)備1.計(jì)算機(jī)一系統(tǒng)最低配置256M內(nèi)存、P4CPU。2.C++編程軟件一VisualC++7.0(MicrosoftVisualStudio2003) VisualC++8.0(MicrosoftVisualStudio2005)四、實(shí)驗(yàn)原理Huffman編碼原理：①將信源符號(hào)按概率從大到小的順序排列，令p(x1)三p(x2)三…三p(xn)②給兩個(gè)概率最小的信源符號(hào)p(xn-1)和p(xn)各分配一個(gè)碼位“0”和“1”，將這兩個(gè)信源符號(hào)合并成一個(gè)新符號(hào)，并用這兩個(gè)最小的概率之和作為新符號(hào)的概率，結(jié)果得到一個(gè)只包含(n—1)個(gè)信源符號(hào)的新信源。稱為信源的第一次縮減信源，用S1表示。③將縮減信源S1的符號(hào)仍按概率從大到小順序排列，重復(fù)步驟2，得到只含(n—2)個(gè)符號(hào)的縮減信源S2。④重復(fù)上述步驟，直至縮減信源只剩兩個(gè)符號(hào)為止，此時(shí)所剩兩個(gè)符號(hào)的概率之和必為1。然后從最后一級(jí)縮減信源開始，依編碼路徑向前返回，就得到各信源符號(hào)所對(duì)應(yīng)的碼字。Huffman樹的編碼原理：步驟1：將各個(gè)符號(hào)及其出現(xiàn)頻率分別作為不同的小二叉樹(目前每棵樹只有根節(jié)點(diǎn))步驟2：在步驟1中得到的樹林里找出頻率值最小的兩棵樹，將他們分別作為-7-左、右子樹連成一棵大一些的二叉樹，該二叉樹的頻率值設(shè)為兩棵子樹頻率值之和。步驟3：對(duì)上面得到的樹林重復(fù)步驟2的做法，直到所有符號(hào)都連入樹中為止。五、 實(shí)驗(yàn)步驟VC環(huán)境下，建一個(gè)C++控制臺(tái)應(yīng)用程序，并把源代碼考到該程序目錄下。項(xiàng)目文件中含有一個(gè)預(yù)編譯頭文件，一個(gè)主函數(shù)入口文件和Huffman編碼算法文件。在入口文件中，輸入任一個(gè)離散信源進(jìn)行編碼調(diào)試。設(shè)置好程序斷點(diǎn)，仔細(xì)分析Huffman樹每步的建立過程。輸出離散信源中每個(gè)符號(hào)的Huffman編碼，并與手工運(yùn)算的結(jié)果進(jìn)行比較。六、 實(shí)驗(yàn)報(bào)告要求按照實(shí)驗(yàn)一附3中實(shí)驗(yàn)報(bào)告樣式書寫本次實(shí)驗(yàn)報(bào)告。總結(jié)C++語言學(xué)習(xí)心得，并結(jié)合Huffman編碼實(shí)驗(yàn)總結(jié)自己的得失，指出今后自己要練習(xí)改進(jìn)之處。根據(jù)自己實(shí)驗(yàn)情況，對(duì)本實(shí)驗(yàn)寫出建議。七、實(shí)驗(yàn)注意事項(xiàng)指針數(shù)據(jù)結(jié)構(gòu)定義typedefstruct{unsignedlongweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;//指向存放數(shù)組指針的數(shù)組即二維數(shù)組二叉樹生成操作放在數(shù)組中(節(jié)點(diǎn)n和數(shù)組大小m關(guān)系為：m=2*n-1)。每次在樹中找到兩顆最小子樹，其函數(shù)為Select(HuffmanTreeHT,intn,int*s1,int*s2)，實(shí)際實(shí)現(xiàn)的是在數(shù)組中找到最小兩個(gè)元素。另外注意C++的數(shù)組起始索引是0，Matlab起始索引是1；程序中為了方便從1開始索引數(shù)組，HT[0].weight的大小設(shè)為OxffffffffL。為了輸出二進(jìn)制Huffman碼，程序最后對(duì)每個(gè)符號(hào)進(jìn)行深度優(yōu)先搜索，得到該符號(hào)的二進(jìn)制字符，然后進(jìn)行字符串拷貝，直到最后輸出。-8-八、思考題根據(jù)Huffman算法的C++源程序，試著寫出Huffman編碼的Matlab程序？附1：Huffman編碼源代碼源代碼列表：stdafx.h Huffman.cpp預(yù)編譯頭文件：stdafx.h以下代碼#pragmaonce#include<iostream>#include<tchar.h>#include<stdio.h>#include<string.h>#include<stdlib.h>控制臺(tái)應(yīng)用CPP文件：Huffman.cpp#include"stdafx.h"typedefstruct{unsignedlongweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;HuffmanCodeHC;voidSelect(HuffmanTreeHT,intn,int*s1,int*s2);voidHuffmanCoding(unsignedlong*w,intn){inti;if(n<=1)return;intm=2*n-1;HuffmanTreep;HuffmanTreeHT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));memset(HT,0,sizeof(HTNode)*(m+1));for(p=HT,i=1;i<=n;++i) { ++p; ++w;p->weight=*w;}-9-ints1,s2;for(i=n+1;i<=m;++i){Select(HT,i-1,&s1,&s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}HC=(HuffmanCode)malloc((n+1)*sizeof(char*));char*cd=(char*)malloc(n*sizeof(char));cd[n-1]=0;intstart;unsignedlongf;for(i=1;i<=n;++i) {start=n-1;intc;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){if(HT[f].lchild==c) cd[--start]='0';else cd[--start]='1';}HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}free(HT);//free(cd);}voidSelect(HuffmanTreeHT,intn,int*s1,int*s2){inti;HT[0].weight=(unsignedlong)(-1l);*s1=*s2=0;for(i=1;i<=n;i++)if(HT[i].parent==0){if(HT[i].weight<HT[*s1].weight) { *s2=*s1; *s1=i;-10} elseif(HT[i].weight<HT[*s2].weight) { *s2=i; } }}//函數(shù)測(cè)試實(shí)例int _tmain(intargc,_TCHAR*argv[]){ const intLEN=3; int i;unsignedlongweight[LEN+1];weight[0]=0;weight[1]=1;weight[2]=7;weight[3]=2;HuffmanCoding(weight,LEN);for(i=1;i<=LEN;i++)printf("%s\n",HC[i]);return0;}//EndofHuffman.cpp-11-實(shí)驗(yàn)三算術(shù)編碼(2學(xué)時(shí))一、實(shí)驗(yàn)?zāi)康倪M(jìn)一步學(xué)習(xí)C++語言概念和熟悉VC編程環(huán)境。2．學(xué)習(xí)算術(shù)編碼基本流程,學(xué)會(huì)調(diào)試算術(shù)編碼程序。根據(jù)給出資料，自學(xué)自適應(yīng)0階算術(shù)編、解碼方法。二、實(shí)驗(yàn)內(nèi)容復(fù)習(xí)C++代碼基本語法(類和虛函數(shù)等面向?qū)ο髷?shù)據(jù)結(jié)構(gòu)定義)2．根據(jù)實(shí)驗(yàn)提供的源代碼，學(xué)習(xí)算術(shù)編碼實(shí)現(xiàn)流程，培養(yǎng)實(shí)際動(dòng)手調(diào)試能力和相應(yīng)的編程技巧。三、實(shí)驗(yàn)儀器、設(shè)備1.計(jì)算機(jī)一系統(tǒng)最低配置256M內(nèi)存、P4CPU。2.C++編程軟件一VisualC++7.0(MicrosoftVisualStudio2003) VisualC++8.0(MicrosoftVisualStudio2005)四、實(shí)驗(yàn)原理算術(shù)編碼基本原理是將編碼消息表示成實(shí)數(shù)0和1之間的一個(gè)間隔，消息越長(zhǎng)，編碼表示它的間隔就越小，表示這一間隔所需的二進(jìn)制位就越多。算術(shù)編碼用到兩個(gè)基本的參數(shù)：符號(hào)的概率和它的編碼間隔。信源符號(hào)的概率決定壓縮編碼的效率，也決定編碼過程中信源符號(hào)的間隔，而這些間隔包含在0到1之間。編碼過程中的間隔決定了符號(hào)壓縮后的輸出。首先借助下面一個(gè)簡(jiǎn)單的例子來闡釋算術(shù)編碼的基本原理?？紤]某條信息中可能出現(xiàn)的字符僅有abc三種，我們要壓縮保存的信息為bccb。在沒有開始?jí)嚎s進(jìn)程之前，假設(shè)對(duì)abc三者在信息中的出現(xiàn)概率一無所知(采用的是自適應(yīng)模型)，暫認(rèn)為三者的出現(xiàn)概率相等各為1/3，將0-1區(qū)間按照概率的比例分配給三個(gè)字符，即a從0.0000到0.3333，b從0.3333到0.6667，c從0.6667到1.0000。進(jìn)行第一個(gè)字符b編碼，b對(duì)應(yīng)的區(qū)間0.3333-0.6667。這時(shí)由于多了字符b，三個(gè)字符的概率分布變成：Pa=1/4,Pb=2/4,Pc=1/4。按照新的概率分布比例劃分0.3333-0.6667這一區(qū)間，-12-劃分的結(jié)果可以用圖形表示為：Pc=1/4+--0.6667|+--0.5834|Pb=2/4||||+--0.4167Pa=1/4|+--0.3333接著拿到字符C,現(xiàn)在要關(guān)注上步中得到的c的區(qū)間0.5834-0.6667。新添了c以后，三個(gè)字符的概率分布變成Pa=1/5，Pb=2/5，Pc=2/5。用這個(gè)概率分布劃分區(qū)間0.5834-0.6667：+--0.6667|Pc=2/5 |+--0.6334Pb=2/5Pb=2/5|+--0.6001Pa=1/5 |+--0.5834輸入下一個(gè)字符C,三個(gè)字符的概率分布為：Pa=1/6,Pb=2/6,Pc=3/6。接著來劃分c的區(qū)間0.6334-0.6667：-13+--0.6667||TOC\o"1-5"\h\zPc=3/6 ||+--0.6501|Pb=2/6 ||+--0.6390Pa=1/6 |+--0.6334輸入最后一個(gè)字符b,因?yàn)槭亲詈笠粋€(gè)字符，不用再做進(jìn)一步的劃分了，上一步中得到的b的區(qū)間為0.6390-0.6501,最后在這個(gè)區(qū)間內(nèi)隨便選擇一個(gè)容易變成二進(jìn)制的數(shù),例如0.64,將它變成二進(jìn)制0.1010001111,去掉前面沒有太多意義的0和小數(shù)點(diǎn),可以輸出1010001111,這就是信息被壓縮后的結(jié)果,由此完成了一次最簡(jiǎn)單的算術(shù)壓縮過程。如何解壓縮呢？那就更簡(jiǎn)單了。解壓縮之前仍然假定三個(gè)字符的概率相等。解壓縮時(shí)面對(duì)的是二進(jìn)制流1010001111,先在前面加上0和小數(shù)點(diǎn)把它變成小數(shù)0.1010001111,也就是十進(jìn)制0.64。這時(shí)我們發(fā)現(xiàn)0.64在分布圖中落入字符b的區(qū)間內(nèi)，立即輸出字符b,并得出三個(gè)字符新的概率分布。類似壓縮時(shí)采用的方法,我們按照新的概率分布劃分字符b的區(qū)間。在新的劃分中,我們發(fā)現(xiàn)0.64落入了字符c的區(qū)間，我們可以輸出字符c。同理，我們可以繼續(xù)輸出所有的字符，完成全部解壓縮過程。2．小數(shù)存儲(chǔ)方法如果信息內(nèi)容特別豐富，我們要輸出的小數(shù)將會(huì)很長(zhǎng)很長(zhǎng)，該如何在內(nèi)存中表示如此長(zhǎng)的小數(shù)呢？其實(shí)，沒有任何必要在內(nèi)存中存儲(chǔ)要輸出的整個(gè)小數(shù)。從上面的例子可以知道，在編碼的進(jìn)行中，會(huì)不斷地得到有關(guān)要輸出小數(shù)的各種信息。具體地講，當(dāng)我們將區(qū)間限定在0.6390-0.6501之間時(shí)，我們已經(jīng)知道要輸出的小-14-數(shù)第一位（十進(jìn)制）一定是6，那么我們完全可以將6從內(nèi)存中拿掉，接著在區(qū)間0.390-0.501之間繼續(xù)我們的壓縮進(jìn)程。內(nèi)存中始終不會(huì)有非常長(zhǎng)的小數(shù)存在。使用二進(jìn)制時(shí)也是一樣的，我們會(huì)隨著壓縮的進(jìn)行不斷決定下一個(gè)要輸出的二進(jìn)制位是0還是1，然后輸出該位并減小內(nèi)存中小數(shù)的長(zhǎng)度，具體可以參考E1/E2/E3放大原理，及它們之間關(guān)系的描述。3．靜態(tài)模型與自適應(yīng)模型靜態(tài)模型上面的簡(jiǎn)單例子采用的是自適應(yīng)模型，那么如何實(shí)現(xiàn)靜態(tài)模型呢？其實(shí)很簡(jiǎn)單。對(duì)信息bccb我們統(tǒng)計(jì)出其中只有兩個(gè)字符，概率分布為Pb=0.5，Pc=0.5。在壓縮過程中不必再更新此概率分布，每次對(duì)區(qū)間的劃分都依照此分布即可，對(duì)上例也就是每次都平分區(qū)間。這樣，壓縮過程可以簡(jiǎn)單表示為輸出區(qū)間的下限輸出區(qū)間的上限壓縮前0.01.0輸入b0.00.5輸入c0.250.5輸入c0.3750.5輸入b0.3750.4375最后的輸出區(qū)間在0.375-0.4375之間，甚至連一個(gè)十進(jìn)制位都沒有確定，也就是說，整個(gè)信息根本用不了一個(gè)十進(jìn)制位。自適應(yīng)模型既然使用靜態(tài)模型可以很好地接近熵值，為什么還要采用自適應(yīng)模型呢？要知道，靜態(tài)模型無法適應(yīng)信息多樣性，例如，上面得出的概率分布沒法在所有待壓縮信息上使用，為了能正確解壓縮，我們必須再消耗一定的空間保存靜態(tài)模型統(tǒng)計(jì)出的概率分布，保存模型所用的空間將使我們重新遠(yuǎn)離熵值。其次，靜態(tài)模型需要在壓縮前對(duì)信息內(nèi)字符的分布進(jìn)行統(tǒng)計(jì)，這一統(tǒng)計(jì)過程將消耗大量的時(shí)間，使得本來就比較慢的算術(shù)編碼壓縮更加緩慢。另外還有最重要的一點(diǎn)，對(duì)較長(zhǎng)的信息，靜態(tài)模型統(tǒng)計(jì)出的符號(hào)概率是該符號(hào)在整個(gè)信息中的出現(xiàn)概率，而自適應(yīng)模型可以統(tǒng)計(jì)出某個(gè)符號(hào)在某一局部的出現(xiàn)概率或某個(gè)符號(hào)相對(duì)于某一上下文的出現(xiàn)概率，換句-15-話說，自適應(yīng)模型得到的概率分布將有利于對(duì)信息的壓縮(可以說結(jié)合上下文的自適應(yīng)模型的信息熵建立在更高的概率層次上，其總熵值更小)，好的基于上下文的自適應(yīng)模型得到的壓縮結(jié)果將遠(yuǎn)遠(yuǎn)超過靜態(tài)模型。自適應(yīng)模型的階通常用“階”(order)這一術(shù)語區(qū)分不同的自適應(yīng)模型。前面例子中采用的是0階自適應(yīng)模型，該例子中統(tǒng)計(jì)的是符號(hào)在已輸入信息中的出現(xiàn)概率，沒有考慮任何上下文信息。如果我將模型變成統(tǒng)計(jì)符號(hào)在某個(gè)特定符號(hào)后的出現(xiàn)概率，那么，模型就成為了1階上下文自適應(yīng)模型。舉個(gè)例子要對(duì)一篇英文文本進(jìn)行編碼，已經(jīng)編碼了10000個(gè)英文字符，剛剛編碼的字符是t,下一個(gè)要編碼的字符是h。我們?cè)谇懊娴木幋a過程中已經(jīng)統(tǒng)計(jì)出前10000個(gè)字符中出現(xiàn)了113次字母t,其中有47個(gè)t后面跟著字母h。我們得出字符h在字符t后的出現(xiàn)頻率是47/113，我們使用這一頻率對(duì)字符h進(jìn)行編碼，需要-log2(47/113)=1.266bit。對(duì)比0階自適應(yīng)模型，如果前10000個(gè)字符中h的出現(xiàn)次數(shù)為82次，則字符h的概率是82/10000，我們用此概率對(duì)h進(jìn)行編碼，需要-log2(82/10000)=6.930bit。考慮上下文因素的優(yōu)勢(shì)顯而易見。還可以進(jìn)一步擴(kuò)大這一優(yōu)勢(shì)，例如要編碼字符h的前兩個(gè)字符是gt，而在已經(jīng)編碼的文本中g(shù)t后面出現(xiàn)h的概率是80%，那么我們只需要0.322bit就可以編碼輸出字符h。此時(shí)，使用的模型叫做2階上下文自適應(yīng)模型。最理想的情況是采用3階自適應(yīng)模型。此時(shí)，如果結(jié)合算術(shù)編碼，對(duì)信息的壓縮效果將達(dá)到驚人的程度。采用更高階的模型需要消耗的系統(tǒng)空間和時(shí)間至少在目前還無法讓人接受，使用算術(shù)壓縮的應(yīng)用程序大多數(shù)采用2階或3階的自適應(yīng)模型。五、實(shí)驗(yàn)步驟項(xiàng)目文件建立步驟同實(shí)驗(yàn)二，下面列出對(duì)給定序列的算術(shù)編碼步驟：步驟1：編碼器在開始時(shí)將“當(dāng)前間隔”[L，H）設(shè)置為[0，1）。步驟2：對(duì)每一事件，編碼器按步驟（a）和（b）進(jìn)行處理（a） 編碼器將“當(dāng)前間隔”分為子間隔，每一個(gè)事件一個(gè)。（b） 一個(gè)子間隔的大小與下一個(gè)將出現(xiàn)的事件的概率成比例，編碼器選擇子間隔對(duì)應(yīng)于下一個(gè)確切發(fā)生的事件相對(duì)應(yīng)，并使它成為新的“當(dāng)前間隔”。-16-步驟3：最后輸出的“當(dāng)前間隔”的下邊界就是該給定事件序列的算術(shù)編碼。六、實(shí)驗(yàn)報(bào)告要求1．按照實(shí)驗(yàn)一附3中實(shí)驗(yàn)報(bào)告樣式提交本次實(shí)驗(yàn)報(bào)告。2．算術(shù)編碼學(xué)習(xí)心得，特別是根據(jù)自適應(yīng)模型0階編碼，調(diào)整概率分布方法。根據(jù)自己實(shí)驗(yàn)情況，寫出自己的做實(shí)驗(yàn)中遇到的具體問題，對(duì)本實(shí)驗(yàn)提出建議。七、 實(shí)驗(yàn)注意事項(xiàng)幾個(gè)重要概念在實(shí)驗(yàn)前一定搞清楚：1） 編碼概論累加分布；2） 編碼區(qū)間上限和下限迭代算法；3） 自適應(yīng)模型0階的編碼原理。程序設(shè)計(jì)時(shí)注意內(nèi)容：1） 基本概論模型的確定（等概率分布，255個(gè)字符）；2） 自適應(yīng)調(diào)整概率分布；3） E1/E2/E3放大原理，及它們之間關(guān)系（認(rèn)真閱讀參考資料）；4） 理解從Buffer中寫bit和讀bit的方法；5） 理解字節(jié)對(duì)齊的方法。八、 思考題能否根據(jù)算法流程和C++源代碼寫出Matlab下算術(shù)編碼程序？-17-實(shí)驗(yàn)四CRC校驗(yàn)碼編碼實(shí)驗(yàn)（2學(xué)時(shí)）一、 實(shí)驗(yàn)?zāi)康?．學(xué)習(xí)CRC編碼基本流程,學(xué)會(huì)調(diào)試循環(huán)冗余校驗(yàn)碼編碼程序。掌握CRC校驗(yàn)碼的編碼原理，重點(diǎn)掌握按字節(jié)（Byte）編碼方法。二、 實(shí)驗(yàn)內(nèi)容根據(jù)實(shí)驗(yàn)原理掌握CRC校驗(yàn)碼編碼/解碼基本流程。在C++編譯器下能夠調(diào)試編碼算法每一個(gè)步驟，重點(diǎn)掌握按字節(jié)編碼的過程。三、 實(shí)驗(yàn)儀器、設(shè)備1.計(jì)算機(jī)一系統(tǒng)最低配置256M內(nèi)存、P4CPU。2.C++編程軟件一VisualC++7.0（MicrosoftVisualStudio2003） VisualC++8.0（MicrosoftVisualStudio2005）四、 實(shí)驗(yàn)原理1.CRC校驗(yàn)碼介紹CRC校驗(yàn)的基本思想是利用線性編碼理論，在發(fā)送端根據(jù)要傳送的k位二進(jìn)制碼序列，以一定的規(guī)則產(chǎn)生一個(gè)校驗(yàn)用的監(jiān)督碼（CRC碼）r位，并附在信息后邊，構(gòu)成一個(gè)新的二進(jìn)制碼序列數(shù)共(k+r)位，最后發(fā)送出去。在接收端，則根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進(jìn)行檢驗(yàn)，以確定傳送中是否出錯(cuò)。16位的CRC碼產(chǎn)生的規(guī)則是先將要發(fā)送的二進(jìn)制序列數(shù)左移16位(乘以216)后，再除以一個(gè)多項(xiàng)式，最后所得到的余數(shù)既是CRC碼。求CRC碼所采用模2加減運(yùn)算法則，既是不帶進(jìn)位和借位的按位加減，這種加減運(yùn)算實(shí)際上就是邏輯上的異或運(yùn)算，加法和減法等價(jià)，乘法和除法運(yùn)算與普通代數(shù)式的乘除法運(yùn)算是一樣，符合同樣的規(guī)律。接收方將接收到的二進(jìn)制序列數(shù)(包括信息碼和CRC碼)除以多項(xiàng)式，如果余數(shù)為0，則說明傳輸中無錯(cuò)誤發(fā)生，否則說明傳輸有誤。2．按位計(jì)算CRC一個(gè)二進(jìn)制序列數(shù)可以表示為求此二進(jìn)制序列數(shù)的CRC碼時(shí)，先乘以216后(左移16位)，再除以多項(xiàng)式G(X),所得的余數(shù)就是所要求的CRC碼。-18-可以設(shè)：其中Qn(X)為整數(shù)，Rn(X