信息論基礎(chǔ)復(fù)習(xí)題目

設(shè)離散無記憶信源

其發(fā)生的消息為：（23211223210）求（1）此消息的自信息量。（2）在此消息中平均每個(gè)符號(hào)攜帶的信息量。例2-2第一頁第二頁，共125頁。解：（1）消息的自信息量就是等于消息中各個(gè)符號(hào)的自信息量之和。根據(jù)題意可得：

此消息中共有14個(gè)“0”符號(hào)，13個(gè)“1”符號(hào)，12個(gè)“2”符號(hào)，6個(gè)“3”符號(hào)，則得到的自信息量是：第二頁第三頁，共125頁。（2）此消息中平均每個(gè)符號(hào)攜帶的信息量為：原因：(2)問的值是該特定消息中平均每個(gè)符號(hào)攜帶的信息量，而信息熵是離散無記憶信源平均每個(gè)符號(hào)攜帶的信息量，是統(tǒng)計(jì)平均值。信源的信息熵:結(jié)論:

(2)問的值與信源的信息熵不完全相等第三頁第四頁，共125頁。

設(shè)在一正方形棋盤上共有64個(gè)方格，如果甲將一粒棋子隨意放在棋盤中的某方格且讓乙猜測(cè)棋子所在的位置所攜帶的信息量：（1）將方格按順序編號(hào)，令乙猜測(cè)棋子所在方格的順序號(hào)；（2）將方格分別按行和列編號(hào)，甲將棋子所在方格的行或列編號(hào)告訴乙之后，再令乙猜測(cè)棋子所在列或行的位置。

例2-3：第四頁第五頁，共125頁。解：（1）令把棋子任意放在棋盤的某一格為事件xi，則該事件發(fā)生的概率為：則該事件攜帶的信息量為：

（2）設(shè)行為隨機(jī)變量X，列為隨機(jī)變量Y，則在事件yj發(fā)生后事件xi發(fā)生的概率為：則該事件攜帶的信息量為：由結(jié)果可知:

事件yj的出現(xiàn)降低了事件xi發(fā)生所攜帶的信息量原因:

事件yj的出現(xiàn)帶來了事件xi的部分的信息，導(dǎo)致對(duì)事件xi的不確定性減小第五頁第六頁，共125頁。設(shè)一系統(tǒng)的輸入符號(hào)集X=(x1,x2,x3,x4,x5)，輸出符號(hào)集Y=(y1,y2,y3,y4)

輸入符號(hào)與輸出符號(hào)間的聯(lián)合分布為試求:

H(XY)、H(X)、H(Y)、H(Y|X)和H(X|Y)例2-4第六頁第七頁，共125頁。解：由全概率公式可知：則從已知可求：第七頁第八頁，共125頁。H(Y|X)=H(XY)-H(X)=2.665-2.066=0.599bit/symbolH(X|Y)=H(XY)-H(Y)=2.665-1.856=0.809bit/symbol第八頁第九頁，共125頁。定義：聯(lián)合集ＸＹＺ中，在給定zk的條件下，xi與yj之間的互信息量定義為條件互信息量，即表明：在隨機(jī)變量Z出現(xiàn)符號(hào)zk的前提條件下，隨機(jī)變量Y出現(xiàn)符號(hào)yj前、后，對(duì)信源發(fā)送符號(hào)xi的條件不確定性的減少2.2.2條件互信息第九頁第十頁，共125頁。上式表明：在隨機(jī)變量Z出現(xiàn)符號(hào)zk的前提條件下，信道1通信前、后，輸入與輸出端同時(shí)出現(xiàn)yj和xi的條件不確定性的減少。

利用互信息和條件互信息可解決符號(hào)序列的信息測(cè)量問題第十頁第十一頁，共125頁。發(fā)送的信息:H(X)損失的信息:H(X|Y)通過信道傳遞到接收端的關(guān)于X的信息:I(X;Y)

信源X有擾信道信宿Y例2-6問:通信中發(fā)送的信息是多少?

信道中損失的信息是多少?X通過信道傳遞了多少信息給信宿？如果X=Y，說明信道無干擾,則I(X;Y)=H(X)如果X與Y相互獨(dú)立，說明干擾很大,I(X;Y)=0第十一頁第十二頁，共125頁。例2-7：把已知信源信道上，求在該信道上傳輸?shù)钠骄バ畔⒘縄(X;Y)、疑義度H(X/Y)、噪聲熵H(Y/X)和聯(lián)合熵H(XY).接到下圖所示的0.980.80.020.2第十二頁第十三頁，共125頁。解：由題意可知第十三頁第十四頁，共125頁。第十四頁第十五頁，共125頁。第十五頁第十六頁，共125頁。平均互信息：噪聲熵：疑義度：第十六頁第十七頁，共125頁。例2-10：設(shè)有一批電阻，按阻值分70%是2千歐姆，30%是5千歐姆；按功耗分64%是1/8W，其余是1/4W?，F(xiàn)已知2千歐姆阻值的電阻中80%是1/8W。問通過測(cè)量阻值可以平均得到的關(guān)于瓦數(shù)的信息量是多少？解：根據(jù)題意，設(shè)電阻的阻值為事件X，電阻的功率為事件Y。它們的概率空間分別為：并且已知：第十七頁第十八頁，共125頁。首先計(jì)算根據(jù)全概率公式可得：

通過測(cè)量電阻阻值可以得到關(guān)于瓦數(shù)的平均信息量就是平均互信息I（X；Y）則通過測(cè)量阻值可以平均得到的關(guān)于瓦數(shù)的信息量是0.816比特第十八頁第十九頁，共125頁。0110011/21/201201101001012例2-11：有一離散無記憶信源，其輸出為相應(yīng)的概率為設(shè)計(jì)兩個(gè)獨(dú)立試驗(yàn)去觀察它，其結(jié)果分別為已知條件概率為第十九頁第二十頁，共125頁。XY1011/4001/41/41/40121/21/2P(Y1)XY2011/401/4001/20121/21/2P(Y2)解：（1）因?yàn)樗员仨毲蟪鰟t有：由此可知第二個(gè)試驗(yàn)好。第二十頁第二十一頁，共125頁。（2）：因?yàn)樗员仨毲蟪鲇钟捎谠囼?yàn)Y1，Y2是相互獨(dú)立的試驗(yàn)，所以則有：XY1Y2000110111000001001/201/2012XY1Y2000110111/4000001/4001/401/40121/41/41/41/4P(Y1Y2)則有：第二十一頁第二十二頁，共125頁。由此可知：做兩個(gè)試驗(yàn)比做可多得關(guān)于X的信息為中的一個(gè)試驗(yàn)各（3）表示做完實(shí)驗(yàn)Y2后，從實(shí)驗(yàn)Y1可獲得關(guān)于X的信息量為0.5bit/signal。表示做完實(shí)驗(yàn)Y1后，從實(shí)驗(yàn)Y2可獲得關(guān)于X的信息量為1bit/signal。第二十二頁第二十三頁，共125頁。例3-1第二十三頁第二十四頁，共125頁。例3-2：

（1）為了使電視圖像獲得良好的清晰度和規(guī)定的適當(dāng)?shù)膶?duì)比度，需要用

個(gè)像素和10個(gè)不同亮度的電平，設(shè)每秒要傳遞30幀圖像，所有象素是獨(dú)立變化的，且所有亮度電平等概率出現(xiàn).求傳遞此圖像所需的信息率（比特/秒）.

（2）設(shè)某彩電系統(tǒng)，除了滿足對(duì)黑白電視系統(tǒng)的上述要求外，還須有30個(gè)不同的色彩度，試證明傳輸這彩色系統(tǒng)的信息率約是黑白系統(tǒng)信息率的2.5倍。第二十四頁第二十五頁，共125頁。解：（1）每個(gè)象素亮度信源的概率空間為：

每個(gè)象素亮度含有的信息量為：

H(X)=log10=1哈特來/象素=3.32比特/象素每幀圖像含有的信息量為：

設(shè)每秒傳送30幀圖像，則傳遞此圖像所需的信息率為：

第二十五頁第二十六頁，共125頁。（2）證明：

色彩度信源的概率空間為:

每個(gè)象素色彩度含有的信息量為：

H(Y)=log30=4.91比特/象素亮度和色彩度同時(shí)出現(xiàn)，每個(gè)象素含有的信息量為：

H(XY)=H(X)+H(Y)=log10+log30=8.23比特/象素

傳輸這彩色系統(tǒng)的信息率與傳輸黑白系統(tǒng)的信息率之比就等于彩色系統(tǒng)每象素含有的信息量與黑白系統(tǒng)每象素含有信息量之比，即：H(XY)/H(X)=2.5

則證明傳輸這彩色系統(tǒng)的信息率是傳輸黑白系統(tǒng)的信息率的2.5倍。第二十六頁第二十七頁，共125頁。例3-3：

每幀電視圖像可以認(rèn)為是由

個(gè)象素組成的，所以象素都是獨(dú)立變化的。且每一個(gè)象素又取128個(gè)不同的亮度電平，并設(shè)亮度電平等概率出現(xiàn)。若現(xiàn)有一個(gè)廣播員在約10000個(gè)漢字的字集中選1000個(gè)字來口述此電視圖像（設(shè)每個(gè)字是等概率分布的，并且彼此獨(dú)立的）。試問廣播員描述此圖像所廣播的信息量是多少？若要恰當(dāng)描述此圖像，廣播員在口述中至少需用多少漢字？第二十七頁第二十八頁，共125頁。解：（1）分析可知漢字字集是等概率分布的，則漢字字集信源為得該漢字字集中每個(gè)漢字含有的信息量為：

H(Y)=log10000=13.29比特/字廣播員描述此幀圖像所廣播的信息量為：（2）分析可知每個(gè)象素的亮度信源為每個(gè)象素亮度含有的信息量為：

H(X)=log128=7比特/象素每幀圖像含有的信息量為：廣播員口述此圖像至少需用的漢字?jǐn)?shù)為：第二十八頁第二十九頁，共125頁。例3-4：

對(duì)一最高頻率分量為4kHz的模擬信號(hào)以奈奎斯特采樣定理采樣，已知抽樣結(jié)果是一個(gè)獨(dú)立的平穩(wěn)隨機(jī)序列?，F(xiàn)將每個(gè)抽樣值量化為5個(gè)離散電平之一，已知這5個(gè)電平構(gòu)成的符號(hào)集{X}的概率特性為

求這個(gè)離散信源每秒傳送的平均信息量。解：由題意可知采樣率為8kHz，則符號(hào)速率是8000個(gè)符號(hào)/s。每個(gè)符號(hào)的平均信息量為則這個(gè)離散信源每秒傳送的平均信息量為

第二十九頁第三十頁，共125頁。例3-5：設(shè)某二階離散平穩(wěn)信源X=X1X2的原始信源的信源模型為：

X=X1X2中前后兩個(gè)符號(hào)的條件概率為：

比較原始信源與二階信源的熵。第三十頁第三十一頁，共125頁。信源X提供的熵

平均每個(gè)符號(hào)攜帶的信息量：

結(jié)論：極限熵、條件熵都小于原始信源的熵原因：符號(hào)之間存在相關(guān)性

解：原始信源的熵：

條件概率確定的條件熵：

第三十一頁第三十二頁，共125頁。二.馬爾可夫信源的狀態(tài)轉(zhuǎn)移圖

例3-6： 設(shè)有一個(gè)二進(jìn)制一階馬爾可夫信源，其信源符號(hào)集為A={0,1},條件概率為

求狀態(tài)轉(zhuǎn)移矩陣。第三十二頁第三十三頁，共125頁。解：信源符號(hào)個(gè)數(shù)q=2，k=1,故狀態(tài)數(shù)則令狀態(tài)S1=0,狀態(tài)S2=1狀態(tài)圖：

S1=0S2=10.750.500.250.50根據(jù)狀態(tài)圖求狀態(tài)轉(zhuǎn)移概率：

p(S1|S1)=0.25p(S2|S1)=0.75p(S1|S2)=0.50p(S2|S2)=0.50則狀態(tài)轉(zhuǎn)移矩陣為：

第三十三頁第三十四頁，共125頁。有一個(gè)二進(jìn)制二階馬爾可夫信源，其信源符號(hào)集為A={0,1},條件概率為：求狀態(tài)轉(zhuǎn)移矩陣。例3-7：第三十四頁第三十五頁，共125頁。由狀態(tài)圖可知轉(zhuǎn)移矩陣：則令：狀態(tài)S1=00,狀態(tài)S2=01，狀態(tài)S3=10，狀態(tài)S4=11則狀態(tài)圖：

0.5S201S310S100S4110.80.80.50.50.50.20.2解：信源符號(hào)個(gè)數(shù)q=2，k=2,故狀態(tài)數(shù)第三十五頁第三十六頁，共125頁。定理：馬爾可夫信源具有穩(wěn)態(tài)分布的充要條件是存在一個(gè)正整數(shù)N，使馬爾可夫信源的狀態(tài)轉(zhuǎn)移矩陣中的所有元素均大于零。例3-8

有一個(gè)馬爾可夫鏈，其狀態(tài)轉(zhuǎn)移矩陣為：問：是否存在穩(wěn)態(tài)分布，如果存在求此穩(wěn)態(tài)分布。

第三十六頁第三十七頁，共125頁。解：

由此判斷：穩(wěn)態(tài)分布存在由WP=W以及各狀態(tài)概率之和為1得：和第三十七頁第三十八頁，共125頁。3.舉例說明馬爾可夫信源熵的計(jì)算方法

例3-9:有一個(gè)二進(jìn)制二階馬爾可夫信源，其信源符號(hào)集為A={0,1},條件概率為：求狀態(tài)轉(zhuǎn)移矩陣。第三十八頁第三十九頁，共125頁。解:由例7可知狀態(tài)轉(zhuǎn)移矩陣為：可知：此信源是遍歷性的馬爾可夫信源，穩(wěn)態(tài)分布存在設(shè)穩(wěn)態(tài)分布為：

則利用WP=W和可知：對(duì)于遍歷性馬爾可夫信源有第三十九頁第四十頁，共125頁。由

則有：

第四十頁第四十一頁，共125頁。3.5

信源的相關(guān)性和剩余度一.信源的相關(guān)性

信源輸出符號(hào)之間的依賴關(guān)系

對(duì)于離散平穩(wěn)信源有

當(dāng)信源輸出符號(hào)之間的相關(guān)程度越長，實(shí)際熵越小

二.信源冗余度γ

第四十一頁第四十二頁，共125頁。例3-10:

英文26個(gè)字母加空格共27個(gè)符號(hào)，根據(jù)統(tǒng)計(jì)出現(xiàn)的概率如表所示，則英文字母攜帶的最大信息量是多少？冗余度為多少？

序號(hào)字母出現(xiàn)概率序號(hào)字母出現(xiàn)概率1空格0.181715M0.021052E0.107316U0.020103T0.085617G0.016334A0.066818Y0.016235O0.065419P0.016236N0.058120W0.012607R0.055921B0.011798I0.051022V0.007529S0.049923K0.0034410H0.0430524X0.0013611D0.0310025J0.0010812L0.0277526Q0.0009913F0.0239527Z0.0006314C0.02260第四十二頁第四十三頁，共125頁。解：英文字母攜帶的最大信息量即為等概時(shí)攜帶的信息量：英文字母攜帶的實(shí)際熵英文字母的冗余度第四十三頁第四十四頁，共125頁。例3-11：中文冗余度的統(tǒng)計(jì)比英文要復(fù)雜得多，難得多，假如以《辭海》（上海，1989）收集的大約15000漢字為信源消息符號(hào)，則中文的最大信息熵為目前還沒有找到給出中文實(shí)際熵好的統(tǒng)計(jì)方法的文獻(xiàn)，但根據(jù)目前廣泛使用的文本壓縮軟件的壓縮率來看，中文實(shí)際熵應(yīng)該不會(huì)大于5比特/漢字，估計(jì)中文的冗余度大約在80%左右。

第四十四頁第四十五頁，共125頁。

討論γ

：

從提高抗干擾能力角度出發(fā):希望減少或去掉剩余度希望增加或保留信源的剩余度因?yàn)?剩余度大的消息具有很強(qiáng)的抗干擾能力。當(dāng)干擾使消息在傳輸過程中出現(xiàn)錯(cuò)誤時(shí)，能從它的上下關(guān)聯(lián)中糾正錯(cuò)誤。從提高信息傳輸?shù)挠行杂^點(diǎn)出發(fā):原因是什么?第四十五頁第四十六頁，共125頁。例3-12：黑白氣象傳真圖的消息只有黑白兩種顏色，即信源X={黑，白}，且p(黑)=0.3，p(白)=0.7。（1）假設(shè)圖上黑白消息出現(xiàn)前后沒有關(guān)系，求熵H(X)。（2）假設(shè)消息前后由關(guān)系，其依賴關(guān)系為

p(白|白)=0.9，p(黑|白)=0.1，p(白|黑)=0.2，

p(黑|黑)=0.8，求此一階馬爾可夫信源的熵H2。（3）分別求上述兩種信源得剩余度，并比較H(X)和H2的大小，并說明其物理意義。第四十六頁第四十七頁，共125頁。信源的信息熵

（2）分析得此信源為一階馬爾可夫信源，它的的狀態(tài)集為：A={S1=黑，S2=白}。則狀態(tài)轉(zhuǎn)移圖：S1

S20.20.10.80.9解：（1）假設(shè)黑白氣象傳真圖上黑白消息出現(xiàn)的前后沒有關(guān)系，則等效于一個(gè)離散無記憶信源。信源概率空間為：

第四十七頁第四十八頁，共125頁。則其狀態(tài)轉(zhuǎn)移矩陣為：由此可見：此馬爾可夫信源是遍歷的，穩(wěn)態(tài)分布存在，則設(shè)W=(p(S1)p(S2)),根據(jù)WP=W可得：可以求出:

第四十八頁第四十九頁，共125頁。則此信源的熵為：

（3）黑白消息信源的剩余度

即第四十九頁第五十頁，共125頁。例4-1：其中：p表示傳輸中發(fā)生錯(cuò)誤的概率二元對(duì)稱信道(BSC)(二進(jìn)制對(duì)稱信道)第五十頁第五十一頁，共125頁。

其中：p、q表示正確傳輸?shù)母怕?/p>

二元?jiǎng)h除信道(二進(jìn)制刪除信道)第五十一頁第五十二頁，共125頁。例4-2：考慮二元對(duì)稱信道，其信源概率空間為

信道XY（0，1）（0，1）求其平均互信息第五十二頁第五十三頁，共125頁。解:應(yīng)用全概率公式則有：第五十三頁第五十四頁，共125頁。則平均互信息：當(dāng)信道固定，即p為一個(gè)固定常數(shù)時(shí)，可得到I(X;Y)是信源輸出分布ω的上凸函數(shù)。

當(dāng)信源固定，即ω是一個(gè)常數(shù)時(shí),可得到I(X;Y)是信道傳遞概率p的下凸函數(shù)。當(dāng)p=0.5時(shí)，I(X;Y)=0，在接收端未獲得信息量。

當(dāng)ω=1/2

時(shí)，即取極大值.第五十四頁第五十五頁，共125頁。例4-3：擲色子，如果結(jié)果是1，2，3，4，則拋一次硬幣；如果結(jié)果是5、6，則拋兩次硬幣。試計(jì)算從拋硬幣的結(jié)果可以得到多少擲色子的信息量。解：設(shè)擲色子結(jié)果是1，2，3，4為事件X=0，結(jié)果是5、6為事件X=1；Y=0表示拋硬幣出現(xiàn)0次正面,Y=1表示拋硬幣出現(xiàn)1次正面,Y=2表示拋硬幣出現(xiàn)2次正面。信源概率空間為信道矩陣為輸出符號(hào)的概率空間為則有：第五十五頁第五十六頁，共125頁。例4-4：求二元無記憶對(duì)稱信道的二次擴(kuò)展信道。解：輸入擴(kuò)展為：00，01，10，11輸出擴(kuò)展為：00，01，10，11傳遞矩陣擴(kuò)展為：請(qǐng)問：與I（X；Y）之間的關(guān)系？第五十六頁第五十七頁，共125頁。

定理1:若信道的輸入、輸出分別為N長序列X和Y，且信道是無記憶的，即：用兩個(gè)定理回答這個(gè)問題定理2：若信道的輸入、輸出分別為N長序列X和Y，且信源是無記憶的，即：第五十七頁第五十八頁，共125頁。由定理1和定理2當(dāng)信源和信道都是無記憶時(shí)有：

當(dāng)每個(gè)序列中的分量Xi取值于同一信源符號(hào)集，且具有同一種概率分布，則輸出Y的分量Yi也取值同一符號(hào)集，則各I（Xi；Yi）是相等的。即：對(duì)于N次擴(kuò)展，則有第五十八頁第五十九頁，共125頁。例4-5：下圖中的X、Y、Z滿足馬氏鏈，求該串聯(lián)信道的總信道矩陣。b1a1a2c1b2c2b3c3XYZ1/31/31/31/21/21/31/32/32/31解：由圖可知第五十九頁第六十頁，共125頁。例4-6：考慮二元對(duì)稱信道，其信源概率空間為求該信道的信道容量。解：信道的平均互信息

當(dāng)ω=1-ω=1/2

時(shí)，I(X;Y)取極大值，即接收到的信息量最大，則信道容量為：C=maxI(X;Y)=1-H(p)由此可知：信道容量只是傳遞概率的函數(shù)第六十頁第六十一頁，共125頁。例4-7：求具有以下信道矩陣的信道的信道容量解：分析可知這是一個(gè)對(duì)稱信道，則信道容量為

結(jié)論：在該對(duì)稱信道中，只有當(dāng)信道輸入符號(hào)等概分布時(shí)，每個(gè)符號(hào)平均能傳送的信息為0.126bit，一般情況下每個(gè)符號(hào)平均傳輸?shù)男畔⒍际切∮?.126bit

。第六十一頁第六十二頁，共125頁。例4-8：求均勻信道的信道容量。為正確傳遞概率為錯(cuò)誤傳遞概率對(duì)于二元對(duì)稱信道：r=2，則信道容量C：解：均勻信道是對(duì)稱信道的一種特例，則其信道容量用對(duì)稱信道的信道容量的求解公式，則

第六十二頁第六十三頁，共125頁。例4-9：求二元對(duì)稱刪除信道的信道容量。解：分析可知該信道分成對(duì)稱的2個(gè)子信道則該信道是一個(gè)準(zhǔn)對(duì)稱信道

其信道容量為

其中輸入符號(hào)個(gè)數(shù)n=2，則有：第六十三頁第六十四頁，共125頁。例4-10：設(shè)有擾離散信道的傳輸情況如圖所示，求C以及達(dá)到C時(shí)的輸入概率分布.利用對(duì)稱信道的信道容量公式求得：第六十四頁第六十五頁，共125頁。解：I(X;Y)=H(Y)-H(Y|X)則有：達(dá)到C時(shí)的輸入分布：第六十五頁第六十六頁，共125頁。六.N次擴(kuò)展離散無記憶信道的信道容量

表示某時(shí)刻通過離散無記憶信道傳輸?shù)淖畲笮畔⒘?。則：

對(duì)于離散無記憶信道有：對(duì)于N次擴(kuò)展信道，任何時(shí)刻是相同的。第六十六頁第六十七頁，共125頁。

例4-12:

已知信道的帶寬B為3kHz,信號(hào)在信道傳輸中受到單邊功率譜密度為的加性白高斯噪聲的干擾,信號(hào)的平均功率S為9W.

(1)求信道的容量;(2)若信道帶寬增加到原來的10倍,并保持信道容量不變,那么信號(hào)平均功率要改變多少dB?解:

(1)信道容量為(2)帶寬變?yōu)?0B,而C保持不變,假設(shè)此時(shí)對(duì)應(yīng)的信號(hào)功率為則第六十七頁第六十八頁，共125頁。無損信道的剩余度第五節(jié)信源與信道匹配一.信道剩余度=C-I(X;Y)=C-R二.相對(duì)剩余度=1-R/C對(duì)于無損信道C=logr無損信道的相對(duì)剩余度信源的剩余度

對(duì)于無損信道，可通過信源編碼，減小信源的剩余度，提高信道的信息傳輸率使之達(dá)到C。第六十八頁第六十九頁，共125頁。例4-13：有一個(gè)二元對(duì)稱信道，其信道矩陣如圖所示。設(shè)該信道以1500個(gè)二元符號(hào)/秒的速度傳輸輸入符號(hào)?，F(xiàn)有一消息序列共有14000個(gè)二元符號(hào)，并設(shè)在這消息中p(1)=p(0)=1/2。問從信息傳輸?shù)慕嵌葋砜紤]，10秒內(nèi)能否將這消息序列無失真?zhèn)魉屯辍?000.980.020.980.021解： 分析得消息信源的熵為H（X）=1比特則這個(gè)消息序列含有信息量

14000*1=14000比特。第六十九頁第七十頁，共125頁。由圖可知，信道矩陣為：由信道矩陣可知，此信道為二元對(duì)稱信道，所以其信道容量（最大信息傳輸率）為：信道的最大信息傳輸速率：信道在10秒鐘內(nèi)能無失真?zhèn)鬏數(shù)淖畲笮畔⒘?12879比特

14000>12879則從信息傳輸?shù)慕嵌瓤紤]，不可能在10秒內(nèi)將這消息無失真?zhèn)鬏斖?。第七十頁第七十一頁，?25頁。例4-14：設(shè)某一信號(hào)的信息輸出率為5.6kbps，噪聲功率譜為傳輸。試求無差錯(cuò)傳輸需要的最小輸入功率P是多少？

在帶寬B=4kHz的高斯信道中解：由香農(nóng)公式可知，該信道的信道容量為要想使信息輸出率為5.6kbps的信號(hào)無差錯(cuò)的傳輸，則必須有得

第七十一頁第七十二頁，共125頁。2.二元碼：3.定長碼：8.非同價(jià)碼：信道的基本符號(hào)集中碼元個(gè)數(shù)為2√

每個(gè)碼元所占的傳輸時(shí)間不完全相同7.同價(jià)碼：每個(gè)碼元所占的傳輸時(shí)間相同√6.奇異碼：碼中碼字至少有兩個(gè)相同5.非奇異碼：碼中所有的碼字都不相同√4.變長碼：碼中的碼字長短不一碼中所有碼字的長度都相同二.碼的類型1.分組碼：將信源符號(hào)集中的每個(gè)信源組符號(hào)映射成一個(gè)固定的碼字

第七十二頁第七十三頁，共125頁。例5-1：設(shè)有二元信道的信源編碼器，其概率空間編碼后的結(jié)果：信源符號(hào)Si碼1碼2碼3碼4S100000S201011110S3100010000S4111111110定長碼非奇異碼非奇異碼變長碼變長碼奇異碼第七十三頁第七十四頁，共125頁。9.N次擴(kuò)展碼（類似N次擴(kuò)展信源）舉例：10.唯一可譯碼：

一個(gè)分組碼若對(duì)任意有限的整數(shù)N,其N次擴(kuò)展碼均為非奇異碼，則稱為唯一可譯碼?；蛎總€(gè)信源符號(hào)序列映射成一個(gè)固定的碼字，并且代碼組中每個(gè)碼字只能唯一地被譯成所對(duì)應(yīng)的信源符號(hào)序列。11.即時(shí)碼：

無需考慮后續(xù)的碼符號(hào)即可從碼符號(hào)序列中譯出碼字，這樣的唯一可譯碼稱為即時(shí)碼，又稱非延時(shí)碼。*唯一可譯碼要成為即時(shí)碼的條件：其中任一碼字都不是其他碼字的前綴第七十四頁第七十五頁，共125頁。即時(shí)碼可用樹圖構(gòu)造：樹根一階節(jié)點(diǎn)二階節(jié)點(diǎn)

三階節(jié)點(diǎn)(終端節(jié)點(diǎn))A00011010111001000111110101100011010001(1)樹圖的最頂部的節(jié)點(diǎn)稱為樹根，樹枝的盡頭稱為節(jié)點(diǎn)(2)每個(gè)節(jié)點(diǎn)的分支數(shù)等于碼元數(shù)，且各分支分別對(duì)應(yīng)一個(gè)固定的碼元，各分支伸出方向所對(duì)應(yīng)的碼元是統(tǒng)一的，如圖向左伸出為0，向右伸出為1。

(3)各碼字分布在碼樹的終端節(jié)點(diǎn)(即不再分支的節(jié)點(diǎn))。

(4)節(jié)點(diǎn)一旦被分配碼字，后邊的枝便要去掉，否則成為非即時(shí)碼。第七十五頁第七十六頁，共125頁。例5-2：

英文電報(bào)有32個(gè)符號(hào)(26個(gè)字母加上6個(gè)字符),請(qǐng)問對(duì)信源符號(hào)進(jìn)行二進(jìn)制編碼，要想有唯一可譯碼，碼長至少為多少？解：r=2,q=32,N=1，要想有唯一可譯碼，則第七十六頁第七十七頁，共125頁。二、定長編碼定理進(jìn)行長度為的定長編碼，對(duì)用碼元集設(shè)離散無記憶信源的熵為H(S)，其N次擴(kuò)展對(duì)于只要滿足(正定理)則當(dāng)N足夠大時(shí)，幾乎可實(shí)現(xiàn)無失真信源編碼，此時(shí)譯碼差錯(cuò)小于δ。反之，若則當(dāng)N足夠大時(shí)，譯碼錯(cuò)誤概率趨于1(編碼誤差任意大)（逆定理）信源為第七十七頁第七十八頁，共125頁。例5-3：仍以英文電報(bào)為例，當(dāng)認(rèn)為各符號(hào)是等概分布時(shí)的熵為，但是考慮相關(guān)性后英文信源的極限熵為

那么對(duì)它們進(jìn)行碼長為l的定長編碼時(shí)，各自需要的碼長是多少？解：等概時(shí)所需的碼長是5，而考慮相關(guān)性時(shí)需要的碼長是2。第七十八頁第七十九頁，共125頁。三.編碼效率η當(dāng)允許錯(cuò)誤概率小于δ時(shí)，信源符號(hào)序列的長度N：為自信息的方差如果為最佳編碼，則第七十九頁第八十頁，共125頁。例5-4：設(shè)離散無記憶信源求信源序列的長度。對(duì)S采取等長二元編碼，要求編碼效率允許錯(cuò)誤概率第八十頁第八十一頁，共125頁。二.克拉夫特(Kraft)不等式和麥克米倫(McMillan)不等式

設(shè)信源符號(hào)集為其分別對(duì)應(yīng)碼長為l1,l2,…lq，則即時(shí)碼存在的充要條件是：對(duì)信源進(jìn)行編碼，相應(yīng)的碼字集為碼符號(hào)集為1.Kraft不等式：2.McMillan不等式

在滿足kraft不等式的條件下，唯一可譯碼存在的充要條件是：第八十一頁第八十二頁，共125頁。

設(shè)S0為原始碼字的集合。再構(gòu)造一系列集合S1,S2,…Sn。構(gòu)造S1,S2,…Sn的方法：

1、首先考察S0中所有的碼字。若碼字Wj是碼字Wi的前綴，即Wi=WjA，則將后綴A列為S1中的元素，S1就是由所有具有這種性質(zhì)的A構(gòu)成的集合。

2、當(dāng)n>1，則將S0于Sn-1比較，看是否S0中的碼字是Sn-1的前綴，如果是，則取后綴為Sn中元素，且看Sn-1中碼字是否為S0中碼字的前綴，如果是，則取后綴為Sn中元素，如此構(gòu)成集合Sn。三.唯一可譯碼判斷準(zhǔn)則準(zhǔn)則：一種碼為唯一可譯碼的充要條件是S1,S2,…中沒有一個(gè)含有S0中的碼字。第八十二頁第八十三頁，共125頁。S0S1S2S3S4S5S6S7S8adebdebaddeb0cbbcdebcdeadabbbaddebbbcde結(jié)論：當(dāng)N>7時(shí)，Sn為空集，而在S5中包含S0中的碼字，故而S0不是唯一可譯碼。例5-5：設(shè)消息集合中共有7個(gè)消息，分別為被編碼成對(duì)應(yīng)的碼字，判斷是否是唯一可譯碼。第八十三頁第八十四頁，共125頁。例5-6:有一離散無記憶信源

,求對(duì)原始信源和二次擴(kuò)展信源用{0，1}碼元集進(jìn)行編碼后的信息傳輸率以及編碼效率.解:(1)用{0，1}對(duì)之進(jìn)行編碼，有(2)二次擴(kuò)展信源為：第八十四頁第八十五頁，共125頁。②用0，1碼符號(hào)分別代表概率最小的兩個(gè)信源符號(hào)，并將這兩個(gè)概率最小的信源符號(hào)合并成一個(gè)，從而得到只包含q-1個(gè)符號(hào)的新信源S1,稱為縮減信號(hào)源。三.二元Huffman編碼1.編碼步驟①將信源發(fā)出的q個(gè)信源按其概率依次從大到小排列③把縮減信源S1的符號(hào)按概率從大到小排列，再將其最后兩個(gè)概率最小的符號(hào)合并成一個(gè)符號(hào)，并分別用0和1碼元表示，這樣形成q-2個(gè)符號(hào)的新信源S2。④依此類推，直至信源只剩兩個(gè)符號(hào)為止，并分別用“0”和“1”表示。⑤從最后一級(jí)縮減信源開始，向前返回，得出各信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即相應(yīng)碼字。第八十五頁第八十六頁，共125頁。例5-8信源符號(hào)Si

概率p(Si)

編碼過程碼字Wi

碼長liS1S2S3S10.4S20.2S30.2S40.1S50.10.40.20.40.60.210101001編碼過程：101200030010400114第八十六頁第八十七頁，共125頁。用樹圖檢驗(yàn)是否為即時(shí)碼0A01001110100000100011第八十七頁第八十八頁，共125頁。(1)每次對(duì)信號(hào)縮減時(shí)，賦予最后兩個(gè)概率最小的符號(hào)用“0”和“1”是可任意的。(2)對(duì)信源進(jìn)行縮減時(shí)兩個(gè)概率最小的符號(hào)合并后的概率與其他符號(hào)概率相同時(shí)，可任意排序。經(jīng)哈夫曼編碼方法得到的碼并非是唯一的,造成非唯一的原因：

碼字Wi

碼長l

i

S10.40.40.40.6002

S20.20.20.40.4102

S30.20.20.2112

S40.10.20103

S50.1011301010101例題5-8：第八十八頁第八十九頁，共125頁。A00111000101101010011即時(shí)碼由此可見：結(jié)論：當(dāng)進(jìn)行哈夫曼編碼時(shí)，為了得到質(zhì)量好的碼，應(yīng)使合并的信源符號(hào)位于縮減信源序列盡可能高的位置，這樣可充分利用短碼。第八十九頁第九十頁，共125頁。r元哈夫曼碼可由二元哈夫曼碼的編碼方法推廣得到。只是編碼過程中構(gòu)成縮減信源時(shí)，每次將r個(gè)概率最小的符號(hào)合并，并分別用0，1，…，r-1碼元表示。為了充分利用短碼，使哈夫曼碼的平均碼長最短，必須是最后一個(gè)縮減信源有r個(gè)信源符號(hào)。因此，對(duì)于r元哈夫曼碼，信源S的符號(hào)個(gè)數(shù)q必須滿足

如果信源S的符號(hào)個(gè)數(shù)q不滿足上式，則增補(bǔ)一些概率為0的信源符號(hào)。四.r元哈夫曼碼第九十頁第九十一頁，共125頁。例5-9：有一離散無記憶信源碼元集X=(0,1,2)，對(duì)S進(jìn)行3元哈夫曼編碼。解：第九十一頁第九十二頁，共125頁。信源符號(hào)概率編碼過程碼字Wi

碼長li

Sip(Si)S1S2

Wi

li

S10.40.40.401

S20.30.30.321

S30.20.20.3102

S40.050.05122S50.0250.051103S60.0251113S701123210210210第九十二頁第九十三頁，共125頁?；舴蚵幋a的特點(diǎn)：

1）由于霍夫曼編碼總是以最小概率相加的方法來縮減參與皮埃對(duì)的概率個(gè)數(shù)，因此概率越小，對(duì)縮減的貢獻(xiàn)越大，其對(duì)應(yīng)消息的碼字也越長。2）最小概率相加的方法使得編碼不具有唯一性，尤其是碰到存在幾個(gè)消息符號(hào)有著相同概率的情況，將會(huì)有多種路徑選擇，即既具有多種可能的代碼組集合。3）盡管對(duì)同一信源存在著多種結(jié)果的霍夫曼編碼，但它們的平均碼長幾乎都是相等的，因?yàn)槊恳环N路徑選擇都是使用最小概率相加的方法，其實(shí)質(zhì)都是遵循最佳編碼的原則，因此霍夫曼編碼是最佳編碼。

霍夫曼編碼存在的問題：

1）霍夫曼編碼要求信源消息概率已知或可估計(jì)。由于初始信源不可能總是統(tǒng)計(jì)好了概率，為此編碼之前必須先估算信源的統(tǒng)計(jì)特性。在信源具有記憶性能并用霍夫曼編碼來表示信源的擴(kuò)展輸出時(shí)，概率的估計(jì)很耗費(fèi)時(shí)間。2）霍夫曼編碼是建立在編碼器和譯碼器都知道碼樹結(jié)構(gòu)的基礎(chǔ)上的，如果信源消息數(shù)目變大，則樹型結(jié)構(gòu)的大小和算法的復(fù)雜性會(huì)呈指數(shù)規(guī)律增加。第九十三頁第九十四頁，共125頁。例6-1：

參見下圖，假設(shè)P(a1)=0.4,分別求出4種譯碼規(guī)則所對(duì)應(yīng)的平均差錯(cuò)率。0.80.20.10.9a1a2b1b2第九十四頁第九十五頁，共125頁。解：信道輸入概率矩陣和轉(zhuǎn)移矩陣分別為：

轉(zhuǎn)移矩陣各行元素乘以對(duì)應(yīng)的輸入概率，得聯(lián)合概率矩陣

譯碼規(guī)則F1對(duì)應(yīng)的平均差錯(cuò)率為

其它譯碼規(guī)則對(duì)應(yīng)的平均差錯(cuò)率分別為Pe(F2)=0.4 Pe(F3)=0.14 Pe(F4)=0.86四種規(guī)則相比，F(xiàn)3最好，F(xiàn)4最差第九十五頁第九十六頁，共125頁。例6-2

參見下圖，假設(shè)P(a1)=0.4，求最佳譯碼規(guī)則。

0.80.20.10.9a1a2b1b2解：例6-1已經(jīng)求出聯(lián)合概率矩陣，重寫為則最大聯(lián)合概率譯碼規(guī)則為：對(duì)應(yīng)的平均差錯(cuò)概率：

第九十六頁第九十七頁，共125頁?！醋畲筠D(zhuǎn)移概率條件確定的譯碼規(guī)則例6-3：已知信道轉(zhuǎn)移矩陣，試確定譯碼規(guī)則。解：按轉(zhuǎn)移概率最大原則確定極大似然譯碼規(guī)則如下：

二、極大似然譯碼規(guī)則第九十七頁第九十八頁，共125頁。提問：傳輸系統(tǒng)的Pe要求控制在10-6以下，而利用譯碼規(guī)則的Pe太高，如何降低平均差錯(cuò)率呢？－－－信道編碼一.簡單重復(fù)編碼

對(duì)信源符號(hào)進(jìn)行“重復(fù)2次”編碼:信道編碼f信道譯碼F第九十八頁第九十九頁，共125頁?！爸貜?fù)2次”編碼規(guī)則為

第九十九頁第一百頁，共125頁。求出3次擴(kuò)展信道的轉(zhuǎn)移矩陣按極大似然譯碼規(guī)則得譯碼函數(shù)

即：

譯碼差錯(cuò)率為：結(jié)論：信道編碼降低平均錯(cuò)誤率第一百頁第一百零一頁，共125頁。提問：信道編碼對(duì)信息傳輸速率有什么影響呢？

信道編碼，或稱為糾錯(cuò)編碼，就是靠增加“冗余”碼元來克服或減輕噪聲影響的。結(jié)論：信道編碼降低了信道的信息傳輸率信道編碼之后的信息率或信道待傳的信息率為無信道編碼的信息率或信道待傳的信息率為

第一百零一頁第一百零二頁，共125頁。二.對(duì)符號(hào)串編碼(矢量編碼）例6-4：二元信源U，若取二元符號(hào)串“00，01，10，11”作為消息，則消息個(gè)數(shù)增加為M=4。提問：此時(shí)平均差錯(cuò)率又發(fā)生怎樣的變化呢？結(jié)論：增加信源消息個(gè)數(shù)，可提高信道的信息傳輸率取碼長N=3，則編碼后的信息率為

R=(log4)/3=2/3比特/碼元第一百零二頁第一百零三頁，共125頁。碼長N=3，可供選擇的碼字為選擇以下編碼函數(shù)：

根據(jù)信道轉(zhuǎn)移矩陣確定極大似然譯碼規(guī)則為

則平均差錯(cuò)率為：

結(jié)論：增加消息個(gè)數(shù)M與重復(fù)編碼相比，在提高信息率的同時(shí)會(huì)使平均差錯(cuò)率增大。第一百零三頁第一百零四頁，共125頁。第四節(jié)漢明距離

兩個(gè)等長符號(hào)序列x和y之間的漢明距離，記為D(x,y)，是x與y之間對(duì)應(yīng)位置上不同符號(hào)的個(gè)數(shù)。解：求漢明距離：

D(x,z)=2;D(y,z)=3因此，z與x的相似程度高于與y的相似程度一.定義例6-5：

x=100111,y=111000,z=111111,比較z與x和y的相似程度。第一百零四頁第一百零五頁，共125頁。X和Y是二元序列，記為

是等長碼，則C中任意兩個(gè)不同碼字之間的漢明距離或碼間距離為碼C的最小碼間距離定義為第一百零五頁第一百零六頁，共125頁。二元對(duì)稱信道，可以根據(jù)漢明距離來決定譯碼規(guī)則

假如有一個(gè)信源有M個(gè)消息二元對(duì)稱信道的輸入符號(hào)集和輸出符號(hào)集分別為A={0，1}和B={0，1}。其N次擴(kuò)展信道的輸入符號(hào)集和輸出符號(hào)集分別為：第一百零六頁第一百零七頁，共125頁。經(jīng)N次擴(kuò)展信道傳送之后，按極大似然譯碼規(guī)則進(jìn)行譯碼記N長二元符號(hào)串為

由信道無記憶可知轉(zhuǎn)移概率為碼元錯(cuò)誤概率為p，正確概率為

則有：極大似然譯碼規(guī)則等價(jià)為最小漢明距離譯碼規(guī)則第一百零七頁第一百零八頁，共125頁。

最小距離譯碼規(guī)則可在一般信道中采用，但不一定與極大似然譯碼規(guī)則等價(jià)，只有對(duì)于二元對(duì)稱信道，它才與極大似然譯碼規(guī)則等價(jià)，并且當(dāng)輸入等概時(shí)是最佳的。

對(duì)于二元對(duì)稱信道，若輸入等概，無論用什么規(guī)則確定譯碼函數(shù)，與之對(duì)應(yīng)的平均差錯(cuò)率都可用漢明距離表示：

結(jié)論：第一百零八頁第一百零九頁，共125頁。第五節(jié)有噪信道編碼定理一.正定理（香農(nóng)第二定理）若信道是離散、無記憶、平穩(wěn)的，且信道容量為C，只要待傳送的信息率R<C，就一定能找到一種信道編碼方法，使得碼長足夠大時(shí)，平均差錯(cuò)率任意接近于零。二.逆定理若信道是離散、無記憶、平穩(wěn)的，且信道容量為C，只要待傳送的信息率R>C，就一定找不到一種信道編碼方法，使得碼長足夠大時(shí)，平均差錯(cuò)率任意接近于零。

信道編碼定理告訴我們：R<=C時(shí)，通過編碼可使平均差錯(cuò)率逼近零；逆定理則說明：R>C時(shí)，無論如何編碼，都不可能使平均差錯(cuò)綠逼近零。因此，信道容量C是確?？煽啃詡鬏?shù)男畔鬏斅实纳舷蕖５谝话倭憔彭摰谝话僖皇?，?25頁。例7-1假定離散矢量信源N=3，輸出矢量序列為X=X1X2X3，其中Xi,i=1,2,3的取值為{0,1}，經(jīng)信道傳輸后的輸出為Y=Y1Y2Y3

，其中Yj,j=1,2,3的取值為{0,1}.定義失真函數(shù)為

d(0,0)=d(1,1)=0,d(0,1)=d(1,0)=1,求矢量失真矩陣[dN]。解：由矢量失真函數(shù)的定義得：第一百一