第二章随机过程的信息度量和渐近等分性

1、12.1 2.1 2.2 2.2 2.3 2.3 2.4 2.4 2.5 2.5 第二章第二章2 信源信源：是信息的来源是信息的来源, ,是产生消息是产生消息( (符号符号) )、消息序列、消息序列 ( (符号序列符号序列) )以及时间连续的消息的来源以及时间连续的消息的来源. . (1) (1)在一个固定的时刻在一个固定的时刻, ,信源发出的是一个随机变量信源发出的是一个随机变量. . (2)(2)随着时间的延续，信源发出的是一个随机过程随着时间的延续，信源发出的是一个随机过程. . l 信源的主要问题信源的主要问题如何描述信源的输出（信源的建模问题）如何描述信源的输出（信源的建模问题）怎样

2、确定信源产生的信息量怎样确定信源产生的信息量信源编码信源编码 第二章第二章1.1.信源的分类及其数学模型信源的分类及其数学模型312( )()NP XP X XX),(teX 时间时间 （空间）（空间）取值取值信源种类信源种类举例举例消息的数学描述消息的数学描述 离散离散离散离散 离散信源离散信源 ( (数字信源数字信源) )文字、数据文字、数据离散化图象离散化图象 离散随机变量序列离散随机变量序列 离散离散连续连续 连续信源连续信源 连续连续连续连续 波形信源波形信源 ( (模拟信源模拟信源) )语音、音乐语音、音乐、热噪声、热噪声、图形、图象图形、图象随机过程随机过程 连续连续离散离散 不

3、常见不常见 根据信源输出消息在时间和取值上是离散或连续分类根据信源输出消息在时间和取值上是离散或连续分类 4信号取值离散信号取值离散：信源输出的消息是有限或可数的，而：信源输出的消息是有限或可数的，而且每次只输出其中一个消息且每次只输出其中一个消息. . 如：如：抛硬币抛硬币！其数学模型是离散型的概率空间：其数学模型是离散型的概率空间：1212,(),(),( )()qqxxxXP xP xP xP x ()1iip a,( , )( )( )Xa bP xP x信号取值连续信号取值连续：信源输出的是单个符号，但符号集的：信源输出的是单个符号，但符号集的取值是连续的，或实数集取值是连续的，或实

4、数集. . 如：如：语音信号某时间的连续数据语音信号某时间的连续数据！其数学模型是离散型的概率空间：其数学模型是离散型的概率空间： ( )1bap x dx 5波形信源波形信源：输出的消息是时间连续，且符号集的取值：输出的消息是时间连续，且符号集的取值也连续也连续. . 如：如：多媒体通信系统的信号多媒体通信系统的信号！一般用一般用平稳平稳遍历遍历的随机过程来描述波形信源的输出的随机过程来描述波形信源的输出. .平稳平稳：在任意两个不同时刻随机变量的各维概率分布：在任意两个不同时刻随机变量的各维概率分布相同相同. . 如：如：自然英文字母自然英文字母！11( , , )nnnp xx tt11

5、(,)nnnpxx tt6 离散信源离散信源 信源每隔一个定长时间段就发出一个随机信源每隔一个定长时间段就发出一个随机变量；随着时间的延续，信源发出的是随机变量序变量；随着时间的延续，信源发出的是随机变量序列列 U-2U-1U0 U1U2， 其中其中 (1) Uk为第为第k个个时间段时间段发出的随机变量发出的随机变量； (2) 每个每个Uk都是一个离散型的随机变量都是一个离散型的随机变量. 信源的分类及其数学模型信源的分类及其数学模型71)1)根据信源发出的消息序列之间是否有统计依赖关系，根据信源发出的消息序列之间是否有统计依赖关系，信源可分为信源可分为有记忆信源、无记忆信源有记忆信源、无记忆

6、信源. . 离散无记忆信源：离散无记忆信源：随机变量随机变量、U-2、U-1、U0、U1、U2、相互相互独立独立. . 简单信源：简单信源：信源在不同时刻发出的随机变量有相同的概率分布信源在不同时刻发出的随机变量有相同的概率分布. .离散无记忆离散无记忆简单简单信源：信源：离散无记忆信源发出的随机变量具有相离散无记忆信源发出的随机变量具有相同的概率分布同的概率分布. .信源的分类及其数学模型信源的分类及其数学模型8注意：注意：有记忆信源有记忆信源： 信源在不同时刻发出的随机变量相互依赖信源在不同时刻发出的随机变量相互依赖. .有限记忆信源有限记忆信源： 在有限时间差内的信源随机变量相互依赖在有

7、限时间差内的信源随机变量相互依赖. . 信源的分类及其数学模型信源的分类及其数学模型9()离散无记忆信源记忆长度无限长离散平稳信源平稳信源离散有记忆信源 记忆长度有限随机序列马尔可夫信源连续平稳信源非平稳信源 随机过程：波形信源2)2)根据信源发出的消息序列中的消息统计特性是否根据信源发出的消息序列中的消息统计特性是否保持不变，信源可分为保持不变，信源可分为平稳信源、非平稳信源平稳信源、非平稳信源. . 信源的分类及其数学模型信源的分类及其数学模型102.2.离散信源离散信源 离散信源离散信源（1 1）单符号离散信源单符号离散信源：信源输出的消息是离散消息，：信源输出的消息是离散消息，且每个符

8、号表示一条消息。且每个符号表示一条消息。 用用离散随机变量离散随机变量表示。表示。 记作：大写字母。记作：大写字母。（2 2）多符号离散信源多符号离散信源：信源输出的消息是离散消息，：信源输出的消息是离散消息，且多个符号表示一条消息。且多个符号表示一条消息。 用用随机矢量随机矢量表示。表示。（3 3）连续信源连续信源：信源输出的消息是连续消息。：信源输出的消息是连续消息。 用用随机过程随机过程表示。表示。11l 离散单符号信源离散单符号信源：输出离散取值的单个符号的信源输出离散取值的单个符号的信源. . 离散单符号信源离散单符号信源是是最简单、最基本最简单、最基本的信源，是组成实际信源的基本的

9、信源，是组成实际信源的基本单元，可以用一个离散随机变量来表示单元，可以用一个离散随机变量来表示. .l 离散单符号信源离散单符号信源X的概率空间的概率空间1212.()( )().()qqxxxXP Xp xp xp x()0ip x1()1niip x2.2.离散信源离散信源12l 信源输出的所有消息的自信息的统计平均值，定信源输出的所有消息的自信息的统计平均值，定义为信源的义为信源的平均自信息（信息熵）平均自信息（信息熵）1()log( )( )log( )niiiiH XEp xp xp x l 信息熵表示离散单符号信源的平均不确定性信息熵表示离散单符号信源的平均不确定性. .离散单符号

10、信源离散单符号信源13 实际信源往往输出的消息是时间和空间上的一系列符号实际信源往往输出的消息是时间和空间上的一系列符号. .例如例如电报系统电报系统, , 这类信源每次输出的不是一个单个的符号，而是一个这类信源每次输出的不是一个单个的符号，而是一个符号序列符号序列. . 通常一个消息序列的每一位出现哪个符号都是随机的通常一个消息序列的每一位出现哪个符号都是随机的, ,而且而且一般前后符号之间的出现是有统计依赖关系的一般前后符号之间的出现是有统计依赖关系的, ,这种信源称为这种信源称为多多符号离散信源符号离散信源. . 为了便于研究为了便于研究, ,假设随机变量序列中随机变量的各维联合概假设随

11、机变量序列中随机变量的各维联合概率分布率分布( (统计特性统计特性)均不随时间的推移而变化均不随时间的推移而变化, ,即信源所发出的符即信源所发出的符号序列的概率分布与时间的起点无关号序列的概率分布与时间的起点无关, ,这种信源称为这种信源称为多符号离散多符号离散平稳信源平稳信源. .多符号离散信源可以用随机变量序列来描述，即多符号离散信源可以用随机变量序列来描述，即12nX XXX X离散多符号信源离散多符号信源14定义定义 对于离散随机变量序列对于离散随机变量序列 ，若任意，若任意两个不同时刻两个不同时刻i和和j( (大于大于1 1的任意整数的任意整数) )信源发出消息的信源发出消息的概率

12、分布完全相同，即对于任意的概率分布完全相同，即对于任意的 , , 和和 具有相同的概率分布，也具有相同的概率分布，也就是就是各维联合概率分布均与时间起点无关的信源称各维联合概率分布均与时间起点无关的信源称离散平离散平稳信源。稳信源。 nXXX21, 2, 1, 0N1iiiNX XX1jjjNX XX)()(jiXPXP)()(11jjiiXXPXXP11()()iii Njjj NP X XXP X XX离散平稳信源离散平稳信源15对离散平稳信源，由联合概率与条件概率的关系可以推出对离散平稳信源，由联合概率与条件概率的关系可以推出 )|()|(11jjiiXXPXXP1111(|)(|)i

13、Niii Nj Njjj NP XX XXP XX XX因此因此 )()()(21NXHXHXH)|()|()|(12312NNXXHXXHXXH31242321(|)(|)(|)NNNH XX XH XX XH XXX离散平稳信源离散平稳信源16如果一个信源序列是平稳遍历过平稳程,遍称信源为历信源.平稳遍历信源平稳遍历信源1223( ,.)(,.),. 设为一个实数序列，用 表示移位算子，称实数列的集合 为，如果当且定平移不变义当集仅xx xTTxx xATxAxA12( ,.)01. 称一个平稳过程为，如果对任何平移不变集定遍历的有或义rAPx xA, 直观地说 一个遍历的马氏过程从任何一

14、个状态出发可以正概率在有限步到达任何其它状态.17 随机变量是定义在概率空间上取值为实数的函随机变量是定义在概率空间上取值为实数的函数。因此我们可以像数学分析讨论函数序列逐点收数。因此我们可以像数学分析讨论函数序列逐点收敛性那样去讨论随机变量序列在每个样本点处的值敛性那样去讨论随机变量序列在每个样本点处的值的收敛性。的收敛性。 然而然而, ,由于随机变量取值的随机性由于随机变量取值的随机性, ,我们常常不我们常常不可能期望随机变量序列在所有点处都存在极限。现可能期望随机变量序列在所有点处都存在极限。现在的问题是研究极限是否在一个概率为在的问题是研究极限是否在一个概率为1 1的点集上的点集上存在

15、。存在。 由于随机变量序列向常数的收敛有多种不同的由于随机变量序列向常数的收敛有多种不同的形式形式, ,按其收敛为按其收敛为依概率收敛依概率收敛, ,依概率依概率1 1收敛收敛, ,相对应相对应分别有弱大数定律、强大数定律。分别有弱大数定律、强大数定律。1812111,.,.1,0,1lim|1.:,1.nniiinrininiiXXXXEXaXanPXannXan 设, 为相互独立的随机变量序列,并且服从相同的分布,有有限数学期望= ,则依概率收敛到即对任意的有 直观的理解除去极小的可能性 只要 充定理(弱大数定律) 分大与 可任意接近弱大数定律弱大数定律191211,.,.1,1lim1.

16、,.nniiinrinikXXXXEXaXnaPXanX定理(强大数定律) 设, 为相互独立的随机变量序列,并且服从相同的分布,有有限数学期望= ,则依概率1收敛到 即 一个信源序列如果使 定义强大数定律成立 称为平均遍历强大数定律强大数定律20121212(, )()( ),(,.,)(,.,)(,.,).,0,()( )( ).m nmmmm nH X YH XH YH XXXH XXXH XXXm nh mnh mh n因为所以对任意的整数满足的定义半可列称加数列数( )()( )( )11,lim( )inf( ).设是满足的半可加数列引则理nnf nf mnf mf nf nf nn

17、n2.22.2随即过程的总度量随即过程的总度量3. 3. 随机过程的信息度量随机过程的信息度量211,1,2,.lim,1lim. 设实数列有极引限则理nnnnknka naaaan定义定义 随机变量序列中，对前随机变量序列中，对前N个随机变量的联个随机变量的联合熵求平均称为合熵求平均称为平均符号熵平均符号熵 . .121()(,)NNHH XXXNX X随机过程的信息度量随机过程的信息度量2212121()lim()lim(,)1inf(,)()defNNNNNNHXHH XXXNH XXXXN是平稳信源X X如果当如果当 时上式极限存在，则时上式极限存在，则 被称为被称为熵率熵率，或，或极

18、限熵极限熵，记为，记为 Nlim()NNHX X随机过程的信息度量随机过程的信息度量2312,.,.,.,nXXXX为了便于计算 我们给出熵定理率的另一个等价形式 设,是平稳信源121(1)()lim(|,.,)存在;defnnnHXH XXXX(2)()().HXHX随机过程的信息度量随机过程的信息度量24 （2 2）对于收敛的实数列，）对于收敛的实数列， 即如果即如果 是一个收敛是一个收敛 于于 a 的实数列，那么的实数列，那么123,a a a 11limlimNkNNNkaaaN利用上述结论及熵的链法则可以推出利用上述结论及熵的链法则可以推出121lim(|)()NNNH XX XXH

19、X121lim()lim(,)()NNNNHH X XXHXNX1111lim(|,)NkkNkH XXXN1213121211lim()(|)(|)(|)NNNH XH XXH XX XNH XX XX25121,.,.()()nXXXXHXH X 设,是无记忆信源,则熵率推论1.随机过程的信息度量随机过程的信息度量1211221,.,.()(|,.,1,()(|2nkkXXXXHXH XXXXkHXH XX设,是k-阶平稳马氏信源,则熵率);特别地时推论).26 为了研究离散平稳无记忆信源的极限熵，把信源输为了研究离散平稳无记忆信源的极限熵，把信源输出的符号序列看成是一组一组发出的。出的符

20、号序列看成是一组一组发出的。例例1 1 电报系统中电报系统中, ,可以认为每可以认为每2 2个二进制数字组成一组。这个二进制数字组成一组。这样信源输出的是由样信源输出的是由2 2个二进制数字组成的一组组符号。这时个二进制数字组成的一组组符号。这时可以将它们等效看成一个新的信源，它由四个符号可以将它们等效看成一个新的信源，它由四个符号00，01，10，11组成，把该信源称为组成，把该信源称为二进制无记忆信源的二次扩展二进制无记忆信源的二次扩展。例例2 2 如果把每三个二进制数字组成一组，这样长度为如果把每三个二进制数字组成一组，这样长度为3 3的二的二进制序列就有进制序列就有8 8种不同的符号，

21、可等效成一个具有种不同的符号，可等效成一个具有8 8个符号的个符号的信源，把它称为信源，把它称为二进制无记忆信源的三次扩展信源二进制无记忆信源的三次扩展信源。4.4.离散平稳无记忆信源离散平稳无记忆信源27l假定信源输出的是假定信源输出的是N长符号序列，把它看成是一个新长符号序列，把它看成是一个新信源，称为信源，称为离散平稳无记忆信源的离散平稳无记忆信源的N N次扩展信源次扩展信源，用，用N维离散随机变量序列来表示：维离散随机变量序列来表示：12NNX XXXX X1212()()()()()NiqNiqNXppppPXiG 是一个长为是一个长为N N的序列，的序列，12Niiiiax xx离

22、散平稳无记忆信源离散平稳无记忆信源lN N 次扩展信源的概率空间为次扩展信源的概率空间为28lN次扩展信源次扩展信源的熵的熵l离散平稳无记忆信源的离散平稳无记忆信源的N次扩展信源的熵等于离散单次扩展信源的熵等于离散单符号信源熵的符号信源熵的N倍倍1()()()log ()NqNiiiHH Xpp X()()()NHH XN H XXl离散平稳无记忆信源的熵率离散平稳无记忆信源的熵率1()lim()lim()()NNNHXHNH XH XNX离散平稳无记忆信源离散平稳无记忆信源29例例 设有一离散无记忆信源设有一离散无记忆信源X，其概率空间为，其概率空间为求该信源的熵率及二次扩展信源的熵。求该信

23、源的熵率及二次扩展信源的熵。123111244xxxXP X解解 离散单符号信源熵离散单符号信源熵321()()log()1.5iiiH Xp xp x 比特/符号() 1.5/HH X比特 符号熵率熵率30二次扩展信源的概率空间二次扩展信源的概率空间二次扩展信源的熵二次扩展信源的熵921()()()log ()3iiiHH Xpp X比特/符号211 121 231 342 152 262 373 183 293 32()()()()()()()()()1/ 41/81/81/81/161/161/81/161/16()x xx xx xx xx xx xx xx xx xXP X31l实际

24、信源常常是有记忆信源实际信源常常是有记忆信源. . 设信源输出设信源输出N N长的符号序列，长的符号序列，则可以用则可以用N N维随机变量序列维随机变量序列 来表示信源，其来表示信源，其中每个随机变量之间存在统计依赖关系中每个随机变量之间存在统计依赖关系. .lN N维随机变量序列的联合熵为维随机变量序列的联合熵为12NX XXX12()(,)NHH XXXX121312121()(|)(|)(|)NNH XH XXH XX XH XX XX离散平稳有记忆信源离散平稳有记忆信源3212314114936xxxXP X例例 信源信源X的信源模型为的信源模型为 输出符号序列中，只有前后输出符号序列

25、中，只有前后两个符号之间有记忆，条件两个符号之间有记忆，条件概率空间见右表。概率空间见右表。求熵率并求熵率并比较比较 H(X)、H(X2|X1) 、 1/2H(X1X2)的大小的大小.2X1X1x2x3x1x2x3x792901834180211911)|(12XXP条件概率条件概率 33解解 1)1) 121121lim(|)lim(|)(|)0.870NNNNNNHH XX XXH XXH XX比特比特/ /符号符号 2)2) 如果不考虑符号间的相关性，则信源熵为如果不考虑符号间的相关性，则信源熵为1 4 11()( ,)1.5424 9 36H XH比特比特/ /符号符号 3)3) 如果

26、把信源发出的符号看成是分组发出的，每两个如果把信源发出的符号看成是分组发出的，每两个 符号为一组，这个新信源的熵为符号为一组，这个新信源的熵为12121()()(|)2.412H X XH XH XX比特比特/ /两个符号两个符号 结论结论 121()()2HH X XH X34l马尔可夫信源是一类相对简单的有记忆信源马尔可夫信源是一类相对简单的有记忆信源. .l信源在某一时刻发出某一符号的概率，除与该符号信源在某一时刻发出某一符号的概率，除与该符号有关外，只与此前发出的有限个符号有关。或者说有关外，只与此前发出的有限个符号有关。或者说任何时刻信源符号发生的概率只与前面已经发生过任何时刻信源符

27、号发生的概率只与前面已经发生过的若干个符号有关，而与更前面的符号无关的若干个符号有关，而与更前面的符号无关. . (1) 定义定义马尔可夫信源马尔可夫信源35l对于对于 m 阶马尔可夫信源阶马尔可夫信源121111121lim(|)lim(|)(|)NNNNN mN mNNmmmHH XX XXH XXXXH XX XXH(2) 熵率熵率l如何计算条件熵？如何计算条件熵？ 条件概率条件概率 通常是已知的，我们通常是已知的，我们需要求解的是联合概率需要求解的是联合概率 . .112(|)mmP XX XX12()mP X XX马尔可夫信源马尔可夫信源362121mmmXXXXX 1212mmmi

28、iiiix xx xx isjs1212mmmS SS SS1121(|)(|)(|)mmmiiiiiijip xx xxp xsp ss(3) 马尔可夫信源马尔可夫信源 马尔可夫链马尔可夫链马尔可夫信源马尔可夫信源37例例1 1 设一个二元一阶马尔可夫信源，信源符号集为设一个二元一阶马尔可夫信源，信源符号集为 ， 输出符号的条件概率为输出符号的条件概率为1, 0X(0|0)0.25, (1|0)0.75, (0|1)0.5, (1|1)0.5,pppp用状态转移图来描述该信源。用状态转移图来描述该信源。11：0.750：0.51：0.50：0.250s2s1二元一阶马尔可夫信源的转移概率矩阵

29、与状态转移图二元一阶马尔可夫信源的转移概率矩阵与状态转移图0.250.750.50.538 0.80.200000.500000.20.821122121(,)01400 011011|, (|,)2)(iiiriiiiiiXXXPXxXx XxP xx x设为取值于，的二阶平稳马氏信源，其状态可用两个二进制数字表示，共有 种，信源的统计特性则由以下的转移概率简记例 二阶平稳为马氏信源信源状态转移概率矩阵和状态转移图为(0|00)0.8, (1|11)0.8, (1|00)(0|11)0.2(0|01)(0|10)(1|01)(1|10)0.5PPPPPPPP39原状态为原状

30、态为0000，则此刻只可能则此刻只可能发出发出0 0或或1.1.所以所以只可能转到只可能转到0000、0101状态状态. .由于由于0000状态时状态时发信号发信号0 0的概率的概率为为0.80.8，所以转，所以转移概率移概率.40 平稳遍历信源：即信源序列是平稳遍历信源：即信源序列是平稳遍历平稳遍历过程过程. 随机过程可以从随机过程可以从任一状态有限任一状态有限步到达任何步到达任何其他状态其他状态41 反例反例 例例3.3.非遍历信源非遍历信源状态转移图状态转移图 (1|00)(0|11)0PP类似于概率论中著名的类似于概率论中著名的两端带有吸收壁的随机两端带有吸收壁的随机游动

31、问题游动问题. .质点最终一定被两端点质点最终一定被两端点之一吸收！之一吸收！42（4）马尔可夫链）马尔可夫链 设设 为一随机序列，如果对所有为一随机序列，如果对所有 ，有，有则称则称 为为马尔可夫链马尔可夫链.,1nXn 1n 11111211|,|nnnnnnininiininiP XsXsXsXsp XsXs,1nXn 12,JSs ss12,Ss sl 如果马尔可夫链的状态空间如果马尔可夫链的状态空间 有限，则称有限，则称为为有限状态马尔可夫链有限状态马尔可夫链；如果状态空间；如果状态空间 是无穷是无穷集合，则称为集合，则称为可数无穷状态的马尔可夫链可数无穷状态的马尔可夫链. 马尔可夫

32、信源马尔可夫信源43l 状态转移概率状态转移概率（描述马氏链最重要的参数）（描述马氏链最重要的参数）l 状态转移概率的性质状态转移概率的性质l 一步转移概率一步转移概率l k步转移概率步转移概率 ( , )|ijnjminmpm nP XsXsP Xj Xi( )0( , )1( )( , )1ijijj Sipm niipm n( ,1)( )ijijpm mpm( )( )|kijm kmpmP Xj Xi马尔可夫信源马尔可夫信源44l 齐次马氏链可以用转移概率矩阵或状态转移图来描述齐次马氏链可以用转移概率矩阵或状态转移图来描述.111212122212JJJJJJpppppppppP11

33、：0.750：0.51：0.50：0.250s2s11( )(|)ijmjmiijp mP XsXsp如果马氏链状态转移概率与起始时刻无关，即对任意如果马氏链状态转移概率与起始时刻无关，即对任意m m，有有 ，则称为，则称为齐次马尔可夫链齐次马尔可夫链，也称具有也称具有平稳转移概率的马尔可夫链平稳转移概率的马尔可夫链. . 马尔可夫信源马尔可夫信源45l 信源的相关性信源的相关性就是信源符号间的依赖程度。就是信源符号间的依赖程度。l 设信源有设信源有q q个符号，那么对于不同情况可以分别计算信源个符号，那么对于不同情况可以分别计算信源的熵的熵0logHq11()HH X221(|)HH XX1

34、112(|)mmmHH XX XX121lim(|)NNNHH XX XX（独立等概信源）（独立等概信源）（平稳无记忆信源）（平稳无记忆信源）(一阶马尔可夫信源一阶马尔可夫信源) (有记忆有记忆)(m阶马尔可夫信源阶马尔可夫信源) (有记忆有记忆)（记忆长度无限的信源）（记忆长度无限的信源）7.7.信源的相关性和冗余度信源的相关性和冗余度46l 对同一信源，采用不同的模型，计算得到的熵的对同一信源，采用不同的模型，计算得到的熵的关系为关系为0121mHHHHHl 由此可见，由于信源输出符号之间的依赖关系而由此可见，由于信源输出符号之间的依赖关系而使信源的平均符号熵减少。如果它们之间的依赖关使信

35、源的平均符号熵减少。如果它们之间的依赖关系即相关性越大，信源的平均符号熵越小。并且，系即相关性越大，信源的平均符号熵越小。并且，只有当信源输出符号之间彼此独立且各符号以等概只有当信源输出符号之间彼此独立且各符号以等概率分布时，信源的符号熵才有最大值。为了衡量信率分布时，信源的符号熵才有最大值。为了衡量信源的相关性程度，引入信源冗余度的概念源的相关性程度，引入信源冗余度的概念。信源的相关性和冗余度信源的相关性和冗余度47l 信源熵的相对率信源熵的相对率：信源实际信息熵与具有同样：信源实际信息熵与具有同样符号集的最大熵的比值，通常也称为符号集的最大熵的比值，通常也称为效率效率。00(),()log

36、.()HXHXHXl 信源的冗余度信源的冗余度0111logHHRH 首先给出熵的相对率的定义首先给出熵的相对率的定义冗余度越低冗余度越低, ,信源输出信号携带信息的有效性越高信源输出信号携带信息的有效性越高. .l信源的信源的相对冗余度相对冗余度（剩余度）（剩余度）log()HX7.7.信源的相关性和冗余度信源的相关性和冗余度48例例 计算汉字的剩余度。计算汉字的剩余度。 假设常用汉字约为假设常用汉字约为10000个，其中个，其中140个汉字出个汉字出现的概率占现的概率占50%，625个汉字（含个汉字（含140个）出现的概个）出现的概率占率占85%，2400个汉字（含个汉字（含625个）出现

37、的概率占个）出现的概率占99.7%，其余，其余7600个汉字出现的概率占个汉字出现的概率占0.3%，不考，不考虑符号间的相关性，只考虑它的概率分布，在这一虑符号间的相关性，只考虑它的概率分布，在这一级近似下计算汉字的剩余度级近似下计算汉字的剩余度. .49解解 为了计算方便，假设每类中汉字出现是等概率的。为了计算方便，假设每类中汉字出现是等概率的。类别类别汉字个数汉字个数 所占概率所占概率每个汉字的概率每个汉字的概率11400.50.5/1402625-140=4850.85-0.5=0.350.35/48532400-625=17750.997-0.85=0.1470.147/1775476

38、000.0030.003/7600H1=H(X) =9.773 bit/汉字H0=13.288 bit/汉字 1010.264HRH 50 绪论中提到信源编码和信道编码。信源编码目的就绪论中提到信源编码和信道编码。信源编码目的就是通过减少或消除信源冗余度来提高信息传输效率；是通过减少或消除信源冗余度来提高信息传输效率；信道编码的目的是通过增加消息的冗余度来提高抗信道编码的目的是通过增加消息的冗余度来提高抗干扰能力，即提高信息传输的可靠性。因此，干扰能力，即提高信息传输的可靠性。因此，信源信源编码也称为有效性编码，信道编码也称为可靠性编编码也称为有效性编码，信道编码也称为可靠性编码。码。 由于信

39、源存在冗余度由于信源存在冗余度, ,即存在一些不必要传送的信息即存在一些不必要传送的信息, ,因此信源也就存在进一步压缩其信息率的可能性。因此信源也就存在进一步压缩其信息率的可能性。 信源冗余度越大信源冗余度越大, ,其进一步压缩的潜力越大。这是信其进一步压缩的潜力越大。这是信源编码与数据压缩的前提与理论基础。源编码与数据压缩的前提与理论基础。512.3 2.3 52 信息论中，渐近等分性是弱大数定理的应用信息论中，渐近等分性是弱大数定理的应用. . 大数定理大数定理指出：对于统计独立、有等同分布的随指出：对于统计独立、有等同分布的随机变量机变量 ，只要，只要n足够大，足够大， 就接近就接近数

40、学期望数学期望 渐近等分性渐近等分性指出，对于统计独立、有等同分布的指出，对于统计独立、有等同分布的随机变量随机变量 ，只要，只要n足够大，联合概率足够大，联合概率就接近信源熵就接近信源熵12,nXXX11niiXnE X12,nXXX()H X2.3 2.3 8. 8. 渐近等分性质渐近等分性质531212( ),(),.,()() (). ()(),().()knnnnnnnnXp xXH XXXXXP XP XP XP XP XXP XP X 设都是互相独立且服从相同的分布用表示有相同分布的生成变量 并设记由于信源的无记忆性,有. 因为是随机变量的函数 所以是随机变量 下面讨论的弱渐近等

41、分性(AEP).8. 8. 渐近等分性质渐近等分性质5412(,1)1log(). )knnnXkPXXXXXnH X 对无记忆信源,有依概率收敛到其中定理渐近等分性质渐近等分性质1211log()log() (). ()nnP XP XP XP Xnn 证11log ()(log()()nkkP XEp XH Xn .由于相互独立随机变量的函数也是随机变量及弱大数定理由于相互独立随机变量的函数也是随机变量及弱大数定理Xi是统计独立，是统计独立，且服从分布且服从分布p(x);视为一个扩展信源视为一个扩展信源55 定义定义 称满足性质称满足性质的的n长序列为弱典型序列，或长序列为弱典型序列，或

42、- -典型序列典型序列. . 记所有集为记所有集为1|log()()|1nrPp XH Xn ( ).nW定义式等价于：定义式等价于：( )( ):1nnnnrrP WPXXW 渐近等分性质渐近等分性质下面研究弱典型序列的性质：下面研究弱典型序列的性质：56( )1()log()(),nnnXWH XP XH Xn 这时对每个都有1log()(),1|log()() |1.nnrP XH XnPP XH Xn因为依概率收敛到即对0,( )( )( )1:|log()()|,:1.nnnnnnnrrWXP XH XnP WP XXW 记则()()()2.n H Xnn H Xp X即 2渐近等分

43、性质渐近等分性质弱弱典典型型序序列列的的性性质：质：57()()()()()()()()()()()()0,(1)()2;(2),:1;(3),1,(1).nnnHXnnHXnnnnrrnnHXnrnHXnnHnXXWp XnPWPXXWnWPWWW 对有若,则2当充 分 大 时 当充 分定大的 性 质2:理时22( )()| 2nn XW()()2nnH XP X58()( )()()2;,.nnH XnnnnH XXP XWX 定理说明了弱典型序列的概率弱典型序列集中元素个数但它不包括所有序列28. 8. 渐近等分性质渐近等分性质,ninXnX 因为若取值有限符号集则 长的序列的总数是弱典

44、型序列集在其中所占比例为( )()(log()log0.21()()log)nnH XnnH XnniWXp XxH X22(当不是均匀分布时,弱典型序列只占全体序列的一小部分！弱典型序列只占全体序列的一小部分！592.4 2.4 60 任何一个离散随机序列信源当序列长度任何一个离散随机序列信源当序列长度n n 时时, ,信源序列会产生两极分化：信源序列会产生两极分化： 大概率事件集合大概率事件集合 与小概率事件集合与小概率事件集合. . 由此可见，信源编码只需对信源中由此可见，信源编码只需对信源中少数少数落入典型落入典型大概率事件的集合的符号进行编码即可；大概率事件的集合的符号进行编码即可；

45、 而对而对大多数大多数属于非典型小概率事件集合中的信源属于非典型小概率事件集合中的信源符号无需编码符号无需编码. .码字总数减少，码字总数减少，所需码长可以减少所需码长可以减少2.42.4节节 9.9.信源编码定理信源编码定理611(,.,( ),nnXXXp xn 设)是服从公共分布的无记忆信源产生的 长序列 我们希望找到一种有效(1)编码以后的码字尽可能地少;(2)从码字复的编码方法原原序列的来描述这些序列,误差概率使得尽可能小.9.9.信源编码定理信源编码定理62( )( )( )( )( )1,2,.,.,nnnnnnnninnXWIMWXWiIXWXW 一一种种有有效效的的编编码码方方法法是是