信息論基礎復習提綱

第一章緒論、什么是信息？香農(nóng)對于信息是如何定義的。答：信息是事物運動狀態(tài)或存在方式的不確定性的描述Informationisameasureofone'sfreedomofchoicewhenoneselectsamessage）。2、簡述通信系統(tǒng)模型的組成及各部分的含義。答：（1）、信源：信源是產(chǎn)生消息的源。信源產(chǎn)生信息的速率---熵率。（2）、編碼器：編碼器是將消

息變成適合于信道傳送的信號的設

備。包括信源編碼器（提高傳輸效

率）、信道編碼器（提高傳輸可靠性）、調(diào)制器。3）、信道：信道是信息傳輸和存儲的媒介。（4） 、譯碼器：譯碼是編碼的逆變換，分為信道譯碼和信源譯碼。（5） 、信宿：信宿是消息的接收者（人或機器）。、簡述香農(nóng)信息論的核心及其特點。答：（1）、香農(nóng)信息論的核心：在通信系統(tǒng)中采用適當?shù)木幋a后能夠實現(xiàn)高效率和高可靠性的信息傳輸，并得出了信源編碼定理和信道編碼定理。（）、特點：①、以概率論、隨機過程為基本研究工具。、研究的是通信系統(tǒng)的整個過程，而不是單個環(huán)節(jié)，并以編、譯碼器為重點。、關心的是最優(yōu)系統(tǒng)的性能和怎樣達到這個性能（并不具體設計系統(tǒng)）。1自信息和互信息i自信息（量）：1自信息和互信息i自信息（量）：（1）、定義：一個事件（消息）本身所包含的信息量，它是由事件的不確定性決定的。某個消息叫出現(xiàn)的不確定性的大小定義為自信息，用這個消息出現(xiàn)的概率的對數(shù)的負I€xi)?-logp(X)?log€x)值來表示：p€x1),pp€x1),p€x2)時I(x1)>I(x2)概率越小，事件發(fā)生的不確定性越大，事件發(fā)生以后所包含的自信息量越大。②、極限情況下，當p(x.)?0時IG/t…；p(x.)=1時，I(x.)t0③、兩個相對獨立的不同的消息所提供的信息量應等于它們分別提供的信息量之和，即自信息論滿足可加性。p(X1x2)?p(xi)p(x2I(X1x2)?I(X])+I(x2)

息論滿足可加性。(3)、例2.：1、英文字母中“a”出現(xiàn)的概率為 ，4”出現(xiàn)的概率為 ，分別計算他們的自信息量。、假定前后字母出現(xiàn)是互相獨立的，計算“ac”的自信息。、假定前后字母出現(xiàn)不是互相獨立的，當“a”出現(xiàn)以后，“c”出現(xiàn)的概率為，計算“a”出現(xiàn)以后，“c”出現(xiàn)的自信息量。2互信息：一個事件y7-所給出關于另一個事件x的信息定義為互信息，用1€xi;y)表示：I(x.;y.)=I(x.)-1(x.Iy.)=logij i ij平均自信息、定義：隨機變量的每一個可能取值的自信息1(xi)H(X)二E[I(x)]二一工p(x)logp(x)..2.的統(tǒng)計平均值定義為隨機變量的平均自信息量。2、 熵函數(shù)的性質：均對稱性：H的統(tǒng)計平均值定義為隨機變量的平均自信息量。2、 熵函數(shù)的性質：均對稱性：H(p,p,，，，p)二H(p,p,，，，p)=???=H(p,p,，，，p)12q21qq1 q-1確定性非負性擴展性連續(xù)性遞推性極值性上凸性i3、 聯(lián)合熵：聯(lián)合自信息的數(shù)學期望。它是二維隨機變量的不確定性的度量。4條件熵：由于不同的X均.1)、2)3)4)5)6)7)8)、H(1,0)3H(iqo,0)=，，2=H(10，，，0)=0H(p)二H(p,p，…p)>01 2qlimH(p,p,…p-￡,￡)二H(p,p,…p)urnH*》,'p:pq-￡,p+￡『二H(p,p:…p)—0 12 q-1 q 12qH(p,p,…p,q,q…q)-H(p,p,…p)+PH("】,,…化)nnnn12 n-1121m1 112nnpppnnnnH(p,p,…p)<pH(_,_,…_)=lognf[<x+Z)x]><f(x)+U-<)f2(x)1212H(XY)=工區(qū)p(xy)I(xy)=-Y區(qū)p(xy)logp(xy).j.j .j 2 .j.=1j=1 .=1j=1H(Y/x)是變化的，對H(Y/x)的所有可能值進行統(tǒng)計平均，..就得出給定X時，Y的條件熵H(Y/X)=—工工p(xy)logp(y/x)H(X/Y)=—工工p(xy)logp(x/y).j2 j. .j2 .j.j .j、各類熵之間的關系：()、聯(lián)合熵與信息熵、條件熵之間的關系:H(XY)=H(X)+H(Y/X)。推廣:H(x1X2...XN)=H(x1)+H(x2/X1)+..+H(XN/X1X2,,XN-1)當二維隨機變量 相互獨立時，聯(lián)合熵等于各自熵之和。H(XY)=H(X)+H(Y)。(2)、條件熵與信息熵的關系：H(X/Y)<H(X);H(Y/X)=H(Y)。()、聯(lián)合熵與信息熵的關系：H(XY)<H(X)+H(Y)當、相互獨立時等號成立。推廣到個隨機變量：H&1X2，，，XN)<H&1)+H&2)+，，，+HR)。

、例：隨機變量，的聯(lián)合概率分布如表 所示，求聯(lián)合熵H€xy）和條件熵H€y1X）表 的聯(lián)合概率分布p表 的聯(lián)合概率分布p（xy）p(xi)p(yj)表 條件概率分布P（Y1x）\3平均互信息、定義：從整體上表示從一個隨機變量所給出關于另一個隨機變量的信息量，定義互信息I€xi；y）在的聯(lián)合空間中的統(tǒng)計平均值為隨機變量和間的平均互信息。I(XI(X；Y)=??p(xi；y)I(X：；y.)=??p(xi；y.)logi=1j=1 i=1j=1—??〃6.；y}og- 1 、=H(X)—H(XIY)zj帀i.i=1j=1條件熵H€x1Y）表示給定隨機變量Y后，對隨機變量X仍然存在的不確定度。所以Y關于X的平均互；當4）、；當4）、FH(Y)，H(XY)補 -+<— —>*-+° 4 ? ?信息是收到Y前后關于X的不確定度減少的量，也就是從Y獲得的關于X的平均信息量。2平均互信息的性質：（）、非負性：I&；y）n0；（）、互易性（對稱性）：1€x；Y）=1€y；X）；（3）、平均互信息與各類熵之間的關系：I（X;Y）=H（X）-H（X/Y）=H（Y）-H（Y/X）=H（X統(tǒng)計獨立時，I€x；Y）=0。（請補充完善右圖）5）、凸函數(shù)性：當條件概率分布｛p（刀1xi入給定時，平均互信息I€x；Y）是輸入分布平均互信息量1€x；Y）是條件概率分布5）、凸函數(shù)性：當條件概率分布｛p（刀1xi入給定時，平均互信息I€x；Y）是輸入分布平均互信息量1€x；Y）是條件概率分布、例：給定 的聯(lián)合概率分布，如表所示。求:第三章信源及信源熵信1源的分類弄清楚以下信源分類的標準）離散無記憶信源隨機過程：波形信源?平穩(wěn)信源?離散平穩(wěn)信源?離散有記憶信源…記憶長度無限€I記憶長度有限也爾科夫信源連續(xù)平穩(wěn)信源非平穩(wěn)信源3離散多符號信源、離散平穩(wěn)信源的特征：統(tǒng)計特性不隨時間推移而變化。隨機過程：波形信源?平穩(wěn)信源?離散平穩(wěn)信源?離散有記憶信源…記憶長度無限€I記憶長度有限也爾科夫信源連續(xù)平穩(wěn)信源非平穩(wěn)信源3離散多符號信源、離散平穩(wěn)信源的特征：統(tǒng)計特性不隨時間推移而變化。2熵率：隨機變量序列中，對前個隨機變量的聯(lián)合熵求平均：H€X）=—H€XX…X）稱為平均N N1 2N符號熵。如果當N—a時上式極限存在，則limHw€x）稱為熵率，或稱為極限熵，記為NN—aH=limHaN—aN、離散平穩(wěn)信源的幾點結論（小題）：條件熵H匕1X1X2…XN_11）、的增加是遞減的（即已知條件越多，不確定性越少）；2）、給定時平均符號熵大于等于條件熵，即hn€x）'H（xn1x1x2…xn丿；平均符號熵HN女口果H（X）＜a，則H=limH1 aN—aNH=limH（X）=limH（XIXX…X）3）、4）、號有記憶，條件概率p€x21X1，求熵率，并比較H（X2IX丿、2H（X1X2）和H（X）的大小。第五章無失真信源編碼1信源編碼的相關概念1、各種碼的分類：(1)、分組碼和非分組碼：、分組碼將信源符號集中的每個信源符號固定地射成一個碼字i1、各種碼的分類：(1)、分組碼和非分組碼：、分組碼將信源符號集中的每個信源符號固定地射成一個碼字i(一個信源符號一一個碼字)、非分組碼又稱樹碼，編碼器輸出的碼符號通常與編碼器的所有信源符號都有關。()、奇異碼與非奇異碼：非分組碼奇異碼碼1分組碼1… …非奇異碼非唯一可譯碼唯一可譯碼1I非及時碼定義若一種分組碼中的所有碼字都不相同,則稱此分組碼為非奇異碼，否則稱為奇異碼。非奇異碼是分組碼能夠正確譯碼的必要條件，而不是充分條件。(3)、唯一可譯碼與非唯一可譯碼：定義任意有限長的碼元序列，如果只能唯一地分割成一個個碼字，便稱為唯一可譯碼。條件：①、此碼本身是非奇異的；②、對于任意有限的整數(shù)其次擴展碼均為非奇異的。唯一可譯碼首先是非奇異碼，且任意有限長的碼字序列不會雷同。()、即時碼與非即時碼：定義無需考慮后續(xù)的碼符號就可以從碼符號序列中譯出碼字，這樣的唯一可譯碼稱為即時碼。條件：①、此碼是唯一可譯碼；②、不需要通過接收到后面的碼字才能譯出前面的碼字，在收到一個完整的碼字后即可以及時譯出。一個唯一可譯碼成為即時碼的充要條件是其中任何一個碼字都不是其他碼字的前綴。5.、3變長碼及變長信源編碼定理1 不等式 不等式：()、 不等式：設信源符號集為 … 碼符號集為 … 對信源進行編碼，得到的碼為 … 碼長分別為，，…即時碼存在的充要條件是為丫匕€1這稱為i,1不等式(其中是被編碼的符號個數(shù)；是信源個數(shù)；是碼的長度)。這也就意味著即時碼存在于二叉樹的葉子節(jié)點處。()、 不等式：判斷唯一可譯碼的條件與即時碼條件一致，都是為r匕€1，條件并不比即時i,1碼判斷條件寬松。2、唯一可譯碼的判別準則：定理一個碼是唯一可譯碼的充要條件是 …的并集中沒有中的碼字。設為碼字集合，我們要構造尾隨后綴的集合，，…和。()、是中所有碼字尾隨后綴的集合：若中的碼字W.是碼字W的前綴，即WWA，則將尾隨j i ij后綴列為中的元素，所有這樣的尾隨后綴構成了；()、考查和兩個集合，若中任意碼字是中元素的前綴，或者中任意元素是中碼字的前綴,則將其相應的尾隨后綴放入集合F.,；i?1

（3）、F€Uf（即為碼的尾隨后綴集合）；..（4）、若中出現(xiàn)了中的元素，則算法終止，判斷不是唯一可譯碼；若出現(xiàn)F1為空集或F1中的元i+1 i+1素在中已經(jīng)全部存在了，則算法終止，判斷是唯一可譯碼?？偠灾?，判斷一個碼是唯一可譯碼的充要條件是中不含有中的碼字。3、例:設消息集合共有個元素 他們分別被編碼為，，， ， ，de，bbd判斷是否為唯一可譯碼。變長碼的編碼方法、香農(nóng)編碼的方法：p(s)?p(s)?p(s)?-12計算各個信源符號的累加概率F(s[…p(s)iki€1,2,…,q；k€1i=i，2,?…，q計算第i個消息的碼長1；i4)將累加概率FC.）變換成二進制小數(shù)得到其碼字。將累加概率FC.）變換成二進制小數(shù)，取小數(shù)點4)ii后l.位數(shù)作為第i個信源符號的碼字。i€[-logp(s刀二3€[-logp(s刀二34、二元霍夫曼編碼的方法：（）、信源的個消息概率從大到小排序p(、二元霍夫曼編碼的方法：（）、信源的個消息概率從大到小排序p(s)?p(s)?…?p()12（2）、0，只包括q1碼分別代表概率最小的兩個信源符號，并將這兩個概率最小的信源符號合并成一個，從而得到-個1符號的新信源。q香農(nóng)編碼信源符號$i概率pc)i累加概率Fc）i-logp(s)i碼長l.i二元碼源符號的二元碼碼長144，因此碼長?。?）、將新信源仍按概率從大到小排序，再將最后兩個概率最小的信源符號分別用0和1碼符號表示，合并成一個新符號，這樣形成了 個符號的新信源。（）、依次繼續(xù)下去，直至信源最后只剩下兩個信源符號為止。將這最后兩個信源符號用和表示。

5）、從最后一級縮減信源開始，進行回溯，將每次標注的碼符號連接起來就得到各信源符號所對應的碼符號序列，即相應的碼字。）、信源的個消息概率從大到小排序。即p）、信源的個消息概率從大到小排序。即p(s),、例5.：7以例5.為6例編制二元霍夫曼碼?；舴蚵幋a碼字信源符號編碼過程碼長01費諾編碼的過程：2）、將依次排列的信源符號以概率分為兩組，使兩組的概率和基本相等。并賦予符號0和1。（）、再分組，使劃分后的兩組的概率和基本相等，并賦予符號和1（）、重復，直至每組只剩下一個信源符號為止。（）、信源符號對應的碼符號序列即為費諾碼。、例：信源與例 和例 相同，請編制費諾碼。費諾碼信源符號概率第次分組第次分組第次分組第次分組二元碼碼長、總結：霍夫曼碼是即時碼，他的兩個特點：（1）保證了概率大的信源符號對應的碼長小，概率小的信源符號對應的碼長大，充分利用了短碼（）每次縮減信源的最長兩個碼字有相同的碼長，最后一位碼符號不同。（碼長相差的小）編碼最短，傳輸效率最高。8、習題5：：8下面是4種不同的編碼：請計算：（）、此碼的碼長分布是否滿足 不等式？（）、此碼是否為即時碼？如果不是，請說明。（3）、此碼是否為唯一可譯碼？如果不是，請說明（可以畫出樹圖說明）。實5用的無失真編碼方法各種編碼的應用（小題）：（）、游程編碼（ ）應用于:（）、碼應用于： I（）、算術編碼應用于： ；

參考答案:①、I(a)，—log0.064，3.96bit2I(c)，—log0.022，5.51bit2、由于前后字母出現(xiàn)是互相獨立的，“”出現(xiàn)的概率為 *所以I(ac)，—log(0.064*0.022)，—(log0.064?log0.022)，I(a)+I(c)=9.47bit222即兩個相對獨立的事件的自信息量滿足可加性，也就是由兩個相對獨立的事件的積事件所提供的信息量應等于他們分別提供的信息量之和。例：H(XY)，bog丄+1log丄+丄】og丄，2log4+1log2，-x2+-x1例：H(XY)，bog丄+1log丄+丄】og丄，2log4+1log2，-x2+-x1，3比特/聯(lián)合符號4 1/4 4 1/4 2 1/2 4 2 4 2 2由聯(lián)合概率分布得的邊緣概率分布：P{X=0}=2,p{X=1}=2和條件概率分布p(y.lxJ(如表 所示)，得到H(YIX，0)，1,H(YIX，1)，0和H(YIX)，-x1+-x0，-。注意到H(Y),°8113…2,H€y1x)。(a)(b)X01r01P(X)21Y)123333例2.1:5由(I)2 3H(X)=~log2—+—\ogi3=0.918=H(Y)(2)H(XIY)=^H(XIF=0)+W丹(XIr=1)=0.667=H(Y\X)(3)H(XX)=3X^log.3=1585比掬符號(4)H(Y)-H(Y\X)=0251比慟符號(5)/(X;Y)=H(Y)-H(FlX)=0251比特/符號1)、熵率：H^，H2，H€X2IX1)，0.870比特/符號；()、如果不考慮符號間的相關性，則信源熵為H(X)，-log4?4log9?11log36，1.542比特/符號4 9 436 11由此可見，H€x2|?)<H€x)=H€x2)，這是由于X「X2之間存在統(tǒng)計依賴關系，在X1已知的情況下，X2的不確定性減少，即條件熵H€x2|X])小于無條件熵H€x)。因此在考慮序列符號之間相關性之后，序列的熵減小。如果信源輸出的符號序列看成是分組發(fā)出的，每兩個符號作為一組，這樣可以把符號序列看成是由一個新信源發(fā)出的，新信源每次發(fā)出的是由兩個符號構成的消息。新信源的數(shù)學模型是一個二維的隨機變量，新信源的熵為H€X1X2)，H€X1\H(X2IX1)，1.542+0.870，2.412比特/兩個符號，平均符號熵為-HX丿，1.206比特/符號，由此可見大小關系為HX1X’)