信息论第二章

信息论第二章第一页，共四十六页，2022年，8月28日2数字通信系统模型信道信源信源编码加密信道编码干扰源信宿信源解码解密信道解码加密密钥解密密钥uxykzvz'y'x'第二页，共四十六页，2022年，8月28日32.1信源的描述和分类2.2离散信源熵和互信息2.3离散序列信源的熵2.4连续信源的熵和互信息2.5冗余度内容第三页，共四十六页，2022年，8月28日4重难点本章重点

信源的统计特性和数学模型、离散信源熵及其性质、互信息本章难点马尔科夫信源、离散序列有记忆信源的熵2.1信源的描述和分类2.2离散信源熵和互信息2.3离散序列信源的熵2.4连续信源的熵和互信息2.5冗余度第四页，共四十六页，2022年，8月28日52.1信源的描述和分类第五页，共四十六页，2022年，8月28日内容2.1.1无记忆信源2.1.2有记忆信源2.1.3马尔科夫信源6第六页，共四十六页，2022年，8月28日7信源信源产生消息(符号)、消息序列和连续消息的来源产生随机变量、随机序列和随机过程的源。在通信系统中收信者在未收到消息以前对信源发出什么消息是不确定的,是随机的，所以可用随机变量、随机序列或随机过程来描述信源输出的消息,或者说用一个样本空间及其概率测度—概率空间来描述信源信源的基本特性：具有随机不确定性。第七页，共四十六页，2022年，8月28日8香农信息论的基本点用随机变量或随机矢量来表示信源用概率论和随机过程的理论来研究信息第八页，共四十六页，2022年，8月28日9一、信源分类2、离散信源：文字、数字、数据等符号{离散无记忆信源离散有记忆信源{{发出单个符号的无记忆信源发出符号序列的无记忆信源发出符号序列的有记忆信源发出符号序列的马尔可夫信源1、连续信源：语音、图像、图形从信源发出的消息在时间上和幅度上的分布第九页，共四十六页，2022年，8月28日10根据人们对信源消息的感知分为数据信源、文本信源、语音信源、图像信源等，其中文本信源和语音信源都是针对人类语言、文字、声乐等感知的，又通称为自然语信源。从描述信源消息的随机过程的平稳性角度分为平稳信源和非平稳信源第十页，共四十六页，2022年，8月28日11信源的分类方法可以有多种，但本质上主要基于两方面的考虑：一是信源消息取值的集合以及消息取值时刻的集合，由此可分为离散信源、连续信源等；二是信源消息的统计特性，由此可分为无记忆（Memoryless）信源、有记忆（Memory）源、平稳信源、非平稳信源、高斯信源、马尔可夫信源等。第十一页，共四十六页，2022年，8月28日122.1.1无记忆信源一、发出单个符号的无记忆离散信源：发出的消息是离散的，且一个符号代表一条完整的消息。消息数为有限或无限可列。用一维离散变量X来描述。例如扔骰子，每次试验结果必然是1～6点中的某一个面朝上。用一个离散型随机变量X来描述这个信源输出的消息。第十二页，共四十六页，2022年，8月28日13在实际情况中，存在着很多这样的信源、例如投硬币、书信文字、计算机的代码、电报符号、阿拉伯数字码等等。这些信源输出的都是单个符号（或代码）的消息，它们符号集的取值是有限的或可数的。第十三页，共四十六页，2022年，8月28日14信源的描述一个离散信源发出的各个符号消息的集合为：它们的概率分别为p(xi):xi的先验概率单符号离散信源的数学模型—概率空间a,b,c,…z第十四页，共四十六页，2022年，8月28日15二、发出单个符号的连续无记忆信源：输出是的单个符号的消息，消息的数量是无限的。可用一维连续型随机变量X描述单符号连续无记忆信源的概率空间消息的集合

随机取一节干电池测其电压值作为输出符号,符号取值为[0,1.5]之间的所有实数。

该信源就是发出单符号的连续无记忆信源第十五页，共四十六页，2022年，8月28日16上述的离散信源和连续信源是最简单最基本的情况，信源输出只输出一个消息符号，所以可以用随机变量来描述。信源的描述第十六页，共四十六页，2022年，8月28日17三、发出符号序列的信源：输出的消息由符号序列组成，用随机矢量X=(X1X2…Xl…XL)描述。需要用联合概率分布表示信源特性。

L=2，X=(X1,X2)，其信源的概率空间为第十七页，共四十六页，2022年，8月28日18信源的描述随机序列的概率—联合概率当信源无记忆时，即Xl(l=1,…,L)之间是无依赖的、统计独立的，则随机矢量的联合概率分布满足：第十八页，共四十六页，2022年，8月28日19离散信源X(n个信源符号)的每次输出L长符号序列消息x=(x1…xl…xL)x共有nL=n×n×…×n（共L个）种组合，即每个随机变量取值有n种，那么L个随机变量组成的随机序列，其样值共有nL种可能取值。有时将这种由信源X输出的L长随机序列X所描述的信源叫做离散信源X的L次扩展信源。L次扩展信源第十九页，共四十六页，2022年，8月28日20一般情况下,信源在不同时刻发出的符号之间是相互依赖的，也就是信源输出的平稳随机序列X中，各随机变量Xl之间是有依赖的。如在汉字序列中前后文字的出现是有依赖的，不能认为是彼此不相关的。

有记忆信源第二十页，共四十六页，2022年，8月28日21离散有记忆序列信源：当信源输出的随机矢量中各个分量之间不相互独立而可以是任意相关的,则称此类信源为有记忆信源。布袋摸球实验，每次取出两个球，由两个球的颜色组成的消息就是符号序列。若每次先取出一个球，记下颜色不放回布袋，再取第二个球。第二十一页，共四十六页，2022年，8月28日22表述有记忆信源要比表述无记忆信源困难得多需在N维随机矢量的联合概率分布中，引入条件概率分布来说明它们之间的关联。第二十二页，共四十六页，2022年，8月28日232.1.3马尔可夫信源马尔可夫信源一类相对简单的离散平稳有记忆信源该信源在某一时刻发出字母的概率除与该字母有关外,只与此前发出的有限个字母有关m阶马尔可夫信源：信源输出某一符号的概率仅与以前的m个符号有关，而与更前面的符号无关。条件概率一阶马尔可夫信源：第二十三页，共四十六页，2022年，8月28日24马氏链的状态变量若把前面有限个字母记作一个状态S，则信源某一时刻发出某一字母的概率除与该字母有关外，只与该时刻信源所处的状态有关。信源将来的状态及其送出的字母将只与信源现在的状态有关，而与信源过去的状态无关。引入状态变量的好处：使得高阶马尔科夫过程可以转化为一阶马尔科夫过程处理。假设m阶马尔可夫信源的一个状态含有m个字母第二十四页，共四十六页，2022年，8月28日25马氏链的基本概念令si

=(xi1,

xi2,

…xim)xi1,,xi2,

…xim

∈{a1,

a2,

…an}状态集S={s1,s2,…,sQ}Q=nm（状态数目）信源输出的随机符号序列为：x1,x2,…xi-1,xi…信源所处的随机状态序列为：s1,s2,…si-1,si

…例：二元序列为…01011100…考虑m=2，Q=nm=22=4s1=00s2=01s3=10s4=11变换成对应的状态序列为

…s2s3s2s4s4s3s1……01011100…第二十五页，共四十六页，2022年，8月28日26转移概率设信源在时刻m处于si状态,它在下一时刻(m+1)状态转移到sj的转移概率为：

pij(m)=p{Sm+1=sj|Sm=si}=p{sj|si}pij(m)：基本转移概率（一步转移概率）齐次马尔可夫链：pij(m)与m的取值无关,则

pij=p{Sm+1=sj|Sm=si}=p{S2=sj|S1=si}pij具有下列性质：

pij≥0第二十六页，共四十六页，2022年，8月28日27若信源处于某一状态si,当它发出一个符号后,所处状态就变了,任何时候信源处于什么状态完全由前一时刻的状态和发出符号决定。系统在任一时刻可处于状态空间S={s1,s2,…,sQ}中的任意一个状态,状态转移时,转移概率矩阵符号条件概率矩阵区别第二十七页，共四十六页，2022年，8月28日28例2-1，如图所示是一个相对码编码器,输入的码Xr(r=1,2,…)是相互独立的，取值0或1，且已知P(X=0)=p,P(X=1)=1－p=q，输出的码是Yr。TXrYrYr-1+Yr是一个二元一阶马氏链,Yr确定后,Yr+1概率分布只与Yr有关,与Yr-1

、Yr-2…等无关。注：⊕模2加第二十八页，共四十六页，2022年，8月28日29sos1pqqpp00=P(Y2=0/Y1=0)=P(X=0)=p状态转移矩阵与时刻无关，所以是齐次的。Yr的状态转移概率：p01=P(Y2=1/Y1=0)=P(X=1)=qp10=P(Y2=0/Y1=1)=P(X=1)=qp11=P(Y2=1/Y1=1)=P(X=0)=p

第二十九页，共四十六页，2022年，8月28日30马尔可夫信源状态转移图齐次马尔可夫链可以用其状态转移图(香农线图)表示每个圆圈代表一种状态

状态之间的有向线代表某一状态向另一状态的转移有向线一侧的符号和数字分别代表发出的符号和条件概率sos11/0.60/0.30/0.4s21/0.20/0.81/0.7第三十页，共四十六页，2022年，8月28日例2设一个二元一阶马尔科夫信源，信源符号集X={0,1}，信源输出符号的条件概率为p(0|0)=0.25,p(0|1)=0.5,p(1|0)=0.75,p(1|1)=0.5求状态转移概率，画出状态转移图。解：311/0.750/0.51/0.5第三十一页，共四十六页，2022年，8月28日例3设有一个二元二阶马尔科夫信源，其信源符号集X={0,1}.状态变化如下：在状态为01时，若出现0，将零附到01后将第一位0挤出，状态变为10.其他状态变化过程类似。信源输出符号的条件概率为P(0|00)=p(1|11)=0.8,p(1|00)=p(0|11)=0.2，p(0|01)=p(0|10)=p(1|01)=p(1|10)=0.5求状态转移概率矩阵，画出状态转移图解：32第三十二页，共四十六页，2022年，8月28日33010/0.80/0.51/0.20/0.51/0.51/0.50/0.21/0.8第三十三页，共四十六页，2022年，8月28日34齐次马尔可夫链中的状态可以根据其性质进行分类:1、如状态si经若干步后总能到达状态sj，即存在k,使pij(k)＞0，则称si可到达sj;若两个状态相互可到达,则称此二状态相通；2、过渡态：一个状态经过若干步以后总能到达某一其他状态，但不能从其他状态返回；3、吸收态：不能到达其他任何状态的状态；4、常返态：经有限步后迟早要返回的状态；5、周期性的：在常返态中，状态中仅当k能被某整数d＞1整除时才有pii(k)＞0；6、非周期性的：对于pii(k)＞0的所有k值，其最大公约数为1。第三十四页，共四十六页，2022年，8月28日35s3s2s4s5s1s6周期性的：在常返态中,状态中仅当k能被某整数d＞1整除时才有pii(k)＞0,图中的周期为2；x5:1非周期性的：对于pii(k)＞0的所有k值，其最大公约数为1。常返态：经有限步后迟早要返回的状态，x4:1x3:1/2x2:1/2x3:1/2x2:1/2x2:1/2x4:1/4x1:1/4x6:1x6:1/4过渡态吸收态相通第三十五页，共四十六页，2022年，8月28日36马尔可夫信源遍历状态：非周期的常返状态,如图中的状态s2和s3闭集：状态空间中的某一子集中的任何一状态都不能到达子集以外的任何状态不可约的：闭集中除自身全体外再没有其他闭集特殊结论第三十六页，共四十六页，2022年，8月28日37马尔可夫信源一个不可约的、非周期的、状态有限的马尔可夫链其k步转移概率pij(k)在k→∞时趋于一个和初始状态无关的极限概率Wj，它是满足方程组的唯一解；Wj

：马尔可夫链的一个平稳分布，

Wj[或p(sj)]就是系统此时处于状态sj的概率。无论随机点从哪一个状态si出发，当转移的步数k足够大时，转移到状态sj的概率pij(k)都近似于一个常数Wj第三十七页，共四十六页，2022年，8月28日38sos11/0.60/0.30/0.4s21/0.20/0.81/0.7例4：求马尔科夫链的稳态分布律第三十八页，共四十六页，2022年，8月28日39例5：有一个二元二阶马尔可夫信源,其信源符号集为{0，1}，已知符号条件概率：

p(0|00)=1/2p(1|00)=1/2p(0|01)=1/3p(1|01)=2/3p(0|10)=1/4p(1|10)=3/4p(0|11)=1/5p(1|11)=4/5求：⑴信源全部状态及状态转移概率⑵画出完整的二阶马尔可夫信源状态转移图。⑶求稳定后的状态分布概率以及符号分布概率

第三十九页，共四十六页，2022年，8月28日40状态转移概率矩阵符号条件概率矩阵(1)1/2(0)1/2(0)1/3(1)2/300011110s2s1s4s3(1)3/4(0)1/4(0)1/5(1)4/5第四十页，共四十六页，2022年，8月28日41稳态分布概率稳态后的符号概率分布第四十一页，共四十六页，2022年，8月28日42例6

一个二元二阶马尔可夫信源,其信源符号集为{0,1}信源开始时：p(0)=p(1)=0.5发出随机变量X1。

下一单位时间：输出随机变量X2与X1有依赖关系x2x10100.30.410.70.6p(x2|x1)再下一单位时间：输出随机变量X3与X2X1有依赖关系x3x1x20001101100.40.20.30.410.60.80.70.6p(x3|x1x2)第四十二页，共四十六页，2022年，8月28日从第四单位时间开始，随机变量Xi只与前面二个单位时间的随机变量Xi-2Xi-1有依赖关系:p(xi|xi-1

xi-2…x2

x1)=p(xi|xi-1

xi-2)(i＞3)且

p(xi|xi-1

xi-2)=p(x3|x2x1)(i＞3)求：⑴信源状态转移情况和相应概率；⑵画出完整的二阶马尔可夫信源状态转移图；⑶求平稳分布概率；

（4）马尔科夫信源达到稳定后，0和1的分布概率。

第四十三页，共四十六页，2022年，8月28日44练习2-12-2第四十四页，共四十六页，2022年，8月28日45马尔可夫链马尔可夫链，因安德烈•马尔可夫（，1856－1922）得名，是数学