信息處理算法信息論基礎(chǔ)information-theory11

1、信息論基礎(chǔ)Elements of Information Theory杭州師范大學(xué)理學(xué)院kht/s/1kT1X4Jd課程安排&課程要求上間地點(diǎn)第1周-第16周，每周二，13:20-15:50 ，下沙校區(qū)A-201教室信息論信息論假說 ：物質(zhì)、能量與信息是組成世界的三大要很深入地了解了物質(zhì)與能量，而對信息的認(rèn)識還相對較少。們已經(jīng)信息論是運(yùn)用概率論與數(shù)理統(tǒng)計的方法對信息定量化，將信的息傳遞作為一種統(tǒng)計現(xiàn)象來考慮，給出了估算通信信道容量的方法。信息傳輸、信息壓縮以及信息是信息論研究中的重要領(lǐng)域。本課程的目標(biāo)研究信息論基本內(nèi)容及相關(guān)應(yīng)用，即信息熵、信道容量以及信源和信道編碼和通信等問題，為進(jìn)一步學(xué)習(xí)相

2、關(guān)課程打下基礎(chǔ)?？己艘蟪銮?15%)+平時的作業(yè)(35%)+期末(50%)電子課件ht/s/1kT1X4Jd及參考書，信息論與編碼（第二版），電子工業(yè)，2014, 信息論基礎(chǔ)（第4版）,郵電大學(xué)2008，信息論2014與編碼，人民郵電T. M. Cover and J. A. Thomas,Elements of Information Theory,（信息論基礎(chǔ), 機(jī)械工業(yè),2012）R.e, Information Theory,Coding and Cryptography, （信學(xué), 機(jī)械工業(yè)息論、編碼與, 2005）主要內(nèi)容第1章 緒論第2章 離散信源及其信息測量基本概念第3章 離

3、散信道及其信道容量第4章 （略去）第5章 無失真信源編碼定理第6章 有噪信道編碼定理基礎(chǔ)理論第7章 保真度準(zhǔn)則下的信源編碼第8章 無失真的信源編碼第9章 信道的糾錯編碼實(shí)際方法第9章 通信與相關(guān)應(yīng)用作業(yè)中問題12U 11 ，失真矩陣信源01/ 3D 117.2 無21 p(u)1/ 31/ 3求Dmin, Dmax, 以及相應(yīng)的信道Pp(u) min d (u, v) 1 1解：Dmin13vuu minp(u) d (u, v) min( 2 ), ( 2 1 ) Dmax11134333333vvu p11p12 設(shè)信道矩陣 P pp , 其中pp 1, i 1, 2, 322 p32 2

4、1i1i 2 1 p310P 1 , 其中0 1相對于Dmin，信道矩陣應(yīng)該有p+ p=0；min1231 0相對于Dmax，信道矩陣應(yīng)該有p12+ p31 =1；1rsD p(xi )p( y j| xi )d (xi , y j )1,i 1 j 1m1 ( p2 p) ( pp) (2 pp)1112212231323133 p p31 12糾錯編碼第二定理證明，當(dāng)R C 0時 PE的碼存在。注：證明過程采用的是隨機(jī)編碼的方法隨機(jī)編碼所得的碼集很大，通過搜索得到好碼的方法在實(shí)際上很難實(shí)現(xiàn)即使找到了好碼，這種碼的碼字也沒有規(guī)律，不便于譯碼（一般的譯碼問題是問題）真正實(shí)用的信道編碼方法還需要

5、通過各種數(shù)學(xué)工具來構(gòu)造，使碼具有好的結(jié)構(gòu)性以便于譯碼近世代數(shù)是糾錯編碼理論用到的最重要的數(shù)學(xué)工具它包括群論、環(huán)論、域論、格論、線性代數(shù)等許多分支糾錯編碼的基本思路糾錯編碼是提高傳輸可靠性的最主要的措施之一根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為的加入一些冗余碼元，這些冗余碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)（約束）。在接收端按照既定的規(guī)則檢驗(yàn)信息碼元與監(jiān)督碼元之間的關(guān)系。如果傳輸過程出錯，則信息碼元與監(jiān)督碼元之間的關(guān)系將受到破壞，從而可以發(fā)現(xiàn)錯誤乃至糾正錯誤。信道模型信道可分為三類只產(chǎn)生隨機(jī)錯誤的信道稱為隨機(jī)信道。比如信道、同軸電纜、光纜信道以及大多數(shù)微波中繼信道產(chǎn)生突發(fā)錯誤的信道稱為突發(fā)

6、信道。實(shí)際的短波信道、移動通信信道、由于擦傷造成成串差錯的光盤和磁盤，均為這一類信道有些實(shí)際信道既有隨機(jī)錯誤又有突發(fā)錯誤，稱為混合信道干擾源一般有兩種一是隨機(jī)噪聲，它主要來源于設(shè)備的熱噪聲和散彈噪聲以及媒介的熱噪聲，它是通信系統(tǒng)中的主要噪聲二是脈沖干擾和信道，它的特點(diǎn)是突發(fā)出現(xiàn)，主要來源于雷電、通電開關(guān)、負(fù)荷突變或設(shè)備故障等CmmR檢錯編碼檢錯譯碼信道糾檢錯的工作方式反饋反饋重傳(ARQ)發(fā)送端經(jīng)編碼后發(fā)出能夠發(fā)現(xiàn)錯誤的碼，接收端收到后經(jīng)檢，驗(yàn)如果發(fā)現(xiàn)傳輸中有錯誤，則通過反饋系統(tǒng)把這一判斷結(jié)果反饋發(fā)回端，然后發(fā)送端把前面發(fā)出的信息重新傳送一次，直到接收端為認(rèn)正確地收到信息為止CmmR糾錯編碼糾

7、錯譯碼信道前向糾錯(FEC)發(fā)送端發(fā)出的是具有糾錯能力的糾錯碼，接收端根據(jù)譯碼規(guī)則進(jìn)行譯碼。當(dāng)誤碼個數(shù)在碼的糾錯能力范圍內(nèi)時，譯可以自動糾錯注：前向糾錯方式不需要反饋信道，特別適合于只能提供單向信道的場合；由于能自動糾錯，不要求檢錯重發(fā)，因而延時小，實(shí)時性好；隨著糾錯能力的增強(qiáng)，譯碼設(shè)備也變得復(fù)雜混合糾錯對發(fā)送端進(jìn)行適當(dāng)?shù)木幋a。當(dāng)錯誤不嚴(yán)重，在碼的糾錯能力范圍之內(nèi)時，采用自動糾錯；當(dāng)產(chǎn)生的差錯超出碼的糾錯能力范圍時，通過反饋系統(tǒng)要求發(fā)端重發(fā)糾錯碼(Error Correcting Code)的分類按功能分檢錯碼：僅能檢測誤碼糾錯碼：可糾正誤碼糾刪碼：兼糾錯和檢錯能力糾錯碼按信息碼元與監(jiān)督碼元之

8、間的檢驗(yàn)關(guān)系分線性碼：滿足線性關(guān)系非線性碼：不存性關(guān)系按信息碼元與監(jiān)督碼元之間的約束方式不同分分組碼：本碼組的監(jiān)督碼元僅和本碼組的信息元相關(guān)樹碼：本碼組的監(jiān)督碼元不僅和本碼組的信息元相關(guān)，而且與前面碼組的信息碼元有關(guān)。如果是線性關(guān)系則稱為卷積碼按信息碼元在編碼后是否保持不式變系統(tǒng)碼：信息碼元與監(jiān)督碼元在分組內(nèi)有確定位置，編碼后的信息碼元保持不變非系統(tǒng)碼：信息位打亂，與編碼前不同按糾正差錯的類型可分為糾隨機(jī)錯誤碼糾突發(fā)錯誤碼糾隨機(jī)和突發(fā)錯誤碼 循環(huán)碼線性分組碼非循環(huán)碼糾錯碼 非線性 線性 卷積碼樹碼非線性信息序列碼字編碼舉例及基本概念00000000000010011101給出一種編碼方式，如右

9、圖：0100100111編碼是消息序列集M 到碼字集C的0110111010M C1001001110m mm mc c c .c1231 271011010011信息序列組由 3(=k) 個信息碼元(信息位)組成，1101101001共有 8=23( =2k )個不同的信息碼組1111110100輸出長度為n=7的碼字編附加 r=n-k個元(校驗(yàn)位或監(jiān)督位)，每個元是該信息碼組的某些信息碼元的模2和：C4C3碼字的數(shù)目共有 M =2k ，最小距離d=4，碼字的集合稱為 (n,k) 線性分組碼，也稱 (n,M,d)碼，n,k,d碼。編碼效率定義：設(shè)x=x1x2xn是碼C的一個碼字，x的漢明重量

10、為wH(x)=#xi 0 | i=1,2,n，則碼C的最小重量wmin (C)=min wH(x) | x C, x 0 最小距離dmin(C)=min D (x, y) | x y C= minwH (x-y) | x y C對二進(jìn)制(n, k)線性分組碼，合法碼字?jǐn)?shù)為2k，可用編碼空間的序列數(shù)為2n個。任一種2k信息集合到二進(jìn)制序列集合(2n)的都是一種(n, k)碼 ，kC 2因此總共可能的編碼方案有種2nlog 2klog Mk信息傳輸率（碼率） R nnn k編碼效率n糾錯編碼發(fā)現(xiàn)或構(gòu)造好碼是信道編碼研究的主要問題一方面要兼顧糾錯能力與編碼性質(zhì)(碼率高)另一方面是實(shí)現(xiàn)的考慮，要求容易

11、譯碼線性分組碼是相對簡單的一類碼，最具實(shí)用價值的有漢明碼、循環(huán)碼、BCH碼、RS碼等對信道編碼的一般要求是糾錯檢錯能力強(qiáng)；信息傳輸率高；編譯碼簡單，實(shí)現(xiàn)容易且費(fèi)用低；與信道的差錯統(tǒng)計特性相匹配。+01線性碼010001001110定義：集合0,1上定義兩種運(yùn)算加法“+”：a+b = a+b mod 2乘法“* ”： a*b則0,1, +, 一個域。稱上述域?yàn)橐粋€二元域(有限域)，記為GF(2)，或F2 。定義：碼C稱作(n,k)-線性碼，如果C是V=F2F2F2=F2n 的一個k-維子空間。定理：是碼C是一個(n,k)-線性碼，則有最小距離dmin(C)=最小重量 wmin (C)定理：碼C稱

12、作(n,k)-線性碼，則存在k個線性無關(guān)碼字x1 , x2 , , xk能夠C, 即L(x1 , x2 , , xk)=C;n-k個線性無關(guān)向量y1 , y2 , , yn-k與C正交, 即L(y1 , y2 , , yn-k)=C 。證明：(略去)例1哪些是線性碼？碼1碼2碼3碼4碼5碼600000101000011100000100001110100000110000000011011011101111001011010100101110111信息序列碼字例200000000000010011101碼字C C1C2C3C4C5C6C7各分量有下面的關(guān)系0100100111C4 011011

13、1010 01001001110 01011010011C3 0 01101101001 C3 C71111110100C1 C 0 2 10011000 C3 10 011010 C TTHC0 4 1010001 C5 0TCH1 0110000C6 稱(n-k)n矩陣HH QIC7 為一致校驗(yàn)矩陣校驗(yàn)矩陣(Parity Check Matrix)H被稱為校驗(yàn)矩陣對 (n,k) 線性分組碼，校驗(yàn)矩陣為(n-k)n矩陣對于系統(tǒng)碼，校驗(yàn)矩陣可以表示為H = QI其中 Q 為(n-k)k 矩陣，I 為(n-k)(n-k)矩陣定理：設(shè)H為(n,k)-線性分組碼C的校驗(yàn)矩陣，則向量x=x1x2xn是

14、碼C的一個碼字當(dāng)且僅當(dāng) (if and only if) Hxt= 0, orxHt= 0等價地，如果H的每一列用向量表示，即H=H1,H2,Hn,則x=x1x2xnC一致校驗(yàn)方程nxHt x H 0iii1 C1 C2C1例2 (續(xù))C2由校驗(yàn)方程，得到C C33C4C4C3C31000111C 01C CC100111230101110事實(shí)上，C的一個基底作為行可以構(gòu)G IP成kn生成矩陣G。m c1, c2 , c3 C = mG令生成矩陣(Generator Matrix)G被稱(n,k)線性分組碼的生成矩陣生成矩陣為 kn 維矩陣對于系統(tǒng)碼，生成矩陣可以表示為G = IP其中P為k(

15、n-k) 維矩陣，為I 維矩陣。把生成矩陣的每一行用一個行向量G1,G2,Gk來表示，則生成矩陣可以表示為G1 G G 2 G k m m1, m2 ,., mk 令，則kC = mG miGii1校驗(yàn)矩陣和生成矩陣的關(guān)系由于生成矩陣G的每一行都是一個碼字，所以G的每行都滿t足 HG= 0 ，則有iHGt = 0對于標(biāo)準(zhǔn)形式的校驗(yàn)矩陣和生成矩陣，有HGt = Q II Pt= Q+ Pt = 0Q = Pt定義：設(shè)C是F2上的一個n長分組碼，則C的對偶碼為C= x | xVn(F2), xy=0,yC定理：C是F2上的(n,k)-線性碼，則C (n,n-k)-線性碼。推論：C的生成矩陣(校驗(yàn)矩

16、陣)為C的校驗(yàn)矩陣(生成矩陣)。例例3：3次簡單重復(fù)碼是一個(3,1)線性分組碼。其生成矩陣為G 1 1 1C C1C2C3 m11 1 1 m1 m1 m1例4：(4,3)偶是一個(4,3)線性分組碼，其生成矩陣為1100G 011010011100m 01C C C C C mm1012341230101 m1, m2 , m3 , m1 m2 m3 例5已知生成矩陣為10010001101111110G 0101mC00000000000010011101求生成的線性分組碼及由H 生成0100100111的線性分組碼0110111010C mG(7,3)-線性碼1001001110101

17、101001111011010011111110100求出校驗(yàn)矩陣?yán)蒙删仃嚺c校驗(yàn)矩陣的關(guān)系10010001101111110G 01G IP011011P 01111110利用標(biāo)準(zhǔn)形式的校驗(yàn)矩陣Q I和生成矩陣I P的關(guān)系 QPt1001100I 1110100H Q10100010111000mC00000001001000110100010101100111000000001100011100010101001111101001000101生成碼空間C mHC的生成矩陣1001111101100001000010H QI 10011000101100100111100010011011

18、0001101001生成矩陣的式1100010101001110100100111101100010110001011110001011000111010011101001011110100111011111111111離散平穩(wěn)無二分組碼的糾錯檢錯能力元對稱信道適用對于一個二進(jìn)制對稱信道，當(dāng)輸入為2k個等可能的n長碼字，則最大后驗(yàn)概率準(zhǔn)則等效于最小漢明距離譯碼準(zhǔn)則np(y j | xi ) p( y jknd| xi) pkdpk 1對于(n, k)線性分組碼，設(shè)dmin為碼的最小距離，則dmin= 2u +1這組碼能糾正 u 個錯誤的充要條件是uu l 1能檢測l個錯誤的充要條件是 dmin2u+1ll問題：以碼字為中心，將空間被劃分成不同的球體，糾錯l+1編碼問題變成空間的覆蓋問題。編碼參數(shù)的關(guān)系能糾正 u 個錯誤，同時可以發(fā)現(xiàn)l (lu)個錯誤的充分必要條件為 u l 1dminluu+l+1碼的糾錯能力u與碼字的長度n和消息數(shù)M滿足以下關(guān)系uC 2niMni0糾錯編碼研究之一：構(gòu)造編碼，使得各個參數(shù)n,k,d,M等滿足要求，且達(dá)到最佳。n校驗(yàn)矩陣與碼的最小距離關(guān)系xHt x H 0iii1定理：對于(n,k)-線性分組碼校驗(yàn)矩陣H中的任意 t 列線性無關(guān)而t+1列線性相關(guān)，則碼的最