信息论与编码基础

1、信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介一、香农第一定理二、香农第二定理三、香农第三定理信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介一、香农第一定理一、香农第一定理二、香农第二定理三、香农第三定理信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介1、信源编码器、信源编码器a、模型编码器编码器1: ,.,qS saa1:,.,qC cWW12,.,liiiiiWxxx1: ,.,rX xxx单符号信源无失真编码器码符号码符号码字码字码长码长信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介N次扩展信源无失真编码器编码器编码器

2、1(,.,)NNSSS12,.,liiiiiWxxx1: ,.,rX xxx1 ,.,1,2,.,iqSaaiN1,2,.,Niq1、信源编码器、信源编码器a、模型信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介b、举例1）ASCII信源编码器1、信源编码器、信源编码器ASCII编码器编码器英文字母/符号/命令二进代码码符号集0，1信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介1、信源编码器、信源编码器信源编码器信源编码器IA,B,Z二进符号码符号集0，1信源编码器信源编码器II码符号集点/划/字母间隔/单词间隔2）摩尔斯电码b、举例2）摩尔斯信源编码器b、举

3、例符号电平二进代码点划字母间隔单词间隔+ + + + 101110000000000信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介3）中文电报信源编码器“中中”“0022”“01101 01101 11001 11001”1、信源编码器、信源编码器b、举例信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介c c、分类、分类等长码等长码变长码变长码中文电报中文电报莫尔斯电码莫尔斯电码有失真编码有失真编码无失真编码无失真编码I(S;C) H(S)，就存在惟一可译变长编码；若RC，则不可能找到一种编码，使输出端错误概率任意小。 信息论与编码基础信息论与编码基础香农三大

4、定理香农三大定理简介简介3、香农第二定理（、香农第二定理（有噪信道编码定理）信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介说明：说明：1 1、定理纠正了人们传统固有的可靠性和有效性矛盾的观点，、定理纠正了人们传统固有的可靠性和有效性矛盾的观点，为信道编码理论和技术的研究指明了方向。为信道编码理论和技术的研究指明了方向。2 2、定理仅指出编码的存在性，未给出编码的具体方法。、定理仅指出编码的存在性，未给出编码的具体方法。3、定理指出：、定理指出：RC是可靠传输的必要条件，但并未指出编码是可靠传输的必要条件，但并未指出编码序列无限长是可靠传输的必要条件。序列无限长是可靠传输的必要

5、条件。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）最大似然译码）最大似然译码信息论与编码基础信息论与编码基础香农三大定理香农三大定理

6、简介简介一、香农第一定理三、香农第三定理三、香农第三定理二、香农第二定理不大于一定编码速率的条件下，使平均失真限 制到最小； 在平均失真不大于某个值的条件下，使编码 速率限制到最小信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介信息率失真理论信息率失真理论1、失真度与信息率失真函数、失真度与信息率失真函数a、系统模型信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介信源信源编码器无噪信道信源编码器信宿试验信道UV,.,1ruuAU符号集,.,1svvBV符号集b、失真测度1）单符号失真测度),(vud设VvUu,定义失真矩阵),(.),(.),(.),(),(.)

7、,(1212111srrssvudvudvudvudvudvudd0),(jivud信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介1、失真度与信息率失真函数、失真度与信息率失真函数如果规定jijijivuvuvud, 1, 0),(，那么失真矩阵为0.11.1.011.10dN=3时，失真度如图UV信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介1、失真度与信息率失真函数、失真度与信息率失真函数b、失真测度2)序列失真测度设序列VyyyUxxxjNiN),.,( ,),.,(11定义序列失真测度为NiiiNyxdNyxd1),(1),(信息论与编码基础信息论与

8、编码基础香农三大定理香农三大定理简介简介1、失真度与信息率失真函数、失真度与信息率失真函数b、失真测度3)平均失真单符号平均失真jijijivudvuPdE,),(),(序列平均失真NiiiyxdENdE1),(1信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介1、失真度与信息率失真函数、失真度与信息率失真函数b、失真测度c、信息率失真函数信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介1、失真度与信息率失真函数、失真度与信息率失真函数定义定义 信息率失真函数);(min)()|(VUIDRDijPuvP0P(v|u)I(U;V)R(D)最佳编码最佳编码DD例例

9、 设信源X，符号集为,.,221naaa，等概分布ninPi2,.,1,2/1给定失真测度为jijidji, 0, 1,设计一种单符号压缩算法使得平均失真D=1/2，并求压缩后的信息传输率R.信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介信息率失真函数性质1）当D Dmax时,R(D)=03）R(0)=H(X)4）在0D Dmax范围内,R(D)是正的、连续的下凸函数R(D)DH(X)Dmax0二、香农第三定理二、香农第三定理（保真度准则下的信源编码定理）定理定理4.3 设)(DR为一离散无记忆信源的信息率失真函

10、数，并且有有限的失真测度D,则对于任意0, 0D，以及任意长的码长k，一定存在一种码字个数为)(2DRkM的信源编码，使编码后码的平均失真度DD 信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介表述二：设)(DR为一离散无记忆信源的信息率失真函数，并且规定了有限的失真测度，对于任意的0, 0D则：)(logDRkMR1）若给定了失真D，且，则存在长度为k的码，它的平均失真度DD 2）若)(DRR 时，无论采用什么编码，其平均失真大于D信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介二、香农第三定理二、香农第三定理（保真度准则下的信源编码定理）几点讨论1）R(D)

11、确定是保真度准则条件下，信源信息率压缩的下限。)()(0XHDR2）R(D)在实际工程中可以作为衡量各种压缩编码方法性能优劣的一种标尺。3）是一种存在定理，其实际应用有待于进一步研究：a)如何计算符合实际信源的信息率失真函数R(D)？b)如何寻找最佳编码方法才能达到信息压缩的极限值R(D)？二、香农第三定理二、香农第三定理（保真度准则下的信源编码定理）信息论与编码基础信息论与编码基础香农三大定理香农三大定理简介简介信信源源信信宿宿限限失失真真信信源源编编码码器器限限失失真真信信源源译译码码器器无无失失真真信信源源编编码码器器无无失失真真信信源源译译码码器器信信道道编编码码信信道道译译码码ABCDEFGH信道信道一般通信系统框图一般通信系统框图信息论与编码基础信息论与编