信息論大復習(2010-5-31)

1、總復習2010-5-31信息論基礎考試題型A卷：一、判斷題（每小題2分，共30分）二、填空題（每小題3分，共30分）三、計算題（前5題每小題6分，第6題10分，共40分）B卷：一、判斷題（每小題1分，共15分）二、填空題（每小題3分，共15分）三、計算題（每小題10分，共70分）第一章 緒論主要內容： 信息 通信系統(tǒng)模型 信息論的形成和發(fā)展 信息論的應用 信息論的數(shù)學基礎1.1 信息信息論也叫做“通信的數(shù)學理論”，是應用近代數(shù)理統(tǒng)計方法研究信息的傳輸、存儲與處理的科學。迄今為止，信息并沒有形成一個很完整的系統(tǒng)的概念。信息和消息并不是一回事，不能等同。物質、能量和信息是構成客觀世界的三大要素。信

2、息必須依附于一定的物質形式，如文字、聲波、電磁波等。這種運載信息的物質，稱為信息的載體。一切物質都有可能成為信息的載體。概率信息、香農信息、狹義信息。信息表征信源的不確定度，但它不等同于不確定度，而是為了消除一定的不確定度必須獲得與此不確定度相等的信息量。信息的性質：（1）信息是無形的；（2）信息是可共享的；（3）信息是無限的；（4）信息是可度量的。數(shù)據(jù)是指能夠被計算機處理的數(shù)字、字母和符號等具有一定意義的實體。信號是數(shù)據(jù)在信道中傳輸時的具體表現(xiàn)形式，一般表現(xiàn)為電信號。信息可通過兩種方式被發(fā)送：模擬方式和數(shù)字方式，這兩種方式均使用電壓產生相應的信號。1948年，香農在 “貝爾系統(tǒng)技術”雜志上發(fā)

3、表了兩篇有關“通信的數(shù)學理論”的論文，在這兩篇論文中，他用概率測度和數(shù)理統(tǒng)計的方法，系統(tǒng)地討論了通信的基本問題，得出了幾個重要的帶有普遍意義的結論，并由此奠定了現(xiàn)代信息論的基礎。在香農信息論的指導下，為提高通信系統(tǒng)信息傳輸?shù)挠行院涂煽啃裕藗冊谛旁淳幋a和信道編碼兩個領域進行了卓有成效的研究，取得了豐碩的成果。1952年Fano證明了Fano不等式，給出了shannon信道編碼逆定理的證明;1957，Wolfowitz，1961 Fano，1968 Gallager給出信道編碼定理的簡潔證明并描述了碼率、碼長和錯誤概率的關系，1972年Arimoto和Blahut提出了信道容量的迭代算法;19

4、56 McMillan證明了Kraft不等式;1952年Fano碼，Huffman碼;1976 Rissanen算術編碼;1977，78 Ziv和Lempel的LZ算法;1950年漢明碼;1960年卷積碼的概率譯碼，Viterbi譯碼;1982年Ungerboeck編碼調制技術;1993年Turbo編譯碼技術;1959年，Shannon提出率失真函數(shù)和率失真信源編碼定理;1961年，Shannon的“雙路通信信道”開拓了網(wǎng)絡信息論的研究，目前是非?；钴S的研究領域。信息論的數(shù)學基礎主要是概率論其次是微積分和線性代數(shù)概 率 概率是從隨機試驗中的事件到實數(shù)域的函數(shù)，用以表示事件發(fā)生的可能性。如果用P

5、(A)作為事件A 的概率，是試驗的樣本空間，則概率函數(shù)必須滿足如下公理：公理1：P(A) 0 公理2：P() = 1公理3：如果對任意的i 和j ( i j )，事件Ai 和Aj 不相交( AiAj)，則有：條件概率如果A 和B 是樣本空間上的兩個事件，P(B)0，那么在給定B 時A 的條件概率P(A|B) 為：條件概率P(A|B) 給出了在已知事件B 發(fā)生的情況下，事件A 發(fā)生的概率。一般地，P(A|B) P(A)。全概率公式設為試驗E 的樣本空間，B1, B2, ， Bn 為 的一組事件，且它們兩兩互斥，且每次試驗中至少發(fā)生一個。即：則稱B1、B2、 Bn 為樣本空間的一個劃分。全概率公式

6、設A為 的事件，B1, B2, , Bn 為的一個劃分，且P(Bi)0 (i=1, 2, , n)，則全概率公式為：設A、B為任意兩個事件，則：P(A+B)=P(A)+P(B)-P(AB)P(A+B+C+D)= ?概率的一般加法公式貝葉斯法則如果A 為樣本空間 的事件，B1，B2，Bn 為 的一個劃分，且P(A) 0，P(Bi) 0 ( I = 1， 2， ，n ) ，那么：貝葉斯法則的意義 貝葉斯公式給出了“結果”事件A已發(fā)生的條件下，“原因”事件B的條件概率。對結果事件的任何觀測都將增加我們對原因事件B的真正分布的知識。期 望期望值是一個隨機變量所取值的概率平均。設X為一隨機變量，其分布為

7、：P（X=xk）=pk，k=1，2，。若級數(shù) 絕對收斂，那么隨機變量X的數(shù)學期望或概率平均值為：方 差 一個隨機變量的方差描述的是該隨機變量的值偏離其期望值的程度。設X為一隨機變量，其方差為：正態(tài)分布記作 思考題1 一個班上有30個學生，至少有兩人生日相同的概率是多少？40個人呢？80個人呢？120個人呢？有4個球，外形一模一樣，其中有一個是假球，重量和真球不同，但是不知道比真球重還是輕，問：能否用沒有砝碼的天平稱兩次，將假球找出來，并判斷假球比真球重還是輕？思考題有一名學生參加北京郵電大學碩士研究生考試，已經通過全國復試線。獲得北郵復試資格的概率是20%。如果未獲北郵復試資格，該生同時調劑南

8、京郵電大學和重慶郵電大學，獲得復試資格的概率分別是40%和60%，那么該生能夠獲得復試資格的概率是多少？4 在空戰(zhàn)中甲機先向乙機開火，擊中的概率是0.2；若乙機未被擊中，就進行還擊，擊中甲機的概率是0.3；若甲機未被擊中，則再進攻乙機，擊中的概率是0.2。求在這幾個回合中： 1）甲機被擊中的概率； 2）乙機被擊中的概率。 如果不停射來射去，直到一方被擊中，概率各為多少？ 如果甲機和乙機的命中率都是0.1,不停射來射去，直到一方被擊中，概率各為多少？說明什么道理?思 考 題5 從（0，1）中任取兩個數(shù)，求： 1）兩數(shù)之和小于1.2的概率； 2）兩數(shù)之積小于1/4的概率。6 有2n名棋手參加象棋比

9、賽，隨機分為兩個組，問最強的兩名棋手分到不同組的概率是多少？思考題思考題7 甲乙兩人棋藝水平相當，參加象棋對抗賽。設立獎金1000元，規(guī)定誰先贏三盤誰獲得全部獎金?，F(xiàn)兩人下了三盤因故未下，比賽結果甲兩勝一負。問這1000元獎金應該如何分配？（注：和棋不計）8 甲乙兩人棋藝水平相當，參加象棋對抗賽。設立獎金1000元，規(guī)定誰多贏三盤誰獲得全部獎金?，F(xiàn)兩人下了三盤因故未下，比賽結果甲兩勝一負。問這1000元獎金應該如何分配？（注：和棋不計）思考題9 有12個球，外形一模一樣，其中有一個是假球，重量和真球不同，但是不知道比真球重還是輕，問：能否用沒有砝碼的天平稱三次，將假球找出來，并判斷假球比真球重

10、還是輕？思考題10 有100個龍，101個鳳，102個凰，它們兩兩相碰 時自身消失而生成另一種動物，例如一個龍和 一個鳳相碰后消失，生成一個凰，但同種動物 相碰不發(fā)生任何改變。問： （1）最后剩下哪種動物？（小學程度） （2）分別剩下多少個？（中學程度） （3）概率分別是多少？（大學程度）自信息和條件自信息量香農注意到：收信者在收到消息之前是不知道消息的具體內容的。通信系統(tǒng)消息的傳輸對收信者來說，是一個從不知到知的過程，或者從知之甚少到知之甚多的過程，或是從不確定到部分確定或全部確定的過程。因此，對于收信者來說，通信過程是消除事物狀態(tài)的不確定性的過程，不確定性的消除，就獲得了信息，原先的不確定

11、性消除的越多，獲得的信息就越多；“信息”是事物運動狀態(tài)或存在方式的不確定性的度量，這就是香農關于信息的定義。信息的度量（自信息量）和不確定性消除的程度有關，消除了多少不確定性，就獲得了多少信息量；不確定性就是隨機性，可以用概率論和隨機過程來測度不確定性的大小，出現(xiàn)概率小的事件，其不確定性大，反之，不確定性??；由以上兩點可知：概率小 信息量大，即信息量是概率的單調遞減函數(shù)；自信息量自信息量由于信息量具有如下性質：（1）概率小的事件一旦發(fā)生，賦予的信息量大，概率大的事件如果發(fā)生，則賦予的信息量小；（2）信息量應具有可加性：對于兩個獨立事件，其信息量應等于各事件自信息量之和；（3）確定事件發(fā)生得不到

12、任何信息；（4）不可能事件一旦發(fā)生，信息量將無窮大。自信息量于是，可以證明，信息量的計算式為： 其中Pk是事件Xk發(fā)生的概率，這也是香農關于(自)信息量的度量(概率信息)；自信息量 I(xk) 的含義：當事件 xk發(fā)生以前，表示事件xk發(fā)生的不確定性；當事件 xk發(fā)生以后，表示事件xk所提供的信息量；自信息量自信息量的單位：自信息量的單位取決于對數(shù)的底；底為a = 2，單位為“比特（bit）”底為a = e，單位為“奈特（nat）”底為a = 10，單位為“哈特（hart）”1 nat = 1.44 bit 1 hart = 3.32 bit互信息和條件互信息定義：對兩個離散隨機事件集X和Y，

13、事件 的出現(xiàn)給出關于事件 的信息量，定義為互信息量。其定義式為：由上式又可以得到：互信息量的性質性質1 互信息量的互易性：性質2 互信息量可為零：當事件 ， 統(tǒng)計獨立時，互信息量為零?；バ畔⒘康男再|性質3 互信息量可正可負。 當后驗概率大于先驗概率時，互信息量為正值； 當后驗概率小于先驗概率時，互信息量為負值。性質4 任何兩個事件之間的互信息量不可能大于其中任一事件的自信息。（根據(jù)定義得出）離散集的平均自信息 通常研究單獨一個事件或單獨一個符號的信息量是不夠的，往往需要研究整個事件集合或符號序列(如信源)的平均信息量(總體特征)，這就需要引入新的概念。信息熵（平均自信息 ）假設離散事件集合的概

14、率特性由以下數(shù)學模型表示： 則如果將自信息量看為一個隨機變量，其平均信息量為自信息量的數(shù)學期望，其定義為：熵的計算例1：設某信源輸出四個符號，其符號集合的概率分布為： 則其熵為：熵的含義熵是從整個集合的統(tǒng)計特性來考慮的，它是從平均意義上來表征集合的總體特征的。 熵表示事件集合中事件發(fā)生后，每個事件提供的平均信息量；熵表示事件發(fā)生前，集合的平均不確定性。例2：有2個集合，其概率分布分別為： 分別計算其熵，則：H(X)=0.08 bit /符號， H(Y)=1 bit / symbol例3：等概信源H(X) = -0.5log 0.5 - 0.5log0.5 = 1（ bit / symbol ）

15、例4： 等概信源H(X) = -40.25log0.25 = log4 = 2（ bit / symbol ）熵函數(shù)的數(shù)學特性對稱性：熵函數(shù)對每個Pk 對稱的。該性質說明熵只與隨機變量的總體結構有關，與事件集合的總體統(tǒng)計特性有關；非負性：H0；擴展性：當某事件Ek的概率Pk稍微變化時，H函數(shù)也只作連續(xù)的不突變的變化；熵函數(shù)的數(shù)學特性可加性：設有一事件的完全集合E1,E2,En,其熵為H1(p1，p2，pn)?，F(xiàn)設其中一事件En又劃分為m個子集，即： 這時構成的三個概率空間分別具有熵函數(shù)： 這說明對集合的進一步劃分會使它的不確定性增加，即熵總是往大增加。熵函數(shù)的數(shù)學特性極值性：即當所有事件等概率

16、出現(xiàn)時，平均不確定性最大，從而熵最大，即：熵函數(shù)的數(shù)學特性確定性，即： H(1，0) = H(1，0，0) = H(1，0，0，0) = 0 即當某一事件為確定事件時，整個事件集的熵為0；上凸性。實際應用有4個球，外形一模一樣，其中有一個是假球，重量和真球不同，但是不知道比真球重還是輕，問：能否用沒有砝碼的天平稱兩次，將假球找出來，并判斷假球比真球重還是輕？ 試用信息熵的概念加以解釋。一個更復雜的例子有12個球，外形一模一樣，其中有11個是真球，重量相等，有1個假球，與真球重量不同（但不知道究竟比真球重還是輕）。 問：能否用沒有砝碼的天平稱三次，將假球找出來，并判斷出假球比真球重還是輕。 試用

17、信息熵的概念加以解釋。條件熵定義：條件熵是在聯(lián)合符號集XY上的條件自信息的數(shù)學期望。在已知Y時，X的條件熵為：在已知X時，Y的條件熵為：條件熵信道疑義度H(X/Y )表示信宿在收到Y 后，信源X 仍然存在的不確定度。是通過有噪信道傳輸后引起的信息量的損失，是傳輸失真造成的，故也可稱為損失熵。存在以下兩種極端情況：（1）對于無噪信道，H (XY ) = 0（2）在強噪聲情況下，收到的Y 與X 毫不相干，可視為統(tǒng)計獨立：H (XY ) = H (X ) 噪聲熵H(Y/X )表示在已知X 的條件下，對于符號集Y 尚存在的不確定性（疑義），這完全是由于信道中噪聲引起的。存在以下兩種極端情況：（1）對于

18、無擾信道，有H (YX ) = 0（2）對于強噪信道，有H (YX )= H (Y ) 聯(lián)合熵定義：是聯(lián)合離散符號集合XY上的每個元素對的聯(lián)合自信息量的數(shù)學期望，也叫共熵。用H(XY)表示。聯(lián)合熵和信息熵、條件熵的關系：H (X ，Y) = H (X) + H (YX)= H (Y) +H (XY)上式反映了信息的可加性。當X，Y統(tǒng)計獨立時，有： H(X ，Y)= H(X)+ H(Y)聯(lián)合熵和信息熵的關系： 聯(lián)合熵大于等于獨立事件的熵，小于等于兩獨立事件熵之和，即： H (X ，Y) H (X) H (X ，Y) H (Y) H (X，Y) H (X) + H (Y) 二個事件之間的互信息：

19、對I(xi ；yj)求統(tǒng)計均值，得到平均互信息量： I (X；Y) = H (X) H (XY) = H (Y) H (YX) = H(X)+ H(Y)- H(XY)離散集的平均互信息量平均互信息量性質非負性：對稱性： I(X ；Y )= I(Y ；X )平均互信息和各類熵的關系；極值性：凸函數(shù)性；I(X；Y)= H（X）- H（XY） I(X；Y)= H（Y）- H（YX） I(X；Y)= H(X) + H(Y) - H(XY)平均互信息和各類熵的關系：維恩圖例題：已知信源消息集為X=0,1,接收符號集為Y=0,1，通過有擾信道傳輸，其傳輸特性如圖所示，這是一個二進制對稱信道BSC。已知先驗

20、概率為 p(0)=p(1=1/2) , 計算平均互信息量I( X;Y)及各種熵。 0 1- 0 1 1- 1 圖 二進制對稱信道記： q(x)為信源輸入概率； (y)為信宿輸出概率； p(yx)為信道轉移概率； (xy)為后驗概率。（1）由圖得： ，先算出 p(xi yj)= q(xi)p(yjxi) （2）計算 得：（3） 計算后驗概率，得：（4）計算各種熵及平均互信息量：信源熵 信宿熵 聯(lián)合熵 = -2 0.5 (1-) log 0.5(1-)-2 0.5log 0.5 = log2 - (1-) log (1-)-log = 1 + H 2 () 式中：噪聲熵：平均互信息量： I(X ;

21、 Y)= H(X)+ H(Y)- H(XY) = 1 + H 2 () 疑義度：信源的數(shù)學模型及其分類信源就是一個概率場；實際存在的兩類信源： 離散信源； 連續(xù)信源。根據(jù)信源消息符號前后的相關性，可以分為無記憶信源和有記憶信源；信源分類及其數(shù)學模型信源是產生消息的源，根據(jù)X的不同情況，信源可分為以下類型： 根據(jù)信源的統(tǒng)計特性，離散信源又分為兩種：無記憶信源：X 的各時刻取值相互獨立；有記憶信源：X 的各時刻取值互相有關聯(lián)。離散信源 消息集X為離散集合。波形信源 時間連續(xù)的信源。連續(xù)信源 時間離散而空間連續(xù)的信源。離散信源信源的性質由其輸出完全確定。實際信源的輸出各不相同，可能是漢字、英文、聲音

22、、圖像等，統(tǒng)稱為消息。信源發(fā)出消息的過程，等同于從一個基本消息集合取出基本消息的過程。信源消息基本消息集合基本消息離散無記憶信源DMS：Discrete Memoryless Source ，離散無記憶信源 。DMS隨機變量序列值域符號集或符號表：獨立同分布隨機變量序列。DMS離散無記憶信源DMS先驗概率：先驗概率集合：DMS的概率空間：概率的完備性條件：有用的記號：自信息量的物理解釋信源觀察過程先驗概率先驗不確定性后驗概率后驗不確定性轉移概率干擾引入的不確定性擴展信源的熵DMSDMS?因為是DMS，故 獨立同分布，所以：離散有記憶信源的熵 N階平穩(wěn)信源一般有記憶信源Bits/N元符號Bits

23、/符號極限熵：Bits/符號離散平穩(wěn)信源的信息測度平均符號熵：離散平穩(wěn)信源輸出N長的信源符號序列中平均每個信源符號所攜帶的信息量稱為平均符號熵，記為HN(X)，則有極限熵：若離散平穩(wěn)信源當N趨于無窮時，平均符號熵的極限存在，則稱此極限為離散平穩(wěn)信源的極限熵（也稱熵率），記為 ，即：實現(xiàn)信息傳輸?shù)挠行院涂煽啃杂行裕撼浞掷眯诺廊萘靠煽啃裕和ㄟ^信道編碼降低誤碼率在通信系統(tǒng)中研究信道，主要是為了描述、度量、分析不同類型信道，計算其容量，即極限傳輸能力，并分析其特性。通信技術研究-信號在信道中傳輸?shù)倪^程所遵循的物理規(guī)律，即傳輸特性信息論研究-信息的傳輸問題（假定傳輸特性已知）研究信道的目的信道的數(shù)

24、學模型及其分類信道是指信息傳輸?shù)耐ǖ?。包括空間傳輸和時間傳輸?？臻g傳輸針對我們常見的情形，例如各種物理通道：電纜、光纜、自由空間等。時間傳輸是指將信息保存，然后在以后讀取。信道可以看成一個變換器，它將輸入事件x變換成輸出事件y。輸入事件x通過信道后變換成輸出事件y，可以采用條件概率分布函數(shù)p(y/x)描述。幾個特殊的信道： 無損信道：輸入完全由輸出決定的信道； 確定信道：輸出完全由輸入決定的信道； 無噪信道：既是無損信道又是確定信道的信道。 無用信道：從輸入不能得到輸出的任何信息的信道。離散信道的數(shù)學模型信道的數(shù)學模型表示為：X，p(y/x)，Y按輸入/輸出之間的記憶性來劃分：若信道的輸出只與

25、信道該時刻的輸入有關而與信道其他時刻的輸入無關，則為無記憶信道；若信道的輸出不僅與信道該時刻的輸入有關而且與以前時刻的輸入有關，則為有記憶信道。根據(jù)輸入/輸出之間的概率關系是否隨時間改變可分為平穩(wěn)信道和非平穩(wěn)信道。信道模型兩個概念熵熵率無失真信源編碼定理中的作用；互信息信道容量信道編碼定理中的作用。平均互信息定義：離散隨機變量X和Y之間的互信息 I（X；Y）=I（Y；X） I（X；Y）和I（Y；X）是隨機變量X和Y之間相互提供的信息量。 一般情況下：理解：了解一事物總對另一事物的了解有所幫助。信道容量的定義對于一切可能的輸入信號的概率分布來說，平均互信息 I(X；Y) 所能達到的最大值，稱為信

26、道容量： 其中max下的P(x)表示對所有可能的輸入信號的概率分布來取最大值。使信道傳輸率達到最大的輸入概率分布稱為最佳輸入分布。比特/符號信道容量的計算通常計算一個信道的信道容量是比較麻煩的，甚至是不可能精確計算出來的，這是因為需要對所有可能的輸入信號的概率分布來計算平均互信息I(X；Y)，從中找出最大可能的一個作為信道容量。下面求一些特殊信道的信道容量。無損信道的容量無損信道的輸入符號集元素個數(shù)小于輸出符號集的元素個數(shù)，信道的一個輸入對應多個互不交叉的輸出，如圖所示，信道輸入符號集X =x1，x2，x3，輸出符號集Y =y1，y2，y3，y4，y5，其信道轉移概率如下圖。計算該信道的信道容

27、量。 x1x2x3y1y2y3y5y62/61/63/61/21/21y41. 先考察平均互信息量I（X；Y）= H（X）-H（XY），在無噪信道條件下，H（XY）= 0，則平均互信息量：I（X；Y）= H（X）2. 根據(jù)定義計算信道容量C 從上式可看出，求信道容量C 的問題轉化為尋找某種分布q (x) 使信源熵H（X）達到最大，由極大離散熵定理知道，在信源消息等概分布時 ，熵值達到最大即有：二進對稱信道的信道容量二進對稱信道BSC的模型：0101XY1- 1-設輸入符號的概率分布為 p(0)= a，p(1)=1- a，條件概率 p(0|0)= p(1|1)= 1-， p(1|0)= p(0|

28、1)=，則有： 從而可以計算出： H(Y|X) = -( (1-)log(1-) + log ) max I(X；Y) = max(H(Y) H(Y|X) ) = max(H(Y) H(Y|X) 但是 max(H(Y)=1，它發(fā)生在p(1)=p(0)=1/2下，故BSC的信道容量為： C = max I(X；Y)=1+ (1-)log(1-) + log 離散對稱信道 定義1 如果信道轉移概率矩陣P 中，每一行元素都是另一行相同元素的不同排列，則稱該信道為離散輸入對稱信道。 離散對稱信道 定義2 如果信道轉移概率矩陣P 中，每一列元素都是另一列相同元素的不同排列，則稱該信道為離散輸出對稱信道。

29、離散對稱信道 定義3 如果信道轉移概率矩陣P 可按輸出符號集Y分成幾個子集（子矩陣），而每一子集關于行、列都對稱，稱此信道為準對稱信道。 當劃分的子集只有一個時，信道是關于輸入和輸出對稱的，這類信道稱為對稱信道。定理1 實現(xiàn)DMC準對稱信道的信道容量的輸入分布為等概分布。定理2 若一個離散對稱信道具有r個輸入符號，s個輸出符號，則當輸入為等概分布時，達到信道容量，且式中， 為信道矩陣中的任一行。二元刪除信道信道容量的計算a1a2b1b21-1-b3 由定理1，當輸入等概分布時，互信息達到信道容量 即：p(a1)= p(a2)=1/2，因此有： 于是：例：設離散無記憶信源的概率空間為：信息熵為H

30、 = 0.811 bits/symbol 若用二元定長編碼(0，1)來構造一個即時碼： 平均碼長 1 bit/symbol編碼效率為：對2次擴展信源序列進行變長編碼，其即時碼如下表： aip(ai)即時碼a1a19/160a1a23/1610a2a13/16110a2a21/16111思考:以上即時碼中,0和1出現(xiàn)的概率各為多少?比特/信源符號比特/信源符號編碼效率：信源編碼 編碼分為信源編碼和信道編碼，其中信源編碼又分為無失真編碼和限失真編碼。 由于信源符號之間存在分布不均勻和相關性，使得信源存在冗余度，信源編碼的主要任務就是減少冗余，提高編碼效率。信源編碼的途徑信源編碼的基本途徑有兩個：使

31、序列中的各個符號盡可能地互相獨立，即消除相關性；使編碼中各個符號出現(xiàn)的概率盡可能地相等，即概率均勻化。 編碼的定義 信源編碼是指信源輸出符號經信源編碼器編碼后轉換成另外的壓縮符號； 無失真信源編碼：可精確無失真地還原信源輸出的消息。離散信源的無失真編碼無失真信源編碼器S離散消息集合C輸出碼字集合X信道基本符號集合信源編碼器幾個基本概念碼中各個碼字都是由同樣多個碼元構成的，稱為等長碼，反之，稱為變長碼；如果碼中所有碼字都不相同，稱為非奇異碼，反之，則為奇異碼。信源符號ai信源符號出現(xiàn)概率p(ai)碼表碼1碼2a1p(a1)000a2p(a2)0101a3p(a3)10001a4p(a4)1111

32、1碼的不同屬性信源符號ai符號出現(xiàn)概率p(ai)碼1碼2碼3碼4a11/20011a21/411101001a31/80000100001a41/8110110000001唯一可譯碼和非唯一可譯碼如果由碼 C 的一組碼字構成的任意長碼序列，只能以唯一的方式分割成若干前后連接的碼字，叫唯一可譯碼；反之，為非唯一可譯碼。例子 C1 = (1，01，00) 是唯一可譯碼，如碼字序列10001101只可唯一劃分為：1、00、01、1、01 C2 = (0，10，01) 為非唯一可譯碼，如序列01001可劃分為：0、10、01或01、0、01即時碼定義：無須考慮后續(xù)的碼符號即可從碼符號序列中譯出碼字，這

33、樣的惟一可譯碼稱為即時碼。即時碼的充要條件：設 Ci=xi1，xi2，xim 是碼 C 中任一碼字，而其他碼字Ck=xk1，xk2,，xkj (j m) 都不是碼字 Ci 的前綴，則稱此碼為即時碼。（即時碼的前綴條件）即時碼一定是唯一可譯碼；反之，唯一可譯碼不一定都是即時碼。 例：對某個信源符號集合按照下面兩種方式編碼，試分析其異同。信源符號 碼1 碼2S1 1 1S2 10 01S3 100 001S4 1000 0001相同點：碼1、碼2都是唯一可譯碼；不同點：碼2中，每個碼字都以“1”為終端，只要一出現(xiàn)“1”時，就知道這是一個碼字已經終結，新的碼字就要開始，因此當出現(xiàn)“1”后，就可以立即

34、將收到的碼元序列譯成對應的信源符號；碼1中，當收到一個或幾個碼元符號后，不能即時判斷碼字是否已經終結，必須等待下一個或幾個碼元符號收到后，才能作出判斷。例：碼1組成的序列：1000100101 碼2組成的序列：0001011001結論：碼1是非即時碼，碼2是即時碼。首先觀察是否是非奇異碼，若是奇異碼，肯定不是唯一可譯碼；其次，計算是否滿足Kraft不等式。若不滿足，則一定不是唯一可譯碼；然后將碼畫成一棵樹圖，觀察是否滿足異前置碼的樹圖的構造，若滿足則是唯一可譯碼。Sardinas和Patterson設計的判斷法：計算分組碼中所有可能的尾隨后綴集合S，觀察S中有沒有包含任一碼字，若無則為唯一可譯

35、碼；若有則一定不是唯一可譯碼。唯一可譯碼的判斷法如何構造后綴分解集判斷由碼字集合0，10，12，21，112，1122構成的碼是否為唯一可譯碼？碼字集合a，c，abb，bad，deb，bbcde構成的碼是否為唯一可譯碼？集合S的構造：首先觀察碼C中最短的碼字是否是其它碼字的前綴。若是，將其所有可能的尾隨后綴排列出；這些尾隨后綴又可能是某些碼字的前綴，再將由這些尾隨后綴產生的新的尾隨后綴列出；尾隨后綴集合的構造然后再觀察這些新的尾隨后綴是否是某些碼字的前綴，再將產生的尾隨后綴列出；這樣，首先獲得由最短的碼字能引起的所有尾隨后綴；接著，按照上述將次短的碼字等等，所有碼字可能產生的尾隨后綴全部列出，

36、由此得到碼C的所有可能的尾隨后綴組成的集合S。尾隨后綴集合的構造101100可以解碼為：10，11001011，0，0碼的類型碼奇異碼非分組碼分組碼非奇異碼非唯一可譯碼非即時碼即時碼(非延長碼)唯一可譯碼碼 樹碼樹的構造：對一棵樹，給每個節(jié)點所伸出的枝分別標上碼元符號0、1、r-1，這樣，葉節(jié)點所對應的碼字就是從根出發(fā)到葉節(jié)點經過的路徑所對應的碼元符號組成。按樹圖法構成的碼一定滿足即時碼的充要條件，因為從根到葉所走的路徑各不相同，而且中間節(jié)點不安排為碼字，所以一定滿足對前綴的限制。碼 樹通常可用碼樹來表示各碼字的構成 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

37、1 0 1 0 1 0 1 0 1 0 1二進制碼樹（滿樹）二進制碼樹（非滿樹） 該樹的5個葉節(jié)點S1，S2，S3，S4，S5 分別表示5個二進制碼字 0，100，111，1010，1011。100001111S3S1S2S4S5 0 1 2 0 1 2 0 1 2 0 1 20 1 20 1 2三進制碼樹（非滿樹）設離散無記憶信源有八種等概率符號，輸出長度N=1， H（X）= 3 bits設離散無記憶信源概率空間為： 比特/符號 變長編碼在變長編碼中，碼長L是變化的，根據(jù)信源各個符號的統(tǒng)計特性，如概率大的符號用短碼，概率小的用長碼，使得編碼后平均碼長降低，從而提高編碼效率。碼字的平均長度最短

38、的變長碼的碼字集合稱為最佳變長碼。 變長碼的編碼方法主要有：香農（Shannon）碼法諾（Fano）碼哈夫曼（Huffman）碼（最佳變長碼）最佳變長編碼Fano編碼方法編碼對象：離散信源概率集合編碼方法（對二元系統(tǒng)）按概率遞減的方式將消息及其概率排列起來；將消息分成概率盡可能相同的兩個子集，兩個子集分別冠以碼元符號“1”和“0”。將每個子集再劃分為概率盡可能相等的兩個子集，并分別冠以11，10和01，00，依此類推，直到子集只包括一個消息為止。例 1將下列消息按二元Fano方法編碼：X2x5x1x6x3x4x7x80.250.250.1250.1250.06250.06250.06250.0

39、6250100011011110111100101110011011110111100011001011100110111101111消息 概率 編碼 碼字編碼后可以計算得到：主要問題當消息數(shù)目很多，而其概率又各不相同時，如何把一個消息集逐次劃分為概率盡可能相同的兩個或多個子集。該方法不能保證概率大的消息一定比概率小的消息能用較短的碼字。對以下信源進行費諾編碼： 消息符號ai各個消息概率 p(ai)第一次分組第二次分組第三次分組第四次分組二元碼字碼長Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a

40、70.01111114例 2 碼元/符號 思考題將以下數(shù)字序列進行二進制Fano編碼：12642583216252326241255765175558 并計算編碼效率。Fano碼的主要問題當消息數(shù)目很多，而其概率又各不相同時，如何把一個消息集逐次劃分為概率盡可能相同的兩個或多個子集。該方法不能保證概率大的消息一定比概率小的消息能用較短的碼字。對以下信源進行Fano編碼： 消息符號ai各個消息概率 p(ai)第一次分組第二次分組第三次分組第四次分組二元碼字碼長Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011

41、104a70.01111114Huffman編碼方法Huffman編碼是一種可變長編碼方式，是由美國數(shù)學家David Huffman創(chuàng)立的，是二叉樹的一種特殊轉化形式。編碼的原理：將使用次數(shù)多的代碼轉換成長度較短的代碼，而使用次數(shù)少的可以使用較長的編碼，并且保持編碼的唯一解碼性。Huffman編碼方法編碼對象：離散信源概率集合編碼方法（對二元系統(tǒng)）將N個信源符號按概率遞增（或遞減）方式排列起來；用“0”，“1”碼符號分別表示概率最小的兩個信源符號，并將這兩個概率最小的信源符號合并成一個符號，從而得到只包含N-1個符號的新信源，稱為S信源的縮減信源S1；將縮減信源S1的符號仍按概率大小以遞減次序

42、排列，再將其最后兩個概率最小的符號合并成一個符號，并分別用0，1碼符號表示，這樣又形成了N-2個符號的縮減信源S2；依次繼續(xù)下去，直到信源最后只剩下兩個符號為止，將這最后兩個符號分別用0，1碼符號表示，然后從最后一級縮減信源開始，向前返回，就得出各信源符號所對應的碼符號序列，即得出對應的碼字。例 1將下列消息按二元Huffman方法編碼：X1 0.20 x2 0.19x3 0.18x4 0.17x5 0.15x6 0.10 x7 0.01SS1100.11100.26S2100.35100.39100.61101.00S3S4S5111001101000100010000編碼后可以計算得到：H

43、uffman編碼的特點Huffman編碼方法得到的編碼不是唯一的；每次對信源縮減時，賦予信源最后兩個概率最小的符號，用0和1可以是任意的，但這不會影響碼字的長度；對信源進行縮減時，若兩個概率最小的符號合并后概率與其他信源符號的概率相同時，這兩者在縮減信源中進行概率排序，其位置次序可以是任意的；Huffman編碼方法保證了概率大的符號對應于短碼，概率小的符號對應于長碼，充分利用了短碼；Huffman編碼方法縮減信源的最后兩個碼字總是最后一位不同，從而保證了編碼結果是即時碼；思考題將以下數(shù)字序列進行二進制Huffman編碼：11221113411124112311 并計算編碼效率。碼方差碼方差定義

44、2 = E (ni-L)2 = p(xi)(ni-L)2對信源進行壓縮時，若兩個概率最小的符號合并后的概率與其他信源符號的概率相同時，這兩者在壓縮信源中進行概率排序，其位置次序可以是任意的，這種情況將影響碼字的長度；在進行編碼時，為了得到碼方差最小的碼，應使合并的信源符號位于壓縮信源序列盡可能高的位置上，以減少再次合并的次數(shù)，充分利用短碼；碼方差例子設離散無記憶信源如下，分別按如下兩種方式編碼，分析哪種編碼更好。Huffman編碼1Huffman編碼2編碼1、2的分析比較這兩種編碼的平均碼長和編碼效率相同，分別為： L= 2.2 ； =0.965 但它們的碼方差不同。 對于方法1，2 = 1.

45、36， 對于方法2，2 = 0.16。 可見方法2的碼方差小，因此編碼質量好。信道編碼器信道信道譯碼器Mxy圖1 編碼信道 我們要盡可能的提高信息傳輸率，并控制傳輸誤差。信源編碼以提高傳輸效率作為主要考慮因素，信道編碼以提高傳輸可靠性作為主要考慮因素。下面討論噪聲信道編碼的一些基本概念及信道編碼定理。 將信道用圖1所示的模型表示。噪聲信道的編碼問題 圖2 二元碼產生誤碼的情況信息傳輸現(xiàn)實：（1）速度：受信道容量的限制，不可能無限大；（2）質量：受信道噪聲的干擾，傳輸錯誤不可避免。衡量信息傳輸可靠性的指標：平均差錯率Pe 。Pe與信道的統(tǒng)計特性有關，不可能為零，有時甚至很大。降低Pe的方法：先對

46、消息進行編碼再送入信道傳送，這種為降低平均差錯率而進行的編碼稱為信道編碼；在信道輸出端增加信道譯碼器進行信息還原。香農第二編碼定理所給出的結論：只要信道編碼和譯碼的方法得當，就可使平均差錯率趨于零。 譯碼規(guī)則譯碼規(guī)則是由人為制訂的；對于同一個信道可制訂出多種譯碼規(guī)則； “好”的譯碼規(guī)則：平均差錯率小。信道譯碼函數(shù)F，又稱譯碼規(guī)則，是從信道輸出符號集合Y到信道輸入符號集合X的映射：例：求最佳譯碼規(guī)則最大后驗概率譯碼規(guī)則最大后驗概率譯碼規(guī)則：平均差錯率最小的譯碼規(guī)則。極大似然譯碼規(guī)則實際應用中，經常只知道信道的統(tǒng)計特性(轉移概率)，而不知道信源的統(tǒng)計特性(輸入概率)，這時求不出聯(lián)合概率和后驗概率，

47、因此無法確定最佳譯碼規(guī)則。既然只知道轉移概率，就只能按轉移概率的某種約束條件制訂譯碼規(guī)則。按最大轉移概率條件來確定的譯碼規(guī)則，稱為極大似然譯碼規(guī)則。 例：極大似然譯碼規(guī)則已知信道轉移矩陣，確定譯碼規(guī)則。只知轉移概率，無法找出最佳譯碼規(guī)則，只能采用極大似然譯碼規(guī)則。將轉移矩陣各列最大的轉移概率標出，重寫轉移矩陣如下： 按“轉移概率最大”原則確定極大似然譯碼規(guī)則：注：無法求出平均差錯率。極大似然譯碼規(guī)則與最大后驗概率譯碼規(guī)則等價的條件極大似然譯碼規(guī)則最大后驗概率譯碼規(guī)則結論：信道輸入等概時，極大似然譯碼規(guī)則與最大后驗概率譯碼規(guī)則等價。注：（1）信道輸入是近似等概的，因為有信源編碼器存在；（2）極大

48、似然譯碼規(guī)則近似最佳，可以放心使用。 錯誤概率和編碼方法DMCDMS平均差錯率Pe與譯碼規(guī)則F 有關。DMC信道譯碼F譯碼規(guī)則：bj的譯碼正確概率是后驗概率： bj的譯碼錯誤概率： 平均差錯率Pe：例：譯碼規(guī)則與平均差錯率(1)找出所有可能的譯碼規(guī)則；(2)求出各個譯碼規(guī)則對應的平均差錯率。 4種譯碼規(guī)則：結論：F3最好，F(xiàn)4最差簡單重復編碼 信道譯碼F信道編碼f信道編碼前后比較 無編碼 bit/符號“重復2次”編碼 bit/符號“重復”編碼 的其它結果bit/符號bit/符號bit/符號結論：隨著“重復”次數(shù)的增加，Pe下降，R 也跟著下降。對符號串編碼 信道譯碼F信道編碼fbit/符號結論

49、：增多消息個數(shù)M會提高R，但會使Pe增大。 信道編碼的有關結論及啟示由前面的例子得出的結論：增加“重復”次數(shù)N（增大碼長），會使Pe下降(好)，但R也跟著下降(不好)。增多消息個數(shù)M會提高R(好)，但會使Pe增大(不好)。啟示： 增大碼長N，同時適當增多消息個數(shù)M，有可能使平均差錯率降低到要求的范圍以內，而又能使信息率不降低或降低不多。 （N，K）分組碼 取M=4、N=5：5次擴展信道(5，2)分組碼：碼長N為5，前2個碼元是信息位（K），后3個碼元是校驗位 。bit/符號bit/符號M=4、N=3： 常用的差錯控制方法有以下幾種： 反饋重傳糾錯發(fā)射信號發(fā)射能夠發(fā)現(xiàn)錯誤的糾錯碼，接收設備檢查收

50、到的編碼信息。當發(fā)現(xiàn)有錯時，通過反饋系統(tǒng)向發(fā)出端發(fā)出詢問信號要求重新發(fā)送。 前向糾錯接收端不僅能發(fā)現(xiàn)錯碼，還能夠確定錯碼的位置，能夠糾正它。 混合糾錯對發(fā)送端進行適當編碼，當錯誤不嚴重時，在碼的糾錯能力內，采用自動糾錯。當超出碼的糾錯能力，且能發(fā)現(xiàn)錯誤，則發(fā)出詢問信號，通過反饋系統(tǒng)到發(fā)送端要求重發(fā)。糾錯碼分類差錯控制方式 ARQ優(yōu)點：冗余碼元少、對信道有自適應能力、成本和復雜性低； ARQ缺點：需要反向信道、重發(fā)控制較復雜、干擾大通信效率低、實時性差。 接收端如何識別有無錯碼？由發(fā)送端的信道編碼器在信息碼元序列中增加一些監(jiān)督碼元。這些監(jiān)督碼和信碼之間有確定的關系，使接收端可以利用這種關系由信道

51、譯碼器來發(fā)現(xiàn)或糾正可能存在的錯碼。 在信息碼元序列中加入監(jiān)督碼元就稱為差錯控制編碼，有時也稱為糾錯編碼。 差錯控制編碼原則上是以降低信息傳輸速率為代價來換取傳輸可靠性的提高。糾錯編碼的基本原理3位二進制數(shù)字構成的碼組，共有8種不同的組合。若將其全部利用來表示天氣，則可以表示8種不同天氣：000(晴)，001(多云)，010(陰)，011(雨)100(雪)，101(霜)， 110(霧)，111(雹)任一碼組在傳輸中若發(fā)生一個或多個錯碼，則將變成另一信息碼組。這時接收端將無法發(fā)現(xiàn)錯誤。例 簡單糾錯碼 改進為：000 =晴001 =不可用010 =不可用011 =云100 =不可用101 =陰110

52、 =雨111 =不可用 那么： 雖然只能傳送4種不同的天氣，但是接收端卻有可能發(fā)現(xiàn)碼組中的一個錯碼。 例如，若000(晴)中錯了一位，則接收碼組將變成100或010或001，這三種碼組都是不準許使用的，稱為禁用碼組，故接收端在收到禁用碼組時，就認為發(fā)現(xiàn)了錯碼。 但是這種碼不能發(fā)現(xiàn)兩個錯碼，因為發(fā)生兩個錯碼后產生的是許用碼組。 上述碼只能檢測錯誤，不能糾正錯誤。例如，當收到的碼組為禁用碼組100時，無法判斷哪一位碼發(fā)生了錯誤，因為晴、陰、雨三者錯了一位都可以變成100。 要想能糾正錯誤，還要增加多余度。例如，苦規(guī)定許用碼組只有兩個：000(晴)、111(雨)，其余都是禁用碼組。這時，接收端能檢測

53、兩個以下錯碼，或能糾正一個錯碼。碼重、碼距碼重“1”的數(shù)量稱為碼組的重量；碼距兩個碼組對應位上數(shù)字不同的位數(shù)稱為碼組的距離，簡稱碼距。又稱漢明(Hamming)距離；最小碼距某種編碼中各個碼組間距離的最小值稱為最小碼距(d0)； 記： d0 最小碼距 e 檢錯位數(shù) t 糾錯位數(shù)漢明距離的定義 定義：兩個等長符號序列 和 之間的漢明距離，記為 ，是 與 之間對應位置上不同符號的個數(shù)。例：用漢明距離來度量兩個符號序列的“相似”程度。漢明重量二元序列漢明重量 ：二元序列 中含“1”的個數(shù)。 （1） e +1 d0，即碼的檢錯能力e比最小碼距d0小1位；（2） 2t+1 d0，即碼的糾錯能力t的2倍比

54、最小碼距d0小1位；（3） e +t+1 d0 ，即若碼同時糾t個錯并檢出e個錯誤，則e + t比最小碼距d0小1位。碼重、碼距與碼的糾檢錯能力（1） e +1 d0（2） 2t +1 d0（3） t +e+1 d0碼的相似性最小碼間距離dmin 是衡量碼的性能的重要參數(shù)，碼的dmin小：說明有些碼字受干擾后容易變?yōu)榱硪淮a字，譯碼時就會出錯。進行信道編碼時，只要條件允許，盡量選擇最小碼間距離大一些的碼。等長碼碼間距離：碼C的最小碼間距離：差錯控制編碼的效率 假設：發(fā)送“0”的錯誤概率和發(fā)送“1”的錯誤概率相等，都等于p，且p1，則在碼長為n的碼組中恰好發(fā)生r個錯碼的概率為：例如，當碼長n7時，

55、p=10-3則有： P7(1) 7p = 710-3 P7(2) 21p2= 2.110-5 P7(3) 35p= 3.510。 可見，采用差錯控制編碼，即使僅能糾正(或檢測)這種碼組中12個錯誤，也可以使誤碼率下降幾個數(shù)量級。這就表明，即使是較簡單的差錯控制編碼也具有較大實際應用價值。 建立在代數(shù)學基礎上的編碼稱為代數(shù)碼。在代數(shù)碼中，常見的是線性碼。線性碼中信息位和監(jiān)督位是由一些線性代數(shù)方程聯(lián)系著的，或者說，線性碼是按一組線性方程構成的。有噪信道編碼定理在有噪信道上傳遞信息，難免會出現(xiàn)差錯；為了降低平均差錯率，可將每個消息重復傳送若干次，但這樣又降低了信息傳遞的速度。理論問題：是否能找到一種

56、信道編碼方法能同時保證差錯率和信息傳輸速率的要求呢？1948年，香農從理論上得出結論：對于有噪信道，只要通過足夠復雜的編碼方法，就能使信息率達到信道的極限通信能力信道容量，同時使平均差錯率逼近零。這一結論稱為香農第二定理或有噪信道編碼定理，是有關信息傳輸?shù)淖罨窘Y論。有噪信道編碼定理定理（香農第二定理）：若信道是離散、無記憶、平穩(wěn)的，且信道容量為C，只要待傳送的信息率RC，就一定能找到一種信道編碼方法，使得碼長足夠大時，平均差錯率任意接近于零。注：（1）香農第二定理實際上是一個存在性定理，它指出：在RC，則肯定找不到一種信道編碼方法，使得碼長足夠大時，平均差錯率任意接近于零。隨堂測驗要求：選做

57、5題2011-4-26設有5個獨立工作的元件1,2,3,4,5，它們的可靠性均為p，將它們按照如圖所示的方式連接，試求該電路的可靠性。3. 有10個一模一樣的小球，其中有一個是假球，重量和真球不同。問能否用沒有砝碼的天平稱兩次，將假球找出？說明理由。4. 莫爾斯電報系統(tǒng)中，若采用點長為0.2s、劃長為0.4s且點和劃出現(xiàn)的概率分別為2/3和1/3，試求它的平均信息速率（b/s）。 5. 下面哪些碼是唯一可譯碼？（1）0，10，11（2）0，01，11（3）0，01，10（4）0，01（5）00，01，10，11（6）110，11，106. 某校入學考試中，有1/4考生被錄取，3/4考生未被錄取

58、。被錄取的考生中有50%來自本市，而落榜考生中有10%來自本市。所有本市的考生都學過英語，而錄取及落榜外地考生中都有40%學過英語。問：（1）當已知考生來自本市時，給出多少關于考生是否被錄取的信息？（2）當已知考生學過英語時，給出多少關于考生是否被錄取的信息？7已知二維隨機變量XY的聯(lián)合概率分布p(xi,yj)為：p(0,0)=p(1,1)=1/8，p(0,1)=p(1,0)=3/8，求H（XY）。 kkkkkkkkn分組碼編碼原理圖中，n k，Rk/n，稱為編碼效率。分組碼的基本原理是將信息碼分成K比特一組，然后將每組的比特數(shù)擴展成n（ n k），也就是說在信息比特中插入n-k個比特。另一種

59、看法：將2k矢量空間映射到2n矢量空間。 建立在代數(shù)學基礎上的編碼稱為代數(shù)碼。在代數(shù)碼中，常見的是線性碼。 分組碼是一種代數(shù)碼，它的基本關系是一個碼字包括獨立的信息元和監(jiān)督元，其監(jiān)督元與信息元之間是一種代數(shù)關系，如果這種代數(shù)關系為線性的，則稱為線性分組碼。分組碼的編碼器的模型為： 線性分組碼線性碼重要性質之一，是它具有封閉性。 若：A1和A2是線性碼中的兩個許用碼組，則：(A1+A2)仍為其中的一個碼組。由封閉性，兩個碼之間的距離必是另一碼的重量。故碼的最小距離即是碼的最小重量(除全“0”碼組外)。線性碼又稱群碼，這是由于線性碼的各許用碼組構成代數(shù)學中的群。群定義了一種運算的集合群運算封閉；有

60、恒等元；有逆元；滿足結合律交換群滿足交換律的群群的定義： 如果一個元素集合G，在其中定義一種運算“*”，并滿足下列條件，則稱為一個群(Group)。a，b，c，e，a-1G。 1）封閉性：c = a*b 2）結合律：a*(b*c) = (a*b)*c 3）單位元：a*e = e*a = a 4）逆元： a*a-1 = a-1*a = e如果還滿足交換律，a*b=b*a, 則稱為交換群。奇偶監(jiān)督碼采用奇偶校驗原理。只能檢錯，不能糾錯。只能檢查出某一分組的單個錯誤或奇數(shù)個錯誤，而不能發(fā)現(xiàn)偶數(shù)個錯誤。最小碼距為2。水平奇偶監(jiān)督碼水平垂直奇偶監(jiān)督碼。 對于長度為n的二元序列 (n-重)來說，共有2n個