信息論基礎(chǔ)A復(fù)習(xí)資料作者郝仁第一章概論在認(rèn)識(shí)論層次研究信息時(shí)，把只考慮到形式因素的部分稱為語(yǔ)法信息，把只考慮到含義因素的部分稱為語(yǔ)義信息；把只考慮到效用因素的部分稱為語(yǔ)用信息。目前，信息論中主要研究語(yǔ)法信息歸納起來(lái)，香農(nóng)信息論的研究?jī)?nèi)容包括：信息熵、信道容量和信息率失真函數(shù)無(wú)失真信源編碼定理、信道編碼定理和保真度準(zhǔn)則下的信源編碼定理信源編碼、信道編碼理論與方法一般認(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)規(guī)律為研究?jī)?nèi)容，信息運(yùn)動(dòng)包括獲取、傳遞、存儲(chǔ)、處理和施用等環(huán)節(jié)。第二章離散信源及離散熵單符號(hào)離散信源的數(shù)學(xué)模型：自信息量：，是無(wú)量綱的，一般根據(jù)對(duì)數(shù)的底來(lái)定義單位：當(dāng)對(duì)數(shù)底為2時(shí)，自信息量的單位為比特(bit,binaryunit)；對(duì)數(shù)底為e時(shí)，其單位為奈特(nat,natureunit)；對(duì)數(shù)底為10時(shí)，其單位為哈特(Hart,Hartley)自信息量性質(zhì)：I(xi)是隨機(jī)量；I(xi)是非負(fù)值；I(xi)是P(xi)的單調(diào)遞減函數(shù)。單符號(hào)離散信源的離散熵：，單位是比特/符號(hào)(bit/symbol)。離散熵的性質(zhì)和定理：H(X)的非負(fù)性；H(X)的上凸性；最大離散熵定理：如果除概率分布相同外，直到N維的各維聯(lián)合概率分布也都與時(shí)間起點(diǎn)無(wú)關(guān)，即：則稱該多符號(hào)離散信源為N維離散平穩(wěn)信源。N維離散平穩(wěn)信源的數(shù)學(xué)模型：二維離散平穩(wěn)信源的離散熵：H(X2/X1)稱為條件熵，是條件信息量在聯(lián)合概率上的數(shù)學(xué)期望，H(X1X2)稱為聯(lián)合熵，離散熵H(X1)、H(X2)稱為無(wú)條件熵，H2(X1X2)稱為平均符號(hào)熵且：，對(duì)于，，當(dāng)N→∞時(shí)，平均符號(hào)熵取極限值，稱之為極限熵，用H∞表示：如果離散平穩(wěn)信源發(fā)出的符號(hào)序列中各符號(hào)相互獨(dú)立，則稱該信源為離散平穩(wěn)無(wú)記憶信源。N維離散平穩(wěn)無(wú)記憶信源(一維離散平穩(wěn)信源的N次擴(kuò)展信源)的數(shù)學(xué)模型：，無(wú)失真編碼定理從理論上闡明了編碼效率：L→∞時(shí)，則極限熵H∞是一個(gè)界限，通常也稱為香農(nóng)界對(duì)于L維離散平穩(wěn)無(wú)記憶信源，由于其平均符號(hào)熵HL(X1X2…XL)=H(X)，故對(duì)信源符號(hào)進(jìn)行m元不等長(zhǎng)組編碼，一定存在一種無(wú)失真編碼方法，當(dāng)L足夠大時(shí)，使得每個(gè)信源符號(hào)所對(duì)應(yīng)碼字的平均比特?cái)?shù)：，此時(shí)香農(nóng)界為H(X)。對(duì)離散平穩(wěn)信源進(jìn)行無(wú)失真編碼，每個(gè)信源符號(hào)所對(duì)應(yīng)碼字的平均比特?cái)?shù)平穩(wěn)無(wú)記憶信源最多，m階馬爾科夫信源次之，一般平穩(wěn)信源最少。二進(jìn)制香農(nóng)碼的編碼步驟如下：將符號(hào)元xi按概率進(jìn)行降序排列令p(x0)=0，計(jì)算第j-1個(gè)碼字的累加概率：確定第i個(gè)碼字的碼長(zhǎng)ki，滿足下列不等式：將pa(xj)用二進(jìn)制表示，取小數(shù)點(diǎn)后ki位作為符號(hào)元xi的碼字。哈夫曼(Huffman)編碼將符號(hào)元按概率進(jìn)行降序排列為概率最小的符號(hào)元分配一個(gè)碼元1，概率次小的符號(hào)元分配一個(gè)碼元0將概率最小的兩個(gè)符號(hào)元合并成一個(gè)新的符號(hào)元，用兩者概率之和作為該新符號(hào)元的概率；重復(fù)以上三個(gè)步驟，直到最后合并出一個(gè)以1為概率的符號(hào)元哈弗曼碼有兩種排列方式，分前置和后置。采用不同排列方法編出的哈夫曼碼，其碼字和碼長(zhǎng)可能完全不相同，但平均碼長(zhǎng)一定是相等的，因此編碼效率不會(huì)因排列方法而改變。但放在前面可以使短碼得到充分利用第四章離散信道及信道容量符號(hào)離散信道的數(shù)學(xué)模型可表示為：互信息量在有噪信道的情況下，將信源發(fā)出xi而信宿接收到y(tǒng)j所包含的信息量用I(yj;xi)來(lái)表示并將其稱為xi對(duì)yj的互信息量，則互信息量的定義為：I(yj/xi)稱為條件信息量，表示信道給出的“信息”。互信息量的性質(zhì)：I(yj;xi)是隨機(jī)量，I(yj;xi)可為正值也可為負(fù)值，I(yj;xi)具有對(duì)稱性單符號(hào)離散信道的平均互信息量：，條件熵H(Y/X)是信道所給出的平均信息量，通常稱為噪聲熵，條件熵H(X/Y)也是信道所給出的平均“信息”量，通常稱為損失熵，也稱為信道疑義度平均互信息量的性質(zhì)和定理：I(Y;X)的對(duì)稱性I(Y;X)的非負(fù)性I(Y;X)的極值性：I(Y;X)的凸函數(shù)性當(dāng)信道固定時(shí)，I(Y;X)是信源概率分布P(X)的上凸函數(shù)；當(dāng)信源固定時(shí)，I(Y;X)是信道轉(zhuǎn)移概率分布P(Y/X)的下凸函數(shù)數(shù)據(jù)處理定理：一個(gè)信息傳遞并進(jìn)行數(shù)據(jù)處理的問(wèn)題可看成是一個(gè)由串聯(lián)信道進(jìn)行信息傳遞的問(wèn)題單符號(hào)離散信道的信道容量由于平均互信息量反映的是每傳輸一個(gè)符號(hào)在信道中流通的平均信息量，從這個(gè)意義上，可以將其理解為信道的信息傳輸率(不是信息傳輸速率！)，即。定義最大的信息傳輸率為信道容量，即：。定義最大信息傳輸速率為：信道容量的計(jì)算步驟均勻信道和對(duì)稱信道的信道容量，，則稱該信道為均勻信道均勻信道的信息傳輸率可達(dá)最大，其信道容量為：對(duì)稱信道和對(duì)稱信道的信道容量既是行可排列的，又是列可排列的，則稱該矩陣所表示的信道為對(duì)稱信道則稱該信道為對(duì)稱信道如果每一行都是同一集合中諸元素的不同排列，則稱該矩陣為行可排列的；如果每一列都是同一集合中諸元素的不同排列，則稱該矩陣為列可排列的均勻信道的信息傳輸率可達(dá)最大，其信道容量為：離散無(wú)記憶信道及其信道容量對(duì)應(yīng)于多符號(hào)離散信源和多符號(hào)離散信宿的信道為多符號(hào)離散信道，可表示為：當(dāng)信源和信宿均為平穩(wěn)無(wú)記憶時(shí)，信道矩陣中的條件概率：該信道矩陣表示的多符號(hào)離散信道稱為離散無(wú)記憶信道(DMC,DiscreteMemorylessChannel)。可稱其為L(zhǎng)次擴(kuò)展信道如果記一維離散無(wú)記憶信道的信道容量為C，則其L次擴(kuò)展信道的信道容量為：第五章離散信道編碼信道編碼定理譯碼規(guī)則的設(shè)計(jì)依據(jù)的是最小錯(cuò)誤概率準(zhǔn)則。為了降低錯(cuò)誤概率，可以考慮重復(fù)發(fā)送，如重復(fù)三次，即將x1編碼為a1=x1x1x1，x2編碼為a2=x2x2x2，稱為3重復(fù)碼香農(nóng)第二定理：對(duì)于離散無(wú)記憶信道，如其信道容量為C，只要信息傳輸率R<C，一定存在一種編碼，當(dāng)L足夠大時(shí)，使得譯碼錯(cuò)誤概率Pe<ε，其中ε為任意給定的小正數(shù)。該定理從理論上證明了譯碼錯(cuò)誤概率任意小的理想糾錯(cuò)編碼的存在性信道編碼定理也指出，信道容量C是一個(gè)界限，如果信息傳輸率超過(guò)這個(gè)界限一定會(huì)出錯(cuò)漢明距離與線性分組碼線性分組碼通常用于前向糾錯(cuò)，可表示為(n,k)，其中n為碼字長(zhǎng)度，k為信息位長(zhǎng)度，從而校驗(yàn)位長(zhǎng)度為n-k在m(=2k)個(gè)碼字構(gòu)成的碼中，兩個(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ò)誤圖案為00…01，00…10，…，01…00，10…00(7,4)漢明碼設(shè)碼字為：，其中為信息位，長(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ò)誤3重復(fù)碼的最小距離，3重復(fù)碼也只能檢出并糾正1個(gè)錯(cuò)誤，5重復(fù)碼能檢出并糾正2個(gè)錯(cuò)誤高萊碼是二進(jìn)制（23，12）線性碼，其最小距離dmin＝7，糾錯(cuò)能力t=3。是完備碼，因?yàn)闈M足等式223-12=2048=在(23,12)碼上添加一位奇偶位即得二進(jìn)制線性（24，12）擴(kuò)展高萊碼，其最小距離dmin＝8。第六章連續(xù)信源與連續(xù)信道單變量連續(xù)信源的數(shù)學(xué)模型定義連續(xù)信源的相對(duì)熵：。相對(duì)熵不能反映連續(xù)信源的平均不確定度。定義相對(duì)熵的目的在于在形式上與離散信源熵統(tǒng)一并使熵差具有信息測(cè)度的意義。兩個(gè)連續(xù)隨機(jī)變量的聯(lián)合熵：兩個(gè)連續(xù)隨機(jī)變量的條件熵：均勻分布連續(xù)信源的相對(duì)熵：，高斯分布連續(xù)信源的相對(duì)熵：，指數(shù)分布連續(xù)信源的相對(duì)熵：，相對(duì)熵的性質(zhì)及最大相對(duì)熵定理相對(duì)熵不具有非負(fù)性相對(duì)熵的可加性：，最大相對(duì)熵定理：連續(xù)信源沒(méi)有一般意義下的最大熵，只有限制條件下的最大熵取值范圍受限條件下的最大熵定理隨機(jī)變量取值被限定在一定范圍內(nèi)，則在該有限定義域內(nèi)均勻分布的連續(xù)信源具有最大熵，即：平均功率受限條件下的最大熵定理隨機(jī)變量的平均功率被限定，則均值為零、方差為該平均功率的高斯分布的連續(xù)信源具有最大熵，即：均值受限條件下的最大熵定理非負(fù)隨機(jī)變量的均值被限定，則均值為該限定值的指數(shù)分布的連續(xù)信源具有最大熵，即：連續(xù)信道的平均互信息量，平均互信息量的性質(zhì)和定理：平均互信息量具有非負(fù)性，平均互信息量具有對(duì)稱性，平均互信息量具有凸函數(shù)性。數(shù)據(jù)處理定理信道固定時(shí)，總能找到一種信源概率密度函數(shù)，使信道的信息傳輸率最大，稱該最大值為信道容量，即：如果噪聲N是均值為0、方差為σ2的高斯噪聲，輸入X均值為零、方差為σX2的高斯分布，則稱為高斯加性信道，此時(shí)X的平均功率被限定為PX，已知噪聲N的平均功率為PN，可取輸出Y的平均功率：。輸出Y為均值等于零、方差σY2等于PY的高斯分布時(shí)具有最大熵，即高斯加性信道的信道容量：條件是p(x)滿足均值為0，方差為σX2的高斯分布，香農(nóng)公式當(dāng)信道的頻帶為(0,W)時(shí)，將信道的一次傳輸看成是一次采樣，根據(jù)采樣定理，采樣率為2W可保證不失真從而不失真的一次傳輸所需時(shí)間為1/2W，相應(yīng)的最大信息傳輸速率：第七章信息率失真理論離散信源的信息率失真函數(shù)總能找到一種信道轉(zhuǎn)移概率分布，使信息傳輸率最小定義非負(fù)函數(shù)d(xi,yj)i=1,2,…,n;j=1,2,…,m為失真度，稱全部n×m個(gè)失真度組成的矩陣為失真矩陣：常用的失真矩陣：，當(dāng)α=1時(shí)，稱為漢明失真矩陣。稱為平方誤差失真度。平均失真度：保真度準(zhǔn)則：如果給定的允許失真為D，則稱為保真度準(zhǔn)則。定義保真度準(zhǔn)則下的最小信息傳輸率為信息率失真函數(shù)：信息率失真函數(shù)的性質(zhì)和定義域：R(D)具有非負(fù)性，R(D)是D的下凸函數(shù)，R(D)是D單調(diào)遞減連續(xù)函數(shù)信息率失真函數(shù)的定義域：，特別地，當(dāng)D=Dmin=0，即不允許任何失真時(shí)R(D)=H(X)信息率失真函數(shù)的參量表達(dá)式信道轉(zhuǎn)移概率分布的n個(gè)約束條件是，。平均失真度的約束條件是：。信息率失真函數(shù)的計(jì)算步驟為：其中，且S<0及等概率信源的信息率失真函數(shù)當(dāng)p=0.5，即二元等概率信源時(shí)的信息率失真函數(shù)：n元等概率信源，其信息率失真函數(shù)