1、信息論與編碼實驗指導書鄒東堯 等編計算機與通信工程學院 信息與通信工程系2010年10月緒 論隨著信息產業的飛速發展，對從事信息、通信、電子工程類等專業的人員的要求也越來越高，而信息論與編碼是這類專業的專業必修課，這門課主要介紹了有關信息論的基本原理以及信源編碼、信道編碼的內容。通過理論與實踐的結合，才能更好的領會知識的真諦。信息論與編碼結合實驗的實踐，讓學生更能深刻的理解和掌握這門課的基本概念、基本理論，并培養學生的動手實踐能力。本實驗指導書正是配合教學計劃的實驗教學而編寫，主要是基于matlab仿真軟件對信源編解碼和信道容量進行仿真。本書共有三個實驗：繪制信源熵函數曲線、哈夫曼編解碼和離散

2、信道容量，為實驗大綱要求的必做實驗。本書主要由鄒東堯編寫，主要參考了李祖賀等編寫的信息論與編碼實驗指導書，并得到了李祖賀等老師的大力支持，特此對他們表示衷心的感謝！由于時間倉促，錯誤難免，懇請讀者諒解和指正！鄭州輕工業學院計算機與通信工程學院信息與通信工程系2010年10月目 錄實驗一 繪制信源熵函數曲線4實驗二 哈夫曼編解碼7實驗三 離散信道容量131 實驗一 繪制信源熵函數曲線一、實驗目的1. 掌握離散信源熵的原理和計算方法。2. 熟悉matlab軟件的基本操作，練習應用matlab軟件進行信源熵函數曲線的繪制。3. 理解信源熵的物理意義，并能從信源熵函數曲線圖上進行解釋其物理意義。二、實

3、驗原理1. 離散信源相關的基本概念、原理和計算公式產生離散信息的信源稱為離散信源。離散信源只能產生有限種符號。假定X是一個離散隨機變量，即它的取值范圍R=x1，x2，x3，是有限或可數的。設第i個變量xi發生的概率為pi=PX=xi。則：定義一個隨機事件的自信息量I（xi）為其對應的隨機變量xi出現概率對數的負值。即：I（xi）= -log2 p(xi)定義隨機事件X的平均不確定度H（X）為離散隨機變量xi出現概率的數學期望，即：單位為 比特/符號 或 比特/符號序列。平均不確定度H（X）的定義公式與熱力學中熵的表示形式相同，所以又把平均不確定度H（X）稱為信源X的信源熵。 必須注意一下幾點：

4、a) 某一信源，不管它是否輸出符號，只有這些符號具有某些概率特性，必有信源的熵值；這熵值是在總體平均上才有意義，因而是個確定值，一般寫成H（X），X是指隨機變量的整體（包括概率分布）。b) 信息量則只有當信源輸出符號而被接收者收到后，才有意義，這就是給與信息者的信息度量，這值本身也可以是隨機量，也可以與接收者的情況有關。c) 熵是在平均意義上來表征信源的總體特征的，信源熵是表征信源的平均不確定度，平均自信息量是消除信源不確定度時所需要的信息的量度，即收到一個信源符號，全部解除了這個符號的不確定度。或者說獲得這么大的信息量后，信源不確定度就被消除了。信源熵和平均自信息量兩者在數值上相等，但含義不

5、同。d) 當某一符號xi的概率p(xi)為零時，p(xi)log p(xi) 在熵公式中無意義，為此規定這時的 p(xi)log p(xi) 也為零。當信源X中只含有一個符號x時，必有p(x)=1，此時信源熵H（X）為零。例1-1，設信源符號集X=0，1，每個符號發生的概率分別為p(0)=p，p(1)=q，p+ q=1，即信源的概率空間為則該二元信源的信源熵為：H(X) = - p log p q log q = - p log p (1- p) log (1- p) 即：H (p) = - p log p (1- p) log (1- p) 其中0 p 1P=0時，H(0) = 0P=1時，

6、H(1) = 02. MATLAB二維繪圖例對函數y= f(x)進行繪圖，則用matlab中的命令plot(x, y)就可以自動繪制出二維圖來。如果打開過圖形窗口，則在最近打開的圖形窗口上繪制此圖；如果未打開圖形窗口，則開一個新的圖形窗口繪圖。例1-2，在matlab上繪制余弦曲線圖，y = cos x，其中0 x 2p。x=0:0.1:2*pi； %生成橫坐標向量，使其為0，0.1，0.2，6.2y=cos(x)； %計算余弦向量plot(x,y) %繪制圖形三、實驗內容用matlab軟件繪制二源信源熵函數曲線。根據曲線說明信源熵的物理意義。四、實驗要求1. 提前預習實驗，認真閱讀實驗原理以

7、及相應的參考書。2. 認真高效的完成實驗，實驗中服從實驗室管理人員以及實驗指導老師的管理。3. 認真填寫實驗報告。2 實驗二 哈夫曼編碼一、實驗目的1. 掌握哈夫曼編碼的原理及編碼步驟2. 練習matlab中哈夫曼編碼函數的調用及通信工具箱的使用二、實驗原理通信的根本問題是如何將信源輸出的信息在接收端的信宿精確或近似的復制出來。為了有效地復制信號，就通過對信源進行編碼，使通信系統與信源的統計特性相匹配。若接收端要求無失真地精確地復制信源輸出的信息，這樣的信源編碼即為無失真編碼。即使對于一個小的時間段內，連續信源輸出的信息量也可以是無限大的，所以對其是無法實現無失真編碼的；而離散信源輸出的信息量

8、卻可以看成是有限的，所以只有離散信源才可能實現無失真編碼。凡是能載荷一定的信息量，且碼字的平均長度最短，可分離的變長碼的碼字集合都可以稱為最佳碼。為此必須將概率大的信息符號編以短的碼字，概率小的符號編以長的碼字，使得平均碼字長度最短。變字長編碼的最佳編碼定理：在變字長碼中，對于概率大的信息符號編以短字長的碼；對于概率小的信息符號編以長字長的碼。如果碼字長度嚴格按照符號概率的大小順序排列，則平均碼字長度一定小于俺任何順序排列方式得到的碼字長度。哈夫曼編碼就是利用了這個定理，講等長分組的信源符號，根據其概率分布采用不等長編碼。概率大的分組，使用短的碼字編碼；概率小的分組，使用長的碼字編碼。哈夫曼編

9、碼把信源按概率大小順序排列，并設法按逆次序分配碼字的長度。在分配碼字的長度時，首先將出現概率最小的兩個符號相加，合成一個概率；第二步把這個合成的概率看成是一個新組合符號的概率，重復上述做法，直到最后只剩下兩個符號的概率為止。完成以上概率相加順序排列后，再反過來逐步向前進行編碼。每一步有兩個分支，各賦予一個二進制碼，可以對概率大的編為0碼，概率小的編為1碼。反之亦然。哈夫曼編碼的具體步驟歸納如下：1. 統計n個信源消息符號，得到n個不同概率的信息符號。2. 將這n個信源信息符號按其概率大小依次排序： p(x1) p(x2) p(xn)3. 取兩個概率最小的信息符號分別配以0和1兩個碼元，并將這兩

10、個概率相加作為一個新的信息符號的概率，和未分配的信息符號構成新的信息符號序列。4. 將剩余的信息符號，按概率大小重新進行排序。5. 重復步驟3，將排序后的最后兩個小概論相加，相加和與其他概率再排序。6. 如此反復重復n-2次，最后只剩下兩個概率。7. 從最后一級開始，向前返回得到各個信源符號所對應的碼元序列，即相應的碼字，構成霍夫曼編碼字。編碼結束。哈夫曼編碼產生最佳整數前綴碼，即沒有一個碼字是另一個碼字的前綴，因此哈夫曼編碼是唯一碼。編碼之后，哈夫曼編碼的平均碼長為：哈夫曼編碼的效率為：例2-1 設信源共7個符號消息，其概率如下表所示信源消息符號xix1x2x3x4x5x6x7符號概率P（

11、xi ）0.200.190.180.170.150.100.01其編碼過程如下所示：該哈夫曼碼的平均碼長為編碼效率為：三、實驗內容為某一信源進行哈夫曼編碼。該信源的字符集為X=x1, x2, x6 ，相應的概率矢量為：P=(0.30,0.25,0.21,0.10,0.09,0.05)，即X，P的概率空間為：根據哈夫曼編碼算法對該信源進行哈夫曼編碼。并計算其平均碼長和編碼效率。調用matlab哈夫曼編碼函數進行哈夫曼編碼，與人工編碼結果做比較。1. huffmandict函數： 為已知概率分布的信源模型生成哈夫曼編解碼索引表。調用方法如下：dict，avglen = huffmandict (s

12、ymbols, p)dict，avglen = huffmandict (symbols, p, N)dict，avglen = huffmandict (symbols, p, N, variance)四、實驗要求1. 提前預習實驗，認真閱讀實驗原理以及相應的參考書。2. 認真高效的完成實驗，實驗中服從實驗室管理人員以及實驗指導老師的管理。3. 認真填寫實驗報告。3 實驗三 離散信道容量一、實驗目的1. 掌握離散信道容量的計算。2. 理解離散信道容量的物理意義。3. 練習應用matlab軟件進行二元對稱離散信道容量的函數曲線的繪制，并從曲線上理解其物理意義。二、實驗原理信道是傳送信息的載體信

13、號所通過的通道。信息是抽象的，而信道則是具體的。比如二人對話，二人間的空氣就是信道；打電話，電話線就是信道；看電視，聽收音機，收、發間的空間就是信道。研究信道的目的：在通信系統中研究信道，主要是為了描述、度量、分析不同類型信道，計算其容量，即極限傳輸能力，并分析其特性。二元對稱信道BSC（Binary Symmetric Channel）二進制離散信道模型有一個允許輸入值的集合X=0，1和可能輸出值的集合Y=0，1，以及一組表示輸入和輸出關系的條件概率（轉移概率）組成。如果信道噪聲和其他干擾導致傳輸的二進序列發生統計獨立的差錯，且條件概率對稱，即這種對稱的二進制輸入、二進制輸出信道稱做二元對稱信道（或二進制對稱信道，簡稱BSC信道）