《第三章信源熵率及冗余度》由会员分享，可在线阅读，更多相关《第三章信源熵率及冗余度（73页珍藏版）》请在金锄头文库上搜索。
1、第三章：信源、熵率及冗余度第三章：信源、熵率及冗余度问题一问题一信息论对信源的研究内容包括哪几个方面？信息论对信源的研究内容包括哪几个方面？信息论对信源研究的内容信息论对信源研究的内容信源的建模：用恰当的随机过程来描述信号信源的建模：用恰当的随机过程来描述信号关心角度：信号中携带的信息关心角度：信号中携带的信息信源输出信号中携带信息的效率的计算信源输出信号中携带信息的效率的计算熵率、冗余度熵率、冗余度信源输出信息的有效表示信源输出信息的有效表示信源编码信源编码问题二从信息论的角度如何为信源建模？从信息论的角度如何为信源建模？信源的统计特性如何？信源的统计特性如何？如何对信源分类？如何对信源分类
2、？各类信源如何建模？各类信源如何建模？信源特性信源特性信源的统计特性信源的统计特性1）什么是信源？）什么是信源？信信源源是是信信息息的的来来源源，实实际际通通信信中中常常见见的的信信源源有有：语语音音、文文字字、图图像像、数数据据。在在信信息息论论中中，信信源源是是产产生生消消息息（符符号号）、消消息息（符符号号）序序列列以以及及连连续续消消息息的的来来源源，数数学学上上，信信源源是是产产生生随随机机变变量量X，随随机机序序列列 和和随随机机过过程程X(t,)的源。的源。2）信源的主要特性）信源的主要特性信信源源的的最最基基本本的的特特性性是是具具有有统统计计不不确确定定性性，它它可可用用概概
3、率率统计特性来描述。统计特性来描述。信源的分类离散信源与连续信源离散信源与连续信源离散信源离散信源单符号信源单符号信源序列信源序列信源平稳平稳&非平稳非平稳有记忆有记忆&无记忆无记忆连续信源连续信源连续信源连续信源波形信源波形信源离散信源单符号离散信源（1）它它是是最最简简单单也也是是最最基基本本的的信信源源，是是组组成成实实际际信信源源的基本单元。的基本单元。这这类类信信源源可可能能输输出出的的消消息息数数是是有有限限的的或或可可数数的的，而而且且每每次次只只输输出出其其中中一一个个消消息息。因因此此，可可以以用用一一个个离离散散型型随随机机变变量量X来来描描述述这这个个信信源源输输出出的的
4、消消息息。这这个个随随机机变变量量X的的样样本本空空间间就就是是符符号号集集A；而而X的的概概率率分分布布就就是是各各消消息息出出现现的的先先验验概概率率，信信源源的的概概率空间必定是一个完备集。率空间必定是一个完备集。离散信源单符号离散信源（2）当当信信源源给给定定，其其相相应应的的概概率率空空间间就就已已给给定定；反反之之，如如果果概概率率空空间间给给定定，这这就就表表示示相相应应的的信信源源已已给给定定。所所以以，概概率率空空间间能能表表征征离离散散信信源源的的统统计计特特性性，因因此此有时也把这个概率空间称为有时也把这个概率空间称为信源空间信源空间。在在实实际际情情况况中中，存存在在着
5、着很很多多这这样样的的信信源源。例例如如投投硬硬币币、书书信信文文字字、计计算算机机的的代代码码、电电报报符符号号、阿阿拉拉伯伯数数字字码码等等等等。这这些些信信源源输输出出的的都都是是单单个个符符号号(或或代代码码)的的消消息息，它它们们符符号号集集的的取取值值是是有有限限的的或或可可数数的的。我我们们可可用用一一维维离离散散型型随随机机变变量量X来来描描述述这这些些信信源源的的输输出出。它的数学模型就是离散型的概率空间：它的数学模型就是离散型的概率空间：离散信源单符号离散信源的数学描述对单符号离散信源对单符号离散信源U有：有：例例31：对于二进制数字信源：对于二进制数字信源：U=0,1，则
6、有，则有离散信源离散多符号信源实际的信源输出的消息是时间或空间上离散的一系列随机实际的信源输出的消息是时间或空间上离散的一系列随机变量。这类信源每次输出的不是一个单个的符号，而是一变量。这类信源每次输出的不是一个单个的符号，而是一个符号序列。个符号序列。在信源输出的序列中，每一位出现哪个符号在信源输出的序列中，每一位出现哪个符号都是随机的，而且一般前后符号的出现是有统计依赖关系都是随机的，而且一般前后符号的出现是有统计依赖关系的。这种信源称为的。这种信源称为多符号离散信源多符号离散信源。例例32： THEY ARE MY FRIENDS.离散信源多符号离散信源的数学描述多符号离散信源可用多符号
7、离散信源可用随机矢量随机矢量/随机变量序列随机变量序列描述，描述，即即X=X1X2X3信源在不同时刻的随机变量信源在不同时刻的随机变量Xi和和Xi+r的概率分布的概率分布P(Xi)和和P(Xi+r)一般来说是不相同的，即随机变量的一般来说是不相同的，即随机变量的统计特性随着时间的推移而有所变化。统计特性随着时间的推移而有所变化。离散信源离散平稳信源若若信信源源输输出出的的随随机机序序列列X=(，)中中，每每个个随随机机变变量量 Xi (i=1,2,，N)都都是是取取值值离离散散的的离离散散型型随随机机变变量量，即即每每个个随随机机变变量量Xi的的可可能能取取值值是是有有限限的的或或可可数数的的
8、。而而且且随随机机矢矢量量X的的各各维维概概率率分分布布都都与与时时间间起起点点无无关关，也也就就是是在在任任意意两两个个不不同同时时刻刻随随机机矢矢量量X的的各各维维概概率率分分布布都都相相同同。这这样样的的信信源源称称为为离离散散平平稳稳信信源源。如如中中文文自自然然语语言言文文字字，离离散化平面灰度图像都是这种离散型平稳信源。散化平面灰度图像都是这种离散型平稳信源。一一般般来来说说，信信源源输输出出的的随随机机序序列列的的统统计计特特性性比比较较复复杂杂，分分析析起起来来也也比比较较困困难难。为为了了便便于于分分析析，我我们们假假设设信信源源输输出出的的是是平平稳稳的的随随机机序序列列，
9、也也就就是是序序列列的的统统计计性性质质与与时时间间的的推推移移无关。很多实际信源也满足这个假设。无关。很多实际信源也满足这个假设。离散信源平稳信源的数学模型（二维）最简单的离散平稳信源：二维平稳信源最简单的离散平稳信源：二维平稳信源 X=X1X2每两个符号看做一组，每组代表信源每两个符号看做一组，每组代表信源X=X1X2的一个消息；的一个消息；每组中的后一个符号和前一个符号有统计关联，这种概率每组中的后一个符号和前一个符号有统计关联，这种概率性的关系与时间起点无关；性的关系与时间起点无关；假定符号序列的组与组之间是统计独立的。假定符号序列的组与组之间是统计独立的。设设X1,X2 x1,x2,
10、xn,矢量矢量Xx1x1, x1xn,x2x1, ,x2xn, xnx1, ,xnxn 令令X的数学模型的数学模型离散信源离散平稳无记忆信源在在某某些些简简单单的的离离散散平平稳稳信信源源情情况况下下，信信源源先先后后发发出出的的一一个个个个符符号号彼彼此此是是统统计计独独立立的的。也也就就是是说说信信源源输输出出的的随随机机矢矢量量X=(XXX）中中，各各随随机机变变量量Xi (i=1,2,N)之之间间是是无无依依赖赖的的、统统计计独独立立的的，则则N维维随随机机矢矢量量的的联联合合概概率率分布满足分布满足P(X)=P（）P（）P（）我我们们称称由由信信源源空空间间X，P(x)描描述述的的信
11、信源源X为为离离散散无无记记忆忆信信源源。这这信信源源在在不不同同时时刻刻发发出出的的符符号号之之间间是是无无依依赖赖的的，彼此统计独立的。彼此统计独立的。离散信源离散无记忆信源的N次扩展信源离散无记忆信源离散无记忆信源X= x1,x2,xn，对它的输出消息序列，可以用对它的输出消息序列，可以用一组组长度为一组组长度为N的序列来表示它。这时它就等效成了一个新信的序列来表示它。这时它就等效成了一个新信源；源；新信源输出的符号是新信源输出的符号是N长的消息序列，用长的消息序列，用N维离散随机矢量来描维离散随机矢量来描述。述。ai=(xi1xi2xiN) i=1,2, ,n 每个分量每个分量xik
12、(k=1,2,N)都是随机变量，都取值于同一信源都是随机变量，都取值于同一信源X，并且分量之间统计独立。并且分量之间统计独立。由随机矢量由随机矢量X组成的新信源称为组成的新信源称为离散无记忆信源离散无记忆信源X的的N次扩展信次扩展信源源。离散无记忆信源的离散无记忆信源的N N次扩展信源的次扩展信源的数学模型数学模型是是X X信源空间的信源空间的N N重空重空间间。ABDACBBACCDX100000000000X211111111111X300000000000X400000000000X500000000000X600100000001X701001110110X810011001110X1
13、、X2、X8,均为单符号随机变量信源均为单符号随机变量信源X=0,1，P(X1X2X8)与时间起点无关与时间起点无关平稳平稳P(X1X2X8)P(X1)P(X2)P(X8)无记忆信源无记忆信源例例33：电文：电文：女女孩孩儿儿在在哭哭XCHUYJKOIUYHSFRTNHYTFSGTRWX1CKHNSX2H0SHGX3UIFYTX4YURTRX5JYTFWX1,X2,X3,X4,X5均为单符号随机变量均为单符号随机变量XA、B、CZP(X1X2X3X4X5)=P (X1)P(X2)P(X3)P(X4)P(X5)且与时间起点无关，且与时间起点无关，X为一无记忆平稳信源为一无记忆平稳信源例例34：离
14、散信源二进制无记忆信源的N次扩展信源把信源输出的序列看成是一组一组发出的。把信源输出的序列看成是一组一组发出的。电报系统中，可以认为每二个二进制数字组成一组。这样信源输出的是由二个电报系统中，可以认为每二个二进制数字组成一组。这样信源输出的是由二个二进制数字组成的一组组符号。这时可以将它们等效看成一个新的信源，它由二进制数字组成的一组组符号。这时可以将它们等效看成一个新的信源，它由四个符号四个符号00，01，10，11组成，把该信源称为二进制无记忆信源的二次扩展。组成，把该信源称为二进制无记忆信源的二次扩展。如果把每三个二进制数字组成一组，这样长度为如果把每三个二进制数字组成一组，这样长度为3
15、的二进制序列就有的二进制序列就有8种不同的种不同的序列，可等效成一个具有序列，可等效成一个具有8个符号的信源，把它称为二进制无记忆信源的三次扩个符号的信源，把它称为二进制无记忆信源的三次扩展信源。展信源。二进制无记忆信源的二进制无记忆信源的N次扩展：把每次扩展：把每N个二进制数字组成一个二进制数字组成一组，则信源等效成一个具有组，则信源等效成一个具有2N个符号的新信源，把它称为个符号的新信源，把它称为二二进制无记忆信源的进制无记忆信源的N次扩展信源次扩展信源。离散信源离散平稳有记忆信源 一一般般情情况况下下，信信源源在在不不同同时时刻刻发发出出的的符符号号之之间间是是相相互互依依赖赖的的。也也
16、就就是是信信源源输输出出的的平平稳稳随随机机序序列列X中中，各各随随机机变变量量Xi之之间是有依赖的。间是有依赖的。例例如如，在在汉汉字字组组成成的的中中文文序序列列中中，只只有有根根据据中中文文的的语语法法、习习惯惯用用语语、修修辞辞制制约约和和表表达达实实际际意意义义的的制制约约所所构构成成的的中中文文序序列列才才是是有有意意义义的的中中文文句句子子或或文文章章。所所以以，在在汉汉字字序序列列中中前前后后文文字字的的出出现现是是有有依依赖赖的的，不不能能认认为为是是彼彼此此不不相相关关的的。其其他他如如英英文文，德德文文等等自自然然语语言言都都是是如如此此。这种信源称为这种信源称为有记忆信
17、源有记忆信源。我我们们需需在在N维维随随机机矢矢量量的的联联合合概概率率分分布布中中，引引入入条条件件概概率率分分布布来说明它们之间的关联。来说明它们之间的关联。女孩儿在哭女孩儿在哭XTHISGIRLISCRYINGX1TGICX2HISRX3IRYX4SLIX5NX6GX1,X2,X3,X4,X5均为单符号随机变量均为单符号随机变量XA、B、CZP(X1X2X3X4X5)P (X1)P(X2)P(X3)P(X4)P(X5)与时间起点无关，与时间起点无关，X是一有记忆平稳信源是一有记忆平稳信源例例35：离散信源马尔可夫信源离散信源马尔可夫信源表表述述有有记记忆忆信信源源要要比比表表述述无无记记
18、忆忆信信源源困困难难得得多多。实实际际上上信信源源发发出出的的符符号号往往往往只只与与前前若若干干个个符符号号的的依依赖赖关关系系强强，而而与与更更前前面面的的符符号号依依赖赖关关系系弱弱。为为此此，可可以以限限制制随机序列的记忆长度。随机序列的记忆长度。当当记记忆忆长长度度为为m+1时时，称称这这种种有有记记忆忆信信源源为为m阶阶马马尔尔可可夫夫信信源源。也也就就是是信信源源每每次次发发出出的的符符号号只只与与前前m个个符符号有关，与更前面的符号无关。号有关，与更前面的符号无关。离散信源时齐马尔可夫信源离散信源时齐马尔可夫信源设设马马尔尔可可夫夫信信源源各各时时刻刻随随机机变变量量的的取取值
19、值为为xk，xkXk，k=1,2,，i-1,i,i+1,N，则则描描述述随随机机序序列列中中各随机变量之间依赖关系的条件概率为各随机变量之间依赖关系的条件概率为 P(xi|xi+2xi+1xi-1xi-2xi-3xi-mx1） = （ xi|xi-1xi-2x-3xi-m） （i=1,2,N）如如果果上上述述条条件件概概率率与与时时间间起起点点i无无关关，即即信信源源输输出出的的符符号号序序列列可可看看成成为为时时齐齐马马尔尔可可夫夫链链，则则此此信信源源称称为为时时齐齐马尔可信源。马尔可信源。1. 各字母等概、字母间不相关（字符独立）各字母等概、字母间不相关（字符独立） XFOML RXKH
20、RJFFJUJ LPWCFWKCYFFJEYVKC QSGHYDQPAAMKBZAACIBZLHJQD.2. 字母出现概率按照英文文本统计，字母间不相关（字符独立）字母出现概率按照英文文本统计，字母间不相关（字符独立） OCRO HLI RGWR NMIELWIS EU LL NBNESEBYA TH EEI ALHENHTTPA OOBTTVANAH 3. 字母出现概率按照英文文本统计，字母间存在二维相关性（两两字母出现概率按照英文文本统计，字母间存在二维相关性（两两相邻字母相关相邻字母相关 ） ON IE ANTSOUTINYS ARE T INCTORE ST BE S DEAMY AC
21、HIN D ILONASIVETUCOOWEAT TEASONARE FUSO TIZIN ANDY TOBE SEACE CTISBE.信源建模信源建模信源建模信源建模4.字母出现概率按照英文文本统计，字母间存在三维相关性字母出现概率按照英文文本统计，字母间存在三维相关性 IN NO IST LAT WHEY CRATICT FROUREBIRSGROCIDPONDENOME OF DEMONSTURESOF THE REPTAGIN IS REGOACTIONA OF CRE.5.字母出现概率按照英文文本统计，字母间存在字母出现概率按照英文文本统计，字母间存在N维相关性维相关性 REPRE
22、SENTING AND SPEEDILY IS AN GOOD APT OR COME CAN DIFFERENT NATURALHERE HE THE A IN CAME THE TOOF TO EXPERT GRAY COME TO FURNISHESTHE LINE MESSAGE HAD BE THESE.6.单词间存在相关性（依据语法）单词间存在相关性（依据语法）. THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE CHARACTER OF THIS POINT IS THEREFORE ANOTHER METH
23、OD FOR THE LETTERS THAT THE TIME OF WHO EVER TOLD THE PROBLEM FOR AN UNEXPECTED. 模型复杂度越高，越逼近实际。模型复杂度越高，越逼近实际。一个足够复杂的随机序列模型能够满意地表示自然语言的信源。一个足够复杂的随机序列模型能够满意地表示自然语言的信源。离散序列信源总结离散序列信源总结模拟信源模拟信源模拟信源又可根据时间是否离散分为模拟信源又可根据时间是否离散分为连续信源连续信源和和波形信波形信源源。连续信源是时间离散而取值连续的一类信源，波形。连续信源是时间离散而取值连续的一类信源，波形信源是指取值连续时间也连续的一
24、类信源。信源是指取值连续时间也连续的一类信源。由于模拟信源的情况比较复杂，限于学时，我们只对单由于模拟信源的情况比较复杂，限于学时，我们只对单变量连续信源的信息测度进行讨论。变量连续信源的信息测度进行讨论。连续信源单变量连续信源（1）有的信源虽输出是单个符号有的信源虽输出是单个符号(代码代码)的消息，但其可能的消息，但其可能出现的消息数是不可数的无限值，即输出消息的符号出现的消息数是不可数的无限值，即输出消息的符号集集A的取值是连续的，或取值是实数集的取值是连续的，或取值是实数集(-，)。例如，。例如，遥控系统中有关电压、温度、压力等测得的连续数据。遥控系统中有关电压、温度、压力等测得的连续数
25、据。这些数据取值是连续的，但又是随机的。我们可用一这些数据取值是连续的，但又是随机的。我们可用一维的维的连续型随机变量连续型随机变量X来描述这些消息。这种信源称来描述这些消息。这种信源称为为连续信源连续信源，其数学模型是连续型的概率空间。，其数学模型是连续型的概率空间。连续信源单变量连续信源的描述单变量连续信源的输出是取值连续的随机变量。可用单变量连续信源的输出是取值连续的随机变量。可用变量的变量的概率密度概率密度、变量间的、变量间的条件概率密度条件概率密度和和联合概率联合概率密度密度描述。描述。一维概率密度函数一维概率密度函数条件概率密度和联合概率密度函数条件概率密度和联合概率密度函数其中：
26、波形信源波形信源l更一般地说，实际信源输出的消息常常是时间和取更一般地说，实际信源输出的消息常常是时间和取值都是连续的。值都是连续的。l例如，语音信号例如，语音信号X(t)、热噪声信号、热噪声信号n(t)、场景图、场景图像信号像信号X(x0,y0,t)等时间连续函数。等时间连续函数。l在某一固定时间在某一固定时间t，它们的可能取值又是，它们的可能取值又是连续的和连续的和随机随机的。的。l对于这种信源输出的消息，可用对于这种信源输出的消息，可用随机过程随机过程来描述。来描述。称这类信源为称这类信源为随机波形信源随机波形信源。波形信源波形信源l分分析析一一般般随随机机波波形形信信源源比比较较复复杂
27、杂和和困困难难。常常见见的的随随机机波波形形信信源源输输出出的的消消息息是是时时间间、频带受限的随机过程。频带受限的随机过程。l 根据取样定理，可以把这根据取样定理，可以把这样的随机过程用一系列时样的随机过程用一系列时间间(或频率或频率)域上离散的取样域上离散的取样值来表示，而每个取样值值来表示，而每个取样值都是连续型随机变量。都是连续型随机变量。l随机过程转换成时间随机过程转换成时间(或频或频率率)上离散的随机序列。在上离散的随机序列。在某种条件下可以转换成随机某种条件下可以转换成随机变量间统计独立的随机序列。变量间统计独立的随机序列。l平稳的随机过程可转换成平平稳的随机过程可转换成平稳的随
28、机序列。稳的随机序列。随机波形信随机波形信源源转换成转换成连续平稳信源连续平稳信源。若。若对每个取样值对每个取样值(连续型的连续型的)经经过分层过分层(量化量化)，就可将连续，就可将连续的取值转换成有限的或可数的取值转换成有限的或可数的离散值。连续信源转换成的离散值。连续信源转换成了了离散信源离散信源。 波形信源（时间连续、取值连续）波形信源（时间连续、取值连续）连续信源（时间离散、取值连续）连续信源（时间离散、取值连续）离散信源（时间离散、取值离散）离散信源（时间离散、取值离散）采样量化实际信源实际信源在离散情况下是消息序列信源，在连续情况下是随机过程信源，它们分别代表数字与模拟信源。实际信
29、源离散序列信源(1)其中，其中，i=1,2,n为每个消息（符号）取值的种类数为每个消息（符号）取值的种类数 l=1,2,L为消息（符号）序列的长度为消息（符号）序列的长度应应注注意意的的是是i和和l是是代代表表两两个个不不同同范范畴畴的的变变量量，表表示示不不同同的的概概念念，切切勿混淆。勿混淆。如：五码英文报：如：五码英文报：i=26+1，l=5i=1,2,nl=1,2,L实际信源离散序列信源(2)信源输出是一组随机序列（矢量）：信源输出是一组随机序列（矢量）：其样值为：其样值为：对应概率为：对应概率为：由由于于每每个个随随机机变变量量U=1,2,n有有n种种取取值值，则则有有种可能取值。种
30、可能取值。如：五码英文报：如：五码英文报：i=26+1，l=5，共有共有275种取值种取值实际信源离散序列信源(3)例例36：最最简简单单L=3的的三三位位PCM信信源源：这这时时L=3,n=2,即即i=0,1，则有：，则有：实际信源连续波形信源（1）在在实实际际的的连连续续波波形形信信源源中中，可可以以采采用用两两种种方方法法进行分析进行分析一类是将连续波形信源转化为随机序列信源一类是将连续波形信源转化为随机序列信源另一类是仍然采用随机过程来分析另一类是仍然采用随机过程来分析o什么样的信源可以进行离散化处理？什么样的信源可以进行离散化处理？n实实际际上上，只只要要满满足足一一个个非非常常宽宽
31、松松的的条条件件，即即满满足足限限时时(T)、限限频频(F)的的连连续续消消息息信信源源，即即满满足足物物理理可可实实现条件下，均可离散化为随机序列。现条件下，均可离散化为随机序列。实际信源连续波形信源（2）图像信源图像信源图像信源一般可以引用一个四元的随机场来表示：图像信源一般可以引用一个四元的随机场来表示：（简化）（简化）主要统计特性主要统计特性：初步可以认为是一个近似的平稳遍历过程初步可以认为是一个近似的平稳遍历过程实际信源连续波形信源（3）语音信源语音信源语语音音信信源源可可以以近近似似用用一一个个一一维维随随机机过过程程U(,t)表表示示。严严格格的的讲讲，它它是是一一个个非非平平稳
32、稳过过程程，但但是是对对于于短短时时段段(5-50ms)可可认认为为是是平平稳稳的的，且且某某些些是是随随机机噪噪声声（清清辅辅音音），而而某某些些时时段段则则呈呈现现周周期期性性特特征征（浊浊音音），还还有有一一些些短短时时段段是是二二者者的的混混合合，但但是是对对于于短短时时段段(5-50ms)可认为是平稳的。可认为是平稳的。信源输出信号中携带信息如何度量？信源输出信号中携带信息如何度量？（以离散信源为例）（以离散信源为例）问题三问题三信源输出信号中携带信息的度量信源输出信号中携带信息的度量单符号信源的熵单符号信源的熵离散无记忆平稳信源的熵离散无记忆平稳信源的熵无记忆平稳信源的无记忆平稳信
33、源的N次扩展信源的熵次扩展信源的熵有记忆平稳信源的熵率有记忆平稳信源的熵率离散无记忆平稳信源的N次扩展信源的熵因为是无记忆的因为是无记忆的/ /统计独立统计独立 若若ai =(xi1xi2xi3xiN) 则则p(ai)=p(xi1)p(xi2) p(xiN) 其中其中i1,i2,iN1,2,n 根据信息熵的定义，根据信息熵的定义，N次扩展信源的熵次扩展信源的熵可以证明：可以证明：离散无记忆信源离散无记忆信源X的的N次扩展信源的熵等于离散信源次扩展信源的熵等于离散信源X的熵的熵的的N倍倍，即，即H(X)=H(XN)=NH(X)例37有一离散无记忆信源有一离散无记忆信源求这个离散无记忆信源的二次扩
34、展信源，扩展信源的每个符号是信源求这个离散无记忆信源的二次扩展信源，扩展信源的每个符号是信源X的输出长度为的输出长度为2的符号序列。的符号序列。因为信源因为信源X共有共有3个不同符号，所以由信源个不同符号，所以由信源X中每两个符号组成的不中每两个符号组成的不同排列共有同排列共有32=9种，得二次扩展信源共有种，得二次扩展信源共有9个不同的符号。个不同的符号。因为信源因为信源X是无记忆的，则有是无记忆的，则有可以算得可以算得H(X)=1.5 比特比特/符号符号（此处的符号是指（此处的符号是指X信源的输出符号信源的输出符号xi）H(X)=H(X2)=H(A)=3 比特比特/符号符号（此处的符号是指
35、扩展信源的输出（此处的符号是指扩展信源的输出符号符号ai ，它是由二个，它是由二个xi符号组成）符号组成） 所以所以 H(X)=2H(X)对上述结论的解释：对上述结论的解释： 因为扩展信源因为扩展信源XN的每一个输出符号的每一个输出符号ai是由是由N个个xi所组成的序所组成的序列，并且序列中前后符号是统计独立的。现已知每个信源符列，并且序列中前后符号是统计独立的。现已知每个信源符号号xi含有的平均信息量为含有的平均信息量为H(X)，那么，那么，N个个xi组成的无记忆序组成的无记忆序列平均含有的信息量就为列平均含有的信息量就为NH(X)（根据熵的可加性）。因此信（根据熵的可加性）。因此信源源XN
36、每个输出符号含有的平均信息量为每个输出符号含有的平均信息量为NH(X)。n离散无记忆平稳信源的熵当随机变量当随机变量X1和和X2相互统计独立时，则相互统计独立时，则因此因此结论：结论：p随机变量随机变量X1和和X2统计独立时，二维离散平稳无记忆信源统计独立时，二维离散平稳无记忆信源X =X1X2的熵的熵H(X)等于等于X1的熵的熵H(X1)和和X2的熵的熵H(X2)之和。之和。当当X1和和X2取值于同一集合时，取值于同一集合时， H(X1)=H(X2)=H(X)， H(X)= H(X2)=2H(X)，与离散无记忆信源二次扩展信源的，与离散无记忆信源二次扩展信源的情况相同。情况相同。p可以把离散
37、无记忆平稳信源的二次扩展信源看成是二维可以把离散无记忆平稳信源的二次扩展信源看成是二维离散无记忆平稳信源的特例；离散无记忆平稳信源的特例；离散平稳有记忆信源的信源熵N维离散平稳有记忆信源的熵维离散平稳有记忆信源的熵H(X)= H(X1)+ H(X2/X1)+ H(X3/X1X2)+ H(XN/X1X2XN-1)证明证明：（略）：（略） 结论：结论：多符号离散平稳有记忆信源多符号离散平稳有记忆信源X的熵的熵H(X)是是X中中起始时起始时刻随机变量刻随机变量X1的熵与各阶条件熵之和。由于信源是平稳的，的熵与各阶条件熵之和。由于信源是平稳的，这个和值与起始时刻无关。这个和值与起始时刻无关。离散平稳有
38、记忆信源的条件熵的非递增性离散平稳有记忆信源的条件熵的非递增性条件熵条件熵H(XN /X1X2XN-1)随随N的增加是非递增的，即的增加是非递增的，即H(XN /X1X2XN-1) H(XN /X1X2XN-2)证明证明 前面已证明：前面已证明： H(X2/X1) H(X2)， 同理可证：同理可证： H(X3/X1X2) H(X3/X2)， 由于信源是平稳的，所以由于信源是平稳的，所以 H(X3/X2)= H(X2/X1)， 故得故得 H(X3/X1X2) H(X2/X1) H(X1) 对于平稳信源递推对于平稳信源递推 H(XN /X1X2XN-1) H(XN-1 /X1X2XN-2 ) H(
39、XN-2 /X1X2XN-3 ) H(X3/X1X2) H(X2/X1) H(X1)离散平稳有记忆信源的平均符号熵离散平稳有记忆信源的平均符号熵H(X)/矢量熵矢量熵= H(X1X2XN-1XN)/联合熵联合熵表示平均发一表示平均发一个消息个消息（由（由N个符号组成）个符号组成）提供的信息量。提供的信息量。平均符号熵平均符号熵：信源平均每发一个符号提供的信息量为：信源平均每发一个符号提供的信息量为离散平稳有记忆信源的离散平稳有记忆信源的熵率（极限熵）熵率（极限熵）对于离散平稳信源，考察其输出信息量对于离散平稳信源，考察其输出信息量例例38XP（x） 0 1 211/36 4/9 1/4ajai
40、01201/41/18011/181/31/18201/187/36ajai01209/111/8012/113/42/9201/87/9P(ai,aj)P(ai/aj)当信源符号间无依赖性时：当信源符号间无依赖性时：当考虑信源符号间的一维依赖性时：当考虑信源符号间的一维依赖性时：条件熵：条件熵：联合熵：联合熵：可见：可见：且：且：考察信源符号间有依赖性时联合信源的平均符号熵：考察信源符号间有依赖性时联合信源的平均符号熵：可见：可见：比特比特/符号符号比特比特/符号符号比特比特/二个符号二个符号比特比特/符号符号分析：分析：结论：符号间的相关性使得信源的平均符号熵减少，即结论：符号间的相关性使
41、得信源的平均符号熵减少，即 每个符号平均携带的信息量减少。每个符号平均携带的信息量减少。问题：问题：H2(X)和和H(X2|X1)哪一个值更能接近实际二维平稳哪一个值更能接近实际二维平稳 信源的熵？即：用哪一个值来表示二维平稳信源信源的熵？即：用哪一个值来表示二维平稳信源 每个符号平均携带的信息量每个符号平均携带的信息量比特比特/符号符号考察：考察：离散平稳有记忆离散平稳有记忆信源符号之间的依赖长度为信源符号之间的依赖长度为N的的信源信源定义定义：N长的信源符号序列的长的信源符号序列的平均符号熵平均符号熵即平均每个信源符号即平均每个信源符号 所携带的信息量为所携带的信息量为比特比特/符号符号当
42、当 时，存在以下性质：时，存在以下性质：条件熵条件熵 随随N的增加是非递增的的增加是非递增的平均符号熵平均符号熵 随随N的增加是非递增的的增加是非递增的N给定时，平均符号熵给定时，平均符号熵=条件熵。即：条件熵。即： 存在，且：存在，且：结论结论：对于有限记忆长度的平稳信源可用有限记忆长度的对于有限记忆长度的平稳信源可用有限记忆长度的条件熵条件熵来对平稳信源进行信息测度。来对平稳信源进行信息测度。熵率熵率对于对于离散平稳信源离散平稳信源，考察其输出信息量，考察其输出信息量假设字母序列长度为假设字母序列长度为N，则有限长度的序列的熵可看成随机矢量（，则有限长度的序列的熵可看成随机矢量（）的熵，可
43、用联合熵表示，）的熵，可用联合熵表示，平均每个字母平均每个字母的熵的熵可以表示为可以表示为当当时，若时，若存在，则：存在，则：定义：定义：为该平稳信源的为该平稳信源的熵率熵率，又称平稳信源的，又称平稳信源的极限熵极限熵或或极极限信息量限信息量对于一般的对于一般的平稳信源平稳信源，可以证明，极限，可以证明，极限一定存在。一定存在。结结 论论熵率的含义：熵率的含义：代表了一般离散平稳有记忆信源平均每发一个符号代表了一般离散平稳有记忆信源平均每发一个符号提供的信息量。提供的信息量。多符号离散平稳信源实际上就是原始信源在不断地发出符号，符多符号离散平稳信源实际上就是原始信源在不断地发出符号，符号之间的
44、号之间的统计关联关系也并不仅限于长度统计关联关系也并不仅限于长度N之内，而是伸向无穷之内，而是伸向无穷远。远。所以要研究实际信源，必须求出熵率所以要研究实际信源，必须求出熵率H，才能确切地表达多，才能确切地表达多符号离散平稳有记忆信源平均每发一个符号提供的信息量。符号离散平稳有记忆信源平均每发一个符号提供的信息量。熵率的计算：熵率的计算：必须测定信源的无穷阶联合概率和条件概率分布，必须测定信源的无穷阶联合概率和条件概率分布，这是相当困难的。有时为了简化分析，往往用条件熵或平均符号这是相当困难的。有时为了简化分析，往往用条件熵或平均符号熵作为熵率的近似值。在有些情况下，即使熵作为熵率的近似值。在
45、有些情况下，即使N值并不大，这些熵值并不大，这些熵值也很接近值也很接近H，例如马尔可夫信源。，例如马尔可夫信源。问题四问题四信源输出信号的信息携带效率如何表示？信源输出信号的信息携带效率如何表示？信源输出信号的信息携带效率的表示信源输出信号的信息携带效率的表示冗余度与信源效率冗余度与信源效率它它表表征征信信源源信信息息率率的的多多余余程程度度，是是描描述述信信源源客客观观统统计计特性的一个物理量。特性的一个物理量。由广义由广义Shannon不等式有：不等式有：冗余度冗余度1o可可见见对对于于有有记记忆忆信信源源，最最小小单单个个消消息息熵熵应应为为 ，即即从理论上看，对有记忆信源只需传送从理论
46、上看，对有记忆信源只需传送 即可。即可。o但但是是这这必必需需要要掌掌握握信信源源全全部部概概率率统统计计特特性性。这这显显然然是是不不现现实实的的。实实际际上上，往往往往只只能能掌掌握握有有限限的的维维，这这时时需需传传送送 ， 那那 么么 与与 理理 论论 值值 相相 比比 ， 就就 多多 传传 送送 了了 。冗余度冗余度2为了定量描述信源有效性，可为了定量描述信源有效性，可定义定义：信源效率：信源效率：信信源源冗冗余余度度：（相对剩余）（相对剩余）或者定义：或者定义：冗余度：冗余度：信源效率：信源效率：相对冗余度：相对冗余度：冗余度冗余度3正正由由于于信信源源存存在在着着冗冗余余度度，即
47、即存存在在着着不不必必要要传传送送的的信信息息，因因此此信信源源也也就就存存在在进进一一步步压压缩缩信信息息率率的的可可能能性性。冗冗余余度度越越大大，压压缩缩潜潜力力也也就就越越大大。可可见见它它是是信信源源编编码码、数数据据压压缩缩的的前前提提与与理理论论基基础础。 字母字母 字母字母 字母字母 空格空格ETOANIR0.20.1050.0720.06540.0630.0590.0550.054SHDLCF.UMP0.05020.0470.0350.0290.0230.0225 0.0210.0175Y.WGBVKXJ.QZ0.0120.0110.01050.0080.0030.0020.
48、0010.001冗余度冗余度4例例39：计算英文文字信源的冗余度）：计算英文文字信源的冗余度）首先给出英文字母（含空格）出现概率如下：首先给出英文字母（含空格）出现概率如下：冗余度冗余度5o首先求得独立等概率情况首先求得独立等概率情况H0 ，即，即o其次，计算独立不等概率情况其次，计算独立不等概率情况H1 ，o再次，若仅考虑字母有一维相关性，求再次，若仅考虑字母有一维相关性，求H2 ，o最最后后实实际际熵熵H，利利用用统统计计推推断断方方法法求求出出。由由于于采采用用的的逼逼近近的的方方法法和和所所取取的的样样本本的的不不同同，推推算算值值也也有有不不同同，这这里里采采用用Shannon的推断
49、值。的推断值。 冗余度冗余度6这这一一结结论论说说明明，英英文文信信源源，从从理理论论上上看看71是多余成分。是多余成分。直直观观地地说说100页页英英文文书书，理理论论上上看看仅仅有有29页页是是有有效效的的，其其余余71页页是是多多余余的的。正正是是由由于于这这一一多多余余量量的的存存在在，才才有有可可能能对对英英文文信源进行压缩编码。信源进行压缩编码。冗余度冗余度7对于其它文字，也有不少人作了大量的统计工作，简述如下：对于其它文字，也有不少人作了大量的统计工作，简述如下：英文英文法文法文德文德文西班牙文西班牙文中文中文（按（按8千汉字计算）千汉字计算）问题五如何有效表示信源输出信号？如何
50、有效表示信源输出信号？编码编码1编码：编码：源字母序列源字母序列码字母序列码字母序列源字母表源字母表码字母表码字母表源序列源序列码序列码序列编码编码2编码分类编码分类信源编码信源编码1针对信源的编码，能更加有效地传输、存储信息。针对信源的编码，能更加有效地传输、存储信息。目目的的：提提高高通通信信系系统统有有效效性性，实实现现信信源源与与通通信信系系统统间间的的统统计计匹匹配配。编编码码后后尽尽可可能能减减少少所所需需信信息的损失，提高编码后携带信息的效率。息的损失，提高编码后携带信息的效率。分类：分类：冗余度压缩冗余度压缩熵压缩熵压缩冗余度冗余度压缩编码，可逆，可逆压缩，经编译码后可以无失真
51、地恢复。后可以无失真地恢复。u(Lossless Coding, Noiseless Coding, Data Compaction, Redundancy Reduction, Entropy Coding)信源信源 = 信息信息 + 冗余冗余对冗余度的冗余度的计算算说明，明，实际信源信源产生信号所携生信号所携带信息的效率非常低，信息的效率非常低，只有只有20 50%，这就涉及数据的有效表示冗余度就涉及数据的有效表示冗余度压缩。 有冗余就可有冗余就可压缩 压缩在一定限度内可逆在一定限度内可逆 技技术 时域域样点之点之间相关（短相关（短时、长时） 统计特性特性：Huffman 编码，算，算术编
52、码Arithmetic Coding 通用通用编码：Lempel-Ziv 编码 信源编码信源编码2熵压缩编码，不可逆压缩熵压缩编码，不可逆压缩 (Lossy Coding, Entropy Compression) 压缩超过一定限度，必然带来失真压缩超过一定限度，必然带来失真 允许的失真越大，压缩的比例越大允许的失真越大，压缩的比例越大 译码时能按一定的失真容许度恢复，保留尽可能多的信息译码时能按一定的失真容许度恢复，保留尽可能多的信息 技术技术 量化：量化： 标量量化标量量化SQ (Scalar Quantization)， 矢量量化矢量量化VQ (Vector Quantization)
53、变换编码变换编码 预测编码预测编码信源编码信源编码3作业 一黑白气象传真图的消息只有黑色和白色两种，即信源一黑白气象传真图的消息只有黑色和白色两种，即信源X=黑黑,白白。设黑色出现的概率为。设黑色出现的概率为P(黑黑)=0.3，白色的出现，白色的出现概率概率P(白白)=0.7。 (1) 假设图上黑白消息出现前后没有关联，求熵假设图上黑白消息出现前后没有关联，求熵H(X)； (2) 假设消息前后有关联，其依赖关系为假设消息前后有关联，其依赖关系为P(白白/白白)=0.9，P(黑黑/白白)=0.1， P(白白/黑黑)=0.2，P(黑黑/黑黑)=0.8，求此一阶马尔可夫信源，求此一阶马尔可夫信源的熵的熵H2 (X)； (3) 分别求上述两种信源的剩余度，比较大小，并说明分别求上述两种信源的剩余度，比较大小，并说明其物理意义。其物理意义。作业1 Kolmogorov A N.Logical Basics for Information Theory and Probability Theory. IEEE Trans on Inform Theory, 1968,Vol IT14，No5， Sept要求要求:1、论文查找（交电子文档）、论文查找（交电子文档）2、论文翻译（交电子文档）、论文翻译（交电子文档）3、论文讲解（交演示电子文档）、论文讲解（交演示电子文档）
