信息論編碼與基礎課后題(第二章)

信息論編碼與基礎課后題(第二章)第二章習題解答2-1、試問四進制、八進制脈沖所含信息量是二進制脈沖的多少倍？解：四進制脈沖可以表示4個不同的消息，例如：{0,1,2,3}八進制脈沖可以表示8個不同的消息，例如：{0,1,2,3,4,5,6,7}二進制脈沖可以表示2個不同的消息，例如：{0,1}假設每個消息的發(fā)出都是等概率的，則：四進制脈沖的平均信息量八進制脈沖的平均信息量二進制脈沖的平均信息量所以：四進制、八進制脈沖所含信息量分別是二進制脈沖信息量的2倍和3倍。設某班學生在一次考試中獲優(yōu)（A）、良（B）、中（C）、及格（D）和不及格（E）的人數(shù)相等。當教師通知某甲：“你沒有不及格”，甲獲得了多少比特信息？為確定自己的成績，甲還需要多少信息？解：根據(jù)題意，“沒有不及格”或“pass”的概率為因此當教師通知某甲“沒有不及格”后，甲獲得信息

在已知“pass”后，成績?yōu)椤皟?yōu)”（A），“良”（B），“中”（C）和“及格”（D）的概率相同：為確定自己的成績，甲還需信息3、中國國家標準局所規(guī)定的二級漢字共6763個。設每字使用的頻度相等，求一個漢字所含的信息量。設每個漢字用一個的二元點陣顯示，試計算顯示方陣所能表示的最大信息。顯示方陣的利用率是多少？解：由于每個漢字的使用頻度相同，它們有相同的出現(xiàn)概率，即 因此每個漢字所含的信息量為 每個顯示方陣能顯示種不同的狀態(tài)，共有21種組合：其中11，22，33，44，55，66的概率是其他15個組合的概率是(4)參考上面的兩個點數(shù)的排列，可以得出兩個點數(shù)求和的概率分布如下：(5)7、某一無記憶信源的符號集為{0,1}，已知P(0)=1/4，P(1)=3/4。(1)求信源熵；(2)有100個符號構(gòu)成的序列，求某一特定序列（例如有m個“0”和（100-m）個“1(3)計算(2)中序列的熵。解：(1)(2)(3)8、某地區(qū)的女孩中有25％是大學生，在女大學生中有75％是身高1.6米以上的，而女孩中身高1.6米以上的占半數(shù)一半。假如我們得知“身高解：設A為女大學生，B為1.6米以上的女孩，則依題意有:，，，，所以信息量為=1.415比特9、設離散無記憶信源=，其發(fā)出的消息為（202120130213001203210110321010021032011223210），求：（1）此消息的自信息是多少？（2）在此消息中平均每個符號攜帶的信息量是多少？解：(1)因為離散信源是無記憶的，所以發(fā)出的消息序列中各符號是無依賴且統(tǒng)計獨立的。因此，此消息的自信息就為該消息中各符號自信息之和。I（）=?logP（）=?log=1.415比特I（）=?logP（）=?log=2比特I（）=?logP（）=?log=2比特I（）=?logP（）=?log=3比特則此消息的自信息是：I=18I（）+13I（）+12I（）+6I（）181.415+132+122+6393.47比特(2)此消息中平均每個符號攜帶的信息量是：I=93.47491.91比特/符號10、從大量統(tǒng)計資料知道，男性中紅綠色盲的發(fā)病率為7％，女性發(fā)病率為0.5％，如果你問一位男同志：“你是否是紅綠色盲？”他的回答可能是“是”，可能是“否”，問這二個答案中各含多少信息量？平均每個回答中含有多少信息量？如果你問一位女同志，則答案中含有的平均自信息量是多少？解：（1）若男同志回答“是”：I＝log(1/7%)＝3.84bit回答“否”：I＝log(1/93%)＝0.1bit平均信息量為：I＝－7%log7%－93%log93%＝0.36bit（2）若問女同志，平均信息量為：I＝－0.5%log0.5%－99.5%log99.5%＝0.045bit11、設信源求這信源的熵，并解釋為什么，不滿足信源熵的極值性。解：信源的熵為：bit/符號是因為此信息的，不滿足信息熵極值性的條件。12、設離散無記憶信源，其符號集為，已知其相應的概率分布為。設另一離散無記憶信源，其符號數(shù)為信源符號數(shù)的兩倍：，并且各符號的概率分布滿足：試求信源的信息熵與信源的信息熵的關(guān)系式。解：13、有一概率空間，其概率分布為{,,…,}，并有>。若取=，=，其中，其他概率不變。試證明由此所得新的概率空間的熵是增加的，并用熵的物理意義加以解釋。證明:開因為f(x)=-xlogx是∩型凸函數(shù)，根據(jù)∩型函數(shù)的性質(zhì)有：同理有：兩式相加，得：H()>H(X)物理意義：當信源部分符號趨于等概分布時，信源的熵是增加的。14、（1）為了使電視圖像獲得良好的清晰度和規(guī)定的適當?shù)膶Ρ榷?，需要?×105個像素和10個不同的亮度電平，求傳遞此圖像所需的信息率（比特/秒）。并設每秒要傳送30幀圖像，所有像素獨立變化，且所有亮度電平等概率出現(xiàn)。（2）設某彩電系統(tǒng)，除了滿足對于黑白電視系統(tǒng)的上述要求外，還必須有30個不同的色彩度，試證明傳輸這彩色系統(tǒng)的信息率約是黑白系統(tǒng)的信息率的2.5倍。解：（1）因為每幀圖象可以看成是離散的數(shù)字圖象，每個像素的亮度是隨機而且等概率出現(xiàn)的，則每個像素亮度信源的概率空間為：==1每個像素亮度含有的信息量為：H(X)=log2103.32比特/像素=1哈特/像素現(xiàn)在，所有的像素是獨立變化的，則每幀圖象可以看成是離散亮度信源的無記憶N次擴展信源。故，每幀圖象含有的信息量是：H(XN)=NH(X)=5105log10=5105哈特/幀1.66106比特/幀而每秒傳送30幀圖象，則傳遞這個圖象所需要的信息率為R1=30H(XN)=1.5106哈特/秒4.98107比特/秒（2）證明：每個像素具有10個不同的亮度和30個色彩度。由上面的計算得亮度等概率出現(xiàn)的情況下，每個像素含有的信息量是：H(X)=log2103.32比特/像素。每個像素的色彩度也是等概率出現(xiàn)的，則色彩度信源的概率空間為：==1每個像素色彩度含有的信息量：H(Y)=log2304.91比特/像素而亮度和色彩度是相互獨立的，所以亮度和色彩度同時出現(xiàn)，每像素含有的信息量：H(XY)=H(X)+H(Y)=log10+log30=log3008.23比特/像素如果每幀所用的像素數(shù)和每秒傳送的幀數(shù)都相同的情況下，傳輸這彩色系統(tǒng)的信息率與傳輸黑白系統(tǒng)的信息率之比就等于彩色系統(tǒng)每像素含有的信息量與黑白系統(tǒng)每像素含有的信息量之比：=2.5證畢。15、每幀電視圖像可以認為是由5×105個像素組成，所有像素均是獨立變化，且每一像素又取128個不同的亮度電平，并設亮度電平等概率出現(xiàn)。問每幀圖像含有多少信息量?現(xiàn)有一廣播員在約10000個漢字的字匯中選1000個字來口述此電視圖像，試問廣播員描述此圖像所廣播的信息量是多少(假設漢字字匯是等概率分布，并彼此無依賴)?若要恰當?shù)孛枋龃藞D像，廣播員在口述中至少需要多少漢字?解:∵亮度電平等概率出現(xiàn)∴每個像素所含的信息量為H(X)=log128=7bit/像素。而每個像素均是獨立變化的∴每幀電視圖像所包含的信息量為H(X)=5×105H(X)=3.5×106bit∵假設漢字字匯是等概率分布∴每個漢字出現(xiàn)的概率均為從而每個漢字攜帶的信息量為log10000=13.2877bit/字∵漢字間彼此無依賴，廣播員口述的1000個漢字所廣播的信息量為1000×13.2877=13287.7bit若要恰當?shù)孛枋鰣D像，廣播員在口述中至少需要的漢字數(shù)為≈2.63*10^5個漢字。16、為了傳輸一個由字母A、B、C、D組成的符號集，把每個字母編碼成兩個二元碼脈沖序列，以00代表A，01代表B，10代表C，11代表D。每個二元脈沖寬度為5ms。（1）不同字母等概率出現(xiàn)時，計算傳輸?shù)钠骄畔⑺俾?；?）若每個字母出現(xiàn)的概率分別為，試計算傳輸?shù)钠骄畔⑺俾?。解：?）由題可知，當不同字母等概率出現(xiàn)時，平均自信息量為：H(x)=log4=2(比特/字母)又因為每個二元脈沖寬度為5ms，故一個字母的脈沖寬度為10ms則字母的傳輸速率為100字母/秒故傳輸?shù)钠骄畔⑺俾蕿椋?00比特/秒(2)當每個字母分別以題中的概率出現(xiàn)時，平均自信息量為：H(x)=－∑P(ai)logP(ai)=(1/2)*log2+(1/4)*log4+2*(1/8)*log8=1.75(比特/字母)同樣字母的傳輸速率為100個/秒故傳輸?shù)钠骄畔⑺俾蕿椋?75比特/秒17、證明：。答案略。18、設有一個信源，它產(chǎn)生0，1序列的消息。它在任意時間而且不論以前發(fā)生過什么符號，均按P(0)=0.4，P(1)=0.6的概率發(fā)出符號。(1)試問這個信源是否是平穩(wěn)的？(2)試計算，及；(3)試計算并寫出信源中可能有的所有符號。解：(1)因為信源發(fā)出符號的概率分布與時間平移無關(guān)，而且信源發(fā)出的序列之間也是彼此無依賴的。所以這個信源是平穩(wěn)信源，是離散無記憶信源。(2)＝，計算H(X)≈0.971bit/符號因為信源是平穩(wěn)無記憶信源，所以H(X2)=2H(X)≈1.942bit/兩個符號H(X3|X1X2)=H(X3)=H(X)≈0.971比特/符號===H(X)≈0.97bit/符號(3)H(X4)=4H(X)≈3.884bit/四個符號可能的所有16個符號:000000010010001101000101011001111000100110101011110011011110111119、有一個二元無記憶信源，其發(fā)0的概率為，而約等于1，所以在發(fā)出的二元序列中經(jīng)常出現(xiàn)的是那些一串為0的序列（稱為高概率序列）。對于這樣的信源我們可以用另一新信源來代替，新信源中只包含這些高概率序列。這時新信源，共有n+1個符號，它與高概率的二元序列的對應關(guān)系如下：二元序列：1,01,001,0001,…,00…01(n位),00…000(n位)新信源符號：（1）求；（2）當時求信源的熵。解：依題意，因為是二元無記憶信源，在發(fā)出的二元序列中符號之間彼此是無依賴的，統(tǒng)計獨立的，所以有：1,2由此可得新信源Sn為：證明滿足完備性：因為所以，則：20、有一信源，它在開始時以，，的概率發(fā)出。如果為時，則為的概率為1/3；如果為，為的概率為1/3；如果為，為的概率為1/2，為的概率為0，而且后面發(fā)出的概率只與有關(guān)，又，。試利用馬爾可夫信源的圖示法畫出狀態(tài)轉(zhuǎn)移圖，并計算信源熵。解：由題可得，狀態(tài)轉(zhuǎn)移圖為：a:0.6a:0.6b:0.3c:0.1b:1/2a:1/2c:1/3a:1/3c:1/3a:1/3b:1/3b:1/3abcabcabcaE0E1E2E3E4E5E6E7E8E9E10E11b可見，狀態(tài)E1和E4、E7、E10的功能是完全相同的，狀態(tài)E2和E5、E8、E11的功能是完全相同的，狀態(tài)E3和E6、E12的功能是完全相同的。其中E0是過渡狀態(tài)，而E1、E2、E3組成一個不可約閉集，具有遍歷性。故有如下的狀態(tài)轉(zhuǎn)移圖A;由于此馬爾可夫信源的狀態(tài)必然會進入這個不可約閉集，所以計算信源熵時，可以不考慮過渡狀態(tài)和過渡過程。由此，可得狀態(tài)E1、E2、E3的極限概率：Q(E1)=1/3Q(E1)+1/3Q(E2)+1/2Q(E3)Q(E2)=1/3Q(E1)+1/3Q(E2)+1/2Q(E3)Q(E3)=1/3Q(E1)+1/3Q(E2)Q(E1)+Q(E2)+Q(E3)=1可得：Q(E1)=Q(E2)=3/8，Q(E3)=1/4c:1/3c:1/3c:1/3b:1/2b:1/3c:0.1b:0.3a:0.6c:1/3b:1/2a:1/3E2E3E0E1a:1/3圖A所以H∞=H2=Q(E1)H(1/3,1/3,1/3)+Q(E2)H(1/3,1/3,1/3)+Q(E3)H(1/2,1/2)=1.4388(比特/符號)21、一階馬爾可夫信源的狀態(tài)圖如題圖2-21所示，信源的符號集為并定義。求信源平穩(wěn)后的概率分布；求此信源的熵；近似認為此信源為無記憶時，符號的概率分布等于平穩(wěn)分布。求近似信源的熵并與進行比較；對一階馬爾可夫信源，取何值時取最大值？又當時結(jié)果如何？解：（1），由圖可得于是得到整理計算得即據(jù)一階馬爾可夫信源的熵的表達式可得信源近似為無記憶信源，符號的概率分布等于平穩(wěn)分布，則此信源得到：由此計算結(jié)果可知求一階馬爾可夫信源的最大值。因為求其對p的一階導數(shù)令，得，所以，所以時，達到最大值；的最大值等。當時當時由此可以看出上面的結(jié)論是正確的。2-22一階馬爾可夫信源的狀態(tài)圖如題圖2-22所示，信源的符號集為{0,1,2}。求平穩(wěn)后信源的概率分布；求信源的熵；求當=0和=1時信源的熵，并說明其理由。解：（1）由圖可知一階馬爾可夫信源的狀態(tài)空間E=A={0,1,2}。平穩(wěn)后信源的概率分布就等于一階馬爾可夫信源狀態(tài)的極限分布，即Q(Ei)＝P(ai)i＝1,2,3Ei∈E,ai∈A,而E＝A從狀態(tài)圖中分析可知，這三個狀態(tài)都是正規(guī)常返態(tài)，所以此馬爾可夫鏈具有各態(tài)歷經(jīng)性，平穩(wěn)后狀態(tài)的極限分布存在?？傻脿顟B(tài)一步轉(zhuǎn)移矩陣，得Q(0)＝Q(1)＝Q(2)＝1/3則可得P(0)＝P(1)＝P(2)＝1/3(2)一階馬爾可夫信源的熵H∞＝H2＝∑I=13Q(Ei)H(X∣Ei)＝P(0)H(X∣E)+P(1)H(X∣1)+P(2)H(X∣2)＝1/3H(P1,0,P)+1/3H(P,P1,0)+1/3H(0,P,P1)＝-P1㏒P1-P㏒P＝H(P)(3)當P＝0,H∞＝0當P＝1,H∞＝1因為信息熵是表示信源的平均不確定性，題中當P=1或P=0時表明信源從某一狀態(tài)出發(fā)轉(zhuǎn)移到另一狀態(tài)的情況是一定發(fā)生或一定不發(fā)生，即是確定的事件。當P=1時，從0狀態(tài)一定轉(zhuǎn)移到2狀態(tài)，2狀態(tài)一定轉(zhuǎn)移到1狀態(tài)，1狀態(tài)一定轉(zhuǎn)移到0狀態(tài)。所以不論從何狀態(tài)起信源輸出的序列一定是021021序列，完全確定的。當P=0時，0狀態(tài)永遠處于0狀態(tài)，1狀態(tài)永遠處于1狀態(tài)，2狀態(tài)用于處于2狀態(tài)。信源輸出的符號序列也是確定的。所以當P=1或P=0時，信源輸出什么符號不存在不確定性，完全是確定的，因此確定信源的信息熵等于零。23、設有一個馬爾可夫信源，它的狀態(tài)集為，符號集為，其在某狀態(tài)下發(fā)出符號的概率為，，如題圖2-23所示。題圖2-23求出圖中馬爾可夫信源的狀態(tài)極限概率并找出符號的極限概率。計算信源處在某一狀態(tài)下輸出符號的條件熵，。求出馬爾可夫信源熵。解:(1)此信源的狀態(tài)集不等于符號集，從狀態(tài)轉(zhuǎn)移圖可知狀態(tài)轉(zhuǎn)移矩陣:P=從圖可知此狀態(tài)馬爾可夫鏈是時齊的，狀態(tài)數(shù)有限的和是不可約閉集，所以其具有各態(tài)歷經(jīng)性，平穩(wěn)后狀態(tài)的極限概率分布存在。得到如下方程組：Q(s1)=Q(s3)Q(s2)=3/4Q(s1)+1/2Q(s2)Q(s3)=1/4Q(s1)+1/2Q(s2)Q(s1)+Q(s2)+Q(s3)=1解得：Q(s1)=2/7，Q(s2)=2/7，Q(s3)=3/7符號的極限概率P(ak)=所以P(a1)=Q(s1)P(a1|s1)+Q(s2)P(a1|s2)+Q(s3)P(a1|s3)=3/7，P(a2)=2/7，P(a3)=2/7(2)信源處于某一狀態(tài)下的輸出符號的條件熵 H(X|sj)=-j=1,2,3H(X|s1)=-P(a1|s1)logP(a1|s1)-P(a2|s1)logP(a2|s1)-P(a3|s1)logP(a3|s1)=-1/2log21/2-1/4log21/4-1/4log21/4=1.5比特/符號 H(X|s2)=H(0,1/2,1/2)=1比特/符號 H(X|s2)=H(1,0,0)=0比特/符號（3）馬爾可夫信源熵H∞= =Q(s1)H(X|s1)+Q(s2)H(X|s2)+Q(s3)H(X|s3)=2/7×1.5+3/7×1+0=6/7比特/符號≈0.857比特/符號2-24黑白氣象傳真圖的消息只有黑色和白色兩種，即信源＝{黑，白}，設黑色出現(xiàn)的概率為P（黑）＝0.3，白色出現(xiàn)的概率為P（白）＝0.7。（1）假設圖上黑白消息出現(xiàn)前后沒有關(guān)聯(lián)，求熵；（2）假設消息前后有關(guān)聯(lián)，其依賴關(guān)系為P（白|白）＝0.9，P（黑|白）＝0.1，P（白|黑）＝0.2，P（黑|黑）＝0.8，求此一階馬爾可夫信源的熵；（3）分別求出上述兩種信源的剩余度，比較和的大小，并說明其物理意義。解：（1）如果圖上黑白消息出現(xiàn)沒有關(guān)聯(lián)，則熵為：H（X）=H（0.7，0.3）=0.881bit/符號