信息論與編碼實驗報告

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

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

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

4、移概率得不同，信道又分為無記憶信道和有記憶信道兩類。強對稱信道是一種常見的離散無記憶信道，每一子集關于行、 列都對稱， 它的輸入符號 x 0 ，1 ，輸出符號 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。強對稱信道的容量計算公式：三、實驗結(jié)果四、實驗結(jié)果分析由圖可知， p=0 時，信道的輸入符號和輸出符號是一一對應的關系，此時信道容量 C=log2，達到最大值。 p=0.5 時，信道的不確定性最大，此時信道容量C=0，這是一種最差的信道。p=1 時，這是一種強噪信道，也是一種確定信道，

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

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

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

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

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

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

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

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

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