西安電子科技大學(xué)信息論與編碼理論講義

1、可編輯WORD版本資料-學(xué)海無涯可編輯WORD版本資料-學(xué)海無涯 34/34可編輯WORD版本資料-學(xué)海無涯(完整word版)西安電子科技大學(xué)信息論與編碼理論講義 信息論 講義 204教研室 2005年11月 主要內(nèi)容： 第一章緒論 第二章離散信源及其信息測度第三章離散信道及其信道容量第四章無失真信源編碼 第五章有噪信道編碼 第一章 緒論 信息論人們在長期通信工程的實踐中，由通信技術(shù)與概率論、隨機過程和數(shù)理統(tǒng)計相結(jié)合而逐步發(fā)展起來的一門學(xué)科。 奠基人香農(nóng) 1948年發(fā)表了著名的論文通信的數(shù)學(xué)理論，為信息論奠定了理論基礎(chǔ)。 1.1 信息的概念 人類離不開信息，信息的接收、傳遞、處理和利用時時刻刻

2、都在發(fā)生。 如：“結(jié)繩記事”、“烽火告警”，信息的重要性是不言而喻的。 什么是信息？信息論中最基本、最重要的概念。 信息與“消息”、“情報”、“知識”、“情況”等的區(qū)別： “情報”人們對于某個特定對象所見、所聞、所理解而產(chǎn)生的知識。是一類特定的信息。 “知識”人們根據(jù)某種目的，從自然界收集得來的數(shù)據(jù)中，整理、概括、提取得到的有價值的、人們所需的信息。是一種具有普遍和概括性質(zhì)的高層次的信息。 “消息”以文字、符號、數(shù)據(jù)、語言、音符、圖片、圖像等能夠被人們感覺器官所感知的形式，表達客觀物質(zhì)運動和主觀思維活動的狀態(tài)。 消息包含信息，是信息的載體。二者既有區(qū)別又有聯(lián)系。 “信號”消息的運載工具。 香農(nóng)

3、從研究通信系統(tǒng)傳輸?shù)膶嵸|(zhì)出發(fā)，對信息作了科學(xué)的定義，并進行了定性和定量的描述。 收信者： 收到消息前，發(fā)送者發(fā)送的消息1、描述的是何種事物運動狀態(tài)的具體消息；2、描述的是這種消息還是那種消息；3、若存在干擾，所得消息是否正確與可靠。 存在“不知”、“不確定”或“疑問” 收到消息后，知道消息的具體內(nèi)容，原先的“不知”、“不確定”或“疑問”消除或部分消除了。 消息傳遞過程從不知到知的過程；從知之甚少到知之甚多的過程；從不確定到部分確定或全部確定的過程。 通信過程消除不確定性的過程。 不確定性的消除，就獲得了信息。 若原先不確定性全部消除了，就獲得了全部的消息；若消除了部分不確定性，就獲得了部分信息

4、；若原先不確定性沒有任何消除，就沒有獲得任何消息。 信息事物運動狀態(tài)或存在方式的不確定性的描述。 通信的結(jié)果消除或部分消除不確定性而獲得信息。 信息如何測度？ 信息量與不確定性消除的程度有關(guān)。消除了多少不確定性，就獲得了多少信息量。 不確定性隨機性概率論與隨機過程。 樣本空間所有可能選擇的消息的集合。 概率空間樣本空間和它的概率測度。,P X ? ?=?)(,),(, ),(,)(2211q q a P a P a a a P a x P X )(i a P 先驗概率，選擇符號i a 作為消息的概率。 定義：自信息) (1log )(i i a P a I = 若信道存在干擾，假設(shè)接收到的消息

5、是j b ，j b 可能與i a 相同，也可能與i a 有差異。 )|(j i b a P 后驗概率 定義：互信息) |(1 log )(1log );(j i i j i b a P a P b a I -= 1.2 信息論研究對象、目的和內(nèi)容 1、 研究對象 （1） 信源產(chǎn)生消息和消息序列的源 （2） 編碼器消息變換成信號 信源編碼對信源輸出的消息進行適當(dāng)?shù)淖儞Q和處理，目的為了提高信息傳輸?shù)男省?信道編碼為了提高信息傳輸?shù)目煽啃远鴮ο⑦M行的變換和處理。 還包括換能、調(diào)制、發(fā)射等。 （3） 信道載荷消息的信號的傳輸媒介。 （4） 譯碼器信道輸出的編碼信號（迭加有干擾）進行反變換。信源譯碼

6、器和信道譯碼器 （5） 信宿消息傳送的對象。 將上述模型中編（譯）碼器分成信源編（譯）碼、信道編（譯）碼和加密（解密）編（譯）碼三個子部分。 2、 研究目的 要找到信息傳輸過程的共同規(guī)律，以提高信息傳輸?shù)目煽啃浴⒂行浴⒈Ｃ苄院驼J證性，使達 圖1.3 信息傳輸系統(tǒng)模型 可靠性高要使信源發(fā)出的消息經(jīng)過信道傳輸以后，盡可能準確地、不失真地再現(xiàn)在接收端。 有效性高經(jīng)濟效益好，即用盡可能短的時間的盡可能少的設(shè)備來傳送一定數(shù)量的信息。 保密性隱蔽和保護通信系統(tǒng)中傳送的消息，使它只能被受權(quán)接收者獲取，而不能被未受權(quán)者接收和理解。 認證性接收者能正確判斷所接收的消息的正確性，驗證消息的完整性，而不是偽造的和

7、被竄改的。 3、研究內(nèi)容 三種理解：（1）狹義信息論（經(jīng)典信息論） 研究信息的測度、信道容量以及信源和信道編碼理論等問題。 香農(nóng)基本理論 （2）一般信息論 香農(nóng)理論、噪聲理論、信號濾波和預(yù)測、統(tǒng)計檢測與估計理論、調(diào)制理論、信息處理理論以及保密理論等。 （3）廣義信息論 第二章 離散信源及其信息測度 2.1 信源的數(shù)學(xué)模型及分類 根據(jù)信源輸出消息的不同的隨機性質(zhì)分類。 一、隨機變量X 描述信源輸出的消息 1、離散信源 信源輸出的消息數(shù)是有限的或可數(shù)的，每次只輸出一個消息。 數(shù)學(xué)模型離散型的概率空間 ? ?=?)(,),(, ),(,)(2211q q a P a P a a a P a x P

8、X （1)(1=q i i a P ：完備集條件） 2、連續(xù)信源 信源輸出的消息數(shù)是無限的或不可數(shù)的，每次只輸出一個消息。 數(shù)學(xué)模型連續(xù)型的概率空間 ? ? ?=? ?)(),()(x p b a x p X 或 ? ? ?)(x p R （1)(=?b a dx x p 或1)(=?R x p ：完備集條件） 二、隨機序列X 描述信源輸出的消息 根據(jù)X 的平穩(wěn)性與否，分平穩(wěn)信源與非平穩(wěn)信源。 1、離散平穩(wěn)信源 信源輸出的隨機序列),(21N X X X X =中),2,1(N i X i =為取值離散的離散型隨機變量，X 的各維概率分布都與時間起點無關(guān)（任意兩個不同時刻X 的各維概率分布都相

9、同）。 2、連續(xù)平穩(wěn)信源 信源輸出的隨機序列),(21N X X X X =中),2,1(N i X i =為取值連續(xù)的連續(xù)性隨機變量，X 的各維概率密度函數(shù)都與時間起點無關(guān)（任意兩個不同時刻X 的各維概率密度函數(shù)都相同）。 3、離散無記憶信源（離散平穩(wěn)信源） 信源輸出的隨機序列),(21N X X X X =中),2,1(N i X i =統(tǒng)計獨立，i X 取值于同一概率空間X 。 = =q i i iN i i i k k a P a a a P x P 1 21)()()( 4、離散無記憶信源X 的N 次擴展信源 由離散無記憶信源輸出N 長的隨機序列構(gòu)成的信源。 ? ?=?)(,),(,

10、 ),(,)(2211N q N q i N P P P P X )(21iN i i i a a a =),2,1,(21q i i i N = 滿足=q i i iN i i i k k a P a a a P x P 1 21)()()( =N k k N q i q i i q i i a P P 11 1 1)()( 5、有記憶信源 信源輸出的隨機序列),(21N X X X X =中),2,1(N i X i =之間有依賴關(guān)系。 6、馬爾可夫信源 信源輸出的隨機序列),(21N X X X X =中),2,1(N i X i =之間有依賴關(guān)系。但記憶長度有限。若記憶長度為m+1，則

11、稱為m 階馬爾可夫信源。（信源每次發(fā)出的符號只與前m 個符號有關(guān)，與更前面的符號無關(guān)。） )|()|(32112132112m i i i i i i i m i i i i i i i x x x x x x x P x x x x x x x x P += ),2,1(N i = 若上述條件概率與時間起點i 無關(guān)，該信源稱為時齊馬爾可夫信源。 三、隨機過程)(t x 描述信源輸出的消息 隨機波形信源 信源輸出的消息是時間（或空間）上和取值上都是連續(xù)的函數(shù)。 轉(zhuǎn)換關(guān)系： 隨機波形信源取樣連續(xù)平穩(wěn)信源 連續(xù)信源分層（量化）離散信源 2.2 離散信源的信息熵 離散信源輸出是單個符號的消息，且這些

12、消息是兩兩互不相容的。 可用一維隨機變量來描述。 ? ?=?)(,),(, ),(,)(2211q q a P a P a a a P a x P X （1)(1=q i i a P ：完備集條件） 2.2.1 自信息 獲得信息量的大小與不確定性消除的多少有關(guān)。 例2.1 （P20） 收到某消息獲得的信息量（即收到某消息后獲得關(guān)于某基本事件發(fā)生的信息量） =不確定性減少的量 =（收到此消息前關(guān)于某事件發(fā)生的不確定性）-（收到此消息后關(guān)于某事件發(fā)生的不確定性） 無噪聲時， 收到某消息獲得的信息量 =收到此消息前關(guān)于某事件發(fā)生的不確定性 =信源輸出的某消息中所含有的信息量 事件發(fā)生的不確定性與事件

13、發(fā)生的概率有關(guān)。 （事件發(fā)生概率越小，不確定性就大；事件發(fā)生概率越大，不確定就越小。） 某事件發(fā)生所含有的信息量：)()(i i a P f a I =自信息量 函數(shù))(i a P f 滿足： （1）)(i a P f 應(yīng)是先驗概率)(i a P 的單調(diào)遞減函數(shù)，即當(dāng))()(2211a P a P 時，21P f P f i x ,),2,1(n i =，有=n i i i n i i i x p x p 1 1 log log （x log 為上凸函數(shù)。） 設(shè)另一概率分量數(shù)同樣也等于n 的概率空間),(21n s s s S = 其中10i x ，),2,1(n i = =n i i i i

14、 n i i i i p s p p s p 1 1log log =-n i i i n i i i n i i p p s p s 1 1 1 log log log =-n i i i n i i i s p p p 1 1 log log =-=n i i i n s p p p p H X H 1 21log ),()( 補充：1ln -= x x f )(x f 在1=x 處取極小值。)(x f 極小值為0。 =-?=-?n i i i n i i i i n i i i i p s e p s e p p s p 1110)(l o g )1(l o g l o g =-n i

15、i i n i i i s p p p 1 1 log log =-=n i i i n s p p p p H X H 1 21log ),()( 9、上凸性 熵函數(shù))(P H 是概率矢量),(21q p p p P =是上凸函數(shù)。即 對任意概率矢量),(211q p p p P =和),(212q p p p P = ，及任意10-+ 證明：)1(21P P H -+ =-+-+- =q i i i i i p p p p 1)1(l o g )1( =-+-+-=q i q i i i i i i i p p p p p p 1 1 )1(l o g )1()1(l o g =-+ -+

16、-=q i q i i i i i i i i i i i p p p p p p p p p p 11 )1(log )1()1(log =-+-+=q i q i i i i i i p p p p p P H P H 1 1 211 log )1(log)()1()( = -+-q i q i i i i i i i p p p p p 1 1 1log )1()1(log)1( 令i i i p p -+=)1(，),2,1(q i =， 11 =q i i =-+-q i q i i i i i i p p p p p 11 1log )1(log 0log log log log

17、1 1 1 1 =+-+-=q i q i i i i i q i q i i i i i p p p p p p p 同理：01log )1()1(log) 1(1 1 -+-=q i q i i i i i i i p p p p p 所以，)()1()()1(2121P H P H P P H -+-+ 2.4 信息熵的唯一性定理 定理2.1 設(shè)),(21n n p p p H 是概率矢量),(21q p p p P =的非負函數(shù)，對于任意n ，概率矢量滿足0i p ， 11 =n i i p 。若)(P H n 滿足下述公理： （A 1）對n ?，函數(shù)),(21n n p p p H

18、是i p ),2,1(n i =的連續(xù)和對稱函數(shù)； （A 2）擴展性。對n ?，有 （A 3）極值性。對n ?，有 )1,1,1(),(21n n n H p p p H n n n ； （A 4）強可加性。若 0ij i p p ，111 =n i m j ij i p p ，11 =m j ij p ),2,1(n i =),2,1(m j = 有 ),(12221211121111nm n n n m m nm p p p p p p p p p p p p p p H ),(),(21121im i i m n i i n n p p p H p p p p H =+=； 則得 i n

19、 i i n n p p p p p H log ),(1 21=-= 其中為一正常數(shù)。 定理中，為一常數(shù)，它由對數(shù)的底來決定，只影響所取的單位。 2.5 離散無記憶的擴展信源 設(shè)一個離散無記憶信源的概率空間 ? ?=?)(,),(, ),(,)(2211q q a P a P a a a P a x P X 11=q i i p 則信源X 的N 次擴展信源N X 是具有N q 個符號的離散信源，其N 重概率空間為 ? ?=?)(,),(,),(,)(2211N q q i N P P P P X i 某一個由N 個i a 組成的序列。 )(i a P N 個k i a 組成的序列的概率。1)

20、(1=N q i i p N 次擴展信源的熵 -=-=N N X i i X N P P X P X P X H X H )(log )()(log )()()( )()(X NH X H N = 證明：),(21N i i i i a a a = i i i i p p p P ?= )( ),2,1,(21q i i i N = -=N X i i N P P X H )(log )()( ?=N N X i i i i N p p p P X H 211 log )()( += N N N N X X i i X i i i i p P p P p P 1 log )(1log )(1l

21、og )(21 =?=?=q i i q i i q i i i X i i i i X i i N N N N N p p p p p p p p p P 11 12211112111log 1log 1log )( )(1 log 111 1X H p p q i i i = 所以，)()()()()()(X NH X H X H X H X H X H N =+= 例2.5 （P40） 2.6 離散平穩(wěn)信源 2.6.1 離散平穩(wěn)信源的數(shù)學(xué)定義 一維平穩(wěn)信源 )()()(x P x P x P j i = （i ，j 為任意大于1的任意整數(shù)） 二維平穩(wěn)信源 )()()(x P x P x

22、P j i = )()(11+=j j i i x x P x x P （i ，j 為任意整數(shù)，j i ） 離散平穩(wěn)信源 )()(j i x P x P = )()(11+=j j i i x x P x x P )()(11N i j j N i i i x x x P x x x P += （i ，j 為任意整數(shù)，j i ） 由聯(lián)合概率與條件概率的關(guān)系： )|()()(11i i i i i x x P x P x x P += )|()|()()(12121+=i i i i i i i i i x x x P x x P x P x x x P )|()|()()(1111-+=N i

23、 i i N i i i i N i i i x x x x P x x P x P x x x P 可得： )|()|(11j j i i x x P x x P += )|()|(1212+=j j j i i i x x x P x x x P )|()|(1111-+-+=N j j j N j N i i i N i x x x x P x x x x P 條件概率均與時間起點無關(guān)，只與關(guān)聯(lián)長度N 有關(guān)。（平穩(wěn)信源發(fā)出的平穩(wěn)隨機序列前后的依賴關(guān)系與時間起點無關(guān)。） 2.6.2 二維平穩(wěn)信源及其信息熵 ? ?=? ?)(,),(, ),(,)(2211q q a P a P a a a

24、 P a x P X 且1)(1=q i i a P 連續(xù)兩個信源符號出現(xiàn)的聯(lián)合概率分布)(j i a a P ),2,1,(q j i =，并有 1)(11 =q i q j j i a a P ) ()()|(i j i i j a P a a P a a P = ),2,1,(q j i = 1)|(1 =q j i j a a P 信源發(fā)出的符號序列中相鄰兩個符號是有關(guān)聯(lián)的。 如何進行信息測度？信息熵的近似值計算 分析一： 將二維信源輸出的隨機序列分成每二個符號一組，每組代表新信源21X X X =中的一個符號。 假設(shè)組與組之間是統(tǒng)計獨立的，互不相關(guān)的。（實際上，不是統(tǒng)計獨立的。） ?

25、 ?=?=?-)|()(,)(,)(121112121i j i q q q q j i a a P a P a a a a a a a a P a a x x P X X 1)(11 =q i q j j i a a P =-=q i q j j i j i a a P a a P X X H 11 21)(log )()( 21X X 的聯(lián)合熵 表示原來信源X 輸出任意一對消息的共熵，即描述信源X 輸出長度為2的序列的平均不確定性，或 所含有的信息量。 可用 )(1 21X X H 作為二維平穩(wěn)信源X 的信息熵的近似值。 分析二： =-=q j i j i j i a a P a a P

26、a X X H 1 12)|(log )|()|( =-=-=q i q i i j i j q j i i i a a P a a P a P a X X H a P X X H 1 11 1212) |(log )|()()|()()|( =-=q i i j q j j i a a P a a P 11 )|(log )( 條件熵 =-=-=q i i j i q j j i q i q j j i j i a a P a P a a P a a P a a P X X H 11 11 21)|()(log )()(log )()( =-=q i i j q j j i q i i q

27、j j i a a P a a P a P a a P 11 11)|(log )()(log )( )|()(log )(1211X X H a P a a P q i i q j j i +-= )|()(log )()|()(log )|()(121 121 1 X X H a P a P X X H a P a a P a P q i i i q i q j i i j i +-=+-= )|()(121X X H X H += )|()()(12121X X H X H X X H +=熵的強可加性 條件熵與無條件熵的關(guān)系：)()|(212X H X X H 證明：在區(qū)域0,1中，設(shè)

28、x x x f log )(-=（上凸函數(shù)）。并設(shè)ij i j i p a a P x =)|(，而i i p a P =)(， 有 11=q i i p 由詹森不等式 )(1 1 =q i i i q i i i x p f x f p 可得： j j q i ij i ij q i i q i ij ij i p p p p p p p p p log )log(log 1 1 1 -=-=)()(1 1 =q i j j j i q i ij i p a P a a p p p 上式對j 求和： =-q j j j q i q j ij ij i p p p p p 1 11 log l

29、og ? )()|(212X H X X H 等式成立條件：只有當(dāng))()|(j i j a P a a P =。 當(dāng)1X 和2X 取自同一概率空間X ，則有)()()(12X H X H X H = )(2)()()(2121X H X H X H X X H =+ 例2.6 （P44） )(2 1 21X X H 與)|(12X X H 選取哪個值更能接近實際二維平穩(wěn)信源的熵？ 2.6.3 離散平穩(wěn)信源的極限熵 設(shè)離散平穩(wěn)有記憶信源 ? ? ?=?q q p p a a p a x P X ,)(2211 且11=q i i p 信源符號之間依賴長度為N ，已知各維概率分布。 離散平穩(wěn)信源的

30、一系列聯(lián)合熵 =-=q i q i i i i i i i N N N N a a a P a a a P X X X H 1 1 2112121)(log )()( ),3,2(N N = 定義N 長的信源符號序列中平均每個信源符號所攜帶的信息量為 )()(21N N X X X H X H =平均符號熵 條件熵： =q i q i i i i i i i i N N N N N N a a a a P a a a P X X X X H 1 1 121112121) |(log )()|( ),3,2(N N = 對于離散平穩(wěn)信源，當(dāng)l p ，所以當(dāng)0=j p ，總?cè)≌龜?shù)，得 ?j p I

31、 。 若0j p ，可取正數(shù)，也可取負數(shù)。若取正數(shù)，得 ?j p I ；若取負數(shù)，得?j p I 故當(dāng)0j p ， =?j p I 滿足（*）式條件。 結(jié)論：當(dāng)信道平均互信息達到信道容量時，輸入信源符號集中每一個信源符號x 對輸出端Y 提供相同的互信息，只是概率為零的符號除外。 例3.8 （P100） P3.9 （P101） 對于一般的離散信道，很難利用Th3.3來尋求信道容量和對應(yīng)的輸入概率分布。因此仍只能采用求解方程組的方法。 ?=+=1)(log )()|(log )|(1 1r i i s j j i j i j a P e b P a b P a b P C b P a b P a

32、b P a b P s j j i j s j i j i j =-=1 1)(log )|()|(log )|( ),2,1(r i = =+s j i j i j s j j i j a b P a b P b P C a b P 1 1 )|(log )|()(log )|( ),2,1(r i = 令)(log j j b P C +=，得： =s j i j i j s j j i j a b P a b P a b P 1 1 )|(log )|()|( 設(shè)s r =，信道傳遞矩陣P 是非奇異矩陣，則此方程組有解?？汕蟪鰆 的數(shù)值。 -=j C j C 2 log （比特/符號）

33、C j j b P -=2 )( ),2,1(s j = ? i p 例3.10 （P102） 3.6 離散無記憶擴展信道及其信道容量 離散無記憶信道的輸入符號集,1r a a A =，輸出符號集,1s b b B =，信道矩陣為： ? ? ?=rs r r r s s p p p p p p p p p p p p P 32 1 2232221 1131211 且11 =s j ij p ),2,1(r i = 則此無記憶信道的N 次擴展信道的數(shù)學(xué)模型： 輸入隨機序列),(21N X X X X =，i X 可能取值：N r 個；輸出隨機序列Y 的可能取值有N s 個。 ?=N r r r

34、r N a a a a a a a a a X )()()(22111 111 N s s s s Y b b b b b b b b b N ? ? ?=)()()(21121111 ? ?=N N N N N N s r r r s s 212222111211 )|(k h kh P = ),2,1,2,1(N N s h r k = 11 =N s h hk )(2 1 N k k k k a a a = ,21r k a a a a i ),2,1(N i = )(2 1 N h h h h b b b = ,21s h b b b b i ),2,1(N i = =N i k h

35、k k k h h h k h kh i i N N a b P a a a b b b P P 1 )|()|()|(2 1 2 1 例3.11 （P112） 無記憶信道的N 次擴展信道的平均互信息： )|()()|()();();(N N N N N N N N X Y H Y H Y X H X H Y X I Y X I -=-= )() |(log )()()|(log )(,h k h Y X h k k h k Y X h k P P P P P P N N N N = Th3.5 若信道的輸入隨機序列為)(21N X X X X =，通過信道傳輸，接收到的隨機序列為 )(21N

36、 Y Y Y Y =。假若信道是無記憶的，即信道傳遞概率滿足=N i k h k h i i a b P P 1 )|()|( ),2,1,2,1(N N s h r k =，則存在=N i i i Y X I Y X I 1 );();(。 證明：設(shè)信道輸入和輸出隨機序列X 和Y 的一個取值為： )(2 1 N k k k k a a a = ,21r k a a a a i ),2,1(N i = )(2 1 N h h h h b b b = ,21s h b b b b i ),2,1(N i = ) () |(log )()|(log )();(;h k h h k h Y X h

37、k P P E P P P Y X I = )() |()|()|(l o g );(2211h k h k h k h P P P P E Y X I N N = =N i Y X h k h h k N i i i i i i i i i i b P a b P b a P Y X I 1,1)() |(l o g )();( + = 2 22222 21 11111 1,) ()|(log )() ()|(log )(Y X h k h h k Y X h k h h k b P a b P b a P b P a b P b a P N N N N N N N Y X h k h h

38、k b P a b P b a P ,) ()|(log )( ?= 1 121221111,) ()()() |()|()|(log )(Y X Y X h h h k h k h k h h h k k N N N N N N N b P b P b P a b P a b P a b P b b a a P ? ? ? ?=)()()()|()|()|(log 212211N N N h h h k h k h k h b P b P b P a b P a b P a b P E =-N i i i Y X I Y X I 1 );();( ? ? ?-?=)()()()|()|()|

39、(log )()|()|()|(log 2122112211N N N N N h h h k h k h k h h k h k h k h b P b P b P a b P a b P a b P P a b P a b P a b P E ? ? ?=)()()()(log 21h h h h P b P b P b P E N ?=? ? ?Y X h h h h h k h h h h P b P b P b P P P b P b P b P E N N ,)()()()() (log )()()()(log 2121 ?=Y X h h h h k N b P b P b P

40、P ,)()()()|(log 21 01log )()()(log 21=?=Y h h h N b P b P b P 即得：= N i i i Y X I Y X I 1 );();(。當(dāng)信源無記憶時，等號成立！ Th3.6 若信道的輸入隨機序列為)(21N X X X X =，通過信道傳輸，接收到的隨機序列為 )(21N Y Y Y Y =，而信道的傳遞概率為)|(x y P ，假若信源是無記憶的，則存在 =N i i i Y X I Y X I 1 );();(。 證明： ) () |(log )()|(log )();(;k h k k h k Y X h k P P E P P

41、P Y X I = )(2 1 N k k k k a a a = ,21r k a a a a i ),2,1(N i = )(2 1 N h h h h b b b = ,21s h b b b b i ),2,1(N i = )()()()(21 N k k k k a P a P a P P = ) ()()() |(l o g );(21N k k k h k a P a P a P P E Y X I = =N i Y X k h k h k N i i i i i i i i i i a P b a P b a P Y X I 1,1)() |(l o g )();( ?= 1

42、121221111,) ()()() |()|()|(log )(Y X Y X k k k h k h k h k h h k k N N N N N N N a P a P a P b a P b a P b a P b b a a P ? ? ?=)()()()|()|()|(l o g 212211N N N k k k h k h k h k a P a P a P b a P b a P b a P E ? ? ?=-=)|()|()|()|(log );();(22111h k h k h k h k N i i i P b a P b a P b a P E Y X I Y X

43、 I N N ? ? ? ?)|()|()|()|(log 2211h k h k h k h k P b a P b a P b a P E N N ?=Y X h k h k h k h k h k P b a P b a P b a P P N N ,) |() |()|()|() (log 2211 ?=Y X h k h k h k h N N b a P b a P b a P P ,) |()|()|()(log 2211 =Y h P 01log )(log 證得：= N i i i Y X I Y X I 1 );();(。當(dāng)信道是無記憶時，等號成立！ 當(dāng)信源和信道都是無記憶

44、時，= N i i i Y X I Y X I 1 );();(。 若信道輸入序列)(21N X X X X =中i X 取自于同一信源符號集，并具有同一概率分布，且通過相同的信道傳送到輸出端（即輸出序列)(21N Y Y Y Y =中i Y 也取自于同一符號集），因此有： );(),(),(),(2211Y X I Y X I Y X I Y X I N N = ? );();(1 Y X NI Y X I N i i i = 對于離散無記憶信道的N 次擴展信道，若信源也是無記憶的，則：);();(Y X NI Y X I =。 （當(dāng)信源無記憶時，無記憶的N 次擴展信道的平均互信息等于原來信

45、道的平均互信息的N 倍。） 對于一般的離散無記憶信道的N 次擴展信道，有= N i i i Y X I Y X I 1 );();(。 其信道容量：=N i i N i i i x P N i i i x P x P N C Y X I Y X I Y X I C i 1 1 ) (1 ) () ();(max );(max );(max 。 NC C N = 離散無記憶的N 次擴展信源的信道容量等于原來原單符號離散信道的信道容量的N 倍。 一般情況下，消息序列在離散無記憶的N 次擴展信道中傳輸?shù)男畔⒘繛椋篘C Y X I );(。 3.7 獨立并聯(lián)信道及其信道容量 設(shè)有N 個信道，它們的輸入

46、分別是N X X X ,21 ，它們的輸出分別是N Y Y Y ,21 ，它們的傳遞概率分別是)|(11x y P ，)|(22x y P ，)|(,N N x y P 。在N 個獨立并聯(lián)信道中，每一個信道的輸出i Y 只與本信道的輸入i X 有關(guān)，與其他信道的輸入、輸出都無關(guān)。則： )|()|()|()|(22112121N N N N x y P x y P x y P x x x y y y P = =N i i i N N Y X I Y Y Y X X X I 1 2121);();( 獨立并聯(lián)信道的信道容量： =N i i N N x x P N C Y Y Y X X X I C

47、 N 1 2121) (,2,1);(max 1 );(max ) (i i x P i Y X I C i = 當(dāng)輸入符號i X 相互獨立，且輸入符號i X 的概率分布達到各信道容量的最佳輸入分布時，獨立并聯(lián)信道的信道容量才等于各信道容量之和。= N i i N C C 1 ,2,1 。 3.8 串聯(lián)信道的互信息和數(shù)據(jù)處理定理 信道輸出端對接收到的信號或數(shù)據(jù)進行適當(dāng)?shù)奶幚頂?shù)據(jù)處理。一般地，數(shù)據(jù)處理系統(tǒng)可看成是一種信道。它與傳輸數(shù)據(jù)的信道是串聯(lián)關(guān)系。 X ：,21r a a a Y ：,21s b b b Z ：,21t c c c ?=Y xy z P x y P x z P )|()|()

48、|( 若信道II 的傳遞概率使其輸出Z 只與輸入Y 有關(guān)，與前面的輸入X 無關(guān)，即滿足 )|()|(y z P xy z P =，稱X 、Y 、Z 構(gòu)成馬爾可夫鏈。 t s s r t r xy z P x y P x z P ?=)|()|()|( t s s r t r y z P x y P x z P ?=)|()|()|(（X 、Y 、Z 滿足馬爾可夫鏈） 討論);(Y X I 、);(Z X I 、);(Z Y I 之間的關(guān)系。 Th3.7 );();(Z Y I Z XY I ，當(dāng)且僅當(dāng))|()|(y z P xy z P =時，等式成立。 證明： = Z Y X z P xy

49、z P E z P xy z P xyz P Z XY I ,) () |(log )()|(log )();( = Z Y Z Y X z P y z P E z P y z P xyz P z P y z P yz P Z Y I ,)()|(log )()|(log )()()|(log )();( ) |() |(l o g )()|(l o g )()|(l o g );();(xy z P y z P E z P xy z P z P y z P E Z XY I Z Y I =-=- =Z Y X Z Y X y z P xy P xy z P y z P xyz P xy z

50、P y z P E ,)|()(log )|() |()(log )|()|(log =Y X Z y z P xy P ,01log )|()(log 同理可得：);();(Z X I Z XY I )|(xy z P =Y x y P 1)|( =Z xy z P 1)|( =Z x z P 1)|( 串接信道 等價總信道 Th3.8 （數(shù)據(jù)處理定理） 若X 、Y 、Z 組成一個馬爾可夫鏈，則有);();(Y X I Z X I 、);();(Z Y I Z X I 。 證明：因為X 、Y 、Z 是馬爾可夫鏈，可得：);();(Z Y I Z XY I =，而);();(Z X I Z X

51、Y I ， 所以：);();(Z Y I Z X I 因為X 、Y 、Z 是馬爾可夫鏈，可證得：Z 、Y 、X 也是馬爾可夫鏈，所以有： );();(X Y I X YZ I =，又可得：);();(X Z I X YZ I );();();();(Z X I X Z I X Y I Y X I = 在串聯(lián)信道中一般有)|()|(Y X H Z X H ，當(dāng)滿足)|()|(z x P y x P =時，等式成立。 例3.12 （P120） 對于一系列不涉及原始信源的數(shù)據(jù)處理，即對一系列串接信道，有： );();();()(W X I Z X I Y X I X H 信息不增性原理。 例3.13

52、 （P124） 一般的通信系統(tǒng)模型： ),(Z Y X S 隨機矢量序列，對于實際通信系統(tǒng)，它們形成一個馬爾可夫鏈。 對),(Z Y X ，有);();(Y X I Z X I ；對),(Z Y S ，有);();(Y S I Z S I ；對),(Z X S ，有 );();(Z X I Z S I ，可得：);();(Y X I Z S I 一般的數(shù)據(jù)處理定理。 3.9 信源與信道匹配 當(dāng)信源與信道連接時，若信息傳輸率達到了信道容量，稱此信源與信道達到匹配。否則認為信道有剩余。 定義：信道剩余度=);(Y X I C - 信道相對剩余度= C Y X I C Y X I C ) ;(1);

53、(-=- 無損信道中，r C log =，)();(X H Y X I =。 無損信道的相對剩余度=r X H log ) (1- 信源剩余度。 一系列串接信道 例 （P127） 是否存在一種信源編碼，使信道的信息傳輸率R 接近或等于信道容量？即存在一種編碼，使每個信源符號所需的二元符號最少？香農(nóng)無失真信源編碼理論（無失真數(shù)據(jù)壓縮理論）。 將信源輸出的消息變換成適合信道傳輸?shù)男滦旁吹南?，使信源和信道達到匹配。 第四章 無失真信源編碼 問題：1、在不失真或允許一定失真條件下，如何用盡可能少的符號來傳送信源信息，以便提高信息 傳輸率？ 信源編碼 2、在信道受干擾的情況下，如何增加信號的抗干擾能力

54、，同時又使得信息傳輸率最大？ 信道編碼 碼符號（碼元）：j x )(),1(21i l i i i i i x x x W q i s =?= X x k i ),1(i l k = )()(2121i l N i i i i i i i i x x x W s s s s =?= S s k i ),1(N k = X x k i ),1(i l k = 碼字i W 碼字長度（碼長）i l 碼C （所有碼字的集合） 編碼：信源符號映射到碼符號。 無失真編碼：映射一一對應(yīng)，可逆。 碼的定義： 1、二元碼 碼符號集1,0=X 2、等長碼（固定長度碼） l l i = ),1(q i = 3、變長

55、碼 所有碼字的碼長各不相同。 4、非奇異碼 j i s s ? j i W W S s s j i , C W W j i , 5、奇異碼 j i s s ? j i W W S s s j i , C W W j i , 6、同價碼 碼符號集X 中每個碼符號i x 所占的傳輸時間都相同。 7、碼的N 次擴展碼 碼,21q W W W C =，)(21i l i i i i i x x x W S s =? X x k i 則N 次擴展碼)(21N i i i i W W W B B = ),1,(21q i i i N = ),1(N q i = 舉例 （P136） 8、惟一可譯碼（單義可譯

56、碼） 若碼的任意一串有限長的碼符號序列只能被惟一地譯成所對應(yīng)的信源符號序列。 碼的任意有限長N 次擴展碼都是非奇異碼。 4.2 等長碼 若等長碼是非奇異碼，則它的任意有限長N 次擴展碼一定也是非奇異碼。 表4.2 （P137） 若對信源S 進行等長編碼，則必須滿足l r q 。q 信源符號個數(shù)；l 碼長；r 碼元數(shù)。 要使編得的等長碼是惟一可譯碼，則必滿足l N r q 。 r q N l l o g l o g 4.3 漸近等分割性和典型序列 漸近等分割性（AEP ）弱大數(shù)定律的推論。 對于獨立、等同分布的隨機變量n X X X 21，只要n 足夠大時，=n i i X n 1 1是接近其數(shù)

57、學(xué)期望值X E 。 設(shè)離散無記憶信源 ? ? ?=?q q P P s s P s s P S ,)(2211 （11=q i i P ） 它的N 次擴展信源，)(21N N S S S S = ? ?=?)(,),(,),(,)(2211N N q q N P P P P S )(21N i i i i s s s = ),1,1(21q i i i q i N N = =N k i N k i i k k P s P P 1 1 )()( ),1,1(21q i i i q i N N = )(log )(log )(1 1 k k i N k i N k i i s I P P I =-

58、=-= )()()()(1 S NH s I E S H I E k i N k N i = log )(log )()()()(1 21 2 2 2 =-=-=q i q i i i i i i i i p p p p N S H s I E N s I ND I D k k Th4.1 漸近等分割性（AEP ）：若N S S S 21隨機序列中i S ),1(N i =相互統(tǒng)計獨立并且服從同一 概率分布)(s P ，又N i i i i S S S s s s N 21)(21=，則)(log 1 )(log 121N i S S S P N P N -=- 以概率收斂于)(S H ),1

59、,1(21q i i i q i N N =。 證明：因為互相統(tǒng)計獨立的隨機變量的函數(shù)也是相互統(tǒng)計獨立的隨機變量。 i S ),1(N i =是統(tǒng)計獨立并服從同一概率分布)(s P ，所以)(log i S P -),1(N i =也是統(tǒng)計獨立隨機變量，且有有限均值)()(log S H S P E i =-。根據(jù)弱大數(shù)定律，有 =-N i i S P N 1)(l o g 1 以概率收斂于均值)(S H 即 )()(l o g 1 )(l o g 1 2 11 S H S S S P N S P N N N i i -=-= 以概率收斂 N i i i i S S S s s s N 21)

60、(21= ),1,1(21q i i i q i N N = 所以 )()(log 1 )(log 121S H S S S P N P N N i -=- 以概率收斂 即 對于0?，1|)() (|lim =，滿足1)(N G P )(N G P （2）若N i i i i G s s s N =)(21 ，則)( )(2)(2 -+-?，1|)() (| lim =?，存在一個0N ，當(dāng)0N N 時有 -1)(N G P 又根據(jù)契比雪夫不等式，對于0?，有2 ) () (|)()(|N I D N S NH I P i i - 即2) (|)()(| N I D S H N I P i i