《信息论与编码第2章》由会员分享，可在线阅读，更多相关《信息论与编码第2章（100页珍藏版）》请在金锄头文库上搜索。
1、信道的通信能力可以度量吗？在有干扰的信道上可以进行无差错的通信吗？,2,第2章 信源及信息度量,信源的数学模型和分类 离散信源熵和互信息离散序列信源熵连续信源熵和互信息冗余度,3,2.1信源的数学模型和分类,信源顾名思义是产生消息的源头，从数学的角度，它产生随机变量、随机序列和随机过程的源。在这里信源指从信源发出的消息。 信源的基本特性是具有随机属性和概率统计特性,4,2.1信源的数学模型和分类,分类 按照信源发出的消息在时间上和幅度上的分布情况，把信源分为： (1) 连续信源（continuous source）：发出在时间上或幅度上是连续分布（只要满足其中之一）的连续消息的信源，如话音、图
2、像，可以认为是一个随机过程。(2) 离散信源（discrete source）：发出在时间上和幅度上都是离散分布的信源。消息的符号的取值是有限的或可数的，且两两不相容。如文字、数据、电报。可以认为是一个随机变量或者随机序列。,5,2.1信源的数学模型和分类,分类 按照信源发出的消息在时间上和幅度上的分布情况，把信源分为： (1) 连续信源（continuous source）：发出在时间上或幅度上是连续分布（只要满足其中之一）的连续消息的信源，如话音、图像，可以认为是一个随机过程。(2) 离散信源（discrete source）：发出在时间上和幅度上都是离散分布的信源。消息的符号的取值是有限
3、的或可数的，且两两不相容。如文字、数据、电报。可以认为是一个随机变量或者随机序列。,6,2.1信源的数学模型和分类,分类离散信源可以根据符号间关系细分为： (1) 离散无记忆信源（discrete memoryless source）：所发出的各个符号之间是相互独立的，发出的符号序列中的各个符号之间没有统计关联性，各个符号的出现概率是它自身的先验概率。(2) 离散有记忆信源（discrete source with memory）：发出的各个符号之间不是相互独立的，各个符号出现的概率是有关联的。,7,2.1信源的数学模型和分类,分类 也可以根据信源发出一个消息所用符号的多少，将离散信源分为 ：
4、 (1) 离散无记忆信源（discrete memoryless source）：所发出的各个符号之间是相互独立的，发出的符号序列中的各个符号之间没有统计关联性，各个符号的出现概率是它自身的先验概率。(2) 离散有记忆信源（discrete source with memory）：发出的各个符号之间不是相互独立的，各个符号出现的概率是有关联的。,8,2.1信源的数学模型和分类,分类 将以上两种分类结合，主要有下面几种离散信源： (1) 发出单个符号的无记忆离散信源；(2) 发出符号序列的无记忆离散信源；(3) 发出符号序列的有记忆离散信源。 当有记忆信源的相关性涉及到前面所有符号的时候，随着序
5、列的增加，相关性的符号也会增加，当序列可能无限长的时候，记忆的长度也是无限的，因此为了简化问题，一类有限记忆、定长记忆、记忆是邻近的离散信源被提出，即马尔可夫信源：某一个符号出现的概率只与前面一个或有限个符号有关，而不依赖更前面的那些符号。,9,2.1信源的数学模型和分类,分类,10,2.1.1 离散无记忆信源,例2-1 扔骰子每次试验结果必然是16点中的某一个面朝上。可以用一个离散型随机变量X来描述这个信源输出的消息。 并满足 需要注意的是，大写字母X代表随机变量，指的是信源整体。带下标的小写字母xi代表随机事件的某一具体的结果或信源的某个元素（符号）。在信息论教材中一般如此约定,11,2.
6、1.1 离散无记忆信源,我们可用一维离散型随机变量X来描述这些信息的输出。这样的信息称为离散信源。其数学模型就是离散型的概率空间： 0p(xi)1 其中，p(xi)：信源输出符号xi（i =1，2，n）的先验概率。当信源给定，其相应的概率空间就已给定；反之，如果概率空间给定，这就表示相应的信源已给定。所以概率空间能表征这离散信源的统计特性。以上的信息表达方式存在局限性吗？对于具体的信息，经过以上表示中去掉了那些因素？,2.1.1 离散无记忆信源,上式表示信源可能的消息（符号）数是有限的，只有n个：x1， x2， ，xn，而且每次必定选取其中一个消息输出，满足完备集条件。这是最基本的离散信源。有
7、的信源输出的消息也是单个符号，但消息的数量是无限的，如符号集A的取值是介于a和b之间的连续值，或者取值为实数集R等。连续信源：输出在时间和幅度上都是连续分布的消息。消息数是无限的或不可数的，且每次只输出其中一个消息。我们可用一维的连续型随机变量X来描述这些消息。其数学模型是连续型的概率空间p(x)是随机变量X的概率密度函数。,2.1.1 离散无记忆信源,例如：随机取一干电池，测电压值作为输出符号，该信源每次输出一个符号，但符号的取值是在0，1.5之间的所有实数，每次测量值是随机的，可用连续型随机变最X来描述。很多实际信源输出的消息是由一系列符号组成，这种用每次发出1组含2个以上符号的符号序列来
8、代表一个消息的信源叫做发出符号序列的信源。需要用随机序列(随机矢量) X =（X1X2XlXL）来描述信源输出的消息，用联合概率分布来表示信源特件。,2.1.2 离散有记忆信源,例2-2 布袋中有100个球，80个红球，20个白球。先取出一个球，记下颜色后不放回布袋，接着取另一个。而在取第二个球时布袋中的红球、白球概率已与取第一个球时不同，此时的概率分布与第1个球的颜色有关：若第1个球为红色，则取第二个球时的概率p(a1)= 79/99，p(a2)= 20/99若第1个球为白色，则取第二个球时的概率p(a1)=80/99，p(a2)=19/99,2.1.2 离散有记忆信源,即组成消息的两个球的
9、颜色之间有关联件，是有记忆的信源，这种信源就叫做发出符号序列的有记忆信原。例如由英文字母组成单词，字母间是有关联性的，不是任何字母的组合都能成为有意义的单词，同样不是任问单词的排列都能形成有意义的文章等。这些都是有记忆信源。此时的联合概率表示比较复杂，需要引入条件概率来反映信源发出符号序列内各个符号之间的记忆特征表述的复杂度将随着序列长度的增加而增加。,2.1.2 离散有记忆信源,离散信源的统计特性：（1）离散消息是从有限个符号组成的符号集中选择排列组成的随机序列（组成离消息的信息源的符号个数是有限的）。一篇汉文，尽管文章优美，词汇丰富，一般所用的词都是从常用 10 000个汉字里选出来的。一
10、本英文书，不管它有多厚，总是从26个英文字母选出来，按一定词汇结构，文法关系排列起来的。（2）在形成消息时，从符号集中选择各个符号的概率不同。对大量的由不同符号组成的消息进行统计，结果发现符号集中的每一个符号都是按一定的概率在消息中出现的。例如在英文中，每一个英文字母都是按照一定概率出现的，符号“e”出现最多，“z”出现最少。（3）组成消息的基本符号之间有一定的统计相关特性。,2.1.3 马尔可夫信源,我们讨论一类相对简单的离散平稳信源，该信源在某一时刻发出字母的概率除与该字母有关外，只与此前发出的有限个字母有关。若把这有限个字母记作一个状态S，则信源发出某一字母的概率除与该字母有关外，只与该
11、时刻信源所处的状态有关。在这种情况下，信源将来的状态及其送出的字母将只与信源现在的状态有关，而与信源过去的状态无关。 这种信源的一般数学模型就是马尔可夫过程（Markov Process），所以称这种信源为马尔可夫信源（Markov source）。可以用马尔可夫链（Markov chain）来描述。,2.1.3 马尔可夫信源,定义：信源输出某一符号的概率仅与以前的m个符号有关，而与更前面的符号无关称为m阶马尔可夫信源。即有：,2.1.3 马尔可夫信源,最简单的马尔可夫信源是一阶马尔可夫信源，如果是高阶马尔可夫信源，处理起来较为复杂。所以解决的办法是，将m个可能影响下一步的信源符号作为一个整体
12、，我们将m阶马尔可夫信源的m个符号组成的序列称为状态。,2.1.3 马尔可夫信源,具体的转换方法如下：令 i1，i2im (1，2， ， q)状态集,信源输出的随机符号序列为：信源输出的随机状态序列为：例如二元序列01011100为二阶马尔可夫信源，考虑m = 2，Q = qm =22= 4s1 = 00 s2 = 01 s3 = 10 s4 = 11最开始是01，对应s2，然后将首位的0挤出，移入后面的0，即为10，对应s3 ，接着挤出1，移入1，得到01，对应s2，接着是11，对应s4，接着又是11对应s4， 接着是10，对应s3，最后是00，对应s1，所以变换成对应的状态序列为s2 s3
13、 s2 s4 s4 s3 s1设信源在时刻m处于si状态（即Sm= si），这里的m指时刻，而不是前面的阶数，它在下一时刻(m+1)状态转移到sj（即Sm+1=sj）的转移概率为：称为基本转移概率，也称为一步转移概率。若与时刻m 的取值（也可以理解为在序列中的位置）无关，则称为齐次(时齐)马尔可夫链。,2.1.3 马尔可夫信源,具有下列性质： 0类似地，定义k步转移概率为,2.1.3 马尔可夫信源,由于系统在任一时刻可处于状态空间中的任意一个状态，因此状态转移时，转移概率是一个矩阵,2.1.3 马尔可夫信源,齐次马尔可夫链可以用马尔可夫状态转移图(因为是香农提出，所以又称香农线图)表示，图中每
14、个圆圈代表一种状态，状态之间的有向线代表某一状态向另一状态的转移，有向线一侧的符号和数字分别代表发出的符号和条件概率。,2.1.3 马尔可夫信源,例2-3 设信源符号，信源所处的状态。各状态之间的转移情况如图:,2.1.3 马尔可夫信源,将图中信源在状态下发符号的条件概率用矩阵表示为 由矩阵可明显看 出,2.1.3 马尔可夫信源,另从图还可得,2.1.3 马尔可夫信源,所以信源某时刻l所处的状态，由当前的输出符号和前一时刻l-1信源的状态唯一确定。由图还可得状态的进一步转移概率该信源是时齐的马尔可夫信源。,2.1.3 马尔可夫信源,齐次马尔可夫链中的状态可以根据其性质进行分类：如状态si经若干
15、步后总能到达状态sj，即存在k，使pij(k)0，则称si可到达sj; 若两个状态相互可到达，则称此二状态相通；过渡态：一个状态经过若干步以后总能到达某一其他状态，但不能从其他状态返回；吸收态：一个只能从自身返回到自身而不能到达其他任何状态的状态；常返态：经有限步后迟早要返回的状态；周期性的：在常返态中，有些状态仅当k能被某整数d1整除时才有pij(k)0；非周期性的：对于pij(k)0的所有k值，其最大公约数为1。遍历状态：非周期的、常返的状态。闭集：状态空间中的某一子集中的任何一状态都不能到达子集以外的任何状态。不可约的：闭集中除自身全体外再没有其他闭集的闭集。,2.1.3 马尔可夫信源,约的、非周期的、状态有限的马尔可夫链其k步转移概率pij(k)在k时趋于一个和初始状态无关的极限概率p(sj)，它是满足方程组 的唯一解；,2.1.3 马尔可夫信源,例2-4,2.1.3 马尔可夫信源,上图的周期为2，因为从S1出发再回到S1所需的步数必为2，4，6，。,
