21信源的描述和分类解析.pptx

1信源与信息熵信源与信息熵信源与信息熵信源与信息熵第二章第二章22.1 2.1 信源的描述和分类信源的描述和分类2.2 2.2 离散信源熵和互信息离散信源熵和互信息2.3 2.3 离散序列信源的熵离散序列信源的熵2.4 2.4 连续信源的熵和互信息连续信源的熵和互信息2.5 2.5 冗余度冗余度内容内容3本章重点本章重点信源熵和离散/连续互信息本章难点本章难点离散序列有记忆信源的熵42.1 2.1 信源的描述和分类信源的描述和分类5信源信源信源产生消息(符号)、消息序列和连续消息的来源产生随机变量、随机序列和随机过程的源。在通信系统中收信者在未收到消息以前对信源发出什么消息是不确定的,是随机的，所以可用随机变量、随机序列或随机过程来描述信源输出的消息,或者说用一个样本空间及其概率测度概率空间来描述信源 信源的基本特性：具有随机不确定性。6香农信息论的基本点香农信息论的基本点用随机变量或随机矢量来表示信源用概率论和随机过程的理论来研究信息7 信源离散信源离散信源:文字、数据、电报文字、数据、电报随机序列随机序列 连续信源连续信源:话音、图像话音、图像随机过程随机过程 信源的分类信源的分类按照信源发出的消息在按照信源发出的消息在时间时间上和上和幅度幅度上的分布上的分布情况可将信源分成离散信源和连续信源两大类情况可将信源分成离散信源和连续信源两大类 连续信源连续信源指发出在时间或幅度上是指发出在时间或幅度上是连续分布连续分布的连续消的连续消息（模拟消息）的信源，如语言、图像、图息（模拟消息）的信源，如语言、图像、图形等都是连续消息。形等都是连续消息。8离散信源离散无记忆信源离散有记忆信源发出单个符号的无记忆信源发出符号序列的无记忆信源发出符号序列的有记忆信源发出符号序列的马尔可夫信源信源的分类信源的分类离散信源指发出在时间和幅度上都是离散分布的离散消息的信源，如文字、数字、数据等符号都是离散消息。92.1.1 2.1.1 无无记忆信源记忆信源例：一个布袋内放例：一个布袋内放100个球，其中个球，其中80个红色，个红色，20个白色。若随机取一个球，看它的颜色。个白色。若随机取一个球，看它的颜色。将这样的试验看成一种信源，请描述该信源。将这样的试验看成一种信源，请描述该信源。记记a1=“红色红色”，a2=“白色白色”ai为随机变量为随机变量X 的样值的样值p(ai)为随机变量为随机变量X 取相应样值的概率取相应样值的概率102.1.1 2.1.1 无无记忆信源记忆信源离散无记忆信源离散无记忆信源所发出的各个符号是相互独立的，发出的符所发出的各个符号是相互独立的，发出的符号序列中的各个符号之间号序列中的各个符号之间没有统计关联性没有统计关联性，各个符号的出现概率是它自身的先验概率。各个符号的出现概率是它自身的先验概率。例如扔骰子，每次试验结果必然是例如扔骰子，每次试验结果必然是16点中的点中的某一个面朝上。某一个面朝上。用一个离散型随机变量用一个离散型随机变量X来描述这个信源输出来描述这个信源输出的消息。的消息。11发出单个符号的信源发出单个符号的信源指信源每次只发出一个符号代表一个消息；指信源每次只发出一个符号代表一个消息；发出符号序列的信源发出符号序列的信源指信源每次发出一组含二个以上符号的符号指信源每次发出一组含二个以上符号的符号序列代表一个消息序列代表一个消息离散离散无无记忆信源记忆信源12信源的描述信源的描述一个离散信源发出的各个符号消息的集合为：一个离散信源发出的各个符号消息的集合为：它们的概率分别为它们的概率分别为p(xi):xi的的先验概率先验概率单符号单符号离散离散信源的数学模型信源的数学模型概率空间概率空间a,b,c,z13离散信源的统计特性离散信源的统计特性离散消息是从有限个符号组成的符号集中选择离散消息是从有限个符号组成的符号集中选择排列组成的随机序列（组成离散消息的信息源排列组成的随机序列（组成离散消息的信息源的符号个数是有限的）的符号个数是有限的）在形成消息时，从符号集中选择各个符号的概在形成消息时，从符号集中选择各个符号的概率不同率不同。组成消息的基本符号之间有一定的统计相关特组成消息的基本符号之间有一定的统计相关特性性。14信源的描述信源的描述连续信源连续信源：输出在时间或幅度上是连续分布的消息输出在时间或幅度上是连续分布的消息 单符号单符号连续连续无记忆信源的无记忆信源的概率空间概率空间 随机取一节干电池测其电压值作为输出符号,符号取值为0,1.5之间的所有实数。该信源就是发出单符号的连续无记忆信源Px x(x)为符号分布的概率密度函数为符号分布的概率密度函数15信源的描述信源的描述发出发出符号序列符号序列的信源的信源设信源输出的随机序列为设信源输出的随机序列为 X=(X1X2XlXL)序列中的变量序列中的变量Xlx1,x2,xn这种由信源这种由信源X输出的输出的L长随机序列长随机序列X所描述的信所描述的信源称为离散无记忆信源源称为离散无记忆信源X的的L次扩展信源次扩展信源 布袋摸球，每次取两个球，球的颜色组成的消息就是符号序列。该信源就是发出符号序列的无记忆信源。(有放回)16例：例：80个红球，个红球，20个白球，随机摸两个，描个白球，随机摸两个，描述该信源（有放回）。述该信源（有放回）。17信源的描述信源的描述随机序列的概率当信源无记忆时 18一般情况下一般情况下,信源在不同时刻发出的符号之间信源在不同时刻发出的符号之间是是相互依赖相互依赖的，也就是信源输出的平稳随机序的，也就是信源输出的平稳随机序列列X中，各随机变量中，各随机变量Xl之间是有依赖的。之间是有依赖的。如在汉字序列中前后文字的出现是有依赖的，如在汉字序列中前后文字的出现是有依赖的，不能认为是彼此不相关的。不能认为是彼此不相关的。表述有记忆信源要比表述无记忆信源困难得多表述有记忆信源要比表述无记忆信源困难得多离散有记忆信源离散有记忆信源所发出的各个符号的概率是所发出的各个符号的概率是有关联有关联的。的。发出符号序列的有记忆信源发出符号序列的有记忆信源发出符号序列的马尔可夫信源发出符号序列的马尔可夫信源2.1.22.1.2 有记忆信源有记忆信源用信源发出的一个符号序列的整体概率(即联合概率)反映有记忆信源的特征一个符号出现的概率只与前面一个或有限个符号有关,而不依赖更前面的那些符号19概率论基础概率论基础无条件概率、条件概率、联合概率的性质和关系20概率论基础概率论基础无条件概率、条件概率、联合概率的性质和关系无条件概率、条件概率、联合概率的性质和关系212.1.3 2.1.3 马尔可夫信源马尔可夫信源马尔可夫信源马尔可夫信源该信源在某一时刻发出字母的该信源在某一时刻发出字母的概率概率除与该字除与该字母有关外母有关外,只与此前发出的只与此前发出的有限有限个字母有关个字母有关m阶马尔可夫信源阶马尔可夫信源：信源输出某一符号的概率仅与以前的信源输出某一符号的概率仅与以前的m个符个符号有关，而与更前面的符号无关。号有关，而与更前面的符号无关。条件概率条件概率22马氏链的基本概念马氏链的基本概念 一阶马尔可夫信源由于高阶马尔可夫链需要引入矢量进行分析运算，由于高阶马尔可夫链需要引入矢量进行分析运算，处理过程复杂。可将矢量转化为处理过程复杂。可将矢量转化为状态变量状态变量，通过，通过分析系统状态在输入符号作用下得转移情况，使分析系统状态在输入符号作用下得转移情况，使高阶马尔可夫过程化为一阶马尔可夫过程来处理。高阶马尔可夫过程化为一阶马尔可夫过程来处理。23马氏链的基本概念马氏链的基本概念 对于对于m阶马尔可夫信源，将该时刻以前出阶马尔可夫信源，将该时刻以前出现的现的m个符号个符号组成的序列定义为状态组成的序列定义为状态si令令si=(xi1,xi2,xim)xi1,xi2,xim(a1,a2,an)状态集状态集S=s1,s2,sQ Q=nm信源输出的随机信源输出的随机符号符号序列为序列为：x1,x2,x i-1,x i信源所处的随机信源所处的随机状态状态序列为序列为：s1,s2,si-1,si,24例例：二元序列为：二元序列为01011100考虑考虑m=2，Q=nm=22=4s1=00 s2=01 s3=10 s4=11变换成对应的变换成对应的状态序列状态序列为为 s2 s3 s2 s4 s4 s3 s125当信源符号出现后，信源所处的状态将当信源符号出现后，信源所处的状态将发生变化，并转入一个新的状态。这种发生变化，并转入一个新的状态。这种状态的转移可用状态的转移可用状态转移概率状态转移概率表示为：表示为：p（sj|si），i,j=1,2,Q。更一般地，在时刻更一般地，在时刻m系统处于状态系统处于状态si的条的条件下，经件下，经n-m步后转移到状态的概率用步后转移到状态的概率用pij(m,n)表示表示:pij(m,n)=pSn=sj|Sm=si=psj|si 其中其中si,sj S马尔可夫信源马尔可夫信源26马尔可夫信源马尔可夫信源设信源在时刻设信源在时刻m处于处于si状态状态,它在下一时刻它在下一时刻(m+1)状状态转移到态转移到sj的的转移概率转移概率为：为：pij(m)=pSm+1=sj|Sm=si=psj|sipij(m)：基本转移概率基本转移概率（一步转移概率）（一步转移概率）若若pij(m)与与m 的取值无关的取值无关,则称为则称为齐次齐次马尔可夫链马尔可夫链 pij=pSm+1=j|Sm=i pij具有下列性质具有下列性质：pij0,i,j S27若信源处于某一状态若信源处于某一状态si,当它发出一个符号后当它发出一个符号后,所所处状态就变了处状态就变了,任何时候信源处于什么状态完全任何时候信源处于什么状态完全由前一时刻的状态和发出符号决定。由前一时刻的状态和发出符号决定。系统在任一时刻可处于状态空间系统在任一时刻可处于状态空间S=s1,s2,sQ中的任意一个状态中的任意一个状态,状态转移时状态转移时,转移概率矩阵转移概率矩阵符号条件概率矩阵第第i行对应从某一个状行对应从某一个状态态si转移到所有状态转移到所有状态sj的的转移概率，非负，并且转移概率，非负，并且每行之和均为每行之和均为1第第j列元素对应从所有列元素对应从所有状态状态si转移到同一状态转移到同一状态sj的转移概率，每列之和的转移概率，每列之和不一定为不一定为128例例2-1，如图所示是一个相对码编码器如图所示是一个相对码编码器,输入的码输入的码Xr(r=1,2,)是相互独立的，取值是相互独立的，取值0或或1，且已知，且已知P(X=0)=p,P(X=1)=1p=q，输出的码是，输出的码是Yr，显然，显然TXrYrYr-1+Yr是一个是一个马氏链马氏链,Yr确定后确定后,Yr+1概率分布只与概率分布只与Yr有有关关,与与Yr-1、Yr-2 等无关等无关,且知且知Yr序列的条件概率序列的条件概率29sos1pqqpp00=P(Y2=0/Y1=0)=P(X=0)=p p01=P(Y2=1/Y1=0)=P(X=1)=q p10=P(Y2=0/Y1=1)=P(X=1)=q p11=P(Y2=1/Y1=1)=P(X=0)=p 30马尔可夫信源马尔可夫信源状态转移图状态转移图齐次马尔可夫链可以用其齐次马尔可夫链可以用其状态转移图状态转移图(香农线图香农线图)表示表示每个圆圈代表一种每个圆圈代表一种状态状态 状态之间的有向线代表某状态之间的有向线代表某一状态向另一状态的一状态向另一状态的转移转移有向线一侧的符号和数字有向线一侧的符号和数字分别代表发出的分别代表发出的符号符号和和条条件概率件概率sos11/0.60/0.30/0.4s21/0.20/0.81/0.731s3s2s4s5s1s6周期性：在常返态中,有些状态仅当k能被某整数d1整除时才有pij(k)0,图中的周期为2x5:1非周期性：对于pij(k)0的所有k值，其最大公约数为1 常返态：经有限步后迟早要返回的状态x4:1x3:1/2x2:1/2x3:1/2x2:1/2x2:1/2x4:1/4x1:1/4x6:1x6:1/432马尔可夫信源马尔可夫信源遍历状态遍历状态非周期的、常返的状态非周期的、常返的状态,如图中的状态如图中的状态s2和和s3闭集闭集状态空间中的某一子集中的任何一状态都不状态空间中的某一子集中的任何一状态都不能到达子集以外的任何状态能到达子集以外的任何状态不可约的不可约的闭集中除自身全体外再没有其他闭集的闭集闭集中除自身全体外再没有其他闭集的闭集33马尔可夫信源马尔可夫信源一个一个不可约的、非周期的、状态有限不可约的、非周期的、状态有限的马尔可的马尔可夫链其夫链其k步转移概率步转移概率pij(k)在在k时趋于一个和时趋于一个和初始状态无关的初始状态无关的极限概率极限概率Wj，它是满足方程组，它是满足方程组 的唯一解；的唯一解；Wj：马尔可夫链的一个：马尔可夫链的一个平稳分布平稳分布，Wj p(sj)就是系统此时处于状态就是系统此时处于状态sj的概率。的概率。34sos11/0.60/0.30/0.4s21/0.20/0.81/0.7练习：35例例2-2：有一个二元二阶马尔可夫信源有一个二元二阶马尔可夫信源,其信其信源符号集为源符号集为0，1，已知符号条件概率：，已知符号条件概率：p(0|00)=1/2 p(1|00)=1/2 p(0|01)=1/3 p(1|01)=2/3 p(0|10)=1/4 p(1|10)=3/4 p(0|11)=1/5 p(1|11)=4/5求：求：信源全部状态及状态转移概率；信源全部状态及状态转移概率；画出完整的二阶马尔可夫信源状态转移图；画出完整的二阶马尔可夫信源状态转移图；求平稳分布概率求平稳分布概率 36状态转移状态转移概率矩阵概率矩阵符号符号条件概率矩阵条件概率矩阵(1)1/2(0)1/2(0)1/3(1)2/300011110s2s1s4s3(1)3/4(0)1/4(0)1/5(1)4/537稳态分布概率稳态分布概率稳态后的符号概率分布稳态后的符号概率分布38例：例：一个二元二阶马尔可夫信源一个二元二阶马尔可夫信源,其信源符号集为其信源符号集为0,1信源开始时信源开始时：p(0)=p(1)=0.5发出随机变量发出随机变量X1。下一单位时间下一单位时间：输出随机变量：输出随机变量X2与与X1有依赖关系有依赖关系x2x10100.30.410.70.6p(x2|x1)再下一单位时间：输出随机变量X3与X2X1有依赖关系x3x1 x20001101100.40.20.30.410.60.80.70.6p(x3|x1x2)39从第四单位时间开始，随机变量从第四单位时间开始，随机变量Xi只与前面二只与前面二个单位时间的随机变量个单位时间的随机变量Xi-2Xi-1有依赖关系有依赖关系:p(xi|xi-1 xi-2x2 x1)=p(xi|xi-1 xi-2)(i3)且且 p(xi|xi-1 xi-2)=p(x3|x2x1)(i3)解解:设信源开始处于设信源开始处于s0状态状态,以等概率发出符号以等概率发出符号0和和1,分分别到达状态别到达状态s1和和s2;若处于若处于s1,以以0.3和和0.7的概率的概率发出发出0和和1到达到达s3和和s4;若处于若处于s2,以以0.4和和0.6的概率的概率发出发出0和和1到达到达s5和和s6。00011011(0)0.5(1)0.5(0)0.3(0)0.4(1)0.7(1)0.6s1s2s0s6s5s4s340信源发完第信源发完第2个符号后再发第个符号后再发第3个及以后的符号。个及以后的符号。从第从第3单位时间以后信源必处在单位时间以后信源必处在s3 s4 s5 s6四种状态四种状态之一。在之一。在i3后后,信源的状态转移可用下图表示信源的状态转移可用下图表示:10110100(0)0.3(0)0.4(1)0.7(0)0.2(1)0.8(1)0.6(0)0.4(1)0.6状态状态s1和和s5功能是完全相同功能是完全相同 状态状态s2和和s6功能是完全相同功能是完全相同可将二图合并成可将二图合并成s3s4s5s6s0(0)0.5(1)0.5s0是过渡状态是过渡状态s3 s4 s5 s6组成一个不组成一个不可约闭集可约闭集,并且具有并且具有遍历性。遍历性。41由题意由题意,此马尔可夫信源的状态必然会进入这个此马尔可夫信源的状态必然会进入这个不可约闭集不可约闭集,所以我们计算信源熵时可以不考虑所以我们计算信源熵时可以不考虑过渡状态及过渡过程。过渡状态及过渡过程。由由 得稳态分布概率42当马尔可夫信源达到稳定后当马尔可夫信源达到稳定后,符号符号0和符号和符号1的概率分布：的概率分布：信源达到稳定后，信源符号的概率分布与初始信源达到稳定后，信源符号的概率分布与初始时刻的概率分布是不同的，所以，一般马尔可时刻的概率分布是不同的，所以，一般马尔可夫信源并非是平稳信源。夫信源并非是平稳信源。但当时齐、遍历的马尔可夫信源达到稳定后，但当时齐、遍历的马尔可夫信源达到稳定后，这时就可以看成一个平稳信源。这时就可以看成一个平稳信源。43习题习题2-12-2