信息論習(xí)習(xí)題

1、例 條件熵 已知X，Y,XY構(gòu)成的聯(lián)合概率為：p(00)=p(11)=1/8,p(01)=p(10)=3/8,計(jì)算條件熵H(X/Y)。 解： 根據(jù)條件熵公式：首先求，有例將已知信源接到下圖所示的信道上，求在該信道上傳輸?shù)钠骄バ畔⒘縄(X;Y)、疑義度H(X/Y)、噪聲熵H(Y/X)和聯(lián)合熵H(XY)。 解：（1）由求出各聯(lián)合概率： （2）由得到Y(jié)集各消息概率：（3）由，得到X的各后驗(yàn)概率： 同樣可推出（4） =(比特/符號(hào))= （比特/符號(hào)）（5）平均互信息（6）疑義度（7）噪聲熵例有一離散平穩(wěn)無(wú)記憶信源，求此信源的二次擴(kuò)展信源的熵。 先求出此離散平穩(wěn)無(wú)記憶信源的二次擴(kuò)展信源。擴(kuò)展信源的每個(gè)

2、元素是信源X的輸出長(zhǎng)度為2的消息序列。由于擴(kuò)展信源是無(wú)記憶的，故信源的元素對(duì)應(yīng)的消息序列概率根據(jù)熵的定義，二次擴(kuò)展信源的熵為結(jié)論：計(jì)算擴(kuò)展信源的熵時(shí)，不必構(gòu)造新的信源，可直接從原信源X的熵導(dǎo)出。即離散平穩(wěn)無(wú)記憶信源X的N次擴(kuò)展信源的熵為離散信源X的熵的N倍。例設(shè)某二維離散信源X=的原始信源X的信源模型為，X=中前后兩個(gè)符號(hào)的條件概率為 7/92/901/83/41/802/119/11原始信源的熵為： 由條件概率確定的條件熵為：條件熵比信源熵（無(wú)條件熵）減少了symbol,正是由于符號(hào)之間的依賴性所造成的。信源X=平均每發(fā)一個(gè)消息所能提供的信息量，即聯(lián)合熵則每一個(gè)信源符號(hào)所提供的平均信息量小于

3、信源X所提供的平均信息量H(X)，這同樣是由于符號(hào)之間的統(tǒng)計(jì)相關(guān)性所引起的。例設(shè)信源符號(hào)，信源所處的狀態(tài)。各狀態(tài)之間的轉(zhuǎn)移情況由下圖給出。將圖中信源在狀態(tài)下發(fā)符號(hào)的條件概率用矩陣表示為由矩陣可明顯看出，。另從圖中還可得所以信源滿足式(4)由圖還可得狀態(tài)的進(jìn)一步轉(zhuǎn)移概率該信源滿足式(2)-(4)，所以是馬爾可夫信源，并且是時(shí)齊的馬爾可夫信源。例某二元2階馬爾可夫信源，原始信源X的符號(hào)集為，其狀態(tài)空間共有個(gè)不同的狀態(tài)，即，其狀態(tài)轉(zhuǎn)移概率圖如下，由上圖可知，當(dāng)信源處于狀態(tài)時(shí),其后發(fā)生符號(hào)0的概率是,即, 狀態(tài)仍停留在,即。當(dāng)信源仍處于狀態(tài)，而發(fā)出的符號(hào)為1時(shí)，狀態(tài)轉(zhuǎn)移至，故一步轉(zhuǎn)移概率。當(dāng)信源處于狀

4、態(tài)時(shí)，其一步轉(zhuǎn)移概率為，。同理，當(dāng)信源處于狀態(tài)時(shí)，當(dāng)信源處于狀態(tài)這樣，由二元信源X得到的狀態(tài)空間和相應(yīng)的一步轉(zhuǎn)移概率構(gòu)成的2階馬爾可夫信源模型為且由可求出穩(wěn)定狀態(tài)下的，稱為狀態(tài)極限概率。將一步轉(zhuǎn)移概率代入上式得：解此方程組得 計(jì)算極限熵需要注意的是并非在任何情況下都存在。首先應(yīng)記住的是：我們討論的是平穩(wěn)信源。其次，對(duì)n元m階馬爾可夫信源來(lái)說(shuō)，只有極限概率都存在時(shí)，方能計(jì)算出。從理論上可以證明，如果m階馬爾可夫信源穩(wěn)定后具有各態(tài)歷經(jīng)性，則狀態(tài)極限概率可根據(jù)式（10）求出。必須強(qiáng)調(diào)的是，m階馬爾可夫信源和消息長(zhǎng)度為m的有記憶信源，其所含符號(hào)的依賴關(guān)系不同，對(duì)相應(yīng)關(guān)系的數(shù)學(xué)描述不同，平均信息量的計(jì)算

5、公式也不同。m階馬爾可夫信源的記憶長(zhǎng)度雖為有限值m，但符號(hào)之間的依賴關(guān)系延伸到無(wú)窮，通常用狀態(tài)轉(zhuǎn)移概率（條件概率）來(lái)描述這種依賴關(guān)系。可理解為馬爾可夫信源以轉(zhuǎn)移概率發(fā)出每個(gè)信源符號(hào)，所以平均每發(fā)一個(gè)符號(hào)提供的信息量應(yīng)是極限熵。而對(duì)于長(zhǎng)度為m的有記憶信息源X，發(fā)出的則是一組組符號(hào)序列，每m個(gè)符號(hào)構(gòu)成一個(gè)符號(hào)序列組，代表一個(gè)消息。組與組之間是相互統(tǒng)計(jì)獨(dú)立的，因此符號(hào)之間的相互依賴關(guān)系僅限于符號(hào)之間的m個(gè)符號(hào)，一般用這m個(gè)符號(hào)的聯(lián)合概率來(lái)描述符號(hào)間的依賴關(guān)系。對(duì)于這種有記憶信源，平均每發(fā)一個(gè)符號(hào)，（不是一個(gè)消息）提供的信息量，是m個(gè)符號(hào)的聯(lián)合熵的m分之一，即平均符號(hào)熵例設(shè)某單符號(hào)信源模型為計(jì)算得 若

6、要求編碼效率為90%,即 則 = 設(shè)譯碼差錯(cuò)率為，由式（3）可得 由此可見(jiàn)，在差錯(cuò)率和效率的要求都不苛刻的情況下，就必須有1600多萬(wàn)個(gè)信源符號(hào)一起編碼，技術(shù)實(shí)現(xiàn)非常困難。不僅如此，它的編碼效率也不高。對(duì)8種可能的取值編定長(zhǎng)碼，要無(wú)差錯(cuò)地譯碼，每種取值需用3個(gè)比特，其編碼效率為了解決這一問(wèn)題，就出現(xiàn)了不等長(zhǎng)編碼，也稱變長(zhǎng)編碼。不等長(zhǎng)編碼允許把等長(zhǎng)的消息變換成不等長(zhǎng)的碼序列。通常把經(jīng)常出現(xiàn)的消息編成短碼，不常出現(xiàn)的消息編成長(zhǎng)碼。這樣可使平均碼長(zhǎng)最短，從而提高通信效率，代價(jià)是增加了編譯碼設(shè)備的復(fù)雜度。例如在不等長(zhǎng)碼字組成的序列中要正確識(shí)別每個(gè)長(zhǎng)度不同的碼字的起點(diǎn)就比等長(zhǎng)碼復(fù)雜得多。另外，接收到一個(gè)

7、不等長(zhǎng)碼序列后，有時(shí)不能馬上斷定碼字是否真正結(jié)束，因而不能立即譯出該碼，要等到后面的符號(hào)收到后才能正確譯出。這就是所謂的譯碼同步和譯碼延時(shí)問(wèn)題。思考題 已知12個(gè)球中有一個(gè)球的重量與其它球不同，其它球均等重。問(wèn)用無(wú)砝碼的天平至少須幾次才能找出此球 解：天平有3種狀態(tài)，即平衡，左重，左輕，所以每稱一次消除的不確定性為log3，12個(gè)球中的不等重球（可較輕，也可較重）的不確定性為： 因?yàn)?3log3log243次測(cè)量可以找出該球具體稱法略。例一一副充分洗亂了的牌（含52張牌），試問(wèn)：(1) 任一特定排列所給出的信息量是多少(2) 若從中抽取13張牌，所給出的點(diǎn)數(shù)都不相同能得到多少信息量(1)任意排

8、列共有種，則任一排列的自信息量為：。(2)應(yīng)將點(diǎn)數(shù)相同花色不同的牌看作一類(lèi)，則任意抽取的13張牌應(yīng)在13類(lèi)中分別進(jìn)行。其概率為：， 信息量。例二 已知隨機(jī)變量X和Y的聯(lián)合概率分布滿足：試求能使H(XY)取最大值的聯(lián)合概率分布。H(X Y) H(X) + H(Y) 等號(hào)在X、Y獨(dú)立時(shí)取得P() = P() = P() = P() = P() = P() = P() = P() = P() = 滿足 H(XY) 取最大值例三求證：I(X;Y;Z)=H(XYZ)-H(X)-H(Y)-H(Z)+I(X;Y)+I(Y;Z)+I(Z;X)例4令X為擲錢(qián)幣直至其正面第一次朝上所需的次數(shù)，求H(X)P(X=n

9、) = = H(X) = = = 2 bit例5一個(gè)無(wú)記憶信源有四種符號(hào)0，1，2，3。已知。試求由6000個(gè)符號(hào)構(gòu)成的消息所含的信息量。解：先計(jì)算一個(gè)符號(hào)所含的平均自信息量，即信源熵HH= =無(wú)記憶信源由6000個(gè)符號(hào)構(gòu)成的符號(hào)序列消息例6發(fā)出二重符號(hào)序列消息的信源熵為而一階馬爾可夫信源的信源熵為試比較這兩者的大小，并說(shuō)明原因。 解：根據(jù)公式，當(dāng)Y和X為同一集合時(shí)，有，各種熵和條件熵均為非負(fù)值，當(dāng)且僅當(dāng)X中只含有一個(gè)確定性事件時(shí)才出現(xiàn)H（X）=0。當(dāng)X中含有二個(gè)或二個(gè)以上事件時(shí)，有H（X）0，及H（X2）0，H（X|X）0，因?yàn)镠（X）0所以H（X2）H（X|X）說(shuō)明，在一般情況下，發(fā)二重符號(hào)序列的信源的信源熵H（X2）大于一階馬爾可夫過(guò)程的信源熵H（X