信息論 總復(fù)習(xí)

1、總總 復(fù)復(fù) 習(xí)習(xí)1 1 緒論緒論2 2 信源的信息量信源的信息量3 3 離散信源離散信源4 4 離散信源的無失真編碼離散信源的無失真編碼5 5 離散信道及其編碼定理離散信道及其編碼定理6 6 連續(xù)信道及其容量連續(xù)信道及其容量8 8 信息率失真理論及其應(yīng)用信息率失真理論及其應(yīng)用10 10 線性分組碼線性分組碼編碼器編碼器信宿信宿信道信道消息消息干擾干擾消息消息通信系統(tǒng)模型通信系統(tǒng)模型信源信源信號(hào)信號(hào)解碼器解碼器信號(hào)信號(hào)+干擾干擾噪聲源噪聲源l信息論的研究對(duì)象信息論的研究對(duì)象: :通信系統(tǒng)模型通信系統(tǒng)模型. .信源信源信道信道加密加密信源信源信道信道解密解密通信系統(tǒng)的基本任務(wù)要求通信系統(tǒng)的基本任務(wù)

2、要求可靠可靠: : 要使信源發(fā)出的消息經(jīng)過傳輸后，盡可能準(zhǔn)確地、要使信源發(fā)出的消息經(jīng)過傳輸后，盡可能準(zhǔn)確地、不失真或限定失真地再現(xiàn)在接收端不失真或限定失真地再現(xiàn)在接收端有效有效: : 用盡可能短的時(shí)間和盡可能少的設(shè)備來傳輸最大的用盡可能短的時(shí)間和盡可能少的設(shè)備來傳輸最大的消息消息l單符號(hào)離散信源單符號(hào)離散信源l自信息量自信息量用概率測度定義信息量，設(shè)離散信源用概率測度定義信息量，設(shè)離散信源 X X，其，其概率空間為概率空間為如果知道事件如果知道事件 x xi i 已發(fā)生，則該事件所含有的已發(fā)生，則該事件所含有的自信息定義為自信息定義為)(log)(1log)(iiixpxpxI)(,),(),

3、(,)(2121nnxpxpxpxxxXPX，l聯(lián)合自信息量聯(lián)合自信息量l當(dāng)當(dāng) X X 和和 Y Y 相互獨(dú)立時(shí)，相互獨(dú)立時(shí)，p(xp(xi iy yj j)=p(x)=p(xi i)p(y)p(yj j) )(log)(1log)(jijijiyxpyxpyxI)()()(jijiyIxIyxIl條件自信息量：條件自信息量：已知已知y yj j 的條件下的條件下x xi i 仍然存仍然存在的不確定度。在的不確定度。l自信息量、條件自信息量和聯(lián)合自信息量之自信息量、條件自信息量和聯(lián)合自信息量之間的關(guān)系間的關(guān)系)|(log)|(1log)|(jijijiyxpyxpyxI)|()()|()(1l

4、og)(ijiijijixyIxIxypxpyxIl互信息量：互信息量：y yj j 對(duì)對(duì) x xi i 的互信息量定義為的后的互信息量定義為的后驗(yàn)概率與先驗(yàn)概率比值的對(duì)數(shù)。驗(yàn)概率與先驗(yàn)概率比值的對(duì)數(shù)。)|()();()()|(log);(jiiijijijiyxIxIxyIxpyxpyxIl兩個(gè)不確定度之差是不確定度被消除的部分兩個(gè)不確定度之差是不確定度被消除的部分，即等于自信息量減去條件自信息量。，即等于自信息量減去條件自信息量。 0);(jiyxIl平均信息量平均信息量信源熵：信源熵：自信息的數(shù)學(xué)期望。也稱為自信息的數(shù)學(xué)期望。也稱為信源的信息熵信源的信息熵/ /信源熵信源熵/ /無條件熵

5、無條件熵/ /熵。熵。l信息熵的意義：信息熵的意義：信源的信息熵信源的信息熵 H H 是從是從整個(gè)整個(gè)信源的信源的統(tǒng)計(jì)特性來考慮的。它是從統(tǒng)計(jì)特性來考慮的。它是從平均意義平均意義上來表征信源上來表征信源的的總體特性總體特性的。對(duì)于某特定的信源，其信息熵是唯的。對(duì)于某特定的信源，其信息熵是唯一的。不同的信源因統(tǒng)計(jì)特性不同，其熵也不同。一的。不同的信源因統(tǒng)計(jì)特性不同，其熵也不同。niiiixpxpxpEXH1)(log)()(1log)(l條件熵：條件熵：是在聯(lián)合符號(hào)集合是在聯(lián)合符號(hào)集合 XY XY 上的條件自信息上的條件自信息的數(shù)學(xué)期望。的數(shù)學(xué)期望。nimjijjiijxypyxpxyIEXYH

6、11)|(1log)()|()|(l聯(lián)合熵聯(lián)合熵 H(XY)H(XY)：表示輸入隨機(jī)變量表示輸入隨機(jī)變量 X X，經(jīng)信道，經(jīng)信道傳輸?shù)竭_(dá)信宿，輸出隨機(jī)變量傳輸?shù)竭_(dá)信宿，輸出隨機(jī)變量 Y Y。即收、發(fā)雙。即收、發(fā)雙方通信后，整個(gè)系統(tǒng)仍然存在的不確定度。方通信后，整個(gè)系統(tǒng)仍然存在的不確定度。nimjjijijiyxpyxpyxIEXYH11)(1log)()()(l信道疑義度信道疑義度H(X|Y)H(X|Y)：表示信宿在收到表示信宿在收到 Y Y 后，信后，信源源 X X 仍然存在仍然存在的不確定度。是通過有噪信道傳輸?shù)牟淮_定度。是通過有噪信道傳輸后引起的信息量的損失，故也可稱為損失熵。后引起的信

7、息量的損失，故也可稱為損失熵。l噪聲熵噪聲熵H(Y|X)H(Y|X)：表示在已知表示在已知 X X 的條件下，對(duì)于的條件下，對(duì)于符號(hào)集符號(hào)集 Y Y 尚存在的不確定性，這完全是由于信道尚存在的不確定性，這完全是由于信道中噪聲引起的。中噪聲引起的。唯一確定信道噪聲所需要的平均信唯一確定信道噪聲所需要的平均信息量。息量。l平均互信息量定義：平均互信息量定義：互信息量互信息量 I(xI(xi i;y;yj j) ) 在聯(lián)合概在聯(lián)合概率空間率空間 P(XY) P(XY) 中的統(tǒng)計(jì)平均值。中的統(tǒng)計(jì)平均值。l從一個(gè)事件獲得另一個(gè)事件的平均互信息需要消除從一個(gè)事件獲得另一個(gè)事件的平均互信息需要消除不確定度，

8、一旦消除了不確定度，就獲得了信息。不確定度，一旦消除了不確定度，就獲得了信息。nimjijijijixpyxpyxpyxIEYXI11)()|(log)();();(熵熵H(X)H(X)H(X)=H(X|Y)H(X)=H(X|Y)H(X)=H(X|Y)+I(X;Y)H(X)=H(X|Y)+I(X;Y) X Y X Y條件熵條件熵H(X|Y)H(X|Y)H(X|Y)=H(XY)-H(Y)H(X|Y)=H(XY)-H(Y) =H(X)-I(X;Y) =H(X)-I(X;Y) X Y X Y聯(lián)合熵聯(lián)合熵H(XY)=H(YX)H(XY)=H(YX)H(XY)=H(X)+H(Y|X)H(XY)=H(X)

9、+H(Y|X)=H(X|Y)+H(Y|X)+I(X;Y)=H(X|Y)+H(Y|X)+I(X;Y) X Y X Y平均互信平均互信息息I(X;Y)=I(Y;X)I(X;Y)=I(Y;X) I(X;Y)=H(X)-H(X|Y)I(X;Y)=H(X)-H(X|Y) =H(X)+H(Y)-H(X,Y) =H(X)+H(Y)-H(X,Y) X Y X Y平均互信息和熵的關(guān)系平均互信息和熵的關(guān)系數(shù)據(jù)處理定理（信息不增原理）數(shù)據(jù)處理定理（信息不增原理）當(dāng)消息通過多級(jí)處理器時(shí)當(dāng)消息通過多級(jí)處理器時(shí), ,隨著處理器數(shù)目的增多隨著處理器數(shù)目的增多, ,輸入消息和輸出消息之間的平均互信息量趨于變小。輸入消息和輸出

10、消息之間的平均互信息量趨于變小。信息不增信息不增I(X;Z) I(X;f(Z)=I(X;Y) H(X|Z) H(X|f(Z)=H(X|Y)l最大離散熵定理最大離散熵定理 ( (極值性極值性) ) ：離散無記憶信源輸離散無記憶信源輸出出 n n 個(gè)不同的信息符號(hào)，當(dāng)且僅當(dāng)個(gè)不同的信息符號(hào)，當(dāng)且僅當(dāng)各個(gè)符號(hào)出各個(gè)符號(hào)出現(xiàn)概率相等現(xiàn)概率相等時(shí)時(shí) ( (即即p(xp(xi i)=1/n)=1/n) )，熵最大。，熵最大。Hp(xHp(x1 1),p(x),p(x2 2),),p(x,p(xn n)logn)lognl二進(jìn)制信源的熵函數(shù)二進(jìn)制信源的熵函數(shù) H(p) H(p) 為為)1log()1 (lo

11、g)(pppppHlBSCBSC信道的平均互信息量信道的平均互信息量l 設(shè)二進(jìn)制對(duì)稱信道的輸入概率空間為設(shè)二進(jìn)制對(duì)稱信道的輸入概率空間為ppXPX10)()()()|()();(qHqpqpHXYHYHYXIl連續(xù)信源的熵連續(xù)信源的熵為為RcdxxpxpXH)(log)()(定義的熵在形式上和離散信源相似。連續(xù)信源熵并不是實(shí)定義的熵在形式上和離散信源相似。連續(xù)信源熵并不是實(shí)際信源輸出的信息量際信源輸出的信息量(絕對(duì)熵絕對(duì)熵)； Hc(X) 也稱為相對(duì)熵也稱為相對(duì)熵babaiiniiinnnduupduupupupupupXH)(loglim)(log)(log)(lim)(log)(lim)(

12、lim0連續(xù)信源的連續(xù)信源的信息量為無限大信息量為無限大；Hc(X) 已不能代表信源的平均不確定度，也不能代表連續(xù)信已不能代表信源的平均不確定度，也不能代表連續(xù)信源輸出的信息量。源輸出的信息量。 離散信源的無失真編碼實(shí)質(zhì)上是一種統(tǒng)計(jì)匹配離散信源的無失真編碼實(shí)質(zhì)上是一種統(tǒng)計(jì)匹配編碼。信息論指出信源中的統(tǒng)計(jì)多余度主要決定于編碼。信息論指出信源中的統(tǒng)計(jì)多余度主要決定于以下兩個(gè)主要因素：以下兩個(gè)主要因素： 一是消息一是消息概率分布的非均勻性概率分布的非均勻性，另一個(gè)是，另一個(gè)是消息消息間的相關(guān)性間的相關(guān)性。對(duì)無記憶信源主要決定于概率分布的。對(duì)無記憶信源主要決定于概率分布的非均勻性，但是，對(duì)于有記憶信源

13、，兩者都起作用非均勻性，但是，對(duì)于有記憶信源，兩者都起作用，且后者相關(guān)性更加重要。，且后者相關(guān)性更加重要。信源編碼信源編碼Def. Def. 對(duì)于給定的信源和編碼速率對(duì)于給定的信源和編碼速率R R及及任意任意00，若存在，若存在L L0 0、( ( ) )、D(D( ) )，使當(dāng)碼長，使當(dāng)碼長LLLL0 0時(shí)，時(shí)，P Pe e H(U)RH(U)，則，則R R是是可達(dá)可達(dá)的；若的；若RH(U)R00，若有一種編，若有一種編碼速率為碼速率為R R 的碼，在的碼，在N N足夠大時(shí)，能使足夠大時(shí)，能使p pe e e e，就，就稱稱R R 是是可達(dá)可達(dá)的。的。 定理定理( (ShannonShannon信道編碼定理信道編碼定理) )，給定容量為，給定容量為C C的離散的離散無記憶信道無記憶信道XX，p(x|y)p(x|y)，YY，若編碼速率，若編碼速率RCRH(U)RH(U) ( (信源熵信源熵) )時(shí)，最優(yōu)的信源編、譯碼存在；反時(shí)，最優(yōu)的信源編、譯碼存在；反之，當(dāng)之，當(dāng)RH(U)RR(D)RR(D)（信息（信息率失真函數(shù)）時(shí)，最優(yōu)的信源編、譯碼存在；反之，率失真函數(shù)）時(shí)，最優(yōu)的信源編、譯碼存在；反之