香农三大定理

信息论与编码基础香农三大定理简介一、香农第一定理二、香农第二定理三、香农第三定理信息论与编码基础香农三大定理简介一、香农第一定理二、香农第二定理三、香农第三定理信息论与编码基础香农三大定理简介1、信源编码器a、模型编码器1:{,...,}qSsaa1:{,...,}qCcWW12{,...,}liiiiiWxxx1:{,...,}rXxxx单符号信源无失真编码器码符号码字码长信息论与编码基础香农三大定理简介N次扩展信源无失真编码器编码器1(,...,)NNSSS12{,...,}liiiiiWxxx1:{,...,}rXxxx1{,...,}1,2,...,iqSaaiN1,2,...,Niq1、信源编码器a、模型信息论与编码基础香农三大定理简介b、举例1）ASCII信源编码器1、信源编码器ASCII编码器{英文字母/符号/命令}二进代码码符号集{0，1}信息论与编码基础香农三大定理简介1、信源编码器信源编码器I{A,B,…,Z}二进符号码符号集{0，1}信源编码器II码符号集{点/划/字母间隔/单词间隔}2）摩尔斯电码b、举例2）摩尔斯信源编码器b、举例符号电平二进代码点划字母间隔单词间隔+—+++——————————101110000000000信息论与编码基础香农三大定理简介3）中文电报信源编码器“中”“0022”“01101011011100111001”1、信源编码器b、举例信息论与编码基础香农三大定理简介c、分类等长码变长码中文电报莫尔斯电码有失真编码无失真编码I(S;C)H(S)I(S;C)=H(S)惟一可译码非惟一可译码若某一种码的任意一串有限长的符号序列只能被惟一地译成所对应的信源符号。1、信源编码器信息论与编码基础香农三大定理简介d、指标1)平均码长1()qiiiLPsl1()NqNiiiLPscode/signcode/N-sign1、信源编码器信息论与编码基础香农三大定理简介2)编码后的信息传输率()/RHSLbit/code()/NNHSRLNbit/coded、指标1、信源编码器信息论与编码基础香农三大定理简介3)编码效率实际编码的信息传输率最大编码的信息传输率()logNHSLrNd、指标1、信源编码器信息论与编码基础香农三大定理简介例：二元DMS进行无失真编码1231()44ssSPsH(S)=H(3/4,1/4)=0.811(bit/sign)N=111L11()0.811log2HSL(code/sign)11()0.811HSRL(bit/code)信息论与编码基础香农三大定理简介例：二元DMS进行无失真编码1231()44ssSPsH(S)=H(3/4,1/4)=0.811(bit/sign)N=2{0,10,110,111}21.688L22()0.961/2log2HSL(code/2-sign)22()0.961/2HSRL(bit/code)信息论与编码基础香农三大定理简介例：二元DMS进行无失真编码1231()44ssSPsH(S)=H(3/4,1/4)=0.811(bit/sign)N=333()0.985/3log2HSL33()0.985/3HSRL(bit/code)N=440.99140.991R(bit/code)随着N的增加，平均码长减小，有效性逐步提高；当N趋于无穷时，平均码长可以无限制地减小吗？信息论与编码基础香农三大定理简介2、香农第一定理（可变长无失真信源编码定理）rSHNLNrSHNlog)(1log)(定理4.1设},...,,{21NqNS为q元离散无记忆信源S的N次扩展信源，若对NS进行编码，码符号集Xxxxr},...,,{21，则总可以找到一种编码方法构成惟一可译码，使信源S中每个符号所需的平均编码长度满足：且当N时有：)(log)(limSHrSHNLrNN信息论与编码基础香农三大定理简介表述二：若RH(S)，就存在惟一可译变长编码；若RH(S)，惟一可译变长编码不存在，不能实现无失真编码。其中rNLRNlog'2、香农第一定理（可变长无失真信源编码定理）信息论与编码基础香农三大定理简介说明：1）通过对扩展信源进行可变长编码，可以使平均码长无限趋近于极限熵值，但这是以编码复杂性为代价的。2）无失真信源编码的实质：对离散信源进行适当的变换，使变换后新的符号序列信源尽可能为等概率分布，从而使新信源的每个码符号平均所含的信息量达到最大。3）香农第一定理仅是一个存在性定理，没有给出更有效的信源编码的实现方法。2、香农第一定理（可变长无失真信源编码定理）信息论与编码基础香农三大定理简介总结：信源编码器模型性能指标香农第一定理（无失真信源编码定理）平均码长、信息传输率、编码效率0123456701234567YtYt+1a(t)={101001011000001100111011}b={001242425124366675013666}信息论与编码基础香农三大定理简介一、香农第一定理二、香农第二定理三、香农第三定理有效性可靠性矛盾X信息论与编码基础香农三大定理简介1、错误概率误码率误字率1-ppp1-pa1=0p(a1)=ωa2=1p(a2)=1-ωb1=0b2=1p=0.01PE=P(a1)P(b2|a1)+P(a2)P(b1|a2)=ωp+(1-ω)p=0.01错误概率与那些因素相关？信息论与编码基础香农三大定理简介2、常用判决准则a、MAP准则（MaximumaPosteriori）)|()|(*RCPRCP对于所有的C*CC)()|()()()|()(**RPCRPCPRPCRPCP信息论与编码基础香农三大定理简介b、ML准则（MaximumLikelihood）若输入符号等概时rCP1)()|()|(*CRPCRP)()()|()|(**CPCPCRPCRP似然比2、常用判决准则a、MAP准则（MaximumaPosteriori）信息论与编码基础香农三大定理简介例1重复编码BSC的三次扩展信道1000211110002001301040115100610171108111(n,1)312433100.01EPpCppp信息论与编码基础香农三大定理简介312433100.01EPpCpppn=5PE≈10-5n=7PE≈4×10-7n=9PE≈10-8R=logM/nbit/codeR=logM/5R=logM/7R=logM/9可靠性增强有效性减小矛盾例1重复编码(n,1)信息论与编码基础香农三大定理简介例2（5，2）线性码),,,,(54321iiiiiiaaaaa21514213iiiiiiiiaaaaaaaaPE=7.8*10-4，R=0.4信息论与编码基础香农三大定理简介例2（5，2）线性码00000011011011111010信道000000001001000100010000100100100000001101101011110010111100011000100111101011101011110101111110011010110100110011110100110101100010010010111101111001010101100100000011011011111010信息论与编码基础香农三大定理简介3、香农第二定理（有噪信道编码定理）定理4.2设某离散无记忆信道有r个输入符号，s个输出符号信道容量为C。只要码长n足够长，总可以在输入的nr个符号集中找到M个码字（代表M个等可能的消息，且为任,2)(CnM意小的正数）组成一个码，并存在相应的译码规则，使信道输出的错误概率任意小。表述二：若在信息传输率R不大于信道容量C（即R≤C），则存在一种编码，当码长n足够大时，它可以使信道输出端的错误概率任意小，而信息传输率无限接近C；如果RC，则不可能找到一种编码，使输出端错误概率任意小。信息论与编码基础香农三大定理简介3、香农第二定理（有噪信道编码定理）信息论与编码基础香农三大定理简介说明：1、定理纠正了人们传统固有的可靠性和有效性矛盾的观点，为信道编码理论和技术的研究指明了方向。2、定理仅指出编码的存在性，未给出编码的具体方法。3、定理指出：RC是可靠传输的必要条件，但并未指出编码序列无限长是可靠传输的必要条件。3、香农第二定理（有噪信道编码定理）AWGN1)Turbo码：1/2码率，BPSK，65536随机交织，18次迭代，Pe=10-5,Eb/N0=0.7dB2)非规则LDPC码：N=107,1/2码率，Pe=10-5,Eb/N0=0.0045dB4、香农进一步证明：R=C时，任意小的差错概率也是可以达到的。证明基本条件：1）随机编码2）码长→∞3）最大似然译码信息论与编码基础香农三大定理简介一、香农第一定理三、香农第三定理二、香农第二定理不大于一定编码速率的条件下，使平均失真限制到最小；在平均失真不大于某个值的条件下，使编码速率限制到最小信息论与编码基础香农三大定理简介信息率失真理论1、失真度与信息率失真函数a、系统模型信息论与编码基础香农三大定理简介信源信源编码器无噪信道信源编码器信宿试验信道UV},...,{1ruuAU符号集},...,{1svvBV符号集b、失真测度1）单符号失真测度),(vud设VvUu,定义失真矩阵),(...),(.....),(...),(),(...),(1212111srrssvudvudvudvudvudvudd0),(jivud信息论与编码基础香农三大定理简介1、失真度与信息率失真函数如果规定jijijivuvuvud,1,0),(，那么失真矩阵为0...11....1...011...10dN=3时，失真度如图UV信息论与编码基础香农三大定理简介1、失真度与信息率失真函数b、失真测度2)序列失真测度设序列VyyyUxxxjNiN),,...,(,),,...,(11定义序列失真测度为NiiiNyxdNyxd1),(1),(信息论与编码基础香农三大定理简介1、失真度与信息率失真函数b、失真测度3)平均失真单符号平均失真jijijivudvuPdE,),(),(][序列平均失真NiiiyxdENdE1)],([1][信息论与编码基础香农三大定理简介1、失真度与信息率失真函数b、失真测度c、信息率失真函数信息论与编码基础香农三大定理简介1、失真度与信息率失真函数定义信息率失真函数)};({min)()|(VUIDRDijPuvP0P(v|u)I(U;V)R(D)最佳编码最佳编码DD例设信源X，符号集为},...,,{221naaa，等概分布ninPi2,...,1,2/1给定失真测度为jijidji,0,1,设计一种单符号压缩算法使得平均失真D=1/2，并求压缩后的信息传输率R.信息论与编码基础香农三大定理简介信息论与编码基础香农三大定理简介信息率失真函数性质1）当D0时,R(D)无意义2）存在一个Dmax，使DDmax时,R(D)=03）R(0)=H(X)4）在0DDmax范围内,R(D)是正的、连续的下凸函数R(D)DH(X)Dmax0二、香农第三定理（保真度准则下的信源编码定理）定理4.3设)(DR为一离散无记忆信源的信息率失真函数，并且有有限的失真测度D,则对于任意0,0D，以及任意长的码长k，一定存在一种码字个数为])([2DRkM的信源编码，使编码后码的平均失真度DD信息论与编码基础香农三大定理简介表述二：设)(DR为一离散无记忆信源的信息率失真函数，并且规定了有限的失真测