信息論與編碼實(shí)驗(yàn)報(bào)告

1、NANCHANGUNIVERSITY信息論與編碼實(shí)驗(yàn)報(bào)告（ 2018 年 11 月 27 日）學(xué)院： 信息工程學(xué)院系電子信息工程系專業(yè)班級(jí)：學(xué)生姓名：學(xué)號(hào)：指導(dǎo)教師：目錄實(shí)驗(yàn)一自信息量和熵源 .實(shí)驗(yàn)二準(zhǔn)對(duì)稱信道容量 .實(shí)驗(yàn)三費(fèi)諾不等式 .實(shí)驗(yàn)四香農(nóng)編碼 .實(shí)驗(yàn)五費(fèi)諾編碼 .實(shí)驗(yàn)六霍夫曼編碼 .實(shí)驗(yàn)一自信息量和熵源一、實(shí)驗(yàn)要求1、畫出I=-的函數(shù)圖；2、畫出H(p)=-p-(1-p)函數(shù)圖。二、實(shí)驗(yàn)原理及理論分析自信息量：一個(gè)事件的自信息量就是對(duì)其不確定性的度量。直觀地把自信息量定義為收到某消息獲得的信息量=不確定性減少的量。而事件x 發(fā)生的不確定性與事件發(fā)生的概率q(x)有關(guān)，概率越小，不確定

2、性越大。定義I(x)=-logq(x)。熵（平均自信息量）：實(shí)際信源包含許多消息X=(x1,x2, )，因此需要考慮整個(gè)信源自信息量的統(tǒng)計(jì)平均值。無記憶信源的平均自信息量定義為各消息自信息量的概率加權(quán)平均值，即平均自信息量H(X) 定義為H(X)=-，簡(jiǎn)稱熵。H(X) 是唯一確定集合X 中任一事件所需要的平均信息量， 反應(yīng)了X 中事件出現(xiàn)的平均不確定性。三、實(shí)驗(yàn)結(jié)果四、實(shí)驗(yàn)結(jié)果分析由圖可知， I(x) 是 p 的單調(diào)遞減函數(shù)，概率小的事件一旦發(fā)生則賦予的信息量大，概率大的事件如果發(fā)生則賦予的信息量小。當(dāng) p=1 時(shí)， I(x)=0 ，表示確定事件發(fā)生得不到任何信息。當(dāng) p=0 時(shí)， I(x)

3、，表示不可能事件一旦發(fā)生，信息量將無窮大。由圖可知，對(duì)于二元信源， p=0 或者 p=1 都對(duì)應(yīng)確定事件的分布，因此熵值 H(X) 為 0，而等概分布時(shí)，熵值H(X) 取最大值為 1。五、實(shí)驗(yàn)總結(jié)通過這次實(shí)驗(yàn)，使用 Matlab 數(shù)值模擬信源熵和自信息量，進(jìn)一步理解了自信息量和熵的概念、 計(jì)算和它們的物理意義。 理論和實(shí)踐的結(jié)合讓我對(duì)這個(gè)知識(shí)點(diǎn)了解得更加深刻。實(shí)驗(yàn)二準(zhǔn)對(duì)稱信道容量一、實(shí)驗(yàn)要求畫出強(qiáng)對(duì)稱信道容量數(shù)值模擬圖。二、實(shí)驗(yàn)原理及理論分析信道是信息傳輸?shù)耐ǖ馈?信道可以按不同得特性進(jìn)行分類，根據(jù)輸入輸出信號(hào)得特點(diǎn)可以分為以下四類：離散信道、連續(xù)信道、半連續(xù)信道、波形信道。根據(jù)統(tǒng)計(jì)特性，即轉(zhuǎn)

4、移概率得不同，信道又分為無記憶信道和有記憶信道兩類。強(qiáng)對(duì)稱信道是一種常見的離散無記憶信道，每一子集關(guān)于行、 列都對(duì)稱， 它的輸入符號(hào) x 0 ，1 ，輸出符號(hào) y0 ，1 ，信道特性可表示為信道矩陣。信道轉(zhuǎn)移概率 p(y=0|x=0)=p(y=1|x=1)=1-p,p(y=1|x=0)=p(y=0|x=1)=p。強(qiáng)對(duì)稱信道的容量計(jì)算公式：三、實(shí)驗(yàn)結(jié)果四、實(shí)驗(yàn)結(jié)果分析由圖可知， p=0 時(shí)，信道的輸入符號(hào)和輸出符號(hào)是一一對(duì)應(yīng)的關(guān)系，此時(shí)信道容量 C=log2，達(dá)到最大值。 p=0.5 時(shí)，信道的不確定性最大，此時(shí)信道容量C=0，這是一種最差的信道。p=1 時(shí)，這是一種強(qiáng)噪信道，也是一種確定信道，

5、此時(shí)信道容量也會(huì)達(dá)到最大值C=log2。五、實(shí)驗(yàn)總結(jié)通過 Matlab 數(shù)值模擬強(qiáng)對(duì)稱信道容量，觀察最高點(diǎn)最低點(diǎn)，加深了對(duì)強(qiáng)對(duì)稱信道這一類特殊信道的理解，驗(yàn)證了理論計(jì)算的正確性。實(shí)驗(yàn)三費(fèi)諾不等式一、實(shí)驗(yàn)要求畫出費(fèi)諾不等式示意圖，以H(X|Y) 為縱坐標(biāo)， Pe 為橫坐標(biāo)，畫出函數(shù)H(Pe)+Pelog(r-1)隨 Pe 變化的曲線圖，標(biāo)注logr 點(diǎn)以及 log(r-1)點(diǎn)。二、實(shí)驗(yàn)原理及理論分析設(shè)信道輸入符號(hào)X 和輸出符號(hào) Y 取自同一符號(hào)集A=，則傳輸過程中的錯(cuò)誤概率 Pe 和信道疑義度 H(X|Y) 之間滿足下列關(guān)系式， 也即著名的費(fèi)諾不等式：費(fèi)諾不等式的物理意義：進(jìn)行一次判決后，關(guān)于1

6、、X 的疑義度可分為兩項(xiàng)：是否判對(duì)，疑義度為；2、如果判決出錯(cuò)（概率為），錯(cuò)在k-1個(gè)符號(hào)中的哪一個(gè)？疑義度不會(huì)超過log(k-1) 。三、實(shí)驗(yàn)結(jié)果四、實(shí)驗(yàn)結(jié)果分析根據(jù)極大離散熵定理，信源的消息個(gè)數(shù)為M ，則 H(X) logM ，等號(hào)當(dāng)且僅當(dāng)信源 X 中各消息等概時(shí)成立。如圖所示，各消息等概分布時(shí)，信道疑義度即信源熵最大為log(r) 。如圖所示，當(dāng)錯(cuò)誤概率為1 時(shí)，判決出錯(cuò)，錯(cuò)誤發(fā)生在k-1 個(gè)符號(hào)中，疑義度最大為log(k-1) 。五、實(shí)驗(yàn)總結(jié)使用Matlab模擬時(shí)，和的值不能直接取到0 和1，這樣圍不成一個(gè)封閉區(qū)域，和可以取到兩個(gè)無限接近0 和1 的值。很好地掌握極大離散熵定理是理解費(fèi)

7、諾不等式的基礎(chǔ)。實(shí)驗(yàn)四香農(nóng)編碼一、實(shí)驗(yàn)要求1、根據(jù)香農(nóng)編碼的方法和步驟，編寫香農(nóng)編碼程序，得到碼字和編碼效率；2、用編寫的源程序驗(yàn)證書中例題的正確性，并用圖表示碼長(zhǎng)結(jié)果。二、實(shí)驗(yàn)原理及理論分析香農(nóng)編碼法是一種常用的變長(zhǎng)編碼法， 對(duì)于證明變長(zhǎng)編碼定理起了很重要的作用。香農(nóng)編碼具體步驟如下：1、將信源發(fā)出的M個(gè)消息，按其概率遞減順序進(jìn)行排列，得;2、計(jì)算出各消息的 -log值， m=1，2， M;3、根據(jù)：為整數(shù)時(shí)取等。計(jì)算出每個(gè)消息的二進(jìn)制代碼的長(zhǎng)度(m=1,2,M) ，取正整數(shù)；4、為得到唯一可譯碼，計(jì)算出第m 個(gè)消息的累加概率，再將變換成二進(jìn)制小數(shù)，取小數(shù)點(diǎn)后面位作為第m 個(gè)消息的碼字。三、

8、實(shí)驗(yàn)結(jié)果四、程序流程圖開始代碼初始化否判斷信源是否合法重新輸入是按遞減順序排列，并計(jì)算累加概率計(jì)算碼字長(zhǎng)度k十進(jìn)制小數(shù)轉(zhuǎn)二進(jìn)制小數(shù)取小數(shù)點(diǎn)后k位作為碼字順序重排計(jì)算平均碼長(zhǎng)、信源熵、編碼效率結(jié)束五、實(shí)驗(yàn)結(jié)果分析香農(nóng)編碼嚴(yán)格意義上來說不是最佳碼，它是采用信源符號(hào)的累計(jì)概率分布函數(shù)來分配碼字。 從結(jié)果中可以看出， 香農(nóng)編碼法中， 碼符號(hào)概率大的用短碼表示，概率小的是用長(zhǎng)碼表示。香農(nóng)編碼的編碼效率并不是特別高。六、實(shí)驗(yàn)總結(jié)和后面兩種編碼方法相比， 香農(nóng)編碼的效率不高， 實(shí)用性不大。 按照香農(nóng)編碼方法編出來的碼， 其平均碼長(zhǎng)不是最短的， 不是最佳碼。 但是對(duì)其他編碼方法有很好的理論指導(dǎo)意義，所以我們也

9、應(yīng)該掌握。實(shí)驗(yàn)五費(fèi)諾編碼一、實(shí)驗(yàn)要求1、根據(jù)費(fèi)諾編碼的方法和步驟編寫費(fèi)諾編碼程序，得到碼字和編碼效率；2、用編寫的源程序驗(yàn)證書中例題的正確性，并用圖表示碼長(zhǎng)結(jié)果。二、實(shí)驗(yàn)原理及理論分析香農(nóng)第一定理的物理意義闡明：信源等概分布時(shí)， 信息傳輸率最大， 應(yīng)用到對(duì)信源進(jìn)行編碼， 應(yīng)使編碼后的碼集盡可能等概分布，如果將該碼集看成一個(gè)新的信源，這時(shí)新信源所包含的信息量最大。據(jù)此，產(chǎn)生了費(fèi)諾編碼法。費(fèi)諾編碼法的具體步驟如下：1、將信源發(fā)出的M個(gè)消息，按其概率遞減順序進(jìn)行排列，得，把消息集按其概率大小分解成兩個(gè)子集，使兩個(gè)子集的概率之和盡可能相等，把第一個(gè)子集編碼為“ 0”，第二個(gè)子集編碼為“ 1”，作為代碼

10、組的第一個(gè)碼元；2、對(duì)子集做第二次分解，同樣分解成兩個(gè)子集，并使兩個(gè)子集的概率之和盡可能接近相等，再把第一個(gè)子集編碼為“0”，第二個(gè)子集編碼為“ 1”，作為代碼組的第二個(gè)碼元；3、如此一直進(jìn)行下去，直到各子集僅含一個(gè)消息為止；4、將逐次分解過程當(dāng)中得到的碼元排列起來就是各消息的代碼。三、實(shí)驗(yàn)結(jié)果四、程序流程圖開始代碼初始化否判斷信源是否合法重新輸入是按概率遞減順序排列否判斷信源個(gè)數(shù)是否大于2是累加求和，確定分組后每組概率累加和盡可能相近第一組的信源碼字加0 ，第二組的信源碼字加1判斷分組點(diǎn)是不是第一個(gè)編號(hào)是分組點(diǎn)為新分組的第一個(gè)編號(hào)，其他依次編號(hào)否是分組點(diǎn)為新分組的最后一判斷分組點(diǎn)是不是該組倒

11、數(shù)第二個(gè)個(gè)編號(hào)，其他編號(hào)不變否以分組點(diǎn)為界，重新編號(hào)分為兩組計(jì)算平均碼長(zhǎng)、信源熵、編碼效率結(jié)束五、實(shí)驗(yàn)結(jié)果分析從結(jié)果中可以看出來，費(fèi)諾編碼法中，碼符號(hào)概率大的，分解次數(shù)小；碼符號(hào)概率小的， 分解次數(shù)大。 這種編碼方法不一定能使短碼得到充分利用。尤其當(dāng)信源符號(hào)較多， 并且有一些符號(hào)概率分布很接近時(shí)，分兩大組的組合方法就很多?？赡艽嬖谀撤N分配結(jié)果， 會(huì)出現(xiàn)后面分組的概率和相差較遠(yuǎn)，因而使平均碼長(zhǎng)增加，所以費(fèi)諾編碼不一定是最佳碼。六、實(shí)驗(yàn)總結(jié)費(fèi)諾編碼方法不唯一，費(fèi)諾編碼適合于對(duì)分組概率相等或相近的信源編碼，費(fèi)諾編碼法編M 進(jìn)制碼， M 越大，信源的符號(hào)數(shù)越多，可能的編碼方式就越多，編碼過程就越復(fù)雜，

12、當(dāng)信源符號(hào)個(gè)數(shù)越多，編碼效率就越低。實(shí)驗(yàn)六霍夫曼編碼一、實(shí)驗(yàn)要求1、根據(jù)霍夫曼編碼的方法和步驟，編寫霍夫曼編碼程序，得到碼字和編碼效率；2、用編寫的源程序驗(yàn)證書中例題3.18 的正確性，通過碼長(zhǎng)均值和均方差結(jié)果比較兩種霍夫曼編碼方法（用圖形表示）。二、實(shí)驗(yàn)原理及理論分析霍夫曼編碼法的具體步驟如下：以 M 個(gè)消息的 D 進(jìn)制編碼為例1、計(jì)算 M+r=D+m(D-1) ，m 為整數(shù)， r 為滿足等式的最小正整數(shù)；2、若 r 0，添加 r 個(gè)概率為 0 的信源消息；3、將信源的 M+r 個(gè)消息按概率遞減順序排列；4、將概率最小的 D 個(gè)消息分別編碼為D-1，D-2， 1，0；5、將上述 D 個(gè)消息合

13、并，求概率之和，并與余下的消息組成一個(gè)新的信源，再按概率遞減順序重新排列。如果概率之和與某個(gè)消息的概率相等，應(yīng)把合并消息排在上面，這樣可使合并消息重復(fù)編碼的次數(shù)減少，使短碼得到充分利用；6、重復(fù)步驟 4、 5，直到合并消息的概率之和為1；7、從最后一步開始，沿編碼逆過程取各步驟得到的碼符號(hào)，如此構(gòu)成的碼符號(hào)序列即為對(duì)應(yīng)消息的碼字。r 個(gè) 0 消息是人為添加的，不需要取碼符號(hào)。三、實(shí)驗(yàn)結(jié)果四、程序流程圖開始代碼初始化否判斷信源是否合法重新輸入是否判斷信源個(gè)數(shù)是否大于2是按遞減順序排列，并將概率最小的兩個(gè)編號(hào)為1，2將概率最小的兩個(gè)加起來，和其他的一起作為一個(gè)新信源重新按遞減順序排列，概率相同的向上排/ 向下排計(jì)算平均碼長(zhǎng)、方差、碼長(zhǎng)是均方差、信源熵、編碼效率結(jié)束五、實(shí)驗(yàn)結(jié)果分析因?yàn)樵?Matlab 中，首位的 0 會(huì)被自動(dòng)省略，不適合編碼。所以這里利用 1，2 進(jìn)行編碼。從結(jié)果中可以看出，每次縮減信源的最后兩個(gè)碼字總是最后一位碼元不同，前面各位碼元相同?；舴蚵幋a法中， 概率小的消息碼長(zhǎng)更大， 概率大的消息碼長(zhǎng)更小。 可以看出霍夫曼編碼法得到的碼并不是唯一的， 因?yàn)閷?duì)于每次選出的兩個(gè)消息， 哪個(gè)編碼為“ 1”，哪個(gè)編碼為“ 0”是可以任意選取的，由此可以得到不同的編碼，而且平均碼長(zhǎng)是不會(huì)變的。新組成的概率之和和原信源中的某概率相等時(shí)，將新組成的概率之和往上排和往下排，