信息論與編碼實(shí)驗(yàn)指導(dǎo)書前 言當(dāng)前，信息論與編碼已經(jīng)成為電子信息類專業(yè)高年級(jí)學(xué)生必修的專業(yè)基礎(chǔ)課。盡管各個(gè)院校開設(shè)課程名稱有所不同，但都是以香農(nóng)信息論為核心內(nèi)容的。這是一門理論性和系統(tǒng)性很強(qiáng)的課程。涉及多個(gè)學(xué)科，需要廣泛數(shù)學(xué)知識(shí)。為了能透徹掌握信息論基本概念和分析方法，做實(shí)驗(yàn)進(jìn)行實(shí)踐練習(xí)是不可缺少的環(huán)節(jié)。通過綜合性、驗(yàn)證性實(shí)驗(yàn)，可以加深對(duì)理論和概念的理解，增強(qiáng)分析和解決實(shí)際問題的能力。為此，河北工業(yè)大學(xué)信息學(xué)院編寫了信息論與編碼實(shí)驗(yàn)指導(dǎo)書，由于可供參考的實(shí)驗(yàn)指導(dǎo)書有限，本書的不妥和錯(cuò)誤之處，懇請(qǐng)讀者予以批評(píng)指正。 馬 杰 2008年2月目 錄 實(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實(shí)驗(yàn)一 信息熵與圖像熵計(jì)算（2學(xué)時(shí)）一、實(shí)驗(yàn)?zāi)康?1復(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)存、P4 CPU。2Matlab仿真軟件 7.0 / 7.1 / 2006a 等版本Matlab軟件。四、實(shí)驗(yàn)原理 1 MATLAB中數(shù)據(jù)類型、矩陣運(yùn)算、圖像文件輸入與輸出知識(shí)復(fù)習(xí)。2 利用信息論中信息熵概念，求出任意一個(gè)離散信源的熵（平均自信息量）。自信息是一個(gè)隨機(jī)變量,它是指某一信源發(fā)出某一消息所含有的信息量。所發(fā)出的消息不同，它們所含有的信息量也就不同。任何一個(gè)消息的自信息量都代表不了信源所包含的平均自信息量。不能作為整個(gè)信源的信息測(cè)度，因此定義自信息量的數(shù)學(xué)期望為信源的平均自信息量：信息熵的意義：信源的信息熵H是從整個(gè)信源的統(tǒng)計(jì)特性來考慮的。它是從平均意義上來表征信源的總體特性的。對(duì)于某特定的信源，其信息熵只有一個(gè)。不同的信源因統(tǒng)計(jì)特性不同，其熵也不同。3學(xué)習(xí)圖像熵基本概念，能夠求出圖像一維熵和二維熵。圖像熵是一種特征的統(tǒng)計(jì)形式，它反映了圖像中平均信息量的多少。圖像的一維熵表示圖像中灰度分布的聚集特征所包含的信息量，令 Pi Pi表示圖像中灰度值為i的像素所占的比例，則定義灰度圖像的一元灰度熵為：圖像的一維熵可以表示圖像灰度分布的聚集特征，卻不能反映圖像灰度分布的空間特征，為了表征這種空間特征，可以在一維熵的基礎(chǔ)上引入能夠反映灰度分布空間特征的特征量來組成圖像的二維熵。選擇圖像的鄰域灰度均值作為灰度分布的空間特征量，與圖像的像素灰度組成特征二元組，記為( i, j )，其中i表示像素的灰度值(0 = i = 255)，j表示鄰域灰度(0 = j .00001, error(Probablities dont sum to 1.)end% Remove any zero probabilities %zeroProbs = find(array eps);if isempty(zeroProbs), array(zeroProbs) = ; %disp(Removed zero or negative probabilities.)End% Compute the entropyH = -sum(array .* log2(array); % 單位 bit/symbol附2：圖像熵計(jì)算源代碼函數(shù)源程序 ImgEntropy.m % Image Entropy calculation % , 22/08/2007 % img : input image data% H1,H2 : Output 1&2 order entropyfunction H1,H2 = ImgEntropy(img)% color image transformation I = imread(img);img = rgb2gray(I);imview(I), imview(img);ix,iy = size(img);%compute probs for each scale level in imageP1 = imhist(img)/(ix*iy);temp = double(img);% for the index of image piexl temp = temp , temp(:,1);% correlation prob matrix between 0 . 255 gray levels CoefficientMat = zeros(256,256);for x = 1:ix for y = 1:iy i = temp(x,y); j = temp(x,y+1); CoefficientMat(i+1,j+1) = CoefficientMat(i+1,j+1)+1; endend% compute the prob of matrix P2 = CoefficientMat./(ix*iy);H1 = 0; H2 = 0;for i = 1:256% calculate 1 ord image entropy if P1(i) = 0 H1 = H1 - P1(i)*log2(P1(i); end% compute 2 ord image entropy for j = 1:256 if P2(i,j) = 0 H2 = H2 - P2(i,j)*log2(P2(i,j); end endendH2 = H2/2; % mean entropy /symbol sprintf(1 ord image entropy is : %d,H1)sprintf(2 ord image entropy is : %d,H2)函數(shù)調(diào)用實(shí)例 test.m% Information Theory experiment testing file% , 22/08/2007% testing Discrete Shannon Entropy % discrete probabilities setprobSet = 0.1 0.2 0.3 0.15 0.25;% call CalEntropy functionH = CalEntropy(probSet);sprintf(Shannon Entropy is: %d,H)% calculate the Image entropyH1,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)建議等。實(shí)驗(yàn)二 Huffman 編碼（2學(xué)時(shí)）一、實(shí)驗(yàn)?zāi)康?1復(fù)習(xí)C+程序基本編寫方法，熟悉VC編程環(huán)境。2會(huì)用VC調(diào)試Huffman編碼程序。二、實(shí)驗(yàn)內(nèi)容 1復(fù)習(xí)C+代碼基本語法（結(jié)構(gòu)體、樹等數(shù)據(jù)結(jié)構(gòu)定義）2根據(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)存、P4 CPU。2C+ 編程軟件 Visual C+ 7.0 （Microsoft Visual Studio 2003） Visual C+ 8.0 （Microsoft Visual Studio 2005）四、實(shí)驗(yàn)原理 1 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è)只包含(n1)個(gè)信源符號(hào)的新信源。稱為信源的第一次縮減信源，用S1表示。將縮減信源S1的符號(hào)仍按概率從大到小順序排列，重復(fù)步驟2，得到只含(n2)個(gè)符號(hào)的縮減信源S2。重復(fù)上述步驟，直至縮減信源只剩兩個(gè)符號(hào)為止，此時(shí)所剩兩個(gè)符號(hào)的概率之和必為1。然后從最后一級(jí)縮減信源開始，依編碼路徑向前返回，就得到各信源符號(hào)所對(duì)應(yīng)的碼字。2Huffman樹的編碼原理：步驟1： 將各個(gè)符號(hào)及其出現(xiàn)頻率分別作為不同的小二叉樹（目前每棵樹只有根節(jié)點(diǎn)）步驟2： 在步驟1中得到的樹林里找出頻率值最小的兩棵樹，將他們分別作為左、右子樹連成一棵大一些的二叉樹，該二叉樹的頻率值設(shè)為兩棵子樹頻率值之和。步驟3：對(duì)上面得到的樹林重復(fù)步驟2的做法，直到所有符號(hào)都連入樹中為止。五、實(shí)驗(yàn)步驟 1VC環(huán)境下，建一個(gè)C+控制臺(tái)應(yīng)用程序，并把源代碼考到該程序目錄下。2項(xiàng)目文件中含有一個(gè)預(yù)編譯頭文件，一個(gè)主函數(shù)入口文件和Huffman編碼算法文件。3在入口文件中，輸入任一個(gè)離散信源進(jìn)行編碼調(diào)試。4設(shè)置好程序斷點(diǎn)，仔細(xì)分析Huffman樹每步的建立過程。5輸出離散信源中每個(gè)符號(hào)的Huffman編碼，并與手工運(yùn)算的結(jié)果進(jìn)行比較。六、實(shí)驗(yàn)報(bào)告要求 1 按照實(shí)驗(yàn)一附3中實(shí)驗(yàn)報(bào)告樣式書寫本次實(shí)驗(yàn)報(bào)告。2 總結(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) 1指針數(shù)據(jù)結(jié)構(gòu)定義typedef structunsigned long weight;int parent, lchild, rchild; HTNode, *HuffmanTree;typedef char* HuffmanCode; / 指向存放數(shù)組指針的數(shù)組即二維數(shù)組 2二叉樹生成操作放在數(shù)組中（節(jié)點(diǎn)n和數(shù)組大小m關(guān)系為：m=2*n-1）。每次在樹中找到兩顆最小子樹，其函數(shù)為Select(HuffmanTree HT, int n, int *s1, int *s2)，實(shí)際實(shí)現(xiàn)的是在數(shù)組中找到最小兩個(gè)元素。另外注意C+的數(shù)組起始索引是0，Matlab起始索引是1；程序中為了方便從1開始索引數(shù)組，HT0.weight 的大小設(shè)為0xffffffffL。為了輸出二進(jìn)制Huffman碼，程序最后對(duì)每個(gè)符號(hào)進(jìn)行深度優(yōu)先搜索，得到該符號(hào)的二進(jìn)制字符，然后進(jìn)行字符串拷貝，直到最后輸出。八、思考題 根據(jù)Huffman算法的C源程序，試著寫出Huffman編碼的Matlab程序？附1：Huffman編碼源代碼源代碼列表：stdafx.h Huffman.cpp預(yù)編譯頭文件：stdafx.h 以下代碼#pragma once#include #include #include #include #include 控制臺(tái)應(yīng)用CPP文件：Huffman.cpp#include stdafx.htypedef structunsigned long weight;int parent, lchild, rchild; HTNode, *HuffmanTree;typedef char* HuffmanCode;HuffmanCode HC;void Select(HuffmanTree HT, int n, int *s1, int *s2);void HuffmanCoding(unsigned long *w, int n)int i;if( n=1 ) return;int m = 2*n - 1;HuffmanTree p;HuffmanTree HT = (HuffmanTree)malloc(m+1)*sizeof(HTNode);memset(HT, 0, sizeof(HTNode) * (m+1);for( p=HT,i=1; iweight = *w;int s1, s2;for( i=n+1; i=m; +i )Select(HT, i-1, &s1, &s2);HTs1.parent = i; HTs2.parent = i;HTi.lchild = s1; HTi.rchild = s2;HTi.weight = HTs1.weight + HTs2.weight;HC = (HuffmanCode)malloc(n+1)*sizeof(char*);char *cd = (char*)malloc(n*sizeof(char);cdn-1 = 0;int start;unsigned long f;for( i=1; i=n; +i )start = n - 1;int c;for( c=i, f=HTi.parent; f!=0; c=f, f=HTf.parent )if( HTf.lchild = c )cd-start = 0;else cd-start = 1;HCi = (char*)malloc(n-start)*sizeof(char);strcpy(HCi, &cdstart);free( HT );/free( cd );void Select(HuffmanTree HT, int n, int *s1, int *s2)int i;HT0.weight = (unsigned long)(-1l);*s1 = *s2 = 0;for( i=1; i=n; i+ )if( HTi.parent = 0 )if( HTi.weight HT*s1.weight )*s2 = *s1;*s1 = i;else if( HTi.weight HT*s2.weight )*s2 = i;/ 函數(shù)測(cè)試實(shí)例int _tmain(int argc, _TCHAR* argv)const int LEN = 3;int i;unsigned long weightLEN+1; weight0 = 0;weight1 = 1;weight2 = 7;weight3 = 2;HuffmanCoding( weight, LEN );for( i=1; i=LEN; i+ )printf(%sn, HCi);return 0;/ End of Huffman.cpp實(shí)驗(yàn)三 算術(shù)編碼（2學(xué)時(shí)）一、實(shí)驗(yàn)?zāi)康?1進(jìn)一步學(xué)習(xí)C+語言概念和熟悉VC編程環(huán)境。2學(xué)習(xí)算術(shù)編碼基本流程, 學(xué)會(huì)調(diào)試算術(shù)編碼程序。3. 根據(jù)給出資料，自學(xué)自適應(yīng)0階算術(shù)編、解碼方法。二、實(shí)驗(yàn)內(nèi)容 1復(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)存、P4 CPU。2C+ 編程軟件 Visual C+ 7.0 （Microsoft Visual Studio 2003） Visual C+ 8.0 （Microsoft Visual Studio 2005）四、實(shí)驗(yàn)原理 1算術(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)的字符僅有 a b c 三種，我們要壓縮保存的信息為 bccb。在沒有開始?jí)嚎s進(jìn)程之前，假設(shè)對(duì) a b c 三者在信息中的出現(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ū)間，劃分的結(jié)果可以用圖形表示為： +- 0.6667 Pc = 1/4 | +- 0.5834 | | Pb = 2/4 | | | +- 0.4167 Pa = 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.6334 | Pb = 2/5 | | +- 0.6001 Pa = 1/5 | +- 0.5834輸入下一個(gè)字符 c，三個(gè)字符的概率分布為：Pa = 1/6，Pb = 2/6，Pc = 3/6。接著來劃分 c 的區(qū)間 0.6334 - 0.6667： +- 0.6667 | | Pc = 3/6 | | +- 0.6501 | Pb = 2/6 | | +- 0.6390 Pa = 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)知道要輸出的小數(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.0 1.0 輸入 b 0.0 0.5 輸入 c 0.25 0.5 輸入 c 0.375 0.5 輸入 b 0.375 0.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)概率，換句話說，自適應(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.266 bit。對(duì)比 0 階自適應(yīng)模型，如果前 10000 個(gè)字符中 h 的出現(xiàn)次數(shù)為 82 次，則字符 h 的概率是 82/10000，我們用此概率對(duì) h 進(jìn)行編碼，需要 -log2(82/10000) = 6.930 bit。考慮上下文因素的優(yōu)勢(shì)顯而易見。還可以進(jìn)一步擴(kuò)大這一優(yōu)勢(shì)，例如要編碼字符 h 的前兩個(gè)字符是 gt，而在已經(jīng)編碼的文本中 gt 后面出現(xiàn) h 的概率是 80%，那么我們只需要 0.322 bit就可以編碼輸出字符 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)前間隔”。 步驟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) 1. 幾個(gè)重要概念在實(shí)驗(yàn)前一定搞清楚：1）編碼概論累加分布；2）編碼區(qū)間上限和下限迭代算法；3）自適應(yīng)模型0階的編碼原理。2. 程序設(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ù)編碼程序？實(shí)驗(yàn)四 CRC校驗(yàn)碼編碼實(shí)驗(yàn)（2學(xué)時(shí)）一、實(shí)驗(yàn)?zāi)康?1學(xué)習(xí)CRC編碼基本流程, 學(xué)會(huì)調(diào)試循環(huán)冗余校驗(yàn)碼編碼程序。2掌握CRC校驗(yàn)碼的編碼原理，重點(diǎn)掌握按字節(jié)（Byte）編碼方法。二、實(shí)驗(yàn)內(nèi)容 1根據(jù)實(shí)驗(yàn)原理掌握CRC校驗(yàn)碼編碼/解碼基本流程。2在C+編譯器下能夠調(diào)試編碼算法每一個(gè)步驟，重點(diǎn)掌握按字節(jié)編碼的過程。三、實(shí)驗(yàn)儀器、設(shè)備 1計(jì)算機(jī)系統(tǒng)最低配置 256M內(nèi)存、P4 CPU。2C+ 編程軟件 Visual C+ 7.0 （Microsoft Visual Studio 2003） Visual C+ 8.0 （Microsoft Visual Studio 2005）四、實(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 碼。可以設(shè)：其中Q n (X) 為整數(shù)， R n (X) 為16位二進(jìn)制余數(shù)，將上式代入前式得：再設(shè)：其中Qn-1(X) 為整數(shù)， Rn-1(X) 為16位二進(jìn)制余數(shù)，繼續(xù)代入前式，多次迭代得到：根據(jù)CRC 的定義，很顯然