第3讲信源模型

1第3讲信源模型信源（informationsource），也称消息源，是通信系统中发送消息的一方。信源所产生或者输出的消息（message）是一个符号序列。任何产生符号序列的事物都可视为信源。报社、广播电台是信源；一个的人表情、行为是信源；我们所说的汉语是一个信源；一本英文小说也构成一个信源；水面波纹、天空的云等等万事万物都是信源，都在传递着各自的信息。这一讲我们介绍离散信源的几种基本的和常用的模型。1.随机过程随机过程是一个带时间参数的随机变量，其取值的统计特性可随时间不断变化，用以机变量描述状态不断变化的物理系统或者随机现象。定义1.1随机过程是定义在同一个样本空间上一族随机变量{(),}XttT，其中t为时间参数，T是参数集合。对于任何tT，随机变量()Xt的值称为随机过程在时刻t的状态。为表达方便，可将随机过程{(),}XttT简记为()XXt或。定义1.2当随机过程的参数集合为实数区间(,)[0,)或者时，该随机过程称为时间连续的。当随机过程的参数集合为整数集或者非负整数集时，该随机过程称为时间离散的。时间离散的随机过程称为随机序列。若X为随机序列，则X在时刻t的状态X(t)一般记为Xn。实例：热噪声电压的样本函数这里我们主要学习关于随机序列的基本概念和性质，随机过程的更多知识在后面需要的地方再作介绍。2随机序列的概率分布：随机序列的统计特性用其中各随机变量的概率分布和联合概率分布进行描述。一维分布：对于()Pr{}ttpxXx这是随机序列在时刻t处于状态x的概率。二维分布：对于任何状态1x与2x，随机序列从t时刻开始所经历的状态序列为12xx的概率记为12112112()Pr{}Pr{,}tttttpxxXXxxXxXx则函数tp称为该随机序列在t时刻的二维分布。n维分布：t时刻的n维分布定义为，对于任何状态序列12nxxx，1212121122()Pr{}Pr{,,,}tntttnntttnnpxxxXXXxxxXxXxXx其中事件1212{}tttnnXXXxxx表示随机序列从t时刻开始所连续经历的状态为12nxxx。记号：我们将随机序列X在t时刻的n维分布也记为1()ttnpXX初始分布：对于任何正整数n，初始时刻的n维分布112()npxxx称为初始分布。高维分布蕴含低维分布由t时刻的n维分布可以确定t时刻的(n-1)维分布，即12112()()tntnnxpxxxpxxx因此，由t时刻的n维分布可以确定t时刻的所有低维分布。3随机序列的平稳性定义1.3若随机序列各时刻的n维分布tp相同，即对于任何n维状态序列011nxxx和任何时刻t，有12112()()tntnpxxxpxxx则称该随机序列是n维平稳的。若对于任何正整数n，随机序列都是n维平稳的，则称该随机序列为平稳的（stationary）。平稳随机序列的n维分布记为1()npXX或者1()npxx。定义1.4若随机序列中各随机变量是相互独立并且具有相同的概率分布，则称该随机序列为独立同分布的，记为i.i.d.。独立同分布序列是最简单的一类随机序列。独立同分布序列是平稳的：（1）由同分布性可得，对于任何时刻t和任何状态x，有1()()ttpxpx等价地，1()()tpxpx（2）由相互独立性可得，对于任何时刻和任何状态序列12nxxx，有12112()()()()tntttnnpxxxpxpxpx再由（1）可得，1211121()()()()tnnpxxxpxpxpx从而有12112()()tntnpxxxpxxx2.波形信源与离散信源波形信源使用波形信号，例如电磁波的信号，调频电磁波的信号是其不同的频率，调幅电磁波的信号是不同的振幅。这些信号是在一段连续时间内高低连续变化的物理量，用以模拟声音、图像的变化，故也称为模拟信号。因此，波形信源的可以用时间参数连续的随机过程进行建模和描述。4波形信源的模型：波形信源可以用连续参数的随机过程{(),}XttT表示，其中参数集合(,)T或者[0,)，随机变量()Xt表示波形信源在时刻t所输出的信号（例如，一个振幅或者一个频率）。波形信源在任何一段时间内输出的波形信号称为该信源的消息，它是随机过程限制在该段时间上的样本函数。形信源的离散化：摸数转换（A/Dtransformation）将连续的模拟量通过取样和量化两个步骤转换为离散的数字量。例如，对一幅图像扫描，将它转换为像素阵列，其中每个像素由色彩和亮度组成，再对每个像素进行量化，即从指定的数值列表中选取最接近像素本身值的整数值作为像素值的近似表示。这样原来的图像就转换为数字图像。波形信源产生的波形信号经过离散化后变为数字信号，从而形成离散信源。离散信源产生的符号是离散的，例如汉字、字母都是离散符号，所以汉语和英语是离散信源。数字线路中传递的数字信号，所以发送这些数字信号的设备是离散信源。离散符号可以编码为等长的整数，例如ASCII码，汉字国家标准码，等等。因此，我们将离散信源的符号统一视为整数。若某离散信源共有n个符号，则该离散信源的符号集记为{0,1,,1}nL离散信源可以用随机序列进行建模和描述。离散信源的数学模型：具有离散时间参数和离散状态的随机序列。{(),}Xtt其中随机变量Xt表示离散信源在时刻t所输出的符号，即状态集{0,1,,1}n中任意整数。该随机序列在一段时间内产生符号序列就是离散信源的消息。最简单的离散信源是离散无记忆信源，其定义如下：定义2.1独立同分布序列所表示的离散信源称为离散无记忆信源，记为DMS。这种信源的符号序列是独立同分布的，即当前符号不影响下一个符号的概率分布，并且所有符号的出现概率在各时刻都是相同的。5当我们不考虑信源符号之间的统计关系时，就可将它粗略地近似为无记忆信源。无损压缩编码的目标就是将信源改造为均匀分布的无记忆信源。离散无记忆信源可以表征为一个其符号集的概率分布：定义2.2平稳随机序列所表示的离散信源称为离散平稳信源。平稳信源特点是，它在任何时刻产生同一条消息的概率是相同的。当我们研究一个信源时，一般假设它是平稳的。平稳性大大方便了我们的统计工作，例如，为了估计一个3-汉字组合的概率，我们可以统计该组合在书本中任何位置上的出现。当然现实的信源可能渐近平稳的。即在初始阶段可能并不具有平稳性，但随着时间的推移，变得越来越平稳。因此，在统计时可以回避不平稳的初始阶段。例如，统计一本书中3-汉字组合的出现次数时，可以跳过开头的几行或者几段文字。3.时齐马尔科夫链离散信源常用的模型是时齐马尔科夫链，其定义如下。定义3.1若随机序列X在任何时刻t的t阶条件概率等于1阶条件概率，即111(|)(|)ttttpXXXpXX则称该随机序列满足马尔科夫性（Markovproperty），称为马尔科夫序列。马尔科夫性也称为无后效性。这个性质表明：在给定当前状态的条件下，下一状态与以前所有状态是相互独立的。定义3.2状态离散的马尔科夫序列称为马尔科夫链。若马尔科夫链的一阶条件概率1(|)ttPXX不随时间t改变，则称该马尔科夫链为时齐的（homogeneous），也称为时不变的（time-invariant）。X01…n-1Xp0p1p…1np6注：与平稳性相比较，时齐性的要求较弱。前者蕴含后者，后者并不蕴含前者。约定：在以后设计马尔科夫链的例题习题中，若无特别声明，就默认其中马尔科夫链为时齐的。时齐马尔科夫链有两种表征：（1）转移矩阵：马尔科夫链的所有一阶条件概率1(|)ttpXX构成的矩阵称为该马尔科夫链的转移矩阵。转移矩阵是一个方阵，记录时齐马尔科夫链各状态之间的转移概率。下列矩阵共有两行，表明时齐马尔科夫链共有2个状态，姑且称为状态1和状态2。矩阵第1行是状态1转移到状态2的概率分布，第2行是状态2转移到状态1的概率分布。0.70.30.10.9（2）状态转移图：上述矩阵表示的时齐马尔科夫链也可直观地表示为如下状态转移图，其中两个结点分别表示两个不同状态，有向边称为状态间的转移，有向边上的标记称为转移概率。0.7S2S10.10.30.9定理3.3令P为时齐马尔科夫链X的转移矩阵，则t+n时刻的概率分布为()()ntntpXpXP其中概率分布()tpX都表示为行向量。根据上述定理，我们称Pn为n-步转移矩阵。命题若时齐马尔科夫链是一维平稳的，则它是任意维平稳的。证明：请读者完成。证毕一些特殊的初始分布会使得时齐马尔科夫链具有平稳性，这就是所谓平稳分布。定义3.4令时齐马尔科夫链（的转移概率矩阵）为P，若存在分布，使得P，则称为平稳分布。可以看出，当马尔科夫链的初始分布为平稳分布，则该马尔科夫链是平稳的。7时齐马尔科夫链的渐近平稳性定义3.5（渐近平稳性）随机序列X称为渐近平稳的，当且仅当其各维分布存在极限分布，即对于任何1n，存在极限110lim()()tnntpxxpxx其中1()npxx称为n-维极限分布。实际意义：随着时间推移，随机序列的统计特性越来越近似平稳序列。命题：时齐马尔科夫链是渐近平稳的，当且仅当它存在一维极限分布。命题：极限分布一定是平稳分布，而反之未必成立。时齐马尔科夫链存在极限分布的充分条件：（1）不可约性：若时齐马尔科夫链的所有状态是相互连通的，则称该马尔科夫链为不可约的（irreducible）。（2）非周期性：从状态i出发再回到i的所有循环路径长度的最大公约数称为状态i的周期。周期等于1的状态称为非周期的（asperiod）。若时齐马尔科夫链的所有状态都是非周期的，则称该马尔科夫链为非周期的。定理3.6（时齐马尔科夫链的渐近平稳性）若时齐马尔科夫链P是不可约的和非周期的，则P是渐近平稳的，并且其极限分布是唯一的平稳分布。因此，若时齐马尔科夫链P具有不可约性和非周期性，则其极限分布π是下列方程的解：P等价地，()0PE定理3.7（正则性蕴含渐近平稳性）若时齐马尔科夫链P是正则的，即存在正整数n，使得n-步转移矩阵Pn不含0项，则P是渐近平稳的，并且其极限分布是唯一的平稳分布。8注：n-步转移矩阵Pn不含0项的含义是，从任何状态出发经过n-步转移都可达到其它任何状态。练习判断下列马尔科夫链是否存在极限分布。若存在试求出该极限分布。0.7S2S10.10.30.9练习设任意相继的两天中，雨天转晴天的概率为1/3，晴天转雨天的概率为1/2，任一天晴或者雨是互为逆事件。以0和1分别表示晴天和雨天这两种状态，Xn表示第n天的状态（0或1）。试写出马氏链{,1}nXn的转移矩阵。又若已知5月1日为晴天，问5月3日为晴天，5月4日为雨天的概率各等于多少？94.马尔科夫信源定义4.1若随机序列X在任何时刻t的t阶条件概率等于m阶条件概率（其中mt），即0-1-1(|)(|)ttttmtpXXXpXXX则称该随机序列具有m-阶马尔科夫性，并称该序列为m阶马尔科夫序列。m阶马尔科夫序列所表示的离散信源称为m阶马尔科夫信源。m阶马尔科夫性表明随机序列具有有限的记忆性，我们称其记忆长度为m+1.根据定义，马尔科夫链是1阶马尔科夫序列，其记忆长度等于2。汉语、英语等自然语言都具有这种有限记忆性。在汉语文章中，一个汉字仅与前几个汉字的关系比较密切，而与更前面的汉字的关系较弱，可以忽略不计。根据实际需要，我们可以构造汉语的1-阶马尔科夫模型、2-阶马尔科夫模型，等等。模型的阶数越大，则该模型的条件概率矩阵越庞大，从而构造和应用该条件概率矩阵所需的统计和计算工作量越大。最常用的是3-单词模型。5.构造英语的马尔科夫模型在研究实际信源时，可根据实际需要，选择合适的信源模型。我们介绍英语信源模型的构造方法。这个方法是香农在1948年的论文Amathematicaltheoryofcommunication中给出的。它通过统计一本书中英文字符间的条件概率而构造英文的几种马尔科夫模型。（本教材此处内容参考自Cover与Thomas的教材《信息