信息论基础第二章

第一页，共六十八页，2022年，8月28日1第一节信源和随机过程的基本概念第二节随机过程的信息度量第三节渐进等分性质第四节渐进等分性质在数据压缩中的作用–信源编码定理第五节Shannon-McMillan-Breiman定理第二页，共六十八页，2022年，8月28日2§2.1信源和随机过程的基本概念 信源即信息的来源，信源的输出称为消息，消息有各种类型，如文本、语音、图像等。消息要转换成信号进行传输。 通常信源的输出是随机的，即事前无法肯定其输出，但其服从一定的随机规律，因此利用随机过程或随机序列来建立信源的数学模型成为必然。第三页，共六十八页，2022年，8月28日3 不同类型的信源具有不同的性质，因此涉及到信源的分类。 按照信源的信号取值集合和信号取值时刻的离散或连续性可分为四类。 信源按其数学模型随机过程的统计特征分类可分为有记忆/无记忆、平稳、遍历、马氏等类型信源。 本章只讨论离散信源。第四页，共六十八页，2022年，8月28日4离散随机过程的定义 一个离散信源的输出为一个取值于有限字母集的一个随机过程，记为 其中称为状态集。一个离散随机过程是一系列随机变量，它是由一簇联合分布

唯一决定第五页，共六十八页，2022年，8月28日5无记忆信源 当为相互独立的随机变量，且服从相同的分布：

对任意的i成立时，信源为无记忆信源第六页，共六十八页，2022年，8月28日6

k-阶马尔可夫信源 称一个离散随机过程为k-阶马尔可夫过程，如果

对任意的m>k>0和成立。 特别当k＝1时，称为马尔可夫过程，此时第七页，共六十八页，2022年，8月28日7 此时联合概率可简化为

如果一个信源序列是k-阶马尔可夫过程，称信源为k-阶马尔可夫信源，k＝1时称为马尔可夫信源，对于k-阶马尔可夫信源通常可以用转移概率矩阵或状态转移图描述。第八页，共六十八页，2022年，8月28日8例一阶平稳马氏信源 设是取值于的一个一阶平稳马氏信源，其平稳分布为 一步转移概率为第九页，共六十八页，2022年，8月28日9 则用转移概率矩阵表示为

也可用状态转移图表示为01第十页，共六十八页，2022年，8月28日10 其n长序列的联合分布为：第十一页，共六十八页，2022年，8月28日11例二阶平稳马氏信源 设是取值于的二阶平稳信源，其状态可用两个二进数字表示，共有四种00，01，10，11，信源的统计特性由以下转移概率给出

用转移概率矩阵表示为

第十二页，共六十八页，2022年，8月28日12

用状态转移图表示为00011110第十三页，共六十八页，2022年，8月28日13 如果把初始状态记为，则信源的联合分布为第十四页，共六十八页，2022年，8月28日14平稳信源 称离散随机过程为平稳的，若对任意的正整数k，及任意的正整数 与有相同的联合分布，即

第十五页，共六十八页，2022年，8月28日15 如果一个马氏过程是平稳的，则

对任意的m>0成立，即此时转移概率不依赖时间，此时称状态转移矩阵 为马氏过程的公共转移矩阵，这时称马氏过程为齐次马氏链。第十六页，共六十八页，2022年，8月28日16 若存在上的一个概率分布，满足 则称其为马氏过程的平稳分布。 显然，对于平稳马氏过程来说 对任意的m>0成立，这时马氏过程完全由该平稳分布和转移概率决定。 如果一个信源序列是平稳过程，则称该信源为平稳信源，如果一个信源序列是平稳马氏过程，称信源为平稳马氏信源。第十七页，共六十八页，2022年，8月28日17

遍历信源 设为一实数列，用T表示移位算子，，称实数列集合A为平移不变集，如果当且仅当。 称一个平稳过程为遍历的，如果对任何平移不变集A有 直观的说，遍历的马氏过程从任何一个状态出发可以在有限步到达其他状态。第十八页，共六十八页，2022年，8月28日18 大多数的马氏信源是遍历的，下一信源为非遍历的00011110吸收态第十九页，共六十八页，2022年，8月28日19定理2.1.1弱大数定律第二十页，共六十八页，2022年，8月28日20定理2.1.2强大数定律第二十一页，共六十八页，2022年，8月28日21 一个信源序列如果使强大数定律成立，称它为平均遍历的。 一个无记忆信源在适当条件下是平均遍历的。平稳遍历信源是平均遍历的，但反之不成立。逆反命题是：一个信源如不满足平均遍历性（即强大数定律），则必是非遍历的。第二十二页，共六十八页，2022年，8月28日22信源熵如何度量？[例]设某二维离散信源的原始信源的信源空间X={x1,x2,x3};P(X)={1/4,1/4,1/2},一维条件概率为：p(x1/x1)=1/2;p(x2/x1)=1/2;p(x3/x1)=0;p(x1/x2)=1/8;p(x2/x2)=3/4;p(x3/x2)=1/8;p(x1/x3)=0;p(x2/x3)=1/4;p(x3/x3)=3/4;原始信源的熵为：H(X)=1.5bit/符号条件熵：H(X2/X1)=1.4bit/符号可见：H(X2/X1)<H(X)二维信源的熵：H(X1,X2)=H(X1)+H(X2/X1)=2.9bit/消息每个信源符号提供的平均信息量为：H2(X)=H(X1,X2)/2=1.45bit/符号。第二十三页，共六十八页，2022年，8月28日23我们现在有两种方法去近似信源的实际熵，一种是为1.45bit，但这种方法不太准确，因为它把两个消息看成一组，认为两组之间是统计独立的，实际上它们之间是有关联的；另一种是我们可以用条件熵来近似，为1.4bit，到底那一种正确呢？我们可以通过对一般离散平稳信源的分析来找到这个答案。分析：我们用来近似信源的实际熵第二十四页，共六十八页，2022年，8月28日24§2.2随机过程的信息度量

设是一个取值于有限字母集的离散随机过程，记 为n维随机变量的联合熵，则有：

当随机过程是平稳的时，上式为第二十五页，共六十八页，2022年，8月28日25 满足上式的数列称为半可加数列，以下引理证明极限存在。

引理设是满足的半可加数列，则第二十六页，共六十八页，2022年，8月28日26 设是平稳信源，则 存在，且 称为平稳信源的熵率，以下给出其容易计算的另一形式。定理第二十七页，共六十八页，2022年，8月28日27定理 设为平稳信源，则 （1）存在； （2） 证明：

第二十八页，共六十八页，2022年，8月28日28引理 数列 ，若有，则 证明：由已知，对任意 则当时第二十九页，共六十八页，2022年，8月28日29定理的证明 （1）易知是关于n递减的，又由于条件熵的非负性，从而的极限存在。 （2）利用联合熵的链式法则有

对上式两边取极限即得第三十页，共六十八页，2022年，8月28日30系 （1）设为无记忆信源，则熵率 （2）设为k-阶马尔可夫信源，则第三十一页，共六十八页，2022年，8月28日31 假设信源字母集的大小为n，易知 对于无无记忆信源来说有，这时如果信源概率分布不均匀，则不能最大限度携带信息，即存在冗余。 信息论中常用冗余度来描述信源输出符合携带信息的有效程度。第三十二页，共六十八页，2022年，8月28日32定义 冗余度＝

相对冗余度＝

由定义可知冗余度越低，则信号携带信息的有效性越高，反正有效性约低。第三十三页，共六十八页，2022年，8月28日33 实际信源中很多都有相当大的冗余度，考虑一个输出26个英文字母的信源 （1）若看作无记忆信源，且看作等概率且无空格，则该信源熵为

试分析此时冗余度？例题第三十四页，共六十八页，2022年，8月28日34space

0.2

;

E

0.105

;

T

0.072

;

O

0.0654

;

A

0.063

;

N

0.059

I

0.055

;

R

0.054

;

S

0.052

;

H

0.047

;

D

0.035

;

L

0.029

C

0.023

;

U

0.0225

;

M

0.021

;

P

0.0175

;

Y

0.012

;

W

0.012

G

0.011

;

B

0.0105

;

V

0.008

;

K

0.003

;

X

0.002

;

J

0.001

Q

0.001

;

Z

0.001

第三十五页，共六十八页，2022年，8月28日35 实际上，英文字母出现的频率不同，可在相关密码分析的书中可以找到，资料表明，若不将空格算在内，熵为4.15，若将空格算在内，熵为4.05。 试计算冗余度？第三十六页，共六十八页，2022年，8月28日36 若把字母间的关系考虑进去，则每个字母的熵更低，若考虑两个字母间的相关关系，即看作马氏信源，则熵率为3.6，贝尔统计8个字母间的关系，即看作7-阶马尔可夫信源，则熵率为2.6。申农估计当考虑100个字母间的关系时熵率只有1。 但是冗余也不是不必要的，冗余的存在为我们提高通讯效率提供了基础。比如mp3能将cd压缩到11%。 因为如果没有冗余，则要求系统不能出任何的错误！冗余的存在提高了抗错能力，比如对赣&*师范*&院。 因此，冗余的存在，从而对于信号的要求可以降低。第三十七页，共六十八页，2022年，8月28日37例 对例中的马氏信源，计算熵率第三十八页，共六十八页，2022年，8月28日38 计算例中的二阶马氏信源的熵率。(从状态的角度再研究，见课本)例第三十九页，共六十八页，2022年，8月28日39§2.3渐进等分性 考虑一个无记忆信源，其中都互相独立且服从相同的分布，记 ，由于信源的无记忆性，有

信源序列的渐进等分性质是大数定律在信息论中的应用，渐进等分性在信源编码问题中有重要应用。要注意的是是一个随机变量，因为它是随机向量的函数。下面来证明它的弱渐进等分性。第四十页，共六十八页，2022年，8月28日40定理 对无记忆信源有 依概率收敛于

要正确理解这里的，它是一个长度为n的信源序列，这里所谓的“信源序列”就是说是信源在正常情况下的发出的序列，它的个数总和绝不等于第四十一页，共六十八页，2022年，8月28日41证明： 由信源的无记忆性知 及弱大数定理易得。第四十二页，共六十八页，2022年，8月28日42 由上述定理知依概率收敛于 即： 以上是从平均角度来说，即从平均来说每个符号携带的信息量与接近。 如果我们记为满足以下性质的序列 的集合：第四十三页，共六十八页，2022年，8月28日43

则定理等价于

这时对于每个都有第四十四页，共六十八页，2022年，8月28日44 或者等价的为

由此我们可以估计出集合中元素的个数，记为 一方面：

一方面：第四十五页，共六十八页，2022年，8月28日45弱典型序列/典型序列 称集合中的序列为弱典型序列，或称典型序列。 对于典型序列有以下性质：

定理：对任给的，有 （1）如，则 （2）当n充分大时， （3）当n充分大时，第四十六页，共六十八页，2022年，8月28日46

（1）弱典型序列总数可能只占总序列的小部分。

注意：第四十七页，共六十八页，2022年，8月28日47（2）弱典型序列总的概率近似为1，而非弱典型序列总的概率很小；但是这并不意味着弱典型序列的概率都大于非典型序列的概率。 如下例： 假设一个二值离散无记忆信源，其公共概率分布为： 因此：第四十八页，共六十八页，2022年，8月28日48

而典型序列的个数满足：第四十九页，共六十八页，2022年，8月28日49§2.4信源编码定理 对于无记忆信源产生的长度为n的信息序列，现要对其进行编码，我们希望编码后的码字数尽可能的少，而译码的错误概率尽可能小。 利用典型序列的理论我们可以做到这些。 我们将所有的n长的信息序列分成两部分，对于弱典型序列，每一个序列给予一个码字，则码字个数记为M＝第五十页，共六十八页，2022年，8月28日50 分成两部分，对于弱典型序列 中的每一个序列分配一个编号，称为一个码字，码字集为，其编号总数为。对于非典型序列，则统一一个编号为1。 在从编码后的码字复原原序列时，如果收到的码字，则能唯一的复原成原来的序列。如果收到的码字为1，若原序列 ，则无法正确地复原，就会产生错误。第五十一页，共六十八页，2022年，8月28日51 我们记以上编码的码率为，其误差概率为 由弱渐进等分性：于是其码率满足：第五十二页，共六十八页，2022年，8月28日52 其误差概率为 由上知，当n充分大时，码率接近于，而误差概率趋于0，此谓之信源编码正定理

第五十三页，共六十八页，2022年，8月28日53 反之，如果我们用少于比特的码率对信源序列进行压缩编码行不行呢？答案是否定的。可以证明，如果码率，其中 不随n改变，则当时。证明如下： 假设用码率为的n长的分组码进行编码，则码字总数为（ ），我们用其中一部分对典型序列进行编码，其它的对非典第五十四页，共六十八页，2022年，8月28日54 型序列编码，则能被编码的典型序列的总概率的上界为：