《信息論》(電子科大)復(fù)習(xí)資料

1、信息論導(dǎo)論參考資料作者 龍非池第一章 概論l 在認(rèn)識(shí)論層次研究信息時(shí)，把只考慮到形式因素的部分稱為語法信息，把只考慮到含義因素的部分稱為語義信息；把只考慮到效用因素的部分稱為語用信息。目前，信息論中主要研究語法信息l 歸納起來，香農(nóng)信息論的研究?jī)?nèi)容包括：1) 信息熵?、信道容量?和信息率失真函數(shù)?2) 無失真信源編碼定理?、信道編碼定理?和保真度準(zhǔn)則下的信源編碼定理?3) 信源編碼、信道編碼理論與方法l 一般認(rèn)為，一般信息論的研究?jī)?nèi)容除香農(nóng)信息論的研究?jī)?nèi)容外，還包括維納的微弱信號(hào)檢測(cè)理論：包括噪聲理論、信號(hào)濾波與預(yù)測(cè)、統(tǒng)計(jì)檢測(cè)與估計(jì)理論、調(diào)制理論等。信息科學(xué)以信息為研究對(duì)象，信息科學(xué)以信息運(yùn)動(dòng)

2、規(guī)律為研究?jī)?nèi)容，信息運(yùn)動(dòng)包括獲取、傳遞、存儲(chǔ)、處理和施用等環(huán)節(jié)。第二章 離散信源及離散熵l 單符號(hào)離散信源的數(shù)學(xué)模型：自信息量：，是無量綱的，一般根據(jù)對(duì)數(shù)的底來定義單位：當(dāng)對(duì)數(shù)底為2時(shí)，自信息量的單位為比特(bit,binary unit)；對(duì)數(shù)底為e時(shí)，其單位為奈特(nat,nature unit)；對(duì)數(shù)底為10時(shí)，其單位為哈特(Hart, Hartley) 自信息量性質(zhì)：I(xi)是隨機(jī)量；I(xi)是非負(fù)值；I(xi)是P(xi)的單調(diào)遞減函數(shù)。l 單符號(hào)離散信源的離散熵：，單位是比特/符號(hào)(bit/symbol)。離散熵的性質(zhì)和定理：H(X)的非負(fù)性；H(X)的上凸性；最大離散熵定理：

3、l 如果除概率分布相同外，直到N維的各維聯(lián)合概率分布也都與時(shí)間起點(diǎn)無關(guān)，即：則稱該多符號(hào)離散信源為N維離散平穩(wěn)信源。l N維離散平穩(wěn)信源的數(shù)學(xué)模型：l 二維離散平穩(wěn)信源的離散熵：H(X2/X1 )稱為條件熵，是條件信息量在聯(lián)合概率上的數(shù)學(xué)期望，H(X1X2)稱為聯(lián)合熵，離散熵H(X1)、 H(X2)稱為無條件熵，H2(X1X2)稱為平均符號(hào)熵且：，l 對(duì)于，當(dāng)N時(shí)，平均符號(hào)熵取極限值，稱之為極限熵，用H表示：l 如果離散平穩(wěn)信源發(fā)出的符號(hào)序列中各符號(hào)相互獨(dú)立，則稱該信源為離散平穩(wěn)無記憶信源。N維離散平穩(wěn)無記憶信源(一維離散平穩(wěn)信源的N次擴(kuò)展信源)的數(shù)學(xué)模型：，其離散熵：信源的平均符號(hào)熵：l 如

4、果離散平穩(wěn)信源發(fā)出的符號(hào)只與前面已經(jīng)發(fā)出的m(N)個(gè)符號(hào)相關(guān)，則稱該信源為m階馬爾科夫信源?？蓪階馬爾科夫信源發(fā)出的符號(hào)序列看成長(zhǎng)度為m+1的一段段符號(hào)序列，m階馬爾科夫信源的數(shù)學(xué)模型：為強(qiáng)調(diào)m階馬爾科夫信源的長(zhǎng)度特征，一般將其極限熵H記為Hm+1，即：馬爾科夫鏈的各態(tài)歷經(jīng)定理：第三章 離散信源無失真編碼l 碼字的每一個(gè)比特?cái)y帶信息的效率即編碼效率：，平均碼長(zhǎng)一般采用不等長(zhǎng)編碼，使平均碼長(zhǎng)接近離散熵，從而在無失真前提下提高編碼效率；編碼的基本原則是大概率符號(hào)元編成短碼，小概率符號(hào)元編成長(zhǎng)碼如果所采用的不等長(zhǎng)編碼使接收端能從碼序列中唯一地分割出對(duì)應(yīng)與每一個(gè)符號(hào)元的碼字，則稱該不等長(zhǎng)編碼為單義可

5、譯碼。單義可譯碼中，如果能在對(duì)應(yīng)與每一個(gè)符號(hào)元的碼字結(jié)束時(shí)立即譯出的稱為即時(shí)碼，如果要等到對(duì)應(yīng)與下一個(gè)符號(hào)元的碼字才能譯出的稱為延時(shí)碼。異前置碼：任何一個(gè)碼字都不是其他碼字的前綴m元長(zhǎng)度為ki , i=1,2, ,n的異前置碼存在的充分必要條件是：，（克拉夫特(Kraft)不等式）l 無失真編碼定理：（香農(nóng)第一定理）如果L維離散平穩(wěn)信源的平均符號(hào)熵為HL(X1X2XL)，對(duì)信源符號(hào)進(jìn)行m元不等長(zhǎng)組編碼，一定存在一種無失真編碼方法，當(dāng)L足夠大時(shí)，使得每個(gè)信源符號(hào)所對(duì)應(yīng)碼字的平均比特?cái)?shù)：無失真編碼定理從理論上闡明了編碼效率：l L時(shí)，則極限熵H是一個(gè)界限，通常也稱為香農(nóng)界對(duì)于L維離散平穩(wěn)無記憶信源

6、，由于其平均符號(hào)熵HL(X1X2XL) =H(X)，故對(duì)信源符號(hào)進(jìn)行m元不等長(zhǎng)組編碼，一定存在一種無失真編碼方法，當(dāng)L足夠大時(shí)，使得每個(gè)信源符號(hào)所對(duì)應(yīng)碼字的平均比特?cái)?shù)：，此時(shí)香農(nóng)界為H(X)。對(duì)離散平穩(wěn)信源進(jìn)行無失真編碼，每個(gè)信源符號(hào)所對(duì)應(yīng)碼字的平均比特?cái)?shù)平穩(wěn)無記憶信源最多， m階馬爾科夫信源次之，一般平穩(wěn)信源最少。l 二進(jìn)制香農(nóng)碼的編碼步驟如下：1) 將符號(hào)元xi按概率進(jìn)行降序排列2) 令p(x0)=0，計(jì)算第j-1個(gè)碼字的累加概率：3) 確定第i個(gè)碼字的碼長(zhǎng)ki，滿足下列不等式：4) 將pa(xj)用二進(jìn)制表示，取小數(shù)點(diǎn)后ki位作為符號(hào)元xi的碼字。l 哈夫曼(Huffman)編碼1) 將

7、符號(hào)元按概率進(jìn)行降序排列2) 為概率最小的符號(hào)元分配一個(gè)碼元1，概率次小的符號(hào)元分配一個(gè)碼元03) 將概率最小的兩個(gè)符號(hào)元合并成一個(gè)新的符號(hào)元，用兩者概率之和作為該新符號(hào)元的概率；4) 重復(fù)以上三個(gè)步驟，直到最后合并出一個(gè)以1為概率的符號(hào)元哈弗曼碼有兩種排列方式，分前置和后置。采用不同排列方法編出的哈夫曼碼，其碼字和碼長(zhǎng)可能完全不相同，但平均碼長(zhǎng)一定是相等的，因此編碼效率不會(huì)因排列方法而改變。但放在前面可以使短碼得到充分利用第四章 離散信道及信道容量l 符號(hào)離散信道的數(shù)學(xué)模型可表示為：l 互信息量在有噪信道的情況下，將信源發(fā)出xi 而信宿接收到y(tǒng)j所包含的信息量用I(yj;xi )來表示并將其

8、稱為xi對(duì)yj的互信息量，則互信息量的定義為：I(yj/xi )稱為條件信息量，表示信道給出的“信息”?；バ畔⒘康男再|(zhì)：I(yj;xi )是隨機(jī)量，I(yj;xi )可為正值也可為負(fù)值，I(yj;xi )具有對(duì)稱性l 單符號(hào)離散信道的平均互信息量：，條件熵H(Y/X)是信道所給出的平均信息量，通常稱為噪聲熵，條件熵H(X/Y)也是信道所給出的平均“信息”量，通常稱為損失熵，也稱為信道疑義度l 平均互信息量的性質(zhì)和定理：1) I(Y;X)的對(duì)稱性2) I(Y;X)的非負(fù)性3) I(Y;X)的極值性： 4) I(Y;X)的凸函數(shù)性當(dāng)信道固定時(shí)，I(Y;X)是信源概率分布P(X)的上凸函數(shù)；當(dāng)信源固

9、定時(shí)，I(Y;X)是信道轉(zhuǎn)移概率分布P(Y/X)的下凸函數(shù)5) 數(shù)據(jù)處理定理： 一個(gè)信息傳遞并進(jìn)行數(shù)據(jù)處理的問題可看成是一個(gè)由串聯(lián)信道進(jìn)行信息傳遞的問題l 單符號(hào)離散信道的信道容量由于平均互信息量反映的是每傳輸一個(gè)符號(hào)在信道中流通的平均信息量，從這個(gè)意義上，可以將其理解為信道的信息傳輸率(不是信息傳輸速率！)，即。定義最大的信息傳輸率為信道容量，即：。定義最大信息傳輸速率為：l 信道容量的計(jì)算步驟 l 均勻信道和對(duì)稱信道的信道容量，則稱該信道為均勻信道均勻信道的信息傳輸率可達(dá)最大，其信道容量為：l 對(duì)稱信道和對(duì)稱信道的信道容量既是行可排列的，又是列可排列的，則稱該矩陣所表示的信道為對(duì)稱信道則稱

10、該信道為對(duì)稱信道如果每一行都是同一集合中諸元素的不同排列，則稱該矩陣為行可排列的；如果每一列都是同一集合中諸元素的不同排列，則稱該矩陣為列可排列的均勻信道的信息傳輸率可達(dá)最大，其信道容量為：l 離散無記憶信道及其信道容量對(duì)應(yīng)于多符號(hào)離散信源和多符號(hào)離散信宿的信道為多符號(hào)離散信道，可表示為：當(dāng)信源和信宿均為平穩(wěn)無記憶時(shí)，信道矩陣中的條件概率：該信道矩陣表示的多符號(hào)離散信道稱為離散無記憶信道(DMC, Discrete Memoryless Channel)?？煞Q其為L(zhǎng)次擴(kuò)展信道如果記一維離散無記憶信道的信道容量為C，則其L次擴(kuò)展信道的信道容量為：第五章 離散信道編碼l 信道編碼定理譯碼規(guī)則的設(shè)計(jì)

11、依據(jù)的是最小錯(cuò)誤概率準(zhǔn)則。為了降低錯(cuò)誤概率，可以考慮重復(fù)發(fā)送，如重復(fù)三次，即將x1編碼為a1=x1x1x1，x2編碼為a2=x2x2x2，稱為3重復(fù)碼香農(nóng)第二定理：對(duì)于離散無記憶信道，如其信道容量為C，只要信息傳輸率RC，一定存在一種編碼，當(dāng)L足夠大時(shí)，使得譯碼錯(cuò)誤概率Pe ，其中為任意給定的小正數(shù)。該定理從理論上證明了譯碼錯(cuò)誤概率任意小的理想糾錯(cuò)編碼的存在性信道編碼定理也指出，信道容量C是一個(gè)界限，如果信息傳輸率超過這個(gè)界限一定會(huì)出錯(cuò)l 漢明距離與線性分組碼線性分組碼通常用于前向糾錯(cuò)，可表示為(n,k)，其中n為碼字長(zhǎng)度，k為信息位長(zhǎng)度，從而校驗(yàn)位長(zhǎng)度為n-k在m(=2k)個(gè)碼字構(gòu)成的碼中，

12、兩個(gè)長(zhǎng)度為n的碼字之間的漢明距離(碼距)是指兩個(gè)碼字對(duì)應(yīng)位置上不同碼元的個(gè)數(shù)；對(duì)于二元碼，碼距可表示為：長(zhǎng)度為n的碼字的漢明重量(碼重)是指碼字中非零碼元的個(gè)數(shù)；對(duì)于二元碼，碼重可表示為：對(duì)于二元碼，兩個(gè)長(zhǎng)度為n的碼字之間的碼距可用碼重表示：線性分組碼(n,k)能檢e個(gè)錯(cuò)誤并能糾t個(gè)錯(cuò)誤的充要條件是：最簡(jiǎn)單的能檢1個(gè)錯(cuò)誤并能糾1個(gè)錯(cuò)誤的線性分組碼(n,k)的將錯(cuò)誤序列E的隨機(jī)結(jié)果ei稱為錯(cuò)誤圖案，當(dāng)eik=1時(shí)，表示第i個(gè)碼字的第k位在傳輸中出現(xiàn)錯(cuò)誤。最簡(jiǎn)單的能檢1個(gè)錯(cuò)誤并能糾1個(gè)錯(cuò)誤的線性分組碼(n,k)的錯(cuò)誤圖案為0001，0010，0100，1000l (7,4)漢明碼設(shè)碼字為：，其中為

13、信息位，長(zhǎng)度為k=4，為校驗(yàn)位，長(zhǎng)度為n-k=3(7,4)漢明碼的編碼由生成矩陣產(chǎn)生：(7,4)漢明碼的最小距離：由線性分組碼(n,k)能檢e個(gè)錯(cuò)誤并能糾t個(gè)錯(cuò)誤的充要條件，(7,4)漢明碼只能檢出并糾正1個(gè)錯(cuò)誤l3重復(fù)碼的最小距離，3重復(fù)碼也只能檢出并糾正1個(gè)錯(cuò)誤，5重復(fù)碼能檢出并糾正2個(gè)錯(cuò)誤第六章 連續(xù)信源與連續(xù)信道l 單變量連續(xù)信源的數(shù)學(xué)模型定義連續(xù)信源的相對(duì)熵：。相對(duì)熵不能反映連續(xù)信源的平均不確定度。定義相對(duì)熵的目的在于在形式上與離散信源熵統(tǒng)一并使熵差具有信息測(cè)度的意義。兩個(gè)連續(xù)隨機(jī)變量的聯(lián)合熵：兩個(gè)連續(xù)隨機(jī)變量的條件熵：l 均勻分布連續(xù)信源的相對(duì)熵：，高斯分布連續(xù)信源的相對(duì)熵：，指數(shù)

14、分布連續(xù)信源的相對(duì)熵：，l 相對(duì)熵的性質(zhì)及最大相對(duì)熵定理1) 相對(duì)熵不具有非負(fù)性2) 相對(duì)熵的可加性：，最大相對(duì)熵定理：連續(xù)信源沒有一般意義下的最大熵，只有限制條件下的最大熵1) 取值范圍受限條件下的最大熵定理隨機(jī)變量取值被限定在一定范圍內(nèi)，則在該有限定義域內(nèi)均勻分布的連續(xù)信源具有最大熵，即：2) 平均功率受限條件下的最大熵定理隨機(jī)變量的平均功率被限定，則均值為零、方差為該平均功率的高斯分布的連續(xù)信源具有最大熵，即：3) 均值受限條件下的最大熵定理非負(fù)隨機(jī)變量的均值被限定，則均值為該限定值的指數(shù)分布的連續(xù)信源具有最大熵，即：l 連續(xù)信道的平均互信息量，平均互信息量的性質(zhì)和定理：平均互信息量具有

15、非負(fù)性，平均互信息量具有對(duì)稱性，平均互信息量具有凸函數(shù)性。數(shù)據(jù)處理定理 信道固定時(shí)，總能找到一種信源概率密度函數(shù)，使信道的信息傳輸率最大，稱該最大值為信道容量，即：l 如果噪聲N是均值為0、方差為2的高斯噪聲，輸入X均值為零、方差為X2的高斯分布，則稱為高斯加性信道，此時(shí)X的平均功率被限定為PX，已知噪聲N的平均功率為PN，可取輸出Y的平均功率：。輸出Y為均值等于零、方差Y2等于PY的高斯分布時(shí)具有最大熵，即高斯加性信道的信道容量：條件是p(x)滿足均值為0，方差為X2的高斯分布，l 香農(nóng)公式當(dāng)信道的頻帶為(0,W)時(shí)，將信道的一次傳輸看成是一次采樣，根據(jù)采樣定理，采樣率為2W可保證不失真從而不失真的一次傳輸所需時(shí)間為1/2W，相應(yīng)的最大信息傳輸速率： 第七章 信息率失真理論l 離散信源的信息率失真函數(shù)總能找到一種信道轉(zhuǎn)移概率分布，使信息傳輸率最小定義非負(fù)函數(shù)d(xi,yj) i=1,2, ,n; j=1,2, ,m為失真度，稱全部nm個(gè)失真度組成的矩陣為失真矩陣：常用的失真矩陣：，當(dāng)=1時(shí)，稱為漢明失真矩陣。稱為平方誤差失真度。平均失真度：保真度準(zhǔn)則：如果給定的允許失