信息論基礎第24次課-總復習

信息論基礎

——總復習第2章信源熵自信息量：

I(ai)=-logp(ai)信源熵：信源的平均信息量條件熵：損失熵噪聲熵聯(lián)合熵：平均互信息：第2章信源熵最大離散熵定理：若信源中包含n個不同離散消息，則當信源等概率時信源熵H(X)取得最大值log2n平均互信息I(X;Y)是輸入信源概率分布的上凸函數(shù)是信道轉(zhuǎn)移概率分布

的下凸函數(shù)。第2章信源熵多符號離散平穩(wěn)無記憶信源亦稱為單符號離散平穩(wěn)無記憶信源的擴展信源。N維離散平穩(wěn)信源平均符號熵：第2章信源熵馬爾可夫信源：m階馬爾可夫信源：第2章信源熵各態(tài)歷經(jīng)定理由狀態(tài)轉(zhuǎn)移圖可求狀態(tài)極限概率定長編碼定理定長編碼定理：一個熵為H(X)的離散無記憶信源X1X2…Xl…XL

，若對信源長為L的符號序列進行定長編碼，設碼字是從m個字母的碼符號集合中，選取K個碼元組成Y1Y2…Yk…YK

。對于任意ε>0，δ>0只要滿足則當L足夠大時，必可使譯碼差錯小于δ，即譯碼錯誤概率能為任意小。反之，若則譯碼差錯一定是有限值，而當L足夠大時，譯碼幾乎肯定出錯（譯碼錯誤概率近似等于1）。

對離散無記憶信源，符號熵為H(X)，對信源進行m元變長編碼，一定存在無失真的信源編碼方法，滿足：其碼字平均長度K(2.4.5)(2.4.6)變長編碼定理其碼字平均信息率R滿足：本章考點1.各種熵的計算。如：P69.2.11;2.一階馬爾可夫信源的狀態(tài)極限概率及極限熵。如：P69.2.16,2.173.各種熵的性質(zhì)：信源熵：非負性、最大離散熵定理、上凸性、確定性。平均互信息：非負性、極值性、凸函數(shù)性、數(shù)據(jù)處理定理、各種熵之間的關系（和差關系、大小關系）連續(xù)信源熵：可為負、平均互信息非負。4.P68.2.8、2.14.5.離散無失真信源編碼定理。第3章信道容量當信道特性p(bj/ai)固定后，I(X;Y)隨信源概率分布p(ai)的變化而變化。調(diào)整p(ai)，在接收端就能獲得不同的信息量。由平均互信息的性質(zhì)已知，I(X;Y)是p(ai)的上凸函數(shù)，因此總能找到一種概率分布p(ai)（即某一種信源），使信道所能傳送的信息率為最大。信道容量C：在信道中最大的信息傳輸速率，單位是比特/信道符號。具有擴展功能的有噪無損信道具有歸并性能的有損無噪信道第3章信道容量如果一個信道矩陣具有可排列性，則它所表示的信道稱為對稱信道若信道矩陣P的行是可排列的，但列不可排列，如果把列分成若干個不相交的子集，且由n行和各子集的諸列構(gòu)成的各個子矩陣都是可排列的，則稱相應的信道為準對稱信道。第3章信道容量例：信道輸入符號集X={x1,x2}，輸出符號集Y={y1,y2,y3,y4}，給定信道轉(zhuǎn)移概率矩陣，

求該信道的信道容量C。解：這是一個準對稱信道，當X等概分布，即p(x1)=p(x2)=1/2時，達到信道容量而此時，信宿端概率為連續(xù)信道的信道容量C：信源X等于某一概率密度函數(shù)p0(x)時，信道平均互信息的最大值，即對于高斯加性信道第3章信道容量信噪功率比香農(nóng)公式設信道的頻帶限于(0,W)；根據(jù)采樣定理，如果每秒傳送2W個采樣點，在接收端可無失真地恢復出原始信號；香農(nóng)公式：把信道的一次傳輸看成是一次采樣，由于信道每秒傳輸2W個樣點，所以單位時間的信道容量為(bit/s)信道編碼定理信道編碼定理：若一離散平穩(wěn)無記憶信道，其容量為C，輸入序列長度為L，只要待傳送的信息率R<C，總能找到一種編碼。當L足夠長時，譯碼差錯概率為任意正數(shù)，反之，當R>C,任何編碼的必大于0，當本章考點1.幾種特殊信道的信道容量。2.準對稱離散信道的信道容量。P99.3.7(4)3.高斯加性信道的信道容量，香農(nóng)公式。4.信道編碼定理。第4章信息率失真函數(shù)信道的傳遞概率矩陣失真矩陣第4章信息率失真函數(shù)漢明失真：平均失真度（2）信息率失真函數(shù)R(D)

在信源給定以后，總希望在允許一定失真的情況下，傳送信源所必須的信息率越小越好。從接收端來看，就是在滿足保真度準則的條件下，尋找再現(xiàn)信源消息必須的最低平均信息量，即平均互信息的最小值。當p(ai)一定時，互信息I是關于p(bj/ai)的下凸函數(shù)，存在極小值。因而在上述允許信道PD中，可以尋找一種信道，使給定的信源經(jīng)過此信道傳輸后，互信息I(X；Y)達到最小。該最小的互信息就稱為信息率失真函數(shù)R(D)，即

率失真函數(shù)的定義域信源最小平均失真度Dmin：對于每一個ai，找出一個bj與之對應，使d(ai,bj)最小，這相當于在失真矩陣的每一行找出一個最小的d(ai,bj)

。只有當失真矩陣的每一行至少有一個0元素時，信源的平均失真度才能達到下限值0。計算Dmax的值令試驗信道特性p(bj/ai)=p(bj)(i=1,2,…,n)這時X和Y相互獨立，等效于通信中斷，因此I(X;Y)=0，即R(D)=0。滿足上式的試驗信道有許多，相應地可求出許多平均失真值，這類平均失真值的下界，就是Dmax。這里令當R(D)等于0時，對應的平均失真最大，也就是函數(shù)R(D)定義域的上界值Dmax。當D>Dmax時，從數(shù)學意義上講，因為R(D)是非負函數(shù)，所以它仍只能等于0。率失真函數(shù)的性質(zhì)連續(xù)性下凸性非負性單調(diào)遞減本章考點1.信息率失真函數(shù)的含義。2.信息率失真函數(shù)的定義域。對應到最大失真度和最小失真度的信道矩陣。P129.4.1、4.2、4.103.信息率失真函數(shù)的性質(zhì)：下凸性、連續(xù)性、非負性、單調(diào)遞減。4.保真度準則下的信源編碼定理。第5章信源編碼異前置碼的充要條件：Craft不等式在Huffman編碼過程中，對縮減信源符號按概率由大到小的順序重新排列時，應使合并后的新符號盡可能排在靠前的位置，這樣可使合并后的新符號重復編碼次數(shù)減少，使碼方差最小。輸入數(shù)據(jù)流：編碼過程：114A1225B2336B2447A4568A7693(最后字符C)BBABABACLZW算法舉例A律特性式中：x為歸一化信號值，當x≥0時函數(shù)取正，否則取負，一般取A=87.6。為實現(xiàn)方便，大多采用13折線來逼近A律特性。非均勻量化1f(x)7/86/85/84/83/82/81/8011/21/41/8xx劃分為8個不均勻的段落：其中第8段占量化范圍的1/2，除第1段外，其余各段的寬度均按1/2倍率減小，即第7段占1/4，第6段占1/8，…，第2段占1/128；第1段也占1/128。0~1量化范圍的13折線A律特性：這樣，0~1量化范圍內(nèi)共劃分出了8*16個不均勻的量化間隔；如果將最小的量化間隔記為Δ，則Δ=1/(128*16)，相應最大的量化間隔為64Δ=1/32。13折線A律非均勻量化編碼也采用定長折疊二進制碼，并將碼長確定為8位；其8位碼元安排如下：最高位C7為極性碼，用以表示信號極性，其準則與均勻量化相同；以下三位C6C5C4為段落碼，用以表示|x|落在正方向的第幾個段落；最后四位C3C2C1

C0為段內(nèi)碼，用以表示|x|在段內(nèi)落在第幾個量化間隔。

每段再均勻地分為16份，每一份作為一個量化間隔。

采用13折線A律非均勻量化編碼，設最小量化間隔為Δ，已知某采樣時刻的信號值為x=635Δ，試求其非均勻量化編碼c，并求量化噪聲e

。解：①635Δ>0，故極性碼為1。②因為512Δ≤635Δ≤1024，所以635Δ在第7個段落，段落碼為110；③由于(1024-512)/16=32，所以該段落內(nèi)每個量化間隔為32Δ，635Δ-512Δ=123Δ最接近32Δ的4倍，所以段內(nèi)碼為0100。故13折線A律非均勻量化編碼為c=11100100。

量化噪聲為e=|123Δ-128Δ|=5Δ一、增量調(diào)制

增量調(diào)制是預測編碼中最簡單的一種，增量調(diào)制原理如下，其中(a)為發(fā)送端，(b)為接收端。1比特量化+-

編碼++

譯碼(a)(b)【例5.3.1】已知某歸一化信號序列，設初始量化dq0=0

，量化增量Δ=0.125，求其增量調(diào)制編碼和量化值。

的編碼；

的量化值。差分脈沖編碼調(diào)制原理如下，+預測+

譯碼(a)(b)量化+++-

編碼預測二、差分脈沖編碼調(diào)制

其中(a)為發(fā)送端，(b)為接收端。【例5.3.2】已知某歸一化信號序列x1,x2,x3,x4=0.05,0.15,0.23,0.2，設初始值dq0=0，，采用碼長為4的均勻量化，量化間隔Δ=0.03125，求其差分脈沖編碼調(diào)制的編碼和量化信號值。DPCM的編碼

DPCM的量化信號值無損編碼香農(nóng)編碼、Huffman編碼、費諾編碼、算術編碼、字典編碼、L-D編碼、行程編碼……有損編碼均勻量化、非均勻量化、矢量量化、增量調(diào)制、差分脈沖編碼調(diào)制、變換編碼……本章考點1.異前置碼存在的充要條件：克拉夫特不等式。2.LZW編碼。見課件3.13折線A律特性非均勻編碼。P168.5.124.增量調(diào)制、差分脈沖編碼調(diào)制。見課件5.哪些是無損編碼、有損編碼。第6章信道編碼檢糾錯能力和最小碼距的關系若要能檢測l個隨機錯誤，則要求dmin≥l+1若要糾正t個隨機錯誤，則要求dmin≥2t+1若要糾正t個，同時檢測l(l>t)個隨機錯誤，則要求dmin≥l+t+1。此處“同時”是指能檢測t+l個錯誤，其中t個錯誤可以糾正。(n,k)線性分組碼：c=mG線性分組碼有如下性質(zhì)：（1）零向量θ=(0,0,…,0)一定是一個碼字；（2）任意兩碼字的和仍是一個碼字；（3）任意碼字c是生成矩陣

G的行向量g0,g1,…,gk-1的線性組合；（4）線性分組碼的最小距離等于最小非零碼字重量。定理

線性分組碼的最小碼距為d，當且僅當其一致校驗矩陣H中任意d-1列線性無關，某d列線性相關。線性分組碼系統(tǒng)碼：生成矩陣G具有如下形式G=Gs=[Ik

Qk×r]即消息比特在碼字中的位置和取值不變在碼字集合不變的情況下，任何一個線性分組碼都可以一對一的去對應一個系統(tǒng)碼。對于系統(tǒng)碼，易求相應的一致校驗矩陣注意，G與Hs仍然滿足線性分組碼的譯碼設一致校驗矩陣為H，對正確的碼字c，應有cHT=0，若接收到的碼字有錯，即r=c+e，則伴隨式s=rHT=(c+e)HT=eHT。事先對最有可能出現(xiàn)的差錯圖案e，求s=eHT，建立e和s的對應關系表，譯碼時對接收到的碼字r，求s=rHT，按es關系表查出對應的錯誤，糾錯計算得c=r+e。如：es關系表對某接收序列r=(1100100)

計算對應的e為（0001000）

糾錯譯碼輸出為循環(huán)碼：一個線性分組碼的任意一個碼字c(n元組)都是另外一個碼字c’的循環(huán)移位.定理1：

(n,k)循環(huán)碼C(x