信息論電子科大復習資料

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