第3讲信源模型

1、 第3讲 信源模型信源（information source），也称消息源，是通信系统中发送消息的一方。信源所产生或者输出的消息（message）是一个符号序列。任何产生符号序列的事物都可视为信源。报社、广播电台是信源；一个的人表情、行为是信源；我们所说的汉语是一个信源；一本英文小说也构成一个信源；水面波纹、天空的云等等万事万物都是信源，都在传递着各自的信息。这一讲我们介绍离散信源的几种基本的和常用的模型。1. 随机过程随机过程是一个带时间参数的随机变量，其取值的统计特性可随时间不断变化，用以机变量描述状态不断变化的物理系统或者随机现象。定义1.1 随机过程是定义在同一个样本空间上一族随机变量

2、，其中t为时间参数，T是参数集合。对于任何，随机变量的值称为随机过程在时刻t的状态。为表达方便，可将随机过程简记为。定义1.2 当随机过程的参数集合为实数区间时，该随机过程称为时间连续的。当随机过程的参数集合为整数集或者非负整数集时，该随机过程称为时间离散的。时间离散的随机过程称为随机序列。若X为随机序列，则X在时刻t的状态X(t)一般记为Xn。实例：热噪声电压的样本函数 这里我们主要学习关于随机序列的基本概念和性质，随机过程的更多知识在后面需要的地方再作介绍。随机序列的概率分布：随机序列的统计特性用其中各随机变量的概率分布和联合概率分布进行描述。一维分布：对于 这是随机序列在时刻t处于状态x

3、的概率。二维分布：对于任何状态与，随机序列从t时刻开始所经历的状态序列为的概率记为 则函数称为该随机序列在t时刻的二维分布。n维分布：t时刻的n维分布定义为，对于任何状态序列， 其中事件表示随机序列从t时刻开始所连续经历的状态为。记号：我们将随机序列X在t时刻的n维分布也记为 初始分布：对于任何正整数n，初始时刻的n维分布称为初始分布。高维分布蕴含低维分布由t时刻的n维分布可以确定t时刻的(n-1)维分布，即 因此，由t时刻的n维分布可以确定t时刻的所有低维分布。随机序列的平稳性定义1.3 若随机序列各时刻的n维分布相同，即对于任何n维状态序列和任何时刻t，有 则称该随机序列是n维平稳的。若对

4、于任何正整数n，随机序列都是n维平稳的，则称该随机序列为平稳的（stationary）。平稳随机序列的n维分布记为或者。定义1.4 若随机序列中各随机变量是相互独立并且具有相同的概率分布，则称该随机序列为独立同分布的，记为i.i.d.。独立同分布序列是最简单的一类随机序列。独立同分布序列是平稳的：（1） 由同分布性可得，对于任何时刻t和任何状态x，有 等价地， （2） 由相互独立性可得，对于任何时刻和任何状态序列，有 再由（1）可得， 从而有 2. 波形信源与离散信源波形信源使用波形信号，例如电磁波的信号，调频电磁波的信号是其不同的频率，调幅电磁波的信号是不同的振幅。这些信号是在一段连续时间内

5、高低连续变化的物理量，用以模拟声音、图像的变化，故也称为模拟信号。因此，波形信源的可以用时间参数连续的随机过程进行建模和描述。波形信源的模型：波形信源可以用连续参数的随机过程表示，其中参数集合或者，随机变量表示波形信源在时刻t所输出的信号（例如，一个振幅或者一个频率）。波形信源在任何一段时间内输出的波形信号称为该信源的消息，它是随机过程限制在该段时间上的样本函数。形信源的离散化：摸数转换（A/D transformation）将连续的模拟量通过取样和量化两个步骤转换为离散的数字量。例如，对一幅图像扫描，将它转换为像素阵列，其中每个像素由色彩和亮度组成，再对每个像素进行量化，即从指定的数值列表中

6、选取最接近像素本身值的整数值作为像素值的近似表示。这样原来的图像就转换为数字图像。波形信源产生的波形信号经过离散化后变为数字信号，从而形成离散信源。离散信源产生的符号是离散的，例如汉字、字母都是离散符号，所以汉语和英语是离散信源。数字线路中传递的数字信号，所以发送这些数字信号的设备是离散信源。离散符号可以编码为等长的整数，例如ASCII码，汉字国家标准码，等等。因此，我们将离散信源的符号统一视为整数。若某离散信源共有n个符号，则该离散信源的符号集记为 离散信源可以用随机序列进行建模和描述。离散信源的数学模型：具有离散时间参数和离散状态的随机序列。 其中随机变量Xt表示离散信源在时刻t所输出的符

7、号，即状态集中任意整数。该随机序列在一段时间内产生符号序列就是离散信源的消息。最简单的离散信源是离散无记忆信源，其定义如下：定义2.1 独立同分布序列所表示的离散信源称为离散无记忆信源，记为DMS。这种信源的符号序列是独立同分布的，即当前符号不影响下一个符号的概率分布，并且所有符号的出现概率在各时刻都是相同的。当我们不考虑信源符号之间的统计关系时，就可将它粗略地近似为无记忆信源。无损压缩编码的目标就是将信源改造为均匀分布的无记忆信源。离散无记忆信源可以表征为一个其符号集的概率分布：X01n-1 定义2.2 平稳随机序列所表示的离散信源称为离散平稳信源。平稳信源特点是，它在任何时刻产生同一条消息

8、的概率是相同的。当我们研究一个信源时，一般假设它是平稳的。平稳性大大方便了我们的统计工作，例如，为了估计一个3-汉字组合的概率，我们可以统计该组合在书本中任何位置上的出现。当然现实的信源可能渐近平稳的。即在初始阶段可能并不具有平稳性，但随着时间的推移，变得越来越平稳。因此，在统计时可以回避不平稳的初始阶段。例如，统计一本书中3-汉字组合的出现次数时，可以跳过开头的几行或者几段文字。3. 时齐马尔科夫链离散信源常用的模型是时齐马尔科夫链，其定义如下。定义3.1 若随机序列X在任何时刻t的t阶条件概率等于1阶条件概率，即 则称该随机序列满足马尔科夫性（Markov property），称为马尔科夫

9、序列。 马尔科夫性也称为无后效性。这个性质表明：在给定当前状态的条件下，下一状态与以前所有状态是相互独立的。 定义3.2 状态离散的马尔科夫序列称为马尔科夫链。 若马尔科夫链的一阶条件概率不随时间t改变，则称该马尔科夫链为时齐的（homogeneous），也称为时不变的（time-invariant）。注：与平稳性相比较，时齐性的要求较弱。前者蕴含后者，后者并不蕴含前者。约定：在以后设计马尔科夫链的例题习题中，若无特别声明，就默认其中马尔科夫链为时齐的。时齐马尔科夫链有两种表征：（1）转移矩阵： 马尔科夫链的所有一阶条件概率构成的矩阵称为该马尔科夫链的转移矩阵。转移矩阵是一个方阵，记录时齐马尔

10、科夫链各状态之间的转移概率。下列矩阵共有两行，表明时齐马尔科夫链共有2个状态，姑且称为状态1和状态2。矩阵第1行是状态1转移到状态2的概率分布，第2行是状态2转移到状态1的概率分布。 （2）状态转移图：上述矩阵表示的时齐马尔科夫链也可直观地表示为如下状态转移图，其中两个结点分别表示两个不同状态，有向边称为状态间的转移，有向边上的标记称为转移概率。 定理3.3令P为时齐马尔科夫链X的转移矩阵，则t+n时刻的概率分布为 其中概率分布都表示为行向量。根据上述定理，我们称Pn为n-步转移矩阵。命题 若时齐马尔科夫链是一维平稳的，则它是任意维平稳的。证明：请读者完成。 证毕一些特殊的初始分布会使得时齐马

11、尔科夫链具有平稳性，这就是所谓平稳分布。定义3.4 令时齐马尔科夫链（的转移概率矩阵）为P，若存在分布，使得，则称为平稳分布。可以看出，当马尔科夫链的初始分布为平稳分布，则该马尔科夫链是平稳的。时齐马尔科夫链的渐近平稳性定义3.5（渐近平稳性）随机序列X称为渐近平稳的，当且仅当其各维分布存在极限分布，即对于任何，存在极限 其中称为n-维极限分布。实际意义：随着时间推移，随机序列的统计特性越来越近似平稳序列。命题：时齐马尔科夫链是渐近平稳的，当且仅当它存在一维极限分布。命题：极限分布一定是平稳分布，而反之未必成立。时齐马尔科夫链存在极限分布的充分条件：（1）不可约性：若时齐马尔科夫链的所有状态是

12、相互连通的，则称该马尔科夫链为不可约的（irreducible）。（2）非周期性：从状态i出发再回到i的所有循环路径长度的最大公约数称为状态i的周期。周期等于1的状态称为非周期的（asperiod）。若时齐马尔科夫链的所有状态都是非周期的，则称该马尔科夫链为非周期的。定理3.6（时齐马尔科夫链的渐近平稳性）若时齐马尔科夫链P是不可约的和非周期的，则P是渐近平稳的，并且其极限分布是唯一的平稳分布。 因此，若时齐马尔科夫链P具有不可约性和非周期性，则其极限分布是下列方程的解： 等价地， 定理3.7（正则性蕴含渐近平稳性）若时齐马尔科夫链P是正则的，即存在正整数n，使得n-步转移矩阵Pn不含0项，则

13、P是渐近平稳的，并且其极限分布是唯一的平稳分布。注：n-步转移矩阵Pn不含0项的含义是，从任何状态出发经过n-步转移都可达到其它任何状态。练习判断下列马尔科夫链是否存在极限分布。若存在试求出该极限分布。 练习设任意相继的两天中，雨天转晴天的概率为1/3，晴天转雨天的概率为1/2，任一天晴或者雨是互为逆事件。以0和1分别表示晴天和雨天这两种状态，Xn表示第n天的状态（0或1）。试写出马氏链的转移矩阵。又若已知5月1日为晴天，问5月3日为晴天，5月4日为雨天的概率各等于多少？4. 马尔科夫信源 定义4.1 若随机序列X在任何时刻t的t阶条件概率等于m阶条件概率（其中mt），即 则称该随机序列具有m

14、-阶马尔科夫性，并称该序列为m阶马尔科夫序列。m阶马尔科夫序列所表示的离散信源称为m阶马尔科夫信源。m阶马尔科夫性表明随机序列具有有限的记忆性，我们称其记忆长度为m+1.根据定义，马尔科夫链是1阶马尔科夫序列，其记忆长度等于2。 汉语、英语等自然语言都具有这种有限记忆性。在汉语文章中，一个汉字仅与前几个汉字的关系比较密切，而与更前面的汉字的关系较弱，可以忽略不计。根据实际需要，我们可以构造汉语的1-阶马尔科夫模型、2-阶马尔科夫模型，等等。模型的阶数越大，则该模型的条件概率矩阵越庞大，从而构造和应用该条件概率矩阵所需的统计和计算工作量越大。最常用的是3-单词模型。5. 构造英语的马尔科夫模型在

15、研究实际信源时，可根据实际需要，选择合适的信源模型。我们介绍英语信源模型的构造方法。这个方法是香农在1948年的论文A mathematical theory of communication中给出的。它通过统计一本书中英文字符间的条件概率而构造英文的几种马尔科夫模型。（本教材此处内容参考自Cover与Thomas的教材信息论基础第2版第96页。）首先，确定英文字母表：为简化统计和计算的工作量，假设英文字母表仅包括27个符号，即26个字母和常见的空格符号，忽略标点和大小写。讨论：英语符号简化为27个符号对于估计其熵率的影响大吗？其次，任意选取一本足够厚重的英文著作。按下列方法统计条件概率。无记

16、忆模型：这个模型假设英文是无记忆信源。更加该假设，做如下统计工作。选择一本英文书，统计出其中各符号出现频率p(x)，构成英文字符的一维分布列，其形式如下：Xabz空格一阶马尔科夫模型：从所选的英文书中，统计出英语符号的一阶条件概率，构成一个转移矩阵，这个转移矩阵就是英文的一阶马尔科夫模型。统计方法如下。第1步，随机地打开书本中的某页，并随机地选定一个符号，作为该序列的第1个符号。第2步，随机地打开某页，找到当前选定的符号Xi，将紧随其后的符号选定为下一个符号。第3步，重复第2步，直到所构造的序列足够长时为止。这种随机跳跃式的统计方法可以构造出具有一阶马尔科夫性的符号序列。只要所构造的符号序列足

17、够长，则足以代表英语字符序列的一阶马尔科夫性。第4步 从所构造的符号序列中统计出相邻符号间的条件概率，构成一阶马尔科夫模型的转移矩阵。m阶马尔科夫模型：类似地，从最初随机选定的连续m个符号开始，随机跳跃若干行符号后，找该符号组的第1次出现，从而将该符号组之后的第1个符号选定下一个符号。依次类推，构造出一个足够长的符号序列。该序列可以反映英语的m阶马尔科夫性。从该序列中统计出所有m分组与紧跟其后的下一个符号之间的条件概率。所有的这些概率构成一个矩阵，这就是英语的m阶马尔科夫模型。上述构造的是以英文字符为符号的马尔科夫模型，称为马尔科夫字符模型。香农在1948年的文章中还介绍了以单词为符号的马尔科

18、夫模型，称为马尔科夫单词模型，其构造方法与上述介绍的方法类似。英语的马尔科夫模型中最常用的是三单词模型，即2阶马尔科夫单词模型，在语音识别系统中起到关键的作用，获得了惊人的效果。6. 隐马尔可夫链 对于m-阶马尔科夫信源，我们将信源符号的所有m-分组视为新的信源符号，从而可将该信源转化为1-阶马尔科夫信源，即马尔科夫链。令为m-阶马尔科夫序列。令，其中 易知Y的记忆长度为1，即所以Y是马尔科夫链，称为X的隐马尔科夫链。因此，通过符号分组，可以将m-阶马尔科夫信源转化为形式比较简单的马尔科夫链。在随机过程理论中，对于马尔科夫链的研究是比较成熟的，许多研究结果可以应用到信源研究上。意义：（1） m-阶马尔科夫信源也可以转化为马尔科夫信源，便于分析和处理。（2）任何m-阶马尔科夫信源都可以视为马尔科夫信源。前一概念完全可以被后一概念所取代。例6.1（傅祖芸，赵建中信息论与编码第54页例2.11）设X是二元二阶马尔科夫序列，其条件概率矩阵P(X3|X1X2)如下： 根据该矩阵可以确定X的隐马尔科夫模