2895.C游程編碼的設計及性能研究 軟件說明書

1、 學院2009屆本科畢業(yè)設計 大學軟 件 說 明 書題 目：游程編碼的設計及性能研究 源代碼請聯(lián)系本人。專 業(yè)：計算機科學與技術學生姓名： 班級學號： 指導教師： 指導單位：計算機硬件基礎教學中心日 期：2009-6-410軟件使用說明書一、軟件概述在數(shù)據(jù)編碼領域，高性能的壓縮算法一直是人們不懈追求的目標，特別是在低比特率壓縮時具有低存儲量、低功耗、實時的高性能編碼算法是近幾年的研究熱點;隨著數(shù)字化技術的普及，各種應用對數(shù)據(jù)壓縮編碼提出了不同要求。本文針對這種要求，對二元相關信源編碼的游程編碼技術進行了研究。設計目的：l 能模擬產(chǎn)生一組信源，該信源即消息通過游程編碼壓縮成為碼子，再經(jīng)過譯碼過程

2、還原為信息的過程，實現(xiàn)游程編碼的設計。l 能在游程編碼的過程中計算壓縮比率，已達到對游程編碼性能的研究。設計目標：實現(xiàn)游程編碼的設計和對其性能進行研究。該軟件使用起來方便靈活，功能簡單易懂。對于怎樣隨機產(chǎn)生信源，進行編碼，譯碼以及計算其壓縮比率在下文有進一步講解。二、軟件開發(fā)原理本軟件是對游程編碼的理解，實現(xiàn)對二元相關信源游程編碼，譯碼以及計算壓縮比率的過程，在這個過程中，首先，是采用隨機數(shù)算法產(chǎn)生一組隨機數(shù)，即信息，然后通過編碼對消息進行壓縮成為碼子，再通過壓縮過程還原為消息的過程。2.1 圖像數(shù)據(jù)壓縮原理由于圖像數(shù)據(jù)之間存在著一定的冗余，所以使得數(shù)據(jù)的壓縮成為可能。信息論的創(chuàng)始人shann

3、on提出把數(shù)據(jù)看作是信息和冗余度（redundancy）的組合。所謂冗余度，是由于一副圖像的各像素之間存在著很大的相關性，可利用一些編碼的方法刪去它們，從而達到減少冗余壓縮數(shù)據(jù)的目的。為了去掉數(shù)據(jù)中的冗余，常常要考慮信號源的統(tǒng)計特性，或建立信號源的統(tǒng)計模型。圖像的冗余包括以下幾種：(1) 空間冗余：像素點之間的相關性。 (2) 時間冗余：活動圖像的兩個連續(xù)幀之間的冗余。 (3) 信息熵冗余：單位信息量大于其熵。 (4) 結構冗余：圖像的區(qū)域上存在非常強的紋理結構。 (5) 知識冗余：有固定的結構，如人的頭像。 (6) 視覺冗余：某些圖像的失真是人眼不易覺察的。對數(shù)字圖像進行壓縮通常利用兩個基本

4、原理：(1) 數(shù)字圖像的相關性。在圖像的同一行相鄰像素之間、活動圖像的相鄰幀的對應像素之間往往存在很強的相關性，去除或減少這些相關性，也就去除或減少圖像信息中的冗余度，即實現(xiàn)了對數(shù)字圖像的壓縮。(2) 人的視覺心理特征。人的視覺對于邊緣急劇變化不敏感(視覺掩蓋效應)，對顏色分辨力弱，利用這些特征可以在相應部分適當降低編碼精度，而使人從視覺上并不感覺到圖像質(zhì)量的下降，從而達到對數(shù)字圖像壓縮的目的。常用圖像壓縮編碼方法的分類編碼壓縮方法有許多種，從不同的角度出發(fā)有不同的分類方法，比如從信息論角度出發(fā)可分 為兩大類：(1)冗余度壓縮方法，也稱無損壓縮，信息保持編碼或熵編碼。具體講就是解碼圖像和壓縮

5、編碼前的圖像嚴格相同，沒有失真，從數(shù)學上講是一種可逆運算。(2)信息量壓縮方法，也稱有損壓縮，失真度編碼或熵壓縮編碼。也就是講解碼圖像和原始圖像是有差別的，允許有一定的失真。2.2 隨機數(shù)算法原理：隨機數(shù)在信息安全領域有著廣泛的應用，比如各種安全認證協(xié)議，一次安全通信中使用到的會晤密鑰，甚至軟件產(chǎn)生rsa密鑰對等，這些應用都會使用到隨機數(shù)。特別是一些安全級別要求比較高的應用，對于隨機數(shù)的質(zhì)量提出了很高的要求。隨機數(shù)的生成一般有兩種方式，一種是硬件方式，一種是軟件方式。一般情況下，硬件方式生成的隨機數(shù)質(zhì)量要好于軟件方式生成的隨機數(shù)。但是對于一般的用戶來說，需要每位用戶都配備一種硬件設備來生成隨機

6、數(shù)，這種方式可能不太現(xiàn)實。因此，通過軟件方式來尋找高質(zhì)量的隨機數(shù)，這是一個很重要而且必要的課題。 隨機數(shù)生成器有真隨機和偽隨機之分。真隨機數(shù)生成器滿足以上所有的三點要求，偽隨機數(shù)生成器只能滿足以上的前兩點要求。 軟件生成隨機數(shù)的一般方式如下： (1) 確定一個數(shù)學模型或者算法。 (2) 設置一些參數(shù)的值。 (3) 按照規(guī)定的步驟和算法來生成第一個隨機數(shù)。 (4) 然后在第一個隨機數(shù)的基礎上，來生成第二個隨機數(shù)。重復同樣的步驟，從而得到一個隨機數(shù)序列。 很明顯，這種軟件方式生成的隨機數(shù)是偽隨機數(shù)序列。只要知道了其使用的算法和參數(shù)值，我們就可以生成同樣的隨機數(shù)序列。因此，真正的隨機數(shù)是不可能通過具

7、體的算法來生成的。 真正的隨機數(shù)序列只能來源于隨機事件，那么我們可以從計算機系統(tǒng)中存在的大量的隨機事件中提取隨機事件，經(jīng)過正確的處理就有可能生成真正的隨機數(shù)序列2.3 設計思想 在信息安全領域，我們經(jīng)常遇到這樣的情況：需要生成8個字節(jié)的隨機數(shù)序列。那么我們可以把這8個字節(jié)的隨機數(shù)序列當成由64個bit所組成的，每個bit位的取值為0或者1。如果我們使用投擲硬幣的方式來決定每個bit位應該取0還是1，那么我們投擲64次硬幣，就會得到一個由0或者1組成的隨機數(shù)序列。這個0和1組成的隨機數(shù)序列每8位組成一個字節(jié)，最終我們得到了要求的8個字節(jié)的隨機數(shù)序列。像這種隨機數(shù)序列的生成方式，它符合了密碼學對于

8、隨機序列定義的3個特點，從而保證它是一個真正的隨機數(shù)序列。但是，顯而易見地，這種生成隨機數(shù)序列的方式效率太低下了。 基于這種思想，我們可以利用計算機系統(tǒng)的隨機性，提取出0和1組成的隨機數(shù)序列，然后對這個0和1組成的隨機數(shù)序列進行組合處理，從而最終得到質(zhì)量很高的真隨機數(shù)序列。我們的算法思想可以總結為如下幾步： (1) 根據(jù)計算機系統(tǒng)中的隨機事件，得到0和1組成的原始隨機數(shù)序列。 (2) 對0和1組成的原始隨機數(shù)序列進行某種處理，獲得組合之后的由0和1組成的組合隨機數(shù)序列。 (3) 繼續(xù)進行類似于第二步的處理，進行多次的組合處理。 (4) 將最終得到的0和1隨機數(shù)序列每8個bit組成一個字節(jié)，從而

9、得到若干字節(jié)的隨機數(shù)。在這個設計方法中，關鍵的是第一步，隨機事件的獲取。只要能保證原始隨機數(shù)序列是真正的隨機事件生成的，即使我們不進行后續(xù)的組合處理，我們也可以得到真正的隨機數(shù)序列。就好像我們通過投擲硬幣來獲得8字節(jié)的隨機數(shù)一樣。但是，由于計算時間或者計算機系統(tǒng)的精度等各方面的限制，長度很長的原始隨機數(shù)序列不容易獲得。所以，需要對獲得的原始隨機數(shù)序列進行數(shù)學上的處理，以便獲得長度很長的隨機數(shù)序列2.4 游程編碼原理在二元序列中，只有兩種符號，即“0”和“1”，這些符號可連續(xù)出現(xiàn)，連“0”這一段稱為“0”游程，連“1”這一段稱為“1”游程。它們的長度分別稱為游程長度l(0)和l(l)。“0”游程

10、和“l(fā)”游程總是交替出現(xiàn)的。如果規(guī)定二元序列是以“0”開始，則第一個游程是“0”游程，第二個必為“1”游程，第三個又是“0”游程等等。對于隨機的二元序列，各游程長度將是隨機變量，其取值可為1，2，3，直到無限。將任何二元序列變換成游程長度序列，這種變換是一一對應的，也就是可逆的。例如有一個二元序列：000101110010001，可變換成下列游程序列：3113213。若已知二元序列是以0起始的，從上面的游程序列很容易恢復成原來的二元序列，包括最后一個“1”，因為長度為3的“0”游程之后必定是“1”。游程序列已是多元序列，各長度可按哈夫曼編碼或其他方法處理，以達到壓縮編碼率的目的。這種從二元序列

11、轉換為多元序列的方法，在實現(xiàn)時比較簡單。因為游程長度的計數(shù)比較容易，得到游程長度后就可從碼表中找出碼字輸出，同時去數(shù)下一個游程長度。此外，在減弱原有序列的符號間的相關性方面，采用游程變換一般也更有效。當然，要對二元序列進行哈夫曼編碼時，應先測定“0”游程長度和“1”游程長度的概率分布，或由二元序列的概率特性去計算各種游程長度的概率。三 運行環(huán)境的安裝3.1 visual studio 2005 的安裝過程運行visual studio安裝程序時，系統(tǒng)會在指定的硬盤上為visual studio創(chuàng)建安裝目錄，下面將介紹如何安裝visual studio 2005。首先，插入 visual stu

12、dio 的安裝光盤，運行安裝程序，你會看到如（圖2-1）所示。請點擊最上面的鏈接 安裝 visual studio 2005。（圖2-1）然后你會進入（圖2-2）畫面，這時候安裝程序會運行一段時間，等待完成安裝程序的組件加載，加載完成以后，右下角的 下一步按鈕就可以點擊了。點擊 “下一步” 按鈕之后，你會被要求填寫 “產(chǎn)品密鑰”，請將 “我接受許可協(xié)議中的條款” 勾上，然后填上你的產(chǎn)品密鑰。至于 “名稱” 欄，一般來說是填寫該軟件的購買者，也可以不用修改它。所有填完之后再按 “下一步”。（圖2-2）接下來出現(xiàn)的（圖2-3）畫面，讓你可以選擇你所要裝的功能。如果你對 visual studio

13、還不是很熟，就直接勾 “默認值”， “默認值”表示 visual studio 會自動幫你安裝推薦的功能。如果你覺得還不放心，你可以選擇 “完全”，“完全”表示 visual studio 會安裝所有的功能（可能包含一些不經(jīng)常使用的功能）。（圖2-3）如果你是對安裝過程比較熟悉，知道什么功能要，什么功能不要，你可以選擇 “自定義”。選擇 “自定義”之后，你會看到一個功能選擇畫面，該畫面列出了所有該版本 visual studio 的功能，打勾的表示要安裝，打叉的表示不要安裝。這里以選擇“默認值”截圖如（圖2-4）所示：（圖2-4）選擇好你要裝的功能之后，就開始安裝了。當屏幕出現(xiàn)如（圖2-5）畫

14、面，其中畫面上方會顯示 “成功”，“visual studio”安裝完畢 綠色字樣，表示已經(jīng)成功安裝完畢。（圖2-5）然后點擊畫面右下角的 “完成”按鈕。點擊了“完成”按鈕，安裝程序會自動回到安裝初畫面。vs2005的默認啟動界面，如（圖2-6）所示：（圖2-6）到此visual studio 2005就全部安裝完成了!32 用戶使用說明本系統(tǒng)主要是對游程編碼的設計及其性能的研究，所以不具備數(shù)據(jù)庫和其他的服務器，只需要在單臺機器上運行即可。整個系統(tǒng)分為三大模塊，產(chǎn)生模擬信源，編碼及其計算壓縮比率和譯碼過程。本系統(tǒng)的第一個模塊，也就是運行時的第一個界面， 如（圖3-1）所示：（圖3-1） 在co

15、unt控件中能輸入05位數(shù)之間的任一個整數(shù)，當輸入不同的值時點擊create就會產(chǎn)生不同的一組二元序列，而且對于輸入同一個值時，單擊create產(chǎn)生的信源也是不一樣的，因為在這里采用的是隨機數(shù)算法，每次點擊create都會隨機產(chǎn)生一組二元序列。比如輸入100和1000這兩個數(shù)值產(chǎn)生的二元序列如（圖3-2）和（圖3-3）所示：（圖3-2）（圖3-3）本系統(tǒng)的第二個模塊，游程編碼的編碼過程，也就是第二大模塊，在這個過程中同時也具備了計算壓縮比率這一功能。點擊上一個頁面的encode按鈕就會將信源壓縮為碼子，以下是分別對100和1000組信源進行壓縮后的碼子如（圖3-4）和（圖3-5）所示：（圖3-4）（圖3-5）在這個界面中會顯示壓縮的比率，輸入不同的值就會產(chǎn)生不同的比率?？梢远嘣噹状?，這樣就會發(fā)現(xiàn)其中的比率規(guī)則，受篇幅限制，這里我就舉這兩個例子。本系統(tǒng)的第三大模塊，譯碼過程，就是把壓縮后的碼子還原為原來的信息，單擊decod