信息處理算法信息論基礎(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教室信息論信息論假說(shuō) ：物質(zhì)、能量與信息是組成世界的三大要很深入地了解了物質(zhì)與能量，而對(duì)信息的認(rèn)識(shí)還相對(duì)較少。們已經(jīng)信息論是運(yùn)用概率論與數(shù)理統(tǒng)計(jì)的方法對(duì)信息定量化，將信的息傳遞作為一種統(tǒng)計(jì)現(xiàn)象來(lái)考慮，給出了估算通信信道容量的方法。信息傳輸、信息壓縮以及信息是信息論研究中的重要領(lǐng)域。本課程的目標(biāo)研究信息論基本內(nèi)容及相關(guān)應(yīng)用，即信息熵、信道容量以及信源和信道編碼和通信等問(wèn)題，為進(jìn)一步學(xué)習(xí)相

2、關(guān)課程打下基礎(chǔ)。考核要求出勤(15%)+平時(shí)的作業(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章 離散信源及其信息測(cè)量基本概念第3章 離

3、散信道及其信道容量第4章 （略去）第5章 無(wú)失真信源編碼定理第6章 有噪信道編碼定理基礎(chǔ)理論第7章 保真度準(zhǔn)則下的信源編碼第8章 無(wú)失真的信源編碼第9章 信道的糾錯(cuò)編碼實(shí)際方法第9章 通信與相關(guān)應(yīng)用作業(yè)中問(wèn)題12U 11 ，失真矩陣信源01/ 3D 117.2 無(wú)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相對(duì)于Dmin，信道矩陣應(yīng)該有p+ p=0；min1231 0相對(duì)于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糾錯(cuò)編碼第二定理證明，當(dāng)R C 0時(shí) PE的碼存在。注：證明過(guò)程采用的是隨機(jī)編碼的方法隨機(jī)編碼所得的碼集很大，通過(guò)搜索得到好碼的方法在實(shí)際上很難實(shí)現(xiàn)即使找到了好碼，這種碼的碼字也沒(méi)有規(guī)律，不便于譯碼（一般的譯碼問(wèn)題是問(wèn)題）真正實(shí)用的信道編碼方法還需要

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

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

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

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

9、圖：0100100111編碼是消息序列集M 到碼字集C的0110111010M C1001001110m mm mc c c .c1231 271011010011信息序列組由 3(=k) 個(gè)信息碼元(信息位)組成，1101101001共有 8=23( =2k )個(gè)不同的信息碼組1111110100輸出長(zhǎng)度為n=7的碼字編附加 r=n-k個(gè)元(校驗(yàn)位或監(jiān)督位)，每個(gè)元是該信息碼組的某些信息碼元的模2和：C4C3碼字的數(shù)目共有 M =2k ，最小距離d=4，碼字的集合稱為 (n,k) 線性分組碼，也稱 (n,M,d)碼，n,k,d碼。編碼效率定義：設(shè)x=x1x2xn是碼C的一個(gè)碼字，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對(duì)二進(jìn)制(n, k)線性分組碼，合法碼字?jǐn)?shù)為2k，可用編碼空間的序列數(shù)為2n個(gè)。任一種2k信息集合到二進(jìn)制序列集合(2n)的都是一種(n, k)碼 ，kC 2因此總共可能的編碼方案有種2nlog 2klog Mk信息傳輸率（碼率） R nnn k編碼效率n糾錯(cuò)編碼發(fā)現(xiàn)或構(gòu)造好碼是信道編碼研究的主要問(wèn)題一方面要兼顧糾錯(cuò)能力與編碼性質(zhì)(碼率高)另一方面是實(shí)現(xiàn)的考慮，要求容易

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

12、作(n,k)-線性碼，則存在k個(gè)線性無(wú)關(guān)碼字x1 , x2 , , xk能夠C, 即L(x1 , x2 , , xk)=C;n-k個(gè)線性無(wú)關(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)矩陣對(duì) (n,k) 線性分組碼，校驗(yàn)矩陣為(n-k)n矩陣對(duì)于系統(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的一個(gè)碼字當(dāng)且僅當(dāng) (if and only if) Hxt= 0, orxHt= 0等價(jià)地，如果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è)基底作為行可以構(gòu)G IP成kn生成矩陣G。m c1, c2 , c3 C = mG令生成矩陣(Generator Matrix)G被稱(n,k)線性分組碼的生成矩陣生成矩陣為 kn 維矩陣對(duì)于系統(tǒng)碼，生成矩陣可以表示為G = IP其中P為k(

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

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