平穩(wěn)信源熵求解課程設(shè)計

1、鄭州工業(yè)應(yīng)用技術(shù)學(xué)院課程設(shè)計（論文）題 目： 離散平穩(wěn)信源熵求解 指導(dǎo)教師： 魏平俊 職稱： 教授 學(xué)生姓名： 魏秀濤 學(xué)號： 1401140108 專 業(yè)： 電子信息工程 院 （系）： 信息工程學(xué)院 答辯日期： 2016年12月18日 2016年12月18日摘要 信息是從人類出現(xiàn)以來就存在于這個世界上，人類社會的生存和發(fā)展都離不開信息的獲取、傳遞、處理、再生、控制和處理。而信息論正是一門把信息作為研究對象，以揭示信息的本質(zhì)特性和規(guī)律為基礎(chǔ)，應(yīng)用概率論、隨即過程和數(shù)理統(tǒng)計等方法來研究信息的存儲、傳輸、處理、控制、和利用等一般規(guī)律的學(xué)科。主要研究如何提高信息系統(tǒng)的可靠性、有效性、保密性和認(rèn)證性，

2、以使信息系統(tǒng)最優(yōu)化。在信息論的指導(dǎo)下，信息技術(shù)得到飛速發(fā)展，這使得信息論滲透到自然科學(xué)和社會科學(xué)的所有領(lǐng)域，并且應(yīng)用與眾多領(lǐng)域：編碼學(xué)、密碼學(xué)與密碼分析、數(shù)據(jù)壓縮、數(shù)據(jù)傳輸、檢測理論、估計理論等。信息論的主要基本理論包括：信息的定義和度量；各類離散信源和連續(xù)信源的信源熵；有記憶，無記憶離散和連續(xù)信道的信道容量，平均互信息；無失真信源編碼相關(guān)理論。 求離散性信源熵也是信息論課程實踐學(xué)習(xí)中必須要經(jīng)歷，在了解常規(guī)的求解方式的同時，利用計算機(jī)語言進(jìn)行實踐編程。 用預(yù)先規(guī)定的方法將文字、數(shù)字或其他對象編成數(shù)碼，或?qū)⑿畔?、?shù)據(jù)轉(zhuǎn)換成規(guī)定的電脈沖信號。編碼在電子計算機(jī)、電視、遙控和通訊等方面廣泛使用。其中哈

3、夫曼編碼有廣泛的應(yīng)用,通過本次實驗,了解編碼的具體過程,通過編程實現(xiàn)編碼。本次實驗所使用的機(jī)器語言均為C語言。關(guān)鍵字：信息論 離散和連續(xù)信源熵 C語言編程設(shè)計目錄緒論11. 課程設(shè)計概述及意義22. 設(shè)計任務(wù)32.1設(shè)計目的32.2設(shè)計內(nèi)容32.3設(shè)計條件33. 理論分析43.1離散信號概念43.2信源熵53.2.1定義53.2.2本質(zhì)53.2.3物理含義63.3離散平穩(wěn)信源的數(shù)學(xué)定義63.4離散平穩(wěn)信源熵求解說明74.軟件介紹84.1 Visual C+ 6.0簡介84. 2主要部分95.程序設(shè)計115.1設(shè)計程序流程圖115.2設(shè)計程序編碼125.3程序運行結(jié)果156.課程設(shè)計心得體會16

4、致謝17參考文獻(xiàn)18緒論在自然界發(fā)生的許多過程中，有的過程朝一個方向可以自發(fā)地進(jìn)行，而反之則不行。自然界發(fā)生的一些過程是有一定的方向性的，這種過程叫不可逆過程。過程前后的兩個狀態(tài)是不等價的。用什么物理量來度量這種不等價性呢?通過研究，找到了“熵”這個物理量。 熵的概念最初是由R.J.克勞修斯在19世紀(jì)中葉建立的，1870年，玻耳茲曼給出了熵的統(tǒng)計解釋。熵概念對于初學(xué)者，一直是一個較抽象并難以通俗表達(dá)的物理概念。近40年來，熵的概念有了迅速而廣泛的發(fā)展。在天體物理中，黑洞的熵與面積這樣的幾何概念有聯(lián)系；在信息論中，信息的熵與信息量的概念有聯(lián)系，并且出現(xiàn)負(fù)熵的概念；在生物學(xué)中，生命現(xiàn)象也與熵有著密

5、切關(guān)系。此外，由普利高津和哈肯建立的非平衡態(tài)統(tǒng)計耗散結(jié)構(gòu)理論及協(xié)同學(xué)理論，使人們對熵規(guī)律有了更新的認(rèn)識，在無序中產(chǎn)生有序機(jī)制的出現(xiàn)，使得熵在許多方面都顯示出它的重要性。信源輸出信號在數(shù)學(xué)中可以用隨機(jī)過程加以描述，因此，可以說信源的建模在某種程度上也就是用恰當(dāng)?shù)碾S機(jī)過程來描述信號。從復(fù)雜性科學(xué)的角度來說，熵率只是非線性系統(tǒng)多重分形譜中特殊的一維，即信息維。熵的單位為 J/(mol·K) 或 kJ/(kmol·K)。對實際的絕熱膨脹過程，熵必然增加。熵增加的幅度越小，說明損失越小，效率越高。 在本文中，我們將信源的隨機(jī)模型和非線性動力學(xué)中對象之間建立聯(lián)系，其中離散無記憶信源、隱

6、馬爾可夫信源和康托集之間具有對應(yīng)關(guān)系。我們還將演示如何用解析的方法計算離散無記憶信源的熵率。并且這種統(tǒng)計物理的方法，完全可以推廣到一般信源熵率的計算。1. 課程設(shè)計概述及意義本課程設(shè)計是在學(xué)習(xí)了信息論與編碼和相關(guān)開發(fā)的軟件課程后，讓我們通過實際的操作來熟悉信源編碼微機(jī)實現(xiàn)，培養(yǎng)我們能夠獨立的完成對相關(guān)課題或者項目的分析能力、設(shè)計能力和調(diào)試能力。本課程設(shè)計是銜接在C課程、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計之后的，運用程序思想來完成的，聯(lián)系信息論與編碼所學(xué)內(nèi)容，要求有獨立的操作界面。在這次的課程設(shè)計中，著重培養(yǎng)的是我們的自學(xué)能力，以及獨立分析互聯(lián)網(wǎng)上和圖書館里的各種資料，來豐富自己的知識并且提高對數(shù)學(xué)公式的計算機(jī)實

7、現(xiàn)、VC+等軟件的實際操作能力。通過這次的課程設(shè)計，能夠使我們對已經(jīng)學(xué)習(xí)過的信息論與編碼課程的進(jìn)一步的掌握，能夠?qū)χR進(jìn)行最大程度的消化融匯。因此這次的課程設(shè)計對我們有著非常重要的意義。 本課程設(shè)計中用VC編寫出基于visual studio2010界面的簡單軟件以實現(xiàn)壓縮信源熵求解及哈夫曼編碼的目的。經(jīng)過比較系統(tǒng)合理的編程操作，實現(xiàn)可視化的窗口以方便用戶使用。通過簡單校驗確保信源正確性，保證軟件的可靠性。最終將結(jié)果保存為文檔方便記錄編碼結(jié)果。 通過讓完成具體編碼算法的程序設(shè)計和調(diào)試工作，達(dá)到提高編程能力和深刻理解編碼理論及信源熵求解的目的。培養(yǎng)我們使用計算機(jī)和查閱參考資料的能力，提高我們的基

8、本設(shè)計能力。培養(yǎng)了理論聯(lián)系實際和獨立思考的能力。并激發(fā)我們的實際開發(fā)創(chuàng)造的意識和能力。培養(yǎng)和提高我們的自學(xué)能力以及綜合運用所學(xué)理論知識去分析解決實際問題的能力。2. 設(shè)計任務(wù)2.1設(shè)計目的 深刻理解信源熵的計算方法；深刻理解信源編碼的基本思想與目的；2.2設(shè)計內(nèi)容首先對拖入文件中的字符總個數(shù)進(jìn)行統(tǒng)計 ，然后從文本頭開始查找同一字符個數(shù)，并計算 其概率 最后由得出的字符概率求得信源熵 2.3設(shè)計條件 計算機(jī)、C語言或其他語言環(huán)境；設(shè)計軟件 visual studio20103. 理論分析3.1離散信號概念離散信源：若一類信源輸出的消息常常是以一個個符號的形式出現(xiàn)，例如文字、字母等，這些符號的取值

9、是有限的或可數(shù)的，這樣的信源稱為離散信源。比如（0、1）二元信元，它的消息是以一定的概率來出現(xiàn)的，所以可以采用概率空間來描述。單符號離散信源的數(shù)學(xué)模型可表示為 （3.1.1）其中滿足：01，（3.1.2）公式(3.1.2)表示信源的可能取值共有n個：，每次必取其中之一。需要注意的是，大寫字母X,Y,Z代表隨機(jī)變量，指的是信源整體。帶下標(biāo)的小寫字母代表隨機(jī)事件的某一結(jié)果或信源的某個元素。兩者不可混淆。其中X1,X2,Xn為信源的消息；P(x1), P(x2),P(xn)為各消息出現(xiàn)的概率。3.2信源熵3.2.1定義已知單符號離散無記憶信源的數(shù)學(xué)模型,其中，且。我們定義信源各個離散消息的自信息量的

10、數(shù)學(xué)期望(即概率加權(quán)的統(tǒng)計平均值)為信源的平均信息量，一般稱為信源的信息熵，也叫信源熵或香農(nóng)熵，有時稱為無條件熵或熵函數(shù)，簡稱熵，記為。它實質(zhì)上是無記憶信源平均不確定度的度量。如果取以2為底的對數(shù)，信源熵的單位是 bit/符號。X中各離散消息的自信息量為非負(fù)值，概率也是非負(fù)值，且01，故信源熵也是非負(fù)值。的定義公式與統(tǒng)計熱力學(xué)中熵的表示形式相同，這就是信源熵名稱的由來。3.2.2本質(zhì)信源熵表征信源的平均不確定度，平均自信息量是消除信源不確定度所需要的信息的度量。信源一定，不管它是否輸出離散消息，只要這些離散消息具有一定的概率特性，必有信源的熵值，這熵值在總體平均的意義上才有意義，因而是一個確定

11、值。3.2.3物理含義總括起來，信源熵有三種物理含義： (1)信源熵表示信源輸出后，每個離散消息所提供的平均信息量。 (2)信源熵表示信源輸出前，信源的平均不確定度。 (3)信源熵反映了變量X的隨機(jī)性。3.3離散平穩(wěn)信源的數(shù)學(xué)定義在一般情況下，離散信源的輸出是空間和時間的離散符號序列，而且在序列中符號之間有依賴關(guān)系。此時可用隨機(jī)矢量來描述信源發(fā)出的消息，即其中任意一變量都是離散隨機(jī)變量，它表示時刻所發(fā)出的符號。信源在時刻將要發(fā)出什么樣的符號決定于兩方面：（1）與信源在時刻隨機(jī)變量的取值的概率分布有關(guān)。一般情況不同時，概率分布也不同，即。（2）與時刻以前信源發(fā)出的符號有關(guān)，即與條件概率有關(guān)。同樣

12、在一般情況下，它也是時間的函數(shù)，所以。對于平穩(wěn)信源來說，其條件概率與時間起點無關(guān)，只與關(guān)聯(lián)長度有關(guān)。它表示平穩(wěn)信源發(fā)出的平穩(wěn)隨機(jī)序列前后的依賴關(guān)系與時間起點無關(guān)。如果某時刻發(fā)出什么符號與前面發(fā)出的個符號有關(guān)。那么任何時刻它們的依賴關(guān)系都是一樣的。即。平均符號熵：定義N長的信源符號序列中平均每個信源符號所攜帶的信息量為：。也叫平均符號熵。3.4離散平穩(wěn)信源熵求解說明離散平穩(wěn)信源也是一種非常重要的信源。不同時刻信源輸出符號的概 率分布完全相同，則稱為一維離散平穩(wěn)信源。二維離散平穩(wěn)信源就是信源輸出的隨機(jī)序列，X1,X2,Xi，滿足其一維和二維概率分布與時間起點無關(guān)。這種各維聯(lián)合概率分布均勻與時間起點

13、無關(guān)的完全平穩(wěn)信源稱離散平穩(wěn)信源。二維離散平穩(wěn)信源的聯(lián)和熵為：，此值表示原來信源X輸出任意一對可能的消息的共熵，即描述信源X輸出長度為2的平均不確定性，或所含的信息量，因此可用作為二維離散平穩(wěn)信源的信息熵的近似值。在通信系統(tǒng)的各種信源中，離散隨機(jī)信源是最基本的一種信源，信源輸出是單個的符號的消息，并且消息之間是兩兩互不相容的。我們知道，事件發(fā)生的不確定性與事件發(fā)生的概率有關(guān)：事件的發(fā)生概率越小，不確定性就越大，事件發(fā)生的概率越大，不確定性就越小，對于發(fā)生概率為1的必然事件就不存在不確定性。設(shè)一離散信源的概率空間為： . . 即，如果知道已發(fā)生，則該事件所含有的信息量稱自信息，表達(dá)式為：上面的自

14、信息是指某一信源發(fā)出某一消息所含的信息量，但所發(fā)消息不同，它們所含信息量也就不同，所以自信息不能作為整個信源的信息測度，我們定義平均自信息量，即對每個事件各自所攜帶的信息量做一個加權(quán)平均，也稱信息熵，表示如下：信息熵具有一些基本的性質(zhì)，比如，對稱性，確定性，非負(fù)性，擴(kuò)展性，可加性等等。這里面有一個最大離散熵定理，表明:離散信源情況下，對于具有q個符號的離散信源，只有在q個信源符號等可能出現(xiàn)的情況下，信源熵才能達(dá)到最大值，這樣也表明等概率分布信源的平均不確定性為最大。4.軟件介紹4.1 Visual C+ 6.0簡介Visual C+ 6.0，簡稱VC或者VC6.0，是微軟推出的一款C+編譯器，

15、將“高級語言”翻譯為“機(jī)器語言（低級語言）”的程序。Visual C+是一個功能強(qiáng)大的可視化軟件開發(fā)工具。自1993年Microsoft公司推出Visual C+1.0后，隨著其新版本的不斷問世，Visual C+已成為專業(yè)程序員進(jìn)行軟件開發(fā)的首選工具。Visual C+6.0由Microsoft開發(fā), 它不僅是一個C+ 編譯器，而且是一個基于Windows操作系統(tǒng)的可視化集成開發(fā)環(huán)境（integrated development environment，IDE）。Visual C+6.0由許多組件組成，包括編輯器、調(diào)試器以及程序向?qū)ppWizard、類向?qū)lass Wizard等開發(fā)工具

16、。 這些組件通過一個名為Developer Studio的組件集成為和諧的開發(fā)環(huán)境。Microsoft的主力軟件產(chǎn)品。Visual C+是一個功能強(qiáng)大的可視化軟件開發(fā)工具。Visual C+6.0以擁有“語法高亮”，自動編譯功能以及高級除錯功能而著稱。比如，它允許用戶進(jìn)行遠(yuǎn)程調(diào)試，單步執(zhí)行等。還有允許用戶在調(diào)試期間重新編譯被修改的代碼，而不必重新啟動正在調(diào)試的程序。其編譯及創(chuàng)建預(yù)編譯頭文件(stdafx.h)、最小重建功能及累加連結(jié)(link)著稱。這些特征明顯縮短程序編輯、編譯及連結(jié)的時間花費，在大型軟件計劃上尤其顯著。4. 2主要部分1Developer Studio 圖1 Develop

17、er Studio環(huán)境這是一個集成開發(fā)環(huán)境，我們?nèi)粘９ぷ鞯?9%都是在它上面完成的，再加上它的標(biāo)題赫然寫著“Microsoft Visual C+”，所以很多人理所當(dāng)然的認(rèn)為，那就是Visual C+了。其實不然，雖然Developer Studio提供了一個很好的編輯器和很多Wizard，但實際上它沒有任何編譯和鏈接程序的功能，真正完成這些工作的幕后英雄后面會介紹。我們也知道，Developer Studio并不是專門用于VC的，它也同樣用于VB，VJ，VID等Visual Studio家族的其他同胞兄弟。所以不要把Developer Studio當(dāng)成Visual C+， 它充其量只是Vis

18、ual C+的一個殼子而已。這一點請切記！ 2MFC從理論上來講，MFC也不是專用于Visual C+，Borland C+，C+Builder和Symantec C+同樣可以處理MFC。同時，用Visual C+編寫代碼也并不意味著一定要用MFC，只要愿意，用Visual C+來編寫SDK程序，或者使用STL，ATL，一樣沒有限制。不過，Visual C+本來就是為MFC打造的，Visual C+中的許多特征和語言擴(kuò)展也是為MFC而設(shè)計的，所以用Visual C+而不用MFC就等于拋棄了Visual C+中很大的一部分功能。但是，Visual C+也不等于MFC。 3Platform SDK

19、這才是Visual C+和整個Visual Studio的精華和靈魂，雖然我們很少能直接接觸到它。大致說來，Platform SDK是以Microsoft C/C+編譯器為核心（不是Visual C+，看清楚了），配合MASM，輔以其他一些工具和文檔資料。上面說到Developer Studio沒有編譯程序的功能，那么這項工作是由誰來完成的呢？是CL，是NMAKE，和其他許許多多命令行程序，這些我們看不到的程序才是構(gòu)成Visual Studio的基石。5.程序設(shè)計5.1設(shè)計程序流程圖 5.2設(shè)計程序編碼#include<stdio.h>#include <stdlib.h&g

20、t;#include <ctype.h>#include<math.h>int check(char* s);void initial(void);struct Shujulong int cishu;double gl;char data;Jc256;int main(void)FILE* fp = NULL;char* filename = NULL;if( ( filename = (char*)malloc(500*sizeof(char) ) =NULL )return 0;doprintf("請拖入一個以字母命名的文件：");gets(f

21、ilename);while( ! check(filename) );if( (fp = fopen(filename, "r") )= NULL )printf("文件名為：'filename' 的文件不存在");return 0;fclose(fp);printf("n開始讀入文件內(nèi)容");initial();long int number = 0L;double Xys = 0.0;char ch = '0'while( !feof(fp) )ch = fgetc(fp);if( ch <

22、= 255 && ch >=0)ch=(ch<='Z'&&ch>='A')? (ch+32):ch;Jcch.cishu += 1;Jcch.data = ch;number += 1;for(int i = 0; i < 256 ;i+)if( Jci.cishu = 0 )continue;Jci.gl = static_cast<double>(Jci.cishu) / static_cast<double>(number);Xys = Xys + ( - log(Jci.gl

23、) * Jci.gl ) /log(2.0);printf("n其中 %c 字符的個數(shù)為：%d ，概率是：%4.5f。",Jci.data,Jci.cishu,Jci.gl);printf("n該信源的熵是:%.4f.",Xys);printf("n本次試驗正常運行n");fclose(fp);return 0;void initial(void)for(int i = 0;i<256;i+)Jci.cishu = 0;int check(char* s)int i = 0;while( *(s+i) != '0')i+;if( *(s+i-4) =