信息论理论基础.ppt

信息论基础 第2章 基本信息论韩宇辉*1第2章 基本信息论2.1 信息度量 2.2 离散信源的熵 2.3 二元联合信源的共熵与条件熵 2.4 连续信源的熵 2.5 熵速率和信道容量 2.6 离散有噪声信道的熵速率和信道容量 2.7 连续有噪声信道的熵速率和信道容量 2.8 使信源与信道匹配的编码Date22.1 信息度量*32.1.1 信息度量的必要性n通信的目的是为了传递信息单位时间内 信道所传递的信息量称为传信率，它是衡 量通信系统性能的重要指标之一为了得 出通信系统的传信率，必须对消息或信源 所含有的信息有一个数量上的度量方法这 就是我们研究信息度量的目的 Date42.1.2 信源的不确定性1. 研究不确定性的目的【例】A. 明天太阳将从东方升起B. 明天小张会给小王打C. 明天上午小张会给小王打结论： (1) 信源发出的消息状态应该存在某种程度的不确 定性； (2) 信息的多少与信源的不确定性有关Date52.不确定性的度量——不确定程度不确定程度可以直观理解为猜测某些随机事件 的难易程度例】布袋中有100个小球，大小、重量、手感完 全相同，但颜色不同从布袋中任取一球，猜 测其颜色。

A. 99个红球，1个白球；B. 50个红球，50个白球；C. 25个红球，25个白球，25个黑球，25个黄球 Date6(1) 不确定程度与信源概率空间有关； (2) 若状态数相同，等概分布时不确定程度最大； (3) 等概分布时，状态数越多则不确定程度越大Date73.不确定程度基本关系式——Hartley公式若信源X等概分布，则其不确定程度H(x)与概率P 满足：nP越大，则H(x)越小；n当P =1时，则H(x) =0；n当P =0时，则H(x) =∞ ；n信源不确定程度应具有可加性若X与X’相互独立，则H(x, x’)=H(x)+ H(x’)对数可以取2、e、10为底，相应不确定程度的单 位分别为比特(bit)、奈特(nat) 、哈特莱(Hartley) Date8不等概情况：n消息xi的不确定程度Date92.1.3 信息量1.概率基本关系式(1)(2)(3)Date10(4)(5) 当X和Y相互独立时，(6)Date112.信息量的定义：收信者收到一个消息后，所获得的信息量等于不 确定度的减少量I=不确定度的减少量Date123. 自信息量在没有噪声的情况下，信源发出xi 接收者就会 收到xi。

这时接收者收到的信息量就等于xi本身 含有的信息量，称为信源状态xi的自信息量， 记为I(xi)n收到xi前对xi的不确定程度：H(xi)n收到xi后对xi的不确定程度：0n自信息量Date13【例】一次掷两个色子，作为一个离散信源，求 下列消息的自信息量a.仅有一个为3； b.至少有一个为4；c.两个之 和为偶数解：p(a)=10/36=5/18p(b)=11/36p(c)=18/36=1/2I(a)=log(18/5)=1.848 (bit)I(b)=log(36/11)=1.7105 (bit)I(c)=log2=1 (bit)Date144.互信息量：在有噪声信道下，假设信源发出的状态为xi，接 收者收到的状态为yj接收者收到yj后，从yj中获 取到关于xi的信息量，就是信源发出xi后接收者 收到的信息量，称为互信息量，记为I(xi, yj)Date15收到yj前对xi的不确定程度：收到yj后对xi的不确定程度：收到yj后对xi的不确定程度：Date16【例1】某电报系统发送传号M和空号S的概率相等 ，即P(M)=P(S)=1/2由于信道中噪声的影响，使 1/6的传号收成空号，而半数的空号收成传号。

问 收信者收到一个符号后所获得的平均信息量是多 少？解：1.计算先验概率、联合概率和后验概率发送符号：接收符号：x1：发M，x2：发S，y1：收M，y2：收Sp(x1)=1/2，p(x2)=1/2S S SSM M MM M M M MM S S S S S S M M M M Mp(x1y1)=5/12，p(x1y2)=1/12，p(x2y1)=1/4p(x2 y2)=1/4p(x1|y1)=5/8，p(x1|y2)=1/4，p(x2|y1)=3/8，p(x2| y2)=3/4Date172.计算收到一个消息所获得的信息量Date183.计算收到一个消息所获得的平均信息量Date192.2 离散信源的熵*201.离散信源离散信源是指只能输出有限数量消息(状态)的信 源 2.离散信源的熵信源输出一个消息(状态)所提供的平均信息量或 信源的不肯定程度称为信源熵单位：bit/符号(消息)、nat/符号(消息)、Hartley/符号(消息)Date21【例1】计算只能输出“1”和“0”两个消息(状态)的 简单二元信源的熵 解：假设p(1)=p, p(0)=1-p(0≤p≤1)(1)当p=1/2时，H(x)=1bit/符号 (2)当p=0或p=1时，H(x)=0H(x)01/21p1Date223. 熵函数的性质 (1) 非负性 H(x) ≥0由于 0≤p(xi)≤1所以 log p(xi) ≤0因此有 H(x)≥0 (2) 对称性 (3) 确定性Date23(4) 极值性且N越大，Hmax(x)越大——离散信源的最大熵定 理证明：作辅助函数Date24令：可得 代入到约束方程可得 因此Date252.3 二元联合信源的共熵与条件熵*262.3.1 二元联合信源的共熵1.定义二元联合信源的共熵是指二元联合信源(X,Y)输 出一个组合消息状态所发出的平均信息量，也 称为联合熵，记作H(x,y)。

2.表达式(xi,yj)的信息量Date272.3.2 条件熵1.定义X的状态已知时， Y输出一个状态所发出的平均信 息量称为在X给定条件下，Y的条件熵，记作 H(y|x)在Y 给定条件下， X的条件熵，记作H(x|y) 2.表达式已知xi的条件下， yj的信息量Date283. H(x,y)=H(x)+H(y|x)= H(y)+H(x|y)证明：将 代入上式得由于因此Date292.3.3 H(x,y) ≤H(x)+H(y)的证明当X，Y相互独立时取“=”，当X，Y相关时取“0 分子0，分母0ii) aij 0，分母0p(xi)p(yj)+θ aij p(xi)p(yj)+ aij = p(xi,yj) ≥0因此 X，Y相关时,H(x,y) C ，就不可能有象R ≤ C 那样的编码方法Date982.8.2 信源最佳化——传输效率n无噪声信道n提高 ，就要使H最大化¨符号独立化，解除符号间的相关性¨各符号概率均匀化——信源最佳化Date991.弱记忆信源（弱相关信源）n如果信源的符号序列中，只有相邻的少数几个 符号之间有统计相关性，而相距较远的符号之 间的统计相关性可以忽略不计，这种信源称为 弱记忆信源或弱相关信源。

n对于这种信源，我们可以把相关性较强的几个 相邻符号看作一个大符号于是这些大符号之 间的相关性就小的多了这种方法通常称为延 长法或合并法2.8.3 符号独立化Date1002.强记忆信源（强相关信源）n如果信源序列具有很强的相关性，以致于根据 其中一部分符号就可以推测出其余的符号，这 种信源称为强记忆信源或强相关信源n对于这种信源，那些可以被推知（或预测）的 符号就无需传送一般来说，难以完全精确的 预测，而只能根据信源的统计特性作近似地预 测这时，我们不必传输序列本身，而只需传 送序列的实际值与预测值之差这种方法通常 称为预测法n预测法应用的典型例子就是增量调制和差分编 码调制Date101X=原始信源符号集；A=信道码元符号集；W=输出码字 （码组）集2.8.4 概率均匀化——最佳编码1.编码的基本知识 (1)编码器n编码器的作用：¨用A中的元素构成各个码字¨建立X与W的对应关系 Date102(2) 几个基本概念 n D元代码 若码元符号集A中有D种元素（码元），则该代码 称为D元代码n 同价代码 若各码元长度相同（占用时间相同），则该代码 称为同价代码 n 等长代码 若任一码字都有同样多个码元构成，则该代码称 为等长代码。

例如，{ 00，01，10，11 } —— 等长代码 { 0，10，110，111 } —— 非等长代码 Date103n 单义代码 若任意一个有限长的码字序列，只能唯一地分割 成一个个码字，则称该代码为单义代码 例如，{ 0，10，110，111 } —— 单义代码 0 0 1 0 1 0 1 1 0 0 …{ 0，10，110，010 } —— 非单义代码0 0 1 0 1 0 1 1 0 0 …0 0 1 0 1 0 1 1 0 0 … n 非续长代码 若任一个码字都不是另一个码字的续长，则称该 代码为非续长代码 例如，{ 0，10，110，111 } —— 非续长代码{ 0，10，110，010 } —— 续长代码| | |||| | ||| ||||Date104n非续长代码与单义代码的关系例如， { 0，10，110，111 } 是非续长代码，也是 单义代码{ 0，01 }是单义代码，但不是非续长代码 0 0 0 1 0 0 0 1 0非续长代码一定是单义的，但 单义代码不一定是非续长的 || | ||Date105n 单义代码存在定理设码元符号集为A:{a1,a2,…,aD}，码字集合为 W:{W1,W2,…Wm}，其码长分别为n1,n2,…,nm； 则单义代码存在的充要条件为码长组合满足 Kraft不等式，即nKraft不等式同时也是非续长代码存在的充要条 件；n满足Kraft不等式的码长组合一定能构成单义码 ，单义码的码长组合一定满足Kraft不等式；n有些码字的码长组合满足Kraft不等式，但不是 单义码。

编码方法不对） Date106【例】A={a1,a2},W={W1,W2,W3,W4},若各个码字 的码长分别为n1=1,n2=n3=2,n4=3问是否存在单 义代码？若n1=1,n2=2, n3=n4=3呢？ 解：(1) D=2，当n1=1,n2=n3=2,n4=3时因此不存在单义代码(2) 当n1=1,n2=2, n3=n4=3时因此存在单义代码Date107(3) 二元非续长代码的构成方法 例如，A={0,1},W={W1,W2,W3,W4},各个码字的码 长分别为n1=1,n2=2, n3=n4=3 “树图” W1=0W2=10W3=110W4=111树图也可以用来解码，如1 0 0 1 1 0 0 1 0非续长码：从顶点到任一码字都不能经过其他的码字| || |根 01 W101 W201 W3W4Date1082.最佳编码法（信源编码，有效性编码）例： X： A B C DP(X): 1/2 1/4 1/8 1/8编码1：A:00 ，B:01 ，C:10 ，D:11码长 L=2 码元/符号原始信源符号熵 H(S)=1.75 bit/符号信道码元熵 H(A)= H(S)/L=0.875 bit/码元编码效率 η= R/C=H(A)/ H(A)max=0.875/1=87.5%Date109编码2：A:0 ，B:10 ，C:110 ，D:111 平均码长 =1×0.5+2×0.25+3×0.25=1.75 码元/符号 原始信源符号熵 H(S)=1.75 bit/符号 信道码元熵 H(A)= H(S)/ =1 bit/码元 编码效率 η= H(A)/ H(A)max=1/1=100%信源编码的基本思想：根据给定的消息概率，编码成二元非续长代码： 消息概率大，编成的代码短；消息概率小，编成 的代码长，从而减小平均码长，增大信道码元熵 ，提高传输效率。

Date110(1)Shannon-Fano编码法步骤： 。