香农三大定理

1、信息论与编码基础信息论与编码基础 香农三大定理香农三大定理 简介简介 一、香农第一定理 二、香农第二定理 三、香农第三定理 信息论与编码基础信息论与编码基础 香农三大定理香农三大定理 简介简介 一、香农第一定理一、香农第一定理 二、香农第二定理 三、香农第三定理 信息论与编码基础信息论与编码基础 香农三大定理香农三大定理 简介简介 1、信源编码器、信源编码器 a、模型 编码器编码器 1 : ,., q S saa 1 :,., q C cWW 12 ,., li iiii Wxxx 1 : ,., r X xxx 单符号信源无失真编码器 码符号码符号 码字码字 码长码长 信息论与编码基础信息论

2、与编码基础 香农三大定理香农三大定理 简介简介 N次扩展信源无失真编码器 编码器编码器 1 (,.,) N N SSS 12 ,., li iiii Wxxx 1 : ,., r X xxx 1 ,., 1,2,., iq Saa iN 1,2,., N iq 1、信源编码器、信源编码器 a、模型 信息论与编码基础信息论与编码基础 香农三大定理香农三大定理 简介简介 b、举例 1）ASCII信源编码器 1、信源编码器、信源编码器 ASCII编码器编码器 英文字母/符号/命令二进代码 码符号集0，1 信息论与编码基础信息论与编码基础 香农三大定理香农三大定理 简介简介 1、信源编码器、信源编码器

3、 信源编码器信源编码器I A,B,Z 二进符号 码符号集0，1 信源编码器信源编码器II 码符号集点/划/字母间隔/单词间隔 2）摩尔斯电码 b、举例 2）摩尔斯信源编码器 b、举例 符号 电平 二进代码 点划字母间隔单词间隔 + + + + 101110000000000 信息论与编码基础信息论与编码基础 香农三大定理香农三大定理 简介简介 3）中文电报信源编码器 “中中” “0022” “01101 01101 11001 11001” 1、信源编码器、信源编码器 b、举例 信息论与编码基础信息论与编码基础 香农三大定理香农三大定理 简介简介 c c、分类、分类 等长码等长码 变长码变长码

4、 中文电报中文电报 莫尔斯电码莫尔斯电码 有失真编码有失真编码 无失真编码无失真编码 I(S;C) H(S)，就存在惟一可译变长编码；若RC，则不可能找到一种编码，使输出端错误 概率任意小。 信息论与编码基础信息论与编码基础 香农三大定理香农三大定理 简介简介 3、香农第二定理（、香农第二定理（有噪信道编码定理） 信息论与编码基础信息论与编码基础 香农三大定理香农三大定理 简介简介 说明：说明： 1 1、定理纠正了人们传统固有的可靠性和有效性矛盾的观点，、定理纠正了人们传统固有的可靠性和有效性矛盾的观点， 为信道编码理论和技术的研究指明了方向。为信道编码理论和技术的研究指明了方向。 2 2、定

5、理仅指出编码的存在性，未给出编码的具体方法。、定理仅指出编码的存在性，未给出编码的具体方法。 3、定理指出：、定理指出：RC是可靠传输的必要条件，但并未指出编码是可靠传输的必要条件，但并未指出编码 序列无限长是可靠传输的必要条件。序列无限长是可靠传输的必要条件。 3、香农第二定理（、香农第二定理（有噪信道编码定理） AWGN 1)Turbo码：码：1/2码率，码率，BPSK，65536随机交织，随机交织， 18次迭代，次迭代，Pe=10-5, Eb/N0 = 0.7dB 2)非规则非规则LDPC码：码：N = 107, 1/2码率，码率， Pe=10-5, Eb/N0 = 0.0045dB 4

6、、香农进一步证明：、香农进一步证明：R=C时，任意小的差错概率也是可以达时，任意小的差错概率也是可以达 到的。到的。 证明基本条件：证明基本条件：1）随机编码）随机编码 2）码长）码长 3）最大似然译码）最大似然译码 信息论与编码基础信息论与编码基础 香农三大定理香农三大定理 简介简介 一、香农第一定理 三、香农第三定理三、香农第三定理 二、香农第二定理 不大于一定编码速率的条件下，使平均失真限 制到最小； 在平均失真不大于某个值的条件下，使编码 速率限制到最小 信息论与编码基础信息论与编码基础 香农三大定理香农三大定理 简介简介 信息率失真理论信息率失真理论 1、失真度与信息率失真函数、失真

7、度与信息率失真函数 a、系统模型 信息论与编码基础信息论与编码基础 香农三大定理香农三大定理 简介简介 信源信源编码器无噪信道信源编码器信宿 试验信道 U V ,., 1r uuAU符号集 ,., 1s vvBV符号集 b、失真测度 1）单符号失真测度),(vud 设VvUu, 定义失真矩阵 ),(.),( . ),(.),( ),(.),( 1 212 111 srr s s vudvud vudvud vudvud d 0),( ji vud 信息论与编码基础信息论与编码基础 香农三大定理香农三大定理 简介简介 1、失真度与信息率失真函数、失真度与信息率失真函数 如果规定 ji ji ji

8、 vu vu vud , 1 , 0 ),(，那么失真矩阵为 0.11 . 1.01 1.10 d N=3时，失真度如图 UV 信息论与编码基础信息论与编码基础 香农三大定理香农三大定理 简介简介 1、失真度与信息率失真函数、失真度与信息率失真函数 b、失真测度 2)序列失真测度 设序列 VyyyUxxx jNiN ),.,( ,),.,( 11 定义序列失真测度为 N i iiN yxd N yxd 1 ),( 1 ),( 信息论与编码基础信息论与编码基础 香农三大定理香农三大定理 简介简介 1、失真度与信息率失真函数、失真度与信息率失真函数 b、失真测度 3)平均失真 单符号平均失真 ji

9、 jiji vudvuPdE , ),(),( 序列平均失真 N i ii yxdE N dE 1 ),( 1 信息论与编码基础信息论与编码基础 香农三大定理香农三大定理 简介简介 1、失真度与信息率失真函数、失真度与信息率失真函数 b、失真测度 c、信息率失真函数 信息论与编码基础信息论与编码基础 香农三大定理香农三大定理 简介简介 1、失真度与信息率失真函数、失真度与信息率失真函数 定义定义 信息率失真函数 );(min)( )|( VUIDR Dij PuvP 0 P(v|u) I(U;V) R(D) 最佳编码最佳编码 DD 例例 设信源X，符号集为,., 221n aaa ，等概分布

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

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

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