信息論大復(fù)習(xí)(2010-5-31)

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

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

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

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

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

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

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

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

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

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

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

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

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

14、率特性由以下數(shù)學(xué)模型表示： 則如果將自信息量看為一個(gè)隨機(jī)變量，其平均信息量為自信息量的數(shù)學(xué)期望，其定義為：熵的計(jì)算例1：設(shè)某信源輸出四個(gè)符號(hào)，其符號(hào)集合的概率分布為： 則其熵為：熵的含義熵是從整個(gè)集合的統(tǒng)計(jì)特性來考慮的，它是從平均意義上來表征集合的總體特征的。 熵表示事件集合中事件發(fā)生后，每個(gè)事件提供的平均信息量；熵表示事件發(fā)生前，集合的平均不確定性。例2：有2個(gè)集合，其概率分布分別為： 分別計(jì)算其熵，則：H(X)=0.08 bit /符號(hào)， 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ù)學(xué)特性對(duì)稱性：熵函數(shù)對(duì)每個(gè)Pk 對(duì)稱的。該性質(zhì)說明熵只與隨機(jī)變量的總體結(jié)構(gòu)有關(guān)，與事件集合的總體統(tǒng)計(jì)特性有關(guān)；非負(fù)性：H0；擴(kuò)展性：當(dāng)某事件Ek的概率Pk稍微變化時(shí)，H函數(shù)也只作連續(xù)的不突變的變化；熵函數(shù)的數(shù)學(xué)特性可加性：設(shè)有一事件的完全集合E1,E2,En,其熵為H1(p1，p2，pn)?，F(xiàn)設(shè)其中一事件En又劃分為m個(gè)子集，即： 這時(shí)構(gòu)成的三個(gè)概率空間分別具有熵函數(shù)： 這說明對(duì)集合的進(jìn)一步劃分會(huì)使它的不確定性增加，即熵總是往大增加。熵函數(shù)的數(shù)學(xué)特性極值性：即當(dāng)所有事件等概率

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

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

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

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

20、概率為 p(0)=p(1=1/2) , 計(jì)算平均互信息量I( X;Y)及各種熵。 0 1- 0 1 1- 1 圖 二進(jìn)制對(duì)稱信道記： q(x)為信源輸入概率； (y)為信宿輸出概率； p(yx)為信道轉(zhuǎn)移概率； (xy)為后驗(yàn)概率。（1）由圖得： ，先算出 p(xi yj)= q(xi)p(yjxi) （2）計(jì)算 得：（3） 計(jì)算后驗(yàn)概率，得：（4）計(jì)算各種熵及平均互信息量：信源熵 信宿熵 聯(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ù)學(xué)模型及其分類信源就是一個(gè)概率場(chǎng)；實(shí)際存在的兩類信源： 離散信源； 連續(xù)信源。根據(jù)信源消息符號(hào)前后的相關(guān)性，可以分為無記憶信源和有記憶信源；信源分類及其數(shù)學(xué)模型信源是產(chǎn)生消息的源，根據(jù)X的不同情況，信源可分為以下類型： 根據(jù)信源的統(tǒng)計(jì)特性，離散信源又分為兩種：無記憶信源：X 的各時(shí)刻取值相互獨(dú)立；有記憶信源：X 的各時(shí)刻取值互相有關(guān)聯(lián)。離散信源 消息集X為離散集合。波形信源 時(shí)間連續(xù)的信源。連續(xù)信源 時(shí)間離散而空間連續(xù)的信源。離散信源信源的性質(zhì)由其輸出完全確定。實(shí)際信源的輸出各不相同，可能是漢字、英文、聲音

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

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

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

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

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

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

28、1)=，則有： 從而可以計(jì)算出： 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 離散對(duì)稱信道 定義1 如果信道轉(zhuǎn)移概率矩陣P 中，每一行元素都是另一行相同元素的不同排列，則稱該信道為離散輸入對(duì)稱信道。 離散對(duì)稱信道 定義2 如果信道轉(zhuǎn)移概率矩陣P 中，每一列元素都是另一列相同元素的不同排列，則稱該信道為離散輸出對(duì)稱信道。

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

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

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

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

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

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

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

36、由此得到碼C的所有可能的尾隨后綴組成的集合S。尾隨后綴集合的構(gòu)造101100可以解碼為：10，11001011，0，0碼的類型碼奇異碼非分組碼分組碼非奇異碼非唯一可譯碼非即時(shí)碼即時(shí)碼(非延長(zhǎng)碼)唯一可譯碼碼 樹碼樹的構(gòu)造：對(duì)一棵樹，給每個(gè)節(jié)點(diǎn)所伸出的枝分別標(biāo)上碼元符號(hào)0、1、r-1，這樣，葉節(jié)點(diǎn)所對(duì)應(yīng)的碼字就是從根出發(fā)到葉節(jié)點(diǎn)經(jīng)過的路徑所對(duì)應(yīng)的碼元符號(hào)組成。按樹圖法構(gòu)成的碼一定滿足即時(shí)碼的充要條件，因?yàn)閺母饺~所走的路徑各不相同，而且中間節(jié)點(diǎn)不安排為碼字，所以一定滿足對(duì)前綴的限制。碼 樹通?？捎么a樹來表示各碼字的構(gòu)成 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二進(jìn)制碼樹（滿樹）二進(jìn)制碼樹（非滿樹） 該樹的5個(gè)葉節(jié)點(diǎn)S1，S2，S3，S4，S5 分別表示5個(gè)二進(jìn)制碼字 0，100，111，1010，1011。100001111S3S1S2S4S5 0 1 2 0 1 2 0 1 2 0 1 20 1 20 1 2三進(jìn)制碼樹（非滿樹）設(shè)離散無記憶信源有八種等概率符號(hào)，輸出長(zhǎng)度N=1， H（X）= 3 bits設(shè)離散無記憶信源概率空間為： 比特/符號(hào) 變長(zhǎng)編碼在變長(zhǎng)編碼中，碼長(zhǎng)L是變化的，根據(jù)信源各個(gè)符號(hào)的統(tǒng)計(jì)特性，如概率大的符號(hào)用短碼，概率小的用長(zhǎng)碼，使得編碼后平均碼長(zhǎng)降低，從而提高編碼效率。碼字的平均長(zhǎng)度最短

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

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

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

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

42、排列，再將其最后兩個(gè)概率最小的符號(hào)合并成一個(gè)符號(hào)，并分別用0，1碼符號(hào)表示，這樣又形成了N-2個(gè)符號(hào)的縮減信源S2；依次繼續(xù)下去，直到信源最后只剩下兩個(gè)符號(hào)為止，將這最后兩個(gè)符號(hào)分別用0，1碼符號(hào)表示，然后從最后一級(jí)縮減信源開始，向前返回，就得出各信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即得出對(duì)應(yīng)的碼字。例 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編碼后可以計(jì)算得到：H

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

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

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

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

47、因此無法確定最佳譯碼規(guī)則。既然只知道轉(zhuǎn)移概率，就只能按轉(zhuǎn)移概率的某種約束條件制訂譯碼規(guī)則。按最大轉(zhuǎn)移概率條件來確定的譯碼規(guī)則，稱為極大似然譯碼規(guī)則。 例：極大似然譯碼規(guī)則已知信道轉(zhuǎn)移矩陣，確定譯碼規(guī)則。只知轉(zhuǎn)移概率，無法找出最佳譯碼規(guī)則，只能采用極大似然譯碼規(guī)則。將轉(zhuǎn)移矩陣各列最大的轉(zhuǎn)移概率標(biāo)出，重寫轉(zhuǎn)移矩陣如下： 按“轉(zhuǎn)移概率最大”原則確定極大似然譯碼規(guī)則：注：無法求出平均差錯(cuò)率。極大似然譯碼規(guī)則與最大后驗(yàn)概率譯碼規(guī)則等價(jià)的條件極大似然譯碼規(guī)則最大后驗(yàn)概率譯碼規(guī)則結(jié)論：信道輸入等概時(shí)，極大似然譯碼規(guī)則與最大后驗(yàn)概率譯碼規(guī)則等價(jià)。注：（1）信道輸入是近似等概的，因?yàn)橛行旁淳幋a器存在；（2）極大

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

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

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

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

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

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

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

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

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

57、5題2011-4-26設(shè)有5個(gè)獨(dú)立工作的元件1,2,3,4,5，它們的可靠性均為p，將它們按照如圖所示的方式連接，試求該電路的可靠性。3. 有10個(gè)一模一樣的小球，其中有一個(gè)是假球，重量和真球不同。問能否用沒有砝碼的天平稱兩次，將假球找出？說明理由。4. 莫爾斯電報(bào)系統(tǒng)中，若采用點(diǎn)長(zhǎng)為0.2s、劃長(zhǎng)為0.4s且點(diǎn)和劃出現(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. 某校入學(xué)考試中，有1/4考生被錄取，3/4考生未被錄取

58、。被錄取的考生中有50%來自本市，而落榜考生中有10%來自本市。所有本市的考生都學(xué)過英語，而錄取及落榜外地考生中都有40%學(xué)過英語。問：（1）當(dāng)已知考生來自本市時(shí)，給出多少關(guān)于考生是否被錄取的信息？（2）當(dāng)已知考生學(xué)過英語時(shí)，給出多少關(guān)于考生是否被錄取的信息？7已知二維隨機(jī)變量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比特一組，然后將每組的比特?cái)?shù)擴(kuò)展成n（ n k），也就是說在信息比特中插入n-k個(gè)比特。另一種

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

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