信息論與編碼全套教學(xué)課件_第1頁(yè)
信息論與編碼全套教學(xué)課件_第2頁(yè)
信息論與編碼全套教學(xué)課件_第3頁(yè)
信息論與編碼全套教學(xué)課件_第4頁(yè)
信息論與編碼全套教學(xué)課件_第5頁(yè)
已閱讀5頁(yè),還剩410頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

信息論與編碼

第1章緒論第2章信源與信息熵第3章信道與信道容量第4章失真與信息率失真函數(shù)第5章信源編碼第6章信道編碼第7章網(wǎng)絡(luò)信息論初步全套可編輯PPT課件2第1章緒論信息論是什么?編碼是用來(lái)干什么的?全套可編輯PPT課件3第1章緒論信息論與編碼課程的內(nèi)容體系信息與編碼的若干基本概念信息論的發(fā)展歷史全套可編輯PPT課件4第1章之“信息論與編碼”課程的內(nèi)容體系通信系統(tǒng)基本模型信息論與編碼課程內(nèi)容體系5第1章之“信息論與編碼”課程的內(nèi)容體系本課程所說“信息論”,主要是指“香農(nóng)信息論”;香農(nóng)信息論的主要內(nèi)容,來(lái)自于其1948年發(fā)表在貝爾技術(shù)雜志上的文章:“通信中的數(shù)學(xué)理論”;所以,香農(nóng)信息論,嚴(yán)格來(lái)說應(yīng)該是“通信論”。6通信系統(tǒng)基本模型既然是通信理論,首先看看通信的定義、基本框圖和基本問題:定義:通信是把信息從一個(gè)地方(發(fā)送端,信源)通過信息的通道(信道)送到另一個(gè)地方(接收端,信宿)。7通信系統(tǒng)基本模型基本框圖:信源信宿噪聲源信息信息干擾信道8通信系統(tǒng)基本模型基本問題:如何使通信“又快又好又安全”?快:用盡可能少的符號(hào)攜帶盡可能多的信息—有效性;好:信息傳輸要盡可能準(zhǔn)確無(wú)誤—可靠性;安全:信息的安全性。本書只考慮有效性和可靠性。9“信息論與編碼”課程的內(nèi)容體系對(duì)有效性和可靠性這兩個(gè)通信中的基本問題,又各有兩個(gè)方面的內(nèi)容:希望“又快”(有效性)、“又好”(可靠性),這個(gè)“快”和“好”有沒有極限?如果有,極限是多少?這是“信息論”要解決的問題;用什么方法和手段達(dá)到或接近該極限?這是“編碼”所要解決的問題。

所以這門課叫做《信息論與編碼》10“信息論與編碼”課程的內(nèi)容體系所以,《信息論與編碼課程》的內(nèi)容體系,可以表示成一個(gè)2×2的矩陣:信息論編碼可靠性有效性有效性的極限是否存在及其大小問題可靠性的極限是否存在及其大小問題達(dá)到或接近有效性極限的手段和方法達(dá)到或接近可靠性極限的手段和方法11“信息論與編碼”課程的內(nèi)容體系有效性是要用盡可能少的符號(hào)攜帶盡可能多的信息,這個(gè)取決于信源的特性。所以在接下來(lái)的第2章,要研究信源與信源熵;可靠性取決于信息傳輸通道(信道)的特性,因此第3章研究信道與信道容量;12“信息論與編碼”課程的內(nèi)容體系相應(yīng)地:提高有效性的方法,是對(duì)信源進(jìn)行編碼,稱為信源編碼,是第5章的內(nèi)容;提高可靠性的方法,是對(duì)信道上傳輸?shù)男畔⑦M(jìn)行編碼,稱為信道編碼,是第6章的內(nèi)容;13“信息論與編碼”課程的內(nèi)容體系此外:第4章也是關(guān)于信源的,與第2章的不同在于:第2章的內(nèi)容用于無(wú)失真信源編碼,而第4章的內(nèi)容用于限失真信源編碼。由于其處理手段,類似于第3章信道的處理方法,故放于第3章之后;第7章對(duì)信息論的前沿技術(shù)—網(wǎng)絡(luò)信息論,進(jìn)行了簡(jiǎn)要介紹。14“信息論與編碼”課程的內(nèi)容體系所以,可以把上面的2×2矩陣重新表示為:信息論編碼可靠性有效性第2章、第4章第3章第5章第6章15“信息論與編碼”課程的內(nèi)容體系從橫的方向看:第2章(包括第4章)和第3章是平行的第2章研究信源,主要關(guān)心信源熵,是有關(guān)有效性的;

第3章研究信道,主要關(guān)心信道容量,是有關(guān)可靠性的;

第2章和第3章的章節(jié)結(jié)構(gòu)是幾乎一樣的。16“信息論與編碼”課程的內(nèi)容體系第5章和第6章是平行的第5章研究信源編碼,是實(shí)現(xiàn)有效性的方法;

第6章研究信道編碼,是實(shí)現(xiàn)可靠性的方法;

第5章和第6章的章節(jié)結(jié)構(gòu)是幾乎一樣的。17“信息論與編碼”課程的內(nèi)容體系從縱的方向看:第2章(包括第4章)和第5章是前后銜接的第2章研究信源特性,第5章在第2章的基礎(chǔ)上,研究提高有效性的手段和方法(信源編碼),這是一條有關(guān)有效性的主線;18“信息論與編碼”課程的內(nèi)容體系第3章和第6章是前后銜接的第3章研究信道特性,第6章在第3章的基礎(chǔ)上,研究提高可靠性的手段和方法(信道編碼),這是一條有關(guān)可靠性的主線;有效性的主線(第2、5章)和可靠性的主線(第3、6章)是平行的。19第1章緒論信息論與編碼課程的內(nèi)容體系信息與編碼的若干基本概念信息論的發(fā)展歷史20第1章之信息與編碼的若干基本概念信息的概念信息的度量21信息的概念信息論是研究信息的,所以首先要明白什么是信息?信息的本質(zhì)是什么?22信息的概念全部意義上的信息(全信息)包括:語(yǔ)法信息、語(yǔ)義信息和語(yǔ)用信息語(yǔ)法信息只考慮信息的外在形式;語(yǔ)義信息要考慮信息的內(nèi)容;語(yǔ)用信息要考慮信息的作用對(duì)象。23信息的概念考慮全信息,則無(wú)法進(jìn)行深入研究??藙诘?香農(nóng)等只考慮語(yǔ)法信息,對(duì)信息進(jìn)行了深入研究,得到了有關(guān)信息的系統(tǒng)理論,是為“香農(nóng)信息論”,也稱“狹義信息論”。24信息的概念香農(nóng):“信息是使隨機(jī)不確定性減少的程度”。要進(jìn)行通信,一定是接收方關(guān)于某事件是未知的或不確定的;接收方接收到信息以后,可以消除或者減少這種不確定性。25信息的度量畢達(dá)哥拉斯:“萬(wàn)物皆數(shù)”。要對(duì)信息進(jìn)行深入研究,必須定量;信息量的多少,等于對(duì)隨機(jī)不確定性減少的程度;隨機(jī)不確定性可以用概率來(lái)描述。26信息的度量要實(shí)現(xiàn)度量,首先需定義一個(gè)單位:信息的基本單位:比特(bit)可以用一個(gè)“是(或否)”的回答來(lái)消除的不確定性,定義為1比特(2選1的不確定性)。27信息的度量一個(gè)事件包含的信息量必須滿足:與該事件出現(xiàn)的概率是反比例關(guān)系(備選答案越多(某一備選答案選中的概率越小),不確定程度越大,信息量越大);確定性的事件信息量為0;信息量具有可加性。28信息的度量根據(jù)以上條件,可以用公式:來(lái)計(jì)算信息的多少。當(dāng)取以2為底的對(duì)數(shù)時(shí),信息量的單位為比特。29第1章之信息論的形成和發(fā)展歷史略30第2章信源與信源熵信源的分類與數(shù)學(xué)模型離散單符號(hào)信源熵離散序列信源熵馬爾科夫信源極限熵連續(xù)信源熵波形信源熵連續(xù)信源最大熵定理信源的冗余度31信號(hào)分類

離散信號(hào)

時(shí)間和幅度均離散

連續(xù)信號(hào)

時(shí)間和幅度均連續(xù)

時(shí)間離散幅度連續(xù)信號(hào)

抽樣信號(hào)

幅度離散時(shí)間連續(xù)信號(hào)2.1信源的分類及數(shù)學(xué)模型2.1.1信源分類321、離散信源離散單符號(hào)信源離散序列信源2、時(shí)間離散幅度連續(xù)信源連續(xù)單符號(hào)信源連續(xù)序列信源無(wú)記憶有記憶馬爾科夫信源無(wú)記憶有記憶3、時(shí)間連續(xù)幅度連讀信源(波形信源)2.1.1信源分類信源分類:(由簡(jiǎn)單到復(fù)雜)(1)離散單符號(hào)信源;(2)離散序列信源;(3)馬爾科夫信源;(4)連續(xù)單符號(hào)信源;(5)連續(xù)序列信源;(6)波形信源。33342.1.2信源的數(shù)學(xué)模型描述:通過概率空間描述(1)離散單符號(hào)信源離散信源:,pi

0。2.1.2信源的數(shù)學(xué)模型(2)離散序列信源(L次擴(kuò)展信源)聯(lián)合概率:無(wú)記憶:

352.1.2信源的數(shù)學(xué)模型(3)馬爾科夫信源聯(lián)合概率:

3637(4)連續(xù)單符號(hào)信源顯然應(yīng)滿足pX(x)

0,

2.1.2信源的數(shù)學(xué)模型38(5)連續(xù)序列信源若為無(wú)記憶的,則

2.1.2信源的數(shù)學(xué)模型2.1.2信源的數(shù)學(xué)模型(6)波形信源某時(shí)刻的取值是隨機(jī)的,用隨機(jī)過程{x(t)}來(lái)描述對(duì)于限頻波形信源,設(shè)其最高頻率為fm,根據(jù)奈奎斯特抽樣定理,只要抽樣頻率fs≥2fm,則可用其抽樣信號(hào)無(wú)失真恢復(fù)原信號(hào)。設(shè)該波形信源持續(xù)時(shí)間為tB,如果我們?nèi)∽畹统闃宇l率fs=2fm,則只需要個(gè)2fmtB采樣點(diǎn)即可。因此,一個(gè)代表波形信源的平穩(wěn)隨機(jī)過程{x(t)},可以用序列長(zhǎng)度L=2fmtB的隨機(jī)矢量來(lái)表示即可,其概率空間可

用序列長(zhǎng)度L=2fmtB的連續(xù)序列信源的概率空間

來(lái)描述。3940從理論上說任何時(shí)間受限的函數(shù),其頻譜是無(wú)限的;反之,任何頻帶受限的函數(shù),其時(shí)間上是無(wú)限的。實(shí)際中,可認(rèn)為函數(shù)在頻帶fm、時(shí)間tB以外的取值很小,不至于引起函數(shù)的嚴(yán)重失真。2.1.2信源的數(shù)學(xué)模型41(1)馬爾可夫信源簡(jiǎn)化形式當(dāng)信源的記憶長(zhǎng)度為m+1時(shí),該時(shí)刻發(fā)出的符號(hào)與前m個(gè)符號(hào)有關(guān)聯(lián)性,而與更前面的符號(hào)無(wú)關(guān)。2.1.3馬爾科夫信源的穩(wěn)態(tài)分布42離散有記憶序列信源與馬爾可夫信源區(qū)別(a)離散有記憶序列信源(b)馬爾可夫信源43(2)齊次馬爾可夫信源齊次馬爾可夫信源:條件概率與時(shí)間起點(diǎn)無(wú)關(guān)。平穩(wěn)包含齊次,齊次不一定平穩(wěn)。2.1.3馬爾科夫信源的穩(wěn)態(tài)分布平穩(wěn)與齊次區(qū)別若Q和T為任意兩個(gè)時(shí)刻,平穩(wěn)滿足44運(yùn)用概率的一般運(yùn)算法則45(3)馬爾可夫信源狀態(tài)轉(zhuǎn)移概率矩陣信源在某一時(shí)刻出現(xiàn)符號(hào)概率xj與信源此時(shí)所處狀態(tài)si有關(guān),用符號(hào)條件概率表示p(xj/si),狀態(tài)轉(zhuǎn)移概率表示為p(sj/si)狀態(tài)集為:2.1.3馬爾科夫信源的穩(wěn)態(tài)分布46馬爾可夫信源一步轉(zhuǎn)移概率特別關(guān)心n-m=1情況,pij(m,m+1)2.1.3馬爾科夫信源的穩(wěn)態(tài)分布47馬爾可夫信源一步轉(zhuǎn)移概率矩陣系統(tǒng)在任一時(shí)刻可處于狀態(tài)空間的任意一狀態(tài),狀態(tài)轉(zhuǎn)移時(shí),轉(zhuǎn)移概率是一個(gè)矩陣。由于共有Q=nm種不同狀態(tài),可用Q×Q的矩陣來(lái)描述一步轉(zhuǎn)移概率矩陣:2.1.3馬爾科夫信源的穩(wěn)態(tài)分布48齊次馬爾可夫信源性質(zhì)對(duì)于齊次馬爾可夫鏈,一步轉(zhuǎn)移概率完全決定了k步轉(zhuǎn)移概率。定義:若齊次馬爾可夫鏈對(duì)一切i,j存在不依賴于i的極限,則稱其具有遍歷性,pj稱為平穩(wěn)分布2.1.3馬爾科夫信源的穩(wěn)態(tài)分布49馬爾可夫信源定理:設(shè)有一齊次馬爾可夫鏈,其狀態(tài)轉(zhuǎn)移矩陣為P,其穩(wěn)態(tài)分布為wj=p(sj)2.1.3馬爾科夫信源的穩(wěn)態(tài)分布2.1.3馬爾科夫信源的穩(wěn)態(tài)分布該方程是否存在解?解是否唯一結(jié)論1:該方程一定存在非零解。

502.1.3馬爾科夫信源的穩(wěn)態(tài)分布解的唯一性

說明:以上條件只是馬爾科夫信源存在穩(wěn)態(tài)分布的必要條件,并不是充要條件。51由于52不可約性:就是任意一對(duì)i和j,都存在至少一個(gè)k,使pij(k)>0。非周期性:所有pii(n)>0的n中沒有比1大的公因子。2.1.3馬爾科夫信源的穩(wěn)態(tài)分布53如圖2-1所示的二進(jìn)制相對(duì)碼編碼器(其中T為時(shí)延模塊),初始狀態(tài)Y1=X1;其余時(shí)刻,如輸入X=0,則當(dāng)前時(shí)刻輸出等于上時(shí)刻輸出,Yi+1=Yi;如輸入X=1,則當(dāng)前時(shí)刻輸出異于上時(shí)刻輸出,

;若已知P(X=0)=p,P(X=1)=1-p=q,試寫出其轉(zhuǎn)移概率矩陣,并畫出狀態(tài)轉(zhuǎn)移圖。2.1.3馬爾科夫信源的穩(wěn)態(tài)分布解:由于當(dāng)前時(shí)刻的輸出,取決于當(dāng)前時(shí)刻的輸入,以及前一個(gè)時(shí)刻的輸出,所以輸出序列是一個(gè)一階馬爾可夫鏈。對(duì)于二進(jìn)制信源,前一個(gè)時(shí)刻的輸出共有兩種(0或者1),所以狀態(tài)共有兩種:“0”狀態(tài)和“1”狀態(tài)。

即轉(zhuǎn)移概率矩陣為:其狀態(tài)轉(zhuǎn)移圖為:

54pqp10q2.1.3馬爾科夫信源的穩(wěn)態(tài)分布二階馬爾科夫信源,X{0,1},求穩(wěn)態(tài)概率分布55起始狀態(tài)符號(hào)01s1(00)1/21/2s2(01)1/32/3s3(10)1/43/4s4(11)1/54/5表2-1符號(hào)條件概率p(aj|si)解:對(duì)二階馬爾可夫鏈,其狀態(tài)共有四種,分別為:S=(00,01,10,11),根據(jù)符號(hào)條件概率表2-1,可以寫出符號(hào)條件概率矩陣為:可得狀態(tài)轉(zhuǎn)移概率矩陣為5657狀態(tài)轉(zhuǎn)移概率起始狀態(tài)(si)s1(00)s2(01)s3(10)s4(11)1/201/401/203/4001/301/502/304/5s1(00)s2(01)s3(10)s4(11)2.1.3馬爾科夫信源的穩(wěn)態(tài)分布表2-2狀態(tài)條件概率p(sj|si)終止?fàn)顟B(tài)(sj)狀態(tài)轉(zhuǎn)移圖:5800100111(0)1/2(0)1/5(1)2/3(0)1/4(1)1/2(1)4/5(1)3/4(0)1/359

設(shè)四種狀態(tài)的穩(wěn)態(tài)概率為W1,W2,W3,W4可得方程組解得穩(wěn)態(tài)分布的概率為:達(dá)到穩(wěn)態(tài)后的符號(hào)概率為:2.1.3馬爾科夫信源的穩(wěn)態(tài)分布例:設(shè)有一馬爾科夫鏈,其狀態(tài)轉(zhuǎn)移矩陣為判斷該馬爾科夫鏈?zhǔn)欠翊嬖诜€(wěn)態(tài)分布?

60612.2離散單符號(hào)信源熵自信息量離散單符號(hào)信源熵離散單符號(hào)信源條件熵離散單符號(hào)信源聯(lián)合熵互信息信源熵性質(zhì)622.2.1自信息量自信息量

例以2為底,單位為比特,用bit(或b)表示。自信息量與不確定度自信息量:符號(hào)出現(xiàn)后,提供給收信者的信息量;不確定度:符號(hào)出現(xiàn)前,所含有的不確定性。二者數(shù)量上相等,物理含義不同。632.2.1自信息量642.2.1自信息量自信息量的性質(zhì)p(xi)=1,I(xi)=0;確定性事件不包含任何信息量;p(xi)=0,I(xi)=∞;出現(xiàn)的概率越小,包含的信息量越大;概率等于零時(shí),包含的信息量為無(wú)窮大;非負(fù)性:p(xi)∈[0,1],所以,故I(xi)≥0;可加性:如果符號(hào)xi中包含I(xi)的信息量,符號(hào)yj中包含I(yj)的信息量,則符號(hào)xi和yj同時(shí)出現(xiàn)包含的信息量,為兩者的自信息量之和(假定兩者互相獨(dú)立p(xi,yj)=p(xi)p(yj)):

I(xi,yj)=I(xi)+I(yj)

例:假設(shè)一次擲兩個(gè)各自均勻、互相不可區(qū)分但又不相關(guān)的骰子。如(A)、(B)分別表示:僅有一個(gè)骰子是3;至少有一個(gè)骰子是4;試計(jì)算(A)、(B)發(fā)生后提供的信息量。65662.2.2離散單符號(hào)信源熵離散單符號(hào)信源熵就是其平均不確定度

對(duì)于

,平均信息量為

離散單符號(hào)信源熵例題例:二元信源的熵67H(X)=-plogp-(1-p)log(1-p)=H(p)當(dāng)p=0.5時(shí),具有最大熵;當(dāng)p=1或p=0時(shí),H(X)=0;信源熵是p的上凸函數(shù)。682.2.3離散單符號(hào)信源條件熵給定條件yj,信源X的概率空間變化為

給定條件yj,可得條件熵:信息量例:某高三畢業(yè)生中,25%的女生考取了大學(xué)。在考取大學(xué)的女生中75%居住在城區(qū),而高三畢業(yè)生中50%住在城區(qū)。假如我們得知“住在城區(qū)的女生考取了大學(xué)”的消息,試問獲取了多少信息量?69702.2.3離散單符號(hào)信源條件熵若Y∈{yj,j=1,2,…,m},可得{H(Y|y1),H(Y|y2),…,H(Y|ym)}若以Y為條件下,則X的條件熵為條件熵H(Y|X)表示當(dāng)已知Y時(shí),X仍然具有的不確定度。

例2-4

某二進(jìn)制數(shù)字通信系統(tǒng)如圖2-5所示。發(fā)送端信源X為二進(jìn)制信源{0,1},其概率空間為由于通信信道中有干擾和噪聲,導(dǎo)致接收端判決結(jié)果除了“0”和“1”以外,還有一種未知的狀態(tài)(既不是“0”也不是“1”),我們表示為“?”狀態(tài)。設(shè)信道的符號(hào)轉(zhuǎn)移概率為:求信源熵H(X)、條件熵H(X/Y)和H(Y/X),以及信源熵H(Y)。71p(y=0/x=0)=3/4,

p(y=0/x=1)=0;p(y=1/x=0)=0,

p(y=1/x=1)=1/2;p(y=?/x=0)=1/4,

p(y=?/x=1)=1/2;圖2-5二進(jìn)制數(shù)字通信系統(tǒng)解:(1)信源熵H(X)可直接由公式求得(2)根據(jù)條件熵公式,求條件熵H(Y/X),,需要知道條件概率p(y=0/x=0)、p(y=1/x=0)、p(y=?/x=0)和p(y=0/x=1)、p(y=1/x=1)、p(y=?/x=1);以及聯(lián)合概率p(x=0,

y=0)、p(x=0,

y=1)、p(x=0,y=?)和p(x=1,y=0)、p(x=1,y=1)、p(x=1,y=?)等:p(x

=0,y=0)=p(x=0)p(y=0/x=0)=1/2p(x

=0,

y=1)=p(x=0)p(y=1/x=0)=0p(x=0,y=?)=p(x=0)p(y=?/x=0)=1/6p(x=1,y=0)=p(x=1)p(y=0/x=1)=0p(x=1,y=1)=p(x=1)p(y=1/x=1)=1/6p(x=1,y=?)=p(x=1)p(y=?/x=1)=1/6則由條件熵公式可得:72(3)、根據(jù)條件熵公式,求條件熵H(X/Y),,需要知道條件概率p(x=0/y=0)、p(x=0/y=1)、p(x=0/y=?)和p(x=1/y=0)、p(x=1/y=1)、p(x=1/y=?);以及聯(lián)合概率p(x=0,y=0)、p(x=0,y=1)、p(x=0,y=?)和p(x=1,y=0)、p(x=1,y=1)、p(x=1,y=?)等:故

73因此(4)由74得:752.2.4離散單符號(hào)信源聯(lián)合熵當(dāng)X和Y聯(lián)合出現(xiàn),若X∈{x1,x2,…,xn},Y∈{y1,y2,…,ym},則其概率空間變化為

聯(lián)合熵:信息量例題例2-5根據(jù)例2-4的信源X和信源Y,求聯(lián)合熵H(X,Y)。

根據(jù)例2-4的求解過程,已知:

p(x

=0,y=0)=p(x=0)p(y=0/x=0)=1/2

p(x

=0,

y=1)=p(x=0)p(y=1/x=0)=0p(x=0,y=?)=p(x=0)p(y=?/x=0)=1/6

p(x=1,y=0)=p(x=1)p(y=0/x=1)=0p(x=1,y=1)=p(x=1)p(y=1/x=1)=1/6p(x=1,y=?)=p(x=1)p(y=?/x=1)=1/676772.2.5互信息互信息:例2-4數(shù)字通信系統(tǒng)78符號(hào)間互信息:在X取值集合上做概率統(tǒng)計(jì)平均,即得:進(jìn)一步,在Y取值集合上做概率統(tǒng)計(jì)平均,即得2.2.5互信息79而且:例2-6,求例2-4中,符號(hào)X和符號(hào)Y之間的互信息2.2.5互信息80信源熵、條件熵、聯(lián)合熵之間的關(guān)系若X和Y相互獨(dú)立,則信源熵、條件熵、聯(lián)合熵、互信息之間的關(guān)系

2.2.6信源熵、條件熵、聯(lián)合熵、互信息等之間的關(guān)系812.2.6信源熵、條件熵、聯(lián)合熵、互信息等之間的關(guān)系圖2-6互信息量與熵之間的關(guān)系圖2-7收、發(fā)兩端的熵關(guān)系822.2.7信源熵的性質(zhì)非負(fù)性對(duì)稱性確定性可擴(kuò)展性遞增性83非負(fù)性84對(duì)稱性85確定性可擴(kuò)展性遞增性這條性質(zhì)表明,若原信源X中有一元素劃分成m個(gè)元素(符號(hào)),而這m個(gè)元素的概率之和等于原元素的概率,則新信源的熵增加。熵增加了一項(xiàng)是由于劃分而產(chǎn)生的不確定性量。例H(1/3,1/3,1/6,1/6)8687上凸性極值性(最大離散熵定理)熵函數(shù)H(P)是概率矢量P={p1,p2,…,pn}的嚴(yán)格∩型凸函數(shù)(上凸函數(shù))??杉有?/p>

一般式當(dāng)X、Y相互獨(dú)立時(shí)熵的可加性可這樣理解:復(fù)合事件集合的平均不確定性為各個(gè)分事件集合的平均不確定性的和。88遞增性這條性質(zhì)表明,若原信源X中有一元素劃分成m個(gè)元素(符號(hào)),而這m個(gè)元素的概率之和等于原元素的概率,則新信源的熵增加。熵增加了一項(xiàng)是由于劃分而產(chǎn)生的不確定性量。例H(1/3,1/3,1/6,1/6)8990

2.3離散序列信源熵離散無(wú)記憶信源及其信息熵離散有記憶信源熵離散平穩(wěn)信源的極限熵

2.3離散序列信源熵離散序列信源(L次擴(kuò)展信源)概率空間離散序列信源熵:

91單位:比特/序列獨(dú)立但非同分布獨(dú)同分布序列熵

2.3.1離散無(wú)記憶信源的序列熵92消息熵平均符號(hào)熵單位:比特/符號(hào)i.i.d.9394

2.3.2離散有記憶信源熵消息熵:序列熵:95對(duì)于有記憶離散序列信源,可得:結(jié)論1:離散序列信源的極限熵為:

結(jié)論2:

是L的單調(diào)非增函數(shù)結(jié)論3:

結(jié)論4:

是L的單調(diào)非增函數(shù)2.3.3離散平穩(wěn)信源的極限熵96例

離散有記憶信源p(xj/xi)xjxix1x2x3x19/111/80x22/113/42/9x301/87/997解:

H(X2/X1)=0.87比特/符號(hào)

H(X1)=1.5比特/符號(hào)

H(X1,X2)=H(X1)+H(X2/X1)

=1.5+0.87=2.37比特/序列 平均符號(hào)熵H2(X)=0.5H(X2)=1.185比特/符號(hào)比較上述結(jié)果可得:H2(X)<H1

(X),即二重序列的符號(hào)熵值較單符號(hào)熵變小了,也就是不確定度減小了,這是由于符號(hào)之間存在相關(guān)性造成的。98馬氏鏈極限熵齊次馬爾科夫鏈2.4馬爾科夫信源的極限熵99例2-8求馬氏鏈平均符號(hào)熵(三個(gè)狀態(tài))

1/0.1s1

1/0.50/0.90/0.50/0.8s2

s31/0.2

三狀態(tài)馬爾可夫信源狀態(tài)轉(zhuǎn)移圖解得:W1=5/59,W2=9/59,W3=45/59。馬爾可夫信源的熵:比特/符號(hào)100求解馬爾可夫信源熵的步驟為:(1)根據(jù)題意畫出狀態(tài)轉(zhuǎn)移圖,或?qū)懗鰻顟B(tài)轉(zhuǎn)移矩陣;(2)計(jì)算信源的平穩(wěn)分布概率(假定信源具有平穩(wěn)分布);(3)根據(jù)一步轉(zhuǎn)移概率和穩(wěn)態(tài)分布概率,計(jì)算信源熵(極限熵)。1011022.5連續(xù)單符號(hào)信源熵2.5.1幅度連續(xù)的單個(gè)符號(hào)信源熵1032.5.1幅度連續(xù)的單個(gè)符號(hào)信源熵1042.6連續(xù)序列信源熵連續(xù)序列的熵和離散序列的熵性質(zhì)完全相同,只要把離散信源熵用連續(xù)信源熵替代即可。105

2.7波形信源熵波形信源可用隨機(jī)過程x(t)表示。對(duì)限時(shí)tB和限頻fm平穩(wěn)隨機(jī)過程,可以抽樣成序列長(zhǎng)度L=2fmtB的連續(xù)序列信源,其熵為:2.8連續(xù)信源最大熵定理問題的提出:

在連續(xù)信源中,不同約束條件(峰值功率、平均功率)下,有不同的最大熵。無(wú)約束時(shí),最大熵不存在。106對(duì)于定義域?yàn)橛邢薜碾S機(jī)變量X,當(dāng)它是均勻分布時(shí),具有最大熵。變量X的幅度取值限制在[a,b],當(dāng)pX

(x)=1/(b-a),則Hc(X)=log(b-a)峰值功率受限為P,則輸出信號(hào)的瞬時(shí)電壓限定在

P1/2,等價(jià)于取值幅度受限。

限峰功率最大熵定理107108限平均功率最大熵定理對(duì)于相關(guān)矩陣一定隨機(jī)變量X,當(dāng)它是正態(tài)分布時(shí)具有最大熵最大熵定理(總結(jié))無(wú)約束條件的最大熵不存在限峰功率最大熵限平均功率最大熵1091102.9信源的冗余度冗余度,表示給定信源在實(shí)際發(fā)出消息時(shí)所包含的多余信息。它來(lái)自兩個(gè)方面,一是信源符號(hào)間的相關(guān)性;二是信源符號(hào)分布的不均勻性1112.9信源的冗余度例:計(jì)算英文字母冗余度H0(X)=l0g27=4.76比特/符號(hào)H1(X)=4.03比特/符號(hào)H2(X)=3.32比特/符號(hào)H3(X)=3.1比特/符號(hào)H∞(X)=1.4比特/符號(hào)本章小結(jié)112第二章主要內(nèi)容結(jié)構(gòu)113本章小結(jié)本章學(xué)習(xí)思路信源(信息的出發(fā)點(diǎn))→對(duì)信源進(jìn)行分類→給出數(shù)學(xué)模型→信源的重要參數(shù):熵、互信息等→按照分類,從簡(jiǎn)單到復(fù)雜,研究信源的熵等重要參數(shù)114定義、性質(zhì)

計(jì)算公式、相互關(guān)系自信息量信源熵、條件熵、聯(lián)合熵、互信息序列熵、平均符號(hào)熵、極限熵連續(xù)信源最大熵定理冗余度115第3章信道與信道容量信道的分類與數(shù)學(xué)模型離散單符號(hào)信道的信道容量離散序列信道的信道容量連續(xù)單符號(hào)信道的信道容量連續(xù)序列信道的信道容量波形信道的信道容量信道冗余度1163.1.1信道的分類(按照信道輸入信號(hào)分類)

離散單符號(hào)信道

離散序列信道

連續(xù)單符號(hào)信道

連續(xù)序列信道

波形信道主要目的:研究信道中理論上能夠傳輸或存儲(chǔ)的最大信息量,即信道容量。3.1信道的分類1173.1.2信道的數(shù)學(xué)模型描述:信道把特定輸入符號(hào)映射為特定輸出符號(hào)的能力(正確概率)以及映射為其他輸出符號(hào)的可能性(錯(cuò)誤概率)。圖3-1信道模型圖P(Y|X)1181.離散單符號(hào)信道的數(shù)學(xué)模型轉(zhuǎn)移概率矩陣離散單符號(hào)信道模型P(Y|X)119例:二進(jìn)制對(duì)稱信道(BSC)轉(zhuǎn)移概率矩陣圖3-2二進(jìn)制對(duì)稱信道(BSC)p11=1-p,p12=p,p21=p,p22=1-p1202.離散序列信道的數(shù)學(xué)模型當(dāng)輸入為離散序列時(shí),用隨機(jī)矢量x來(lái)表示,若輸出隨機(jī)矢量為y,則信道可用轉(zhuǎn)移概率P(y/x)表示。當(dāng)信源和信道無(wú)記憶時(shí),離散序列信道可看成一系列離散單符號(hào)信道。121例:擴(kuò)展信道如果對(duì)離散單符號(hào)信道進(jìn)行L次擴(kuò)展,就形成了L次離散無(wú)記憶序列信道BSC的二次擴(kuò)展信道

00101101000111X

{00,01,10,11},Y

{00,01,10,11},二次擴(kuò)展無(wú)記憶信道的序列轉(zhuǎn)移概率p(00/00)=p(0/0)p(0/0)=(1-p)2,p(01/00)=p(0/0)p(1/0)=p(1-p),p(10/00)=p(1/0)p(0/0)=p(1-p),p(11/00)=p(1/0)p(1/0)=p2101223.連續(xù)單符號(hào)信道的數(shù)學(xué)模型對(duì)連續(xù)單符號(hào)輸入信源x,對(duì)應(yīng)的輸出為隨機(jī)變量y。若信道為加性高斯白噪聲信道:

y=x+n其中,n為0均值、方差為σ2的高斯隨機(jī)變量。若給定輸入x0,則1234.連續(xù)序列信道的數(shù)學(xué)模型當(dāng)輸入為連續(xù)序列時(shí),用隨機(jī)矢量x來(lái)表示,若輸出隨機(jī)矢量為y,則信道可用轉(zhuǎn)移概率密度pY(y/x)表示。若輸入序列無(wú)記憶,無(wú)記憶連續(xù)序列信道可以看作是一系列連續(xù)單符號(hào)信道。1245.波形信道的數(shù)學(xué)模型若輸入為波形信源,用隨機(jī)過程{x(t)}表示,則輸出也為隨機(jī)過程,記為{y(t)}。若滿足限時(shí)(tB)限頻(fm)條件,則可以抽樣成L=2fmtB的連續(xù)平穩(wěn)隨機(jī)序列,則信道用轉(zhuǎn)移概率密度描述,為:若信源信道無(wú)記憶,則1251.互信息量表達(dá)式3.1.3信道容量的定義126定理3.1

在p(yj|xi)給定時(shí),互信息量I(X;Y)是p(xi)的上凸函數(shù)。通信的目的:每次信道使用(每發(fā)送一個(gè)符號(hào)),傳送到接收端盡可能多的信息量(互信息量I(X;Y)取最大值)。需要解決的問題是:①該最大值是多少?②p(xi)是什么分布時(shí),取得該最大值?1272.信道容量的定義信道容量(ChannelCapacity):信道所能傳送的最大信息量。比特/符號(hào)(bits/symbol或bits/channeluse)

在p(y/x)給定時(shí),I(X;Y)是關(guān)于p(x)的上凸函數(shù)。信道容量要解決的問題:C=?p(xi)=?128離散無(wú)記憶信道(DMC)

對(duì)稱離散無(wú)記憶信道

準(zhǔn)對(duì)稱離散無(wú)記憶信道

一般離散無(wú)記憶信道3.2離散單符號(hào)信道的信道容量129輸入對(duì)稱如果轉(zhuǎn)移概率矩陣P的每一行都是第一行的置換(包含同樣元素),稱該矩陣是輸入對(duì)稱。輸出對(duì)稱如果轉(zhuǎn)移概率矩陣P的每一列都是第一列的置換(包含同樣元素),稱該矩陣是輸出對(duì)稱。對(duì)稱信道如果輸入、輸出都對(duì)稱。3.2.1對(duì)稱離散無(wú)記憶信道130對(duì)稱DMC信道例子131輸入對(duì)稱132如果信道輸入符號(hào)等概分布p(ai)=1/n當(dāng)轉(zhuǎn)移概率矩陣列對(duì)稱時(shí),信道輸出符號(hào)p(bj)等概分布--輸出對(duì)稱133例3-2.求信道容量134例3-3.求信道容量信道輸入符號(hào)和輸出符號(hào)的個(gè)數(shù)相同,都為n,且正確的傳輸概率為1-

,錯(cuò)誤概率

被對(duì)稱地均分給n-1個(gè)輸出符號(hào),此信道稱為強(qiáng)對(duì)稱信道或均勻信道,是對(duì)稱離散信道的一個(gè)特例。135例3-4.二進(jìn)制對(duì)稱信道(BSC):當(dāng)

時(shí),錯(cuò)誤概率為0,無(wú)差錯(cuò),信道容量達(dá)到最大,每符號(hào)1bit,輸入端的信息全部傳輸至輸出端。當(dāng)

時(shí),錯(cuò)誤概率與正確概率相同,從輸出端得不到關(guān)于輸入的任何信息,互信息為0,即信道容量為0。對(duì)于

的情況,可在BSC的輸出端顛倒0和1,導(dǎo)致信道容量以

點(diǎn)中心對(duì)稱。136例3-5.串聯(lián)信道137例3-5.串聯(lián)信道圖3-6m個(gè)BSC串聯(lián)信道的互信息串接的信道越多,其信道容量可能會(huì)越小,當(dāng)串接信道數(shù)無(wú)限大時(shí),信道容量就有可能趨于零。

138若信道的轉(zhuǎn)移概率矩陣輸入對(duì)稱而輸出不對(duì)稱,這樣的信道稱為準(zhǔn)對(duì)稱離散無(wú)記憶信道。當(dāng)輸入等概率時(shí)不能確保輸出等概:一般情況下:

3.2.2準(zhǔn)對(duì)稱離散無(wú)記憶信道1391.求極值方法例:求信道容量信道的輸入符號(hào)有兩個(gè),可設(shè)p(a1)=

,p(a2)=1-

,信道的輸出符號(hào)有三個(gè),用b1、b2、b3表示

3.2.2準(zhǔn)對(duì)稱離散無(wú)記憶信道1401.求極值方法因?yàn)?/p>

,所以應(yīng)有:

p(a1)=p(a2)=1/21412.矩陣分解法

將轉(zhuǎn)移概率矩陣劃分成若干個(gè)互不相交的對(duì)稱的子集,則準(zhǔn)對(duì)稱DMC的信道容量為:其中,Nk為第k個(gè)對(duì)稱子矩陣一行元素之和,Mk為第k個(gè)對(duì)稱子矩陣一列元素之和。

1422.矩陣分解法

1433.觀察法

觀察該矩陣可知,因?yàn)閜(xi)無(wú)論如何分布,p(b3)為恒定值0.2,故要得到最大的H(Y),b1和b2應(yīng)為均勻分布,即p(b1)=p(b2)=0.4,此時(shí):p(a1)=p(a2)=0.5。

144一般地說,為使I(X;Y)最大化以便求取DMC容量,輸入符號(hào)概率集{p(ai)}必須滿足的充分和必要條件是:

當(dāng)信道平均互信息達(dá)到信道容量時(shí),輸入符號(hào)概率集{p(ai)}中每一個(gè)符號(hào)ai對(duì)輸出端Y提供相同的互信息,只是概率為零的符號(hào)除外。

3.2.2一般離散無(wú)記憶信道145離散序列信道

對(duì)離散無(wú)記憶序列信道:若信道同時(shí)還是平穩(wěn)的,則3.3離散序列信道的信道容量1461.信道無(wú)記憶的情形例:X1=X2=…=XL=Y1=Y2=…=YL3.3.1信道與信源無(wú)記憶情形1472.信源無(wú)記憶的情形例:Yi=Xi+1,YL=X1;X1,X2,…,XL互相獨(dú)立1483.信源和信道皆無(wú)記憶的情形此時(shí),149對(duì)離散單符號(hào)信道進(jìn)行N次擴(kuò)展,就形成了N次離散無(wú)記憶信道。3.3.2N次擴(kuò)展信道BSC的二次擴(kuò)展信道0010110100011011X

{00,01,10,11},Y

{00,01,10,11},二次擴(kuò)展無(wú)記憶信道的序列轉(zhuǎn)移概率p(00/00)=p(0/0)p(0/0)=(1-p)2,p(01/00)=p(0/0)p(1/0)=p(1-p),p(10/00)=p(1/0)p(0/0)=p(1-p),p(11/00)=p(1/0)p(1/0)=p2150擴(kuò)展信道若p=0.1,則C2=2-0.938=1.062比特/序列

151序列轉(zhuǎn)移概率若信道無(wú)記憶,則3.3.3獨(dú)立并聯(lián)信道圖3-8獨(dú)立并聯(lián)信道只有當(dāng)輸入相互獨(dú)立時(shí)取等號(hào)。152平均互信息

I(X;Y)=HC(Y)-HC(Y/X)3.4連續(xù)單符號(hào)信道的信道容量圖3-9連續(xù)單符號(hào)信道y=x+npn(x)=N(0,

2)153pn(n)=N(0,

2),當(dāng)

pY(y)=N(0,Po)時(shí)取得maxHC(Y),

pX(x)=N(0,Ps),Po=Ps+2C=1/2log(1+SNR)

信道輸入X是均值為零、方差為PS的高斯分布隨機(jī)變量時(shí),信息傳輸率達(dá)到最大值。若是加性的,可以求出信道容量的上下界

154

信道輸入隨機(jī)序列X=X1X2…XL,輸出隨機(jī)序列Y=Y(jié)1Y2…YL,加性信道有y=x+n,其中n=n1n2…nL

是均值為零的高斯噪聲

3.5連續(xù)序列信道的信道容量圖3-10多維無(wú)記憶加性信道等價(jià)于L個(gè)獨(dú)立并聯(lián)加性信道155連續(xù)單符多維無(wú)記憶高斯加性信道就可等價(jià)成L個(gè)獨(dú)立的并聯(lián)高斯加性信道。若

將總功率P如何分配給輸入序列中的各個(gè)符號(hào),才能得到最大的信道容量?3.5連續(xù)序列信道的信道容量156噪聲均值為零、方差相同(平均分配,每個(gè)符號(hào)均值為0,方差為S的高斯變量)

若噪聲均值為零、方差不同,總平均功率受限P,功率則應(yīng)合理分配。最大容量問題即為:3.5連續(xù)序列信道的信道容量157用拉格朗日乘子法構(gòu)造無(wú)約束極值問題:各個(gè)時(shí)刻的信道輸出功率相等設(shè)為常數(shù)

158討論均值為零、方差不同,總平均功率受限P,功率合理分配。159注水法(water-filling)功率分配該功率分配方法,可以形象地描述為圖3-11,如果把噪聲功率看成是容器底部的凸起,把v看成是水平面,則每個(gè)子信道上分配的功率,就如往底部有不同凸起的容器中注水,故形象地稱為“注水算法”。圖3-11注水法功率分配160例:有一并聯(lián)高斯加性信道,各子信道噪聲方差為(1)P=5:輸出端總功率

各子信道分配的功率分別是:0.95,0.85,0.75,0.65,0.55,0.45,0.35,0.25,0.15,0.05。(2)P=3?平均輸出功率(水平面)為10.5/10=1.05161限時(shí)限頻(fm)高斯白噪聲過程可分解L=2fmtB維統(tǒng)計(jì)獨(dú)立的隨機(jī)序列

若每個(gè)抽樣時(shí)刻的噪聲均為零均值、方差為σ2的加性高斯噪聲(W為帶寬,W=fm),則:3.6波形信道的信道容量162信道容量單位時(shí)間的信道容量香農(nóng)公式

輸入信號(hào){x(t)}滿足均值為零、平均功率P的高斯白噪聲的特性163帶寬W一定時(shí),信噪比SNR與信道容量Ct成對(duì)數(shù)關(guān)系,SNR增大,Ct就增大,但增大到一定程度后就趨于緩慢。增加輸入信號(hào)功率有助于容量的增大,但該方法是有限的;降低噪聲功率也是有用的,當(dāng)N0→0,Ct→∞即無(wú)噪聲信道的容量為無(wú)窮大。討論

Ct

=Wlog(1+SNR)單位時(shí)間的信道容量圖3-12信道容量與信噪比的關(guān)系164Ct一定時(shí),帶寬W增大,信噪比SNR可降低,即兩者是可以互換的。若有較大的傳輸帶寬,則在保持信號(hào)功率不變的情況下,可容許較大的噪聲,即系統(tǒng)的抗噪聲能力提高。無(wú)線通信中的擴(kuò)頻系統(tǒng)就是利用了這個(gè)原理,將所需傳送的信號(hào)擴(kuò)頻,使之遠(yuǎn)遠(yuǎn)大于原始信號(hào)帶寬,以增強(qiáng)抗干擾的能力。Ct=Wlog(1+SNR)比特/秒165Ct/W=log(1+SNR)比特/秒/Hz,單位頻帶的信息傳輸速率--頻帶利用率,該值越大,信道就利用得越充分。當(dāng)SNR=1(0dB),Ct/W=1bit/s/Hz;當(dāng)SNR=-1.6dB,Ct/W=0bit/s/Hz。(因?yàn)榇藭r(shí)需要無(wú)窮大的的帶寬W)。頻帶利用率圖3-13頻帶利用率與信噪比的關(guān)系166

信源發(fā)出的消息(符號(hào))要通過信道來(lái)傳輸,因此要求信源的輸出與信道的輸入匹配。符號(hào)匹配:信源輸出的符號(hào)必須是信道能夠傳送的符號(hào);信息匹配:當(dāng)信源與信道連接時(shí),信息傳輸率達(dá)到信道容量,則稱信源與信道達(dá)到匹配。3.7信道冗余度167

信道冗余度信道絕對(duì)冗余度

γ=C-I(X;Y);信道相對(duì)冗余度γ=168信道冗余度冗余度大:信源與信道匹配程度低,信道的信息傳遞能力未得到充分利用;冗余度小:信源與信道匹配程度高,信道的信息傳遞能力得到較充分利用;冗余度為零,說明信源與信道(信息)完全匹配,即信源概率分布符合最佳輸入分布。一般來(lái)說,實(shí)際信源的概率分布未必就是信道的最佳輸入分布,所以I(X;Y)≤C,冗余度不為零。本章小結(jié)169第三章主要內(nèi)容結(jié)構(gòu)170本章小結(jié)本章學(xué)習(xí)思路信道(信息傳輸?shù)耐罚鷮?duì)信道進(jìn)行分類→給出數(shù)學(xué)模型→信道的重要參數(shù):信道容量→按照分類,從簡(jiǎn)單到復(fù)雜,研究信道的信道容量。171第4章失真與信息率失真函數(shù)失真的概念和性質(zhì)信息率失真函數(shù)172問題信源熵H(X)的物理含義是什么?為什么要研究信源熵?信源無(wú)失真?zhèn)鬏斔璧淖钚⌒畔⒙蕿镽

H(X);允許信源有失真時(shí),輸出的最小速率可降低為R<H(X);失真D越大,R可以越小,因此R是D的函數(shù),且為單調(diào)遞減函數(shù)。R(D)就叫做信息率失真函數(shù)。173限失真編碼的必要性對(duì)于連續(xù)信源,因?yàn)槠潇貫闊o(wú)窮大,若要求對(duì)其進(jìn)行無(wú)失真編碼,需要用無(wú)窮多個(gè)比特才能完全無(wú)失真地來(lái)描述。由于人耳能夠接收的帶寬和分辨率是有限的,因此對(duì)數(shù)字音頻,就允許有一定的失真,并且對(duì)音樂欣賞沒有影響??砂杨l譜范圍從20Hz~8000Hz的語(yǔ)音信號(hào)去掉低頻和高頻,保留帶寬范圍300Hz~3400Hz的信號(hào),這種失真是允許的。對(duì)于數(shù)字電視,由于人的視覺系統(tǒng)對(duì)低頻比較敏感,對(duì)高頻不太敏感,且人眼分辨率有限,因此可以在一定限度內(nèi)損失部分高頻分量。174限失真編碼從直觀感覺可知,若允許失真越大,信息傳輸率可越??;若允許失真越小,信息傳輸率需越大。所以信息傳輸率與信源編碼所引起的失真(或誤差)是有關(guān)的。1754.1失真的概念和性質(zhì)X={xi},xi

{a1,…an}

信源編碼器

Y={yj},yj

{b1,…bm}失真函數(shù)d(xi,yj)176最常用的失真函數(shù)均方失真:

相對(duì)失真:誤碼失真:絕對(duì)失真:前三種失真度量適用于連續(xù)信源,后一種適用于離散信源。177失真矩陣

單個(gè)符號(hào)的失真度的全體構(gòu)成的矩陣,稱為失真矩陣178平均單符號(hào)失真

已知p(ai)和d(ai,bj),平均失真只是符號(hào)轉(zhuǎn)移概率p(bj/ai)的函數(shù)。p(bj/ai

)在此實(shí)質(zhì)上代表編碼方式。179例:x1

y1x2

y2x1

y1x2

y1180序列失真函數(shù)平均序列失真其中d(Xl,Yl)是編碼前序列中的第l個(gè)符號(hào)和編碼后序列中的第l個(gè)符號(hào)之間的失真。

1814.2信息率失真函數(shù)

信源編碼器的目的是使編碼后所需的信息傳輸率R盡量小,R

給定失真的限制值D,使

D,找最小R,

R(D),定義為信息率失真函數(shù)。4.2.1信息率失真函數(shù)的定義:182p(yj/xi)信源符號(hào)編碼概率信道轉(zhuǎn)移概率

將信源編碼器看作信道,信源編碼器輸出的信息率R對(duì)應(yīng)到信道,即為接收端Y需要獲得的有關(guān)X的信息量,也就是互信息I(X;Y)。183D允許試驗(yàn)信道

若p(xi)和d(xi,yj)已定,則可給出滿足條件的所有轉(zhuǎn)移概率分布pij,它們構(gòu)成了一個(gè)信道集合PD。稱為D允許試驗(yàn)信道。184信息率失真函數(shù)R(D)所有的允許試驗(yàn)信道PD(即滿足

失真要求的所有假想信道)上,最低的輸出信息速率(最有效的信源編碼),就叫做信息率失真函數(shù)。離散無(wú)記憶信源:185例4-1:計(jì)算平均失真。已知編碼器輸入的概率分布為p(x)=[0.5,0.5],兩種信源編碼器轉(zhuǎn)移矩陣分別為:定義單符號(hào)失真度:186例4-1:計(jì)算平均失真。由此可得:由轉(zhuǎn)移概率矩陣,可得:1874.2.2信息率失真函數(shù)的性質(zhì)1.R(D)函數(shù)的定義域和值域

⑴Dmin和R(Dmin)

Dmin=0

對(duì)于連續(xù)信源:

188討論何時(shí)Dmin=0?只有當(dāng)失真矩陣中每行至少有一個(gè)零元素。何時(shí)R(0)=H(X)?只有當(dāng)失真矩陣中每行至少有一個(gè)零,并每一列最多只有一個(gè)零。否則R(0)可以小于H(X),表示這時(shí)信源符號(hào)集中有些符號(hào)可以壓縮、合并而不帶來(lái)任何失真。189定理證明:190證明:1911.R(D)函數(shù)的定義域和值域

(2)

Dmax和R(Dmax)

選擇所有滿足R(D)=0中D的最小值,定義為R(D)定義域的上限D(zhuǎn)max,即因此可以得到R(D)的定義域?yàn)?92Dmax=?R(D)=0就是I(X;Y)=0,這時(shí)試驗(yàn)信道輸入與輸出是互相獨(dú)立的,所以條件概率p(yj/xi)與xi無(wú)關(guān)。即需滿足條件193

從上式觀察可得:在j=1,…,m中,可找到

值最小的j,當(dāng)該j對(duì)應(yīng)的pj=1,而其余pj為零時(shí),上式右邊達(dá)到最小,這時(shí)上式可簡(jiǎn)化成194例4-2:設(shè)輸入輸出符號(hào)表為X=Y(jié)

{0,1},輸入概率分布p(x)={1/3,2/3},失真矩陣為求Dmin和Dmax。195解:

當(dāng)Dmin=0時(shí),R(Dmin)=H(X)=H(1/3,2/3)=0.91比特/符號(hào),這時(shí)信源編碼器無(wú)失真,該編碼器的轉(zhuǎn)移概率為196當(dāng)R(Dmax)=0時(shí)

此時(shí)輸出符號(hào)概率p(b1)=0,p(b2)=1,

所以這時(shí)的編碼器的轉(zhuǎn)移概率為

1972.R(D)函數(shù)的下凸性

當(dāng)給定信源概率分布p(x)時(shí),互信息量I(X;Y)是信道(假想信道)的轉(zhuǎn)移概率p(y/x)的下凸函數(shù),有極小值,該極小值即為信息率失真函數(shù):3.R(D)函數(shù)的單調(diào)遞減性

若D>D’,PD

PD’(選擇pij的范圍大)198綜上所述,可以得出如下結(jié)論:R(D)是非負(fù)的實(shí)數(shù),即R(D)

0。其定義域?yàn)?~Dmax,其值為0~H(X)。當(dāng)D>Dmax時(shí),R(D)

0。R(D)是關(guān)于D的下凸函數(shù),因而也是關(guān)于D的連續(xù)函數(shù)。R(D)是關(guān)于D的嚴(yán)格遞減函數(shù)。容許的D越大,所要求的R越小。反之亦然。199由以上三點(diǎn)結(jié)論,對(duì)一般信息率失真R(D)曲線的形態(tài)可以畫出來(lái):R(D)H(X)R(D)

0

D

Dmax

DR(D)0Dmax

D

離散信源連續(xù)信源2004.信息率失真函數(shù)與信道容量的比較

信息率失真函數(shù)R(D)信道容量C研究對(duì)象信源信道給定條件信源概率分布p(x)信道轉(zhuǎn)移概率p(y|x)選擇參數(shù)信源編碼器編碼方法p(y|x)信源分布p(x)限制條件結(jié)論H(X/Y)=H(X)-I(X;Y)噪聲干擾丟失的信息量編碼壓縮損失的信息量比較項(xiàng)本章小結(jié)201第四章主要內(nèi)容結(jié)構(gòu)202本章小結(jié)本章學(xué)習(xí)思路失真信源編碼必要性→失真測(cè)度函數(shù)→信源編碼器數(shù)學(xué)模型→D允許試驗(yàn)信道→信息率失真函數(shù)→信息率失真函數(shù)性質(zhì)203本章小結(jié)本章學(xué)習(xí)要點(diǎn)1.失真函數(shù)

均方失真、絕對(duì)失真、相對(duì)失真、誤碼失真2.平均失真度測(cè)量

(1)單符號(hào)平均失真:

(2)序列平均失真:204本章小結(jié)本章學(xué)習(xí)要點(diǎn)3.D允許試驗(yàn)信道4.信息率失真函數(shù)5.失真函數(shù)的性質(zhì)

下凸性,單調(diào)遞減性

205第5章信源編碼目的:提高通信系統(tǒng)的有效性,即通過編碼,用盡可能短的編碼序列符號(hào)來(lái)表示原信源序列?;舅枷胧牵?.盡可能去除原消息序列中符號(hào)之間的相關(guān)性;2.盡可能使編碼后各符號(hào)出現(xiàn)的概率相等。206第5章信源編碼主要解決兩個(gè)方面的問題:1.“信源編碼是用盡可能短的編碼序列符號(hào)來(lái)表示原信源序列”,這個(gè)“短”,有沒有極限?如果有,該極限是多少?2.用什么方法達(dá)到或者接近該極限?207非分組碼和分組碼將長(zhǎng)消息序列按順序分成若干個(gè)符號(hào)一組,對(duì)每一組獨(dú)立進(jìn)行編碼,稱為分組碼;否則稱為非分組碼。定長(zhǎng)碼和變長(zhǎng)碼若編碼后的碼字長(zhǎng)度都相同,則稱為定長(zhǎng)碼;否則稱為變長(zhǎng)碼。5.1信源編碼的有關(guān)概念5.1.1幾個(gè)概念208奇異碼和非奇異碼若編碼前的信源組和編碼后的碼字是一一對(duì)應(yīng)的,則稱為非奇異碼;否則稱為奇異碼。非唯一可譯碼和唯一可譯碼如果任意有限長(zhǎng)的碼元序列都只能被唯一地分割成一個(gè)個(gè)的碼字,則稱為唯一可譯碼;否則稱為非唯一可譯碼。5.1信源編碼的有關(guān)概念209非即時(shí)碼和即時(shí)碼在接收端接收碼元序列的過程中,如果接收到的碼元序列已經(jīng)組成了一個(gè)碼字,但接收端并不能立即判斷出,還要等下一個(gè)碼字開始接收的時(shí)候才能判斷出前者已經(jīng)是一個(gè)完整碼字,從而開始譯碼,則稱為非即時(shí)碼;反之則稱為即時(shí)碼。5.1信源編碼的有關(guān)概念2105.1信源編碼的有關(guān)概念5-1編碼的分類2115.1信源編碼的有關(guān)概念信源符號(hào)ai符號(hào)出現(xiàn)的概率p(ai)碼1碼2碼3碼4碼5a11/2000011a21/40111101001a31/8100000100001a41/811110110000001例5-1表5-1中的分組碼1、碼2、碼3、碼4和碼5,從上述的4個(gè)方面分別判斷屬于什么類型的碼。表5-1碼的不同屬性2125.1.2克勞福特不等式唯一可譯碼存在的充分和必要條件各碼字的長(zhǎng)度Ki應(yīng)符合克勞夫特不等式:

其中m是進(jìn)制,n是信源可能取值的符號(hào)數(shù)。213例:設(shè)對(duì)符號(hào)集{ai,i=1,2,3,4}進(jìn)行二進(jìn)制編碼;(1)對(duì)應(yīng)的碼長(zhǎng)分別為K1=1,K2=2,K3=2,K4=3,試判斷是否存在這樣的唯一可譯碼;(2)

若K1=1,

K2=2,

K3=3,

K4=3又如何?答:(1)由克勞福特定理可得:因此不存在滿足這種碼長(zhǎng)的唯一可譯碼。

214(2)由克勞福特定理可得:因此滿足這種碼長(zhǎng)的唯一可譯碼是存在的,例如{0,10,110,111}。

克勞夫特不等式只是用來(lái)說明唯一可譯碼是否存在,并不能作為唯一可譯碼的判據(jù)。例如,{0,10,010,111}215無(wú)失真信源編碼定理定長(zhǎng)信源編碼定理變長(zhǎng)信源編碼定理限失真信源編碼定理

5.2信源編碼定理2165.2.1無(wú)失真信源編碼(香農(nóng)第一定理)X=(X1X2…Xi…XL)Xi

{a1,a2,…,ai,…,an}

nL種信源編碼器Yk

{b1,b2,…,bj,…,bm}

M=mKL種

KL

logm用Y表示L長(zhǎng)的信源序列X,則送出一個(gè)信源符號(hào)所需要的信息率平均為

編碼目的:使最小。

217無(wú)失真信源編碼定理研究的內(nèi)容:最小信息率為多少時(shí),才能得到無(wú)失真的譯碼?若小于這個(gè)信息率是否還能無(wú)失真地譯碼?

無(wú)記憶平穩(wěn)信源平均符號(hào)熵為HL(X),對(duì)任意

,只要

則當(dāng)L足夠大時(shí),必可使譯碼差錯(cuò)概率小于δ;即可實(shí)現(xiàn)幾乎無(wú)失真編碼;

反之,當(dāng)時(shí),譯碼差錯(cuò)一定是有限值,而L足夠大時(shí),譯碼幾乎必定出錯(cuò)。2181.無(wú)失真定長(zhǎng)信源編碼定理:碼字所能攜帶的信息量大于信源序列輸出的信息量,則可以使傳輸幾乎無(wú)失真,當(dāng)然條件是L足夠大。反之,當(dāng)時(shí),不可能構(gòu)成無(wú)失真的編碼,也就是不可能做一種編碼器,能使收端譯碼時(shí)差錯(cuò)概率趨于零。當(dāng)時(shí),則為臨界狀態(tài),可能無(wú)失真,也可能有失真。219說明:L,,

,δ三者之間有什么關(guān)系?對(duì)于給定的

和δ,多大的L算足夠大?220問題:式中

為信源序列的自信息方差,

為一正數(shù)。當(dāng)

2均為定值時(shí),只要L足夠大,Pe可以小于任一正數(shù)

。即,如果給定差錯(cuò)概率上界δ,則

越小,要求的編碼長(zhǎng)度L就越大。L越大,編碼器越復(fù)雜,且時(shí)延越大,在有時(shí)延要求的場(chǎng)合,往往難以滿足實(shí)時(shí)性要求。增加

,可以減小對(duì)編碼長(zhǎng)度L的要求,但以犧牲編碼效率為代價(jià):221討論:222例題5-3:設(shè)離散無(wú)記憶信源概率空間為若要求編碼效率為90%,譯碼差錯(cuò)概率δ≤10-6試求所需要的編碼序列長(zhǎng)度L。223例題5-3:自信息方差為:若要求編碼效率η=90%:若要求編碼效率δ≤10-6:當(dāng)L有限時(shí),要做到高編碼效率、低錯(cuò)誤率,對(duì)于定長(zhǎng)編碼來(lái)說是不可能做到的。對(duì)例5-3中的信源,有8種不同的信源符號(hào)取值(a1~a8),如果用二進(jìn)制序列來(lái)表示的話,每個(gè)符號(hào)需要3

bit(3位二進(jìn)制數(shù)可以表示8中不同的符號(hào))。但由于不是等概率的,所以其熵H(X)=2.55

bit,按照無(wú)失真定長(zhǎng)信源編碼定理,其極限編碼長(zhǎng)度是2.55bit,而,也就是說,只能表示5.856種不同的符號(hào),其余的符號(hào)怎么辦?實(shí)際上,由于a1~a8中部分符號(hào)的概率較小,如果序列長(zhǎng)度L足夠大,則總有某種序列出現(xiàn)的概率足夠小,對(duì)這些概率足夠小的序列,如果不設(shè)計(jì)對(duì)應(yīng)的編碼碼字,造成的錯(cuò)誤概率也非常小。224思考:2252.無(wú)失真變長(zhǎng)信源編碼定理:平均碼長(zhǎng):定長(zhǎng)編碼中,由于所有的碼字都使用相同的長(zhǎng)度,限制了其靈活性,導(dǎo)致或者效率不高,或者復(fù)雜度太高(L太大)。變長(zhǎng)編碼可以對(duì)出現(xiàn)概率大的信源盡量用短碼,從而提高編碼效率.(統(tǒng)計(jì)匹配)2262.無(wú)失真變長(zhǎng)信源編碼定理:(1).單符號(hào)變長(zhǎng)編碼定理若離散單符號(hào)信源X:xi∈{a1,a2,…,an}的熵為H(X),對(duì)每個(gè)單符號(hào)進(jìn)行無(wú)失真變長(zhǎng)編碼,設(shè)yj∈{b1,b2,…,bm}。則227(2).離散平穩(wěn)無(wú)記憶序列變長(zhǎng)編碼定理

對(duì)于平均符號(hào)熵為HL(X)的離散平穩(wěn)無(wú)記憶信源,必存在一種無(wú)失真編碼方法,使平均信息率滿足不等式其中

為任意小正數(shù)。228例題5-4:設(shè)離散無(wú)記憶信源概率空間為試討論其編碼效率。若L=1,用二元定長(zhǎng)編碼(0,1)來(lái)構(gòu)造一個(gè)即時(shí)碼:x1→0,x2→1。平均碼長(zhǎng)=1二元碼符號(hào)/信源符號(hào)

編碼效率為輸出的信息率為229(續(xù))例題5-4:若對(duì)長(zhǎng)度為L(zhǎng)=2的信源序列進(jìn)行變長(zhǎng)編碼,其即時(shí)碼如表5-2所示。230(續(xù))例題5-4:xip(xi)即時(shí)碼x1x19/160x1x23/1610x2x13/16110x2x21/16111表5-2長(zhǎng)度為2的信源序列對(duì)應(yīng)的即時(shí)碼該碼平均長(zhǎng)度:?jiǎn)畏?hào)平均碼長(zhǎng):編碼效率為:231(續(xù))例題5-4:232(續(xù))例題5-4:L=3

η3=0.985

R3=0.985比特/二元碼符號(hào)

L=4

η4=0.991

R4=0.991比特/二元碼符號(hào)

233(續(xù))例題5-4:定長(zhǎng)二元碼編碼,要求編碼效率達(dá)到96%時(shí),允許譯碼錯(cuò)誤概率δ≤10-5

。2345.2.2限失真信源編碼(香農(nóng)第三定理)

信息率失真函數(shù)給出了失真小于D時(shí)所必須具有的最小信息率R(D);只要信息率大于R(D),一定可以找到一種編碼,使譯碼后的失真小于D。

限失真信源編碼定理:對(duì)于任意的D≥0和

>0,當(dāng)信息率R>R(D)時(shí),一定存在一種編碼方法,其譯碼失真小于或等于D+

,條件是編碼的信源序列長(zhǎng)度L足夠長(zhǎng)。反之,如果R<R(D),則無(wú)論采用什么編碼方法,其譯碼失真必大于D。2355.2.2限失真信源編碼(香農(nóng)第三定理)香農(nóng)第三定理是一個(gè)存在性定理,它只說明一定存在一種滿足要求的編碼方法。至于如何尋找這種最佳壓縮編碼方法,定理中沒有給出。在實(shí)際應(yīng)用中,該理論主要存在以下兩類問題:(1)符合實(shí)際信源的R(D)函數(shù)的計(jì)算相當(dāng)困難;(2)即使求得了符合實(shí)際的信息率失真函數(shù),還需要研究采用何種編碼方法,才能達(dá)到或接近極限值R(D)。2365.2.2限失真信源編碼(香農(nóng)第三定理)237香農(nóng)編碼哈弗曼編碼算術(shù)編碼(非分組碼)

5.3常用信源編碼方法2385.3.1

香農(nóng)編碼將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列確定滿足下列不等式的整數(shù)碼長(zhǎng)Ki

5.3常用信源編碼方法239香農(nóng)編碼為了編成唯一可譯碼,計(jì)算第i個(gè)消息的累加概率將累加概率Pi變換成二進(jìn)制數(shù)。取Pi二進(jìn)數(shù)的小數(shù)點(diǎn)后Ki位即為該消息符號(hào)的二進(jìn)制碼字。

5.3常用信源編碼方法240香農(nóng)編碼為了編成唯一可譯碼,計(jì)算第i個(gè)消息的累加概率將累加概率Pi變換成二進(jìn)制數(shù)。取Pi二進(jìn)數(shù)的小數(shù)點(diǎn)后Ki位即為該消息符號(hào)的二進(jìn)制碼字。

241香農(nóng)編碼

香農(nóng)編碼的基本做法:是把長(zhǎng)度為1的整個(gè)累積概率區(qū)間,按照信源符號(hào)集中q個(gè)信源符號(hào)的概率大小,分成q份不同長(zhǎng)度的子區(qū)間(每份子區(qū)間的長(zhǎng)度正比于對(duì)應(yīng)符號(hào)的概率大?。?,將每種信源符號(hào)xi,映射到其對(duì)應(yīng)子區(qū)間上的一個(gè)點(diǎn)。這樣,每個(gè)信源符號(hào)xi映射區(qū)間都是不重疊的,從而可以保證唯一可譯碼,而且可以證明,也是即時(shí)碼;另一方面,碼字長(zhǎng)度由其概率決定,概率大的用短碼。

242香農(nóng)編碼

例5.4設(shè)信源共7個(gè)符號(hào)消息

信源消息符號(hào)ai符號(hào)概率p(ai)累加概率Pi-logp(ai)碼字長(zhǎng)度Ki碼字a10.200

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論