電子科大信息論與編碼2016復(fù)習(xí)提綱

1、概論2021-10-152. Algorithms（Chapter 5, 6）： 信源編碼，信道編碼信息信息（information）定義：消除不確定性的東西Theory（Chapter 2,3,4）： 熵，信道容量，率失真函數(shù)Chapter 1概論2021-10-15消息信號(hào)信號(hào)+噪聲消息消息（message）中用以消除不確定性的成分, 就是信息（information）編碼信道譯碼噪聲信源信宿消息（message）是由圖像、聲音、文字、數(shù)字等符號(hào)組成的序列信號(hào)（signal）是承載消息的載體，如電信號(hào)、光信號(hào)等概論3Model of Digita CommunicationnSource

2、CodingnCompresses the data to remove redundancynChannel CodingnAdds redundancy/structure to protect against channel errorsCompressDecompressEncodeDecodeNoisyChannelSource CodingChannel CodingInOut概論2021-10-15香農(nóng)第一定理：信源發(fā)出的消息有冗余，為有效通信，可以進(jìn)行壓縮冗余的信源編碼，給出無(wú)失真復(fù)現(xiàn)消息的信源編碼臨界值（下界）信息熵。香農(nóng)第二定理：噪聲的存在使信道能可靠傳輸信息的能力受到限制

3、，提出信道容量的概念。為可靠通信，增加冗余糾錯(cuò)的信道編碼，給出無(wú)失真復(fù)現(xiàn)消息的信道編碼的臨界值（上界）信道容量香農(nóng)第三定理：給出在允許一定的失真條件下復(fù)現(xiàn)消息的信源編碼臨界值（下界）信息律失真函數(shù)概論2021-10-15無(wú)條件自信息量)x(Plog)x( IiaiChapter 2 信息熵n1iiin1iiii)x(Plog)x(P)x( I )x(P)x( I E)X(H嚴(yán)格上凸性（Concave）非負(fù)性最大熵定理離散信源等概率信源具有最大熵，最大熵H(X)max=log(n)，n為信源的消息個(gè)數(shù)注意：?jiǎn)挝桓耪?021-10-15二、多符號(hào)離散信源及信息熵離散型隨機(jī)過(guò)程X1X2XN自信息量自

4、信息量的鏈接準(zhǔn)則（可從概率乘法公式推導(dǎo)出來(lái)）)xx/x( I)x/x( I)x( I)xxx( I1N1N121N21iiiiiiiii)xxx(Plog)xxx( IN21N21iiiiii聯(lián)合熵用H(X1X2XN)表示)XXX/X(H)X/X(H)X(H)XXX(H1N21N121N21概論2021-10-15)X(H)X/X(H)XXX/X(HN1NN1N21N信息熵的界N1kk1N21N121N21)X(H)XXX/X(H)X/X(H)X(H)XXX(H條件熵小于無(wú)條件熵熵率)XXX(HN1)XXX(HN21N21N信源每發(fā)出一個(gè)消息符號(hào)所提供的平均信息量，也叫平均符號(hào)熵，用HN(X1

5、X2XN)表示概論2021-10-15N維離散平穩(wěn)信源多符號(hào)離散信源對(duì)任意兩個(gè)不同時(shí)間起點(diǎn)k和L，其概率分布及直到N維的各維聯(lián)合概率分布都相同概率分布與時(shí)間起點(diǎn)無(wú)關(guān))XXX/X(H)X/X(H)X(H)XXX(H)XXX(H1N21N121N211Nk1kk)X(NH)X(HN1kk信息熵概論2021-10-15N維離散平穩(wěn)信源的熵率)XXX/X(H)X/X(H)X(HN1)XXX(HN1)XXX(H)XXX(H1N21N121N21N21N1Nk1kkN)X(H)X(HN1N1kk概論2021-10-15 N維離散平穩(wěn)無(wú)記憶無(wú)記憶信源各符號(hào)相互獨(dú)立，條件熵=無(wú)條件熵信息熵和熵率)X(H)XX

6、X(H)XXX(HNN211Nk1kk)X(NH)X(HN1kk)X(H)X(NHN1)X(HN1)X(HNNN概論2021-10-15m階馬爾科夫信源階馬爾科夫信源第N個(gè)符號(hào)只與前m (N-1)個(gè)符號(hào)相關(guān)，無(wú)后效性)s /s (P)xxx/xxx(P)xxx/xxx(P)xxx/x(Pijiiijjjiiiiiiiiiim21m21m211m32m211m要會(huì)求出狀態(tài)轉(zhuǎn)移圖m =條件中的x的數(shù)目概論2021-10-15遍歷定理mijn1iijn, 2 , 1j)s /s (P)s (P)s (Pm1)s (P1)s (P0mn1jjj，且根據(jù)狀態(tài)圖，就可以求出所有P(Si)平穩(wěn)時(shí)的極限熵H

7、記為Hm+1 （熵率轉(zhuǎn)變?yōu)闂l件熵）mmn1in1jijiji1m)s /s (Plog)s /s (P)s (PHH概論 求求H（X1Xk）馬爾科夫鏈的聯(lián)合熵）馬爾科夫鏈的聯(lián)合熵nH(X1Xk)=H(X1Xm)+H(Xm+1/X1Xm) +H(Xm+2/X2Xm+1)+ ,(km) 鏈接準(zhǔn)則 =H(X1Xm)+p H(Xm+1/X1Xm), 平穩(wěn)性2. 聯(lián)合熵3. 條件熵4. 狀態(tài)概率（由遍歷定理）1311111(X/X .X )( ) (/)log (/)mmNNmmmijijiijHHP s P ssP ss 1(X .X )(S)( )log ( )miiiHHP SP S 1( )(

8、) (/),jmNjijiiP sP s P ss 1( )1mNjjP sand 概論2021-10-15五、單符號(hào)連續(xù)信源及相對(duì)熵( )p x概率密度函數(shù)絕對(duì)熵0()( )log ( )lim logbanxH Xp xp x dxx 相對(duì)熵bacdx)x(plog)x(p)X(H概論2021-10-151. 均勻信源的相對(duì)熵bxa ,ab1)x(p()log()cHXba2. 高斯信源的相對(duì)熵x,e21)x(p222)x(221()log(2)2cHXe x,0 e1)x(px當(dāng)3. 指數(shù)信源的相對(duì)熵()log()cHXe概論2021-10-152021-10-15最大相對(duì)熵定理連續(xù)信源

9、沒(méi)有一般意義下的最大相對(duì)熵，只有限制條件下的最大相對(duì)熵取值范圍受限，= 均勻分布信源平均功率受限，= 高斯分布信源均值受限，= 指數(shù)分布信源概論2021-10-15第3章 信道及信道容量XP(Y/X)Y)x/y(P)x/y(P)x/y(P)x/y(P)x/y(P)x/y(P)x/y(P)x/y(P)x/y(P)X/Y(Pnmn2n12m22211m1211維數(shù)： 發(fā)送信號(hào)個(gè)數(shù)（行）接收信號(hào)數(shù)（列）概論2021-10-15第第3章章 信道及信道容量信道及信道容量互信息量：信宿消息yj 所含信源消息xi的信息量)/()()/(log)(log);()/()()/(log)(log)/()(log)

10、;(jiijiiijijjijjijjjiyxIxIyxPxPxyIxyIyIxyPyPxyPyPyxI概論2021-10-15平均互信息量11( ; ) ( ;)() ( ;)( )( /)nmijijijijI X YE I x yP x y I x yH YH Y X)/()(YXHXH)()()(XYHYHXH條件熵H(Y/X)噪聲熵或信道散布度條件熵H(X/Y)損失熵或信道疑義度概論2021-10-15)X;Y( I)Y;X( IX與Y一一對(duì)應(yīng)時(shí)(無(wú)噪聲)，)X(H)Y(H)Y;X( IX與Y相互獨(dú)立時(shí)(噪聲太大)，0)Y;X( I概論2021-10-15嚴(yán)格凸函數(shù)性信道固定時(shí)，I(

11、X;Y)是信源概率分布P(X)的嚴(yán)格上凸函數(shù)，concave，求最大值信源固定時(shí)，I(X;Y)是信道轉(zhuǎn)移概率分布P(Y/X)的嚴(yán)格下凸函數(shù)，convex，求最小值11)/(log)/()()/(ijijijixyPxyPxPXYH概論2021-10-15信道容量信道固定時(shí)，平均互信息量是信源概率分布P(X)的嚴(yán)格上凸函數(shù)，尋找一種信源概率分布P(X)，使得平均互信息量達(dá)到最大)Y;X( ImaxC)X(P概論2021-10-15m=n信道的信道容量11(1)(/)(/)log (/)1,2,mmkikkikikkkP yxP yxP yxkm由P(Y/X)的行求出)2log(C) 2(m1kk

12、求出m, 2 , 1k2)y(P) 3 (Ckk求出1(4)()( ) (/ )( )1,2,nkikiiiP yP x P yxP xin由P(Y/X)的列求出概論2021-10-15二、對(duì)稱信道及信道容量1、對(duì)稱信道矩陣中每一行都是集合中各元素的不同排列矩陣行可排列；每一列都是集合 中各元素的不同排列矩陣列可排列q,q,qQm21p,p,pPn21既行可排列，又列可排列的信道矩陣所表示的單符號(hào)離散信道概論2021-10-151、對(duì)稱信道)q,q,q(H)Y(Hmax)X/Y(H)Y(Hmax)Y;X( ImaxCm21)X(P)X(P)X(P信宿等概時(shí)最大m1jjjm21qlogqmlog

13、)q ,q ,q (HmlogCnxPi1)(概論2021-10-15 準(zhǔn)對(duì)稱信道:行可排列而列不可排列 12111()log ()( ,)()log ()logmjjmjmmjjjjjjCP yP yH q qqP yP yqqnxPxPn1)()(1 達(dá)到信道容量的信源概率分布1()* ( /)j 1,jP yP Y Xjmn 矩陣第 列所有元素之和 ，111log),.2,1()/(log)/()()/(噪聲熵iiiijijijiqqqmqqHxyPxyPxPXYH概論2021-10-15 單符號(hào)連續(xù)信道單符號(hào)連續(xù)信道 )Y;X( ImaxC)x(p連續(xù)信道習(xí)慣于考慮信道在單位時(shí)間內(nèi)平均

14、互信息量的最大值最大信息傳輸速率定義單位時(shí)間的信道容量，用Ct表示)Y;X( ImaxT1TCC)x(pt概論2021-10-15 高斯加性信道及信道容量高斯加性信道及信道容量高斯加性信道的信道容量1log(1)2XNPCPSNRPPNX為信噪功率比其中222n2e21)n(p)x/y(p概論2021-10-154、高斯加性信道的最大信息傳輸速率信號(hào)帶寬為B，采樣時(shí)間T=1/（2B）高斯加性信道的最大信息傳輸速率香農(nóng)公式log(1)XtNPCCBTP的單邊功率譜密度為設(shè)WGANBPNN0)BNP1log(BC0Xt0XtBNPelogClim使用Taylor級(jí)數(shù)，ln(1+x)x概論2021-

15、10-15香農(nóng)公式的意義最大信息傳輸速率與所傳輸信號(hào)的帶寬成正比，基本與信噪功率比成正比信噪功率比小于1時(shí)最大信息傳輸速率仍大于0所傳輸信號(hào)的帶寬趨于無(wú)窮時(shí)，最大信息傳輸速率趨于有限值0XtBNPelogClim最大信息傳輸速率一定時(shí)，增大所傳輸信號(hào)的帶寬，可以降低對(duì)信噪功率比的要求概論2021-10-15第4章 信息率失真理論漢明失真矩陣漢明失真矩陣0.11.1.011.10D平方誤差失真函數(shù)平方誤差失真函數(shù)2)x x()x , x(d概論2021-10-15 單符號(hào)離散信源的信息率失真函數(shù))X;X( Imin)D(R)X/X(PD信源固定時(shí)信源固定時(shí)，平均互信息量是，平均互信息量是信道轉(zhuǎn)移

16、概率信道轉(zhuǎn)移概率分布分布的嚴(yán)格下凸函數(shù)，總能在實(shí)驗(yàn)信道中找到一種信的嚴(yán)格下凸函數(shù)，總能在實(shí)驗(yàn)信道中找到一種信道轉(zhuǎn)移概率分布，使實(shí)驗(yàn)信道中傳輸?shù)钠骄バ诺擂D(zhuǎn)移概率分布，使實(shí)驗(yàn)信道中傳輸?shù)钠骄バ畔⒘吭诒Ｕ娑葴?zhǔn)則下達(dá)到最小息量在保真度準(zhǔn)則下達(dá)到最小概論二進(jìn)制信源的信息率失真函數(shù)二進(jìn)制信源的信息率失真函數(shù)21pp1pxx)X(PX21其中二進(jìn)制信源0110D失真矩陣概論0)D(H)p(H)D(R0R(p)D(RpDDmaxmax時(shí)，R(D)D0.50.25p=0.25p=0.5010.811)p(H) 0 (R)D(R0DDminmin時(shí)，當(dāng)，當(dāng)0 =D =minp，1-p概論()R D達(dá)到的實(shí)驗(yàn)信

17、道11(1)() (/)(1 2 )DDpDP xxpD12() (/)(1)(1 2 )DD pDP xxpD21(1) (/)(1 2 )DDpDP xxpD22(1)(1) (/)(1)(1 2 )DDpDP xxpD概論()R D達(dá)到的實(shí)驗(yàn)信道項(xiàng)，共njiD12) 1n(11)x/x (PSijD項(xiàng)，共) 1n(nji1nD2) 1n(12)x/x (PSSijD0)D(H) 1nlog(Dnlog)D(R0)n1nR()D(Rn1nDDmaxmax時(shí)，nlog) 0 (R)D(R0DDminmin時(shí)，等概率信源的信息率失真函數(shù)等概率信源的信息率失真函數(shù)概論2021-10-15高斯信源

18、的信息率失真函數(shù)高斯信源的信息率失真函數(shù)2x22x2xe21)x(p 高斯信源2)x x()x , x(d 失真函數(shù)概論()R D達(dá)到的實(shí)驗(yàn)信道D2nD2eD21)x /x(p方差為方差為D的的反向反向高斯加性信道高斯加性信道0Dln21)D(R2x0)R()D(RDD2xmax2xmax時(shí)，) 0 (R)D(R0DDminmin時(shí)，2xR(D)D0概論2021-10-15第第5章章 信源編碼信源編碼編碼效率編碼效率1K)X(HHNK)X(H異前置碼異前置碼延時(shí)碼延時(shí)碼等到對(duì)應(yīng)于下個(gè)符號(hào)序列的碼字出現(xiàn)時(shí)等到對(duì)應(yīng)于下個(gè)符號(hào)序列的碼字出現(xiàn)時(shí)才能譯出才能譯出概論2021-10-15長(zhǎng)度為長(zhǎng)度為ki

19、i=1,2, ,nN的二進(jìn)制異前置碼存在的充的二進(jìn)制異前置碼存在的充分必要條件分必要條件12Nin1ikKraft不等式不等式Niin, 2 , 1i)a (Plogk選取Niiin, 2 , 1i1)a (Plogk)a (PlogN1)X(HNK)X(H概論2021-10-15香農(nóng)碼香農(nóng)碼將符號(hào)序列將符號(hào)序列ai i=1,2,nN按概率降序排列按概率降序排列確定第確定第i個(gè)碼字的碼長(zhǎng)個(gè)碼字的碼長(zhǎng)Niin, 2 , 1i)a (Plogk令令P(a0)=0，計(jì)算第，計(jì)算第i-1個(gè)符號(hào)序列的累加概率個(gè)符號(hào)序列的累加概率N1i1ia1i0jjian, 2 , 1i)a (P)a (P)a (P)

20、a (P將將Pa(ai)用二進(jìn)制表示，取小數(shù)點(diǎn)后用二進(jìn)制表示，取小數(shù)點(diǎn)后ki位作為符位作為符號(hào)序列號(hào)序列ai的碼字的碼字ci i=1,2,nN概論42費(fèi)諾碼(Fano Code)費(fèi)諾碼算法：費(fèi)諾碼算法：n符號(hào)序列符號(hào)序列ai按概率降序排列按概率降序排列n劃分為兩組，每組概率之和盡可能相等劃分為兩組，每組概率之和盡可能相等n為兩組分別分配編碼為兩組分別分配編碼“0”和和“1”1.在每個(gè)分組中，重復(fù)步驟在每個(gè)分組中，重復(fù)步驟 2、3，直到不可劃分，直到不可劃分概論2021-10-15將符號(hào)序列將符號(hào)序列ai i=1,2,nN按概率降序排列按概率降序排列為概率最小的兩個(gè)符號(hào)序列各自分配一個(gè)二進(jìn)為概率最小的兩個(gè)符號(hào)序列各自分配一個(gè)二進(jìn)制碼元制碼元將概率最小的兩個(gè)符號(hào)序列合并成一個(gè)新的符將概率最小的兩個(gè)符號(hào)序列合并成一個(gè)新的符號(hào)序列，用兩者概率之和作為新符號(hào)序列的概率號(hào)序列，用兩者概率之和作為新符號(hào)序列的概率赫夫曼碼赫夫曼碼重復(fù)重復(fù) 步驟，直到合并出一個(gè)以步驟，直到合并出一個(gè)以1為概率的為概率的新符號(hào)序列新符號(hào)序列分配給符