信息论基础详细课件.ppt

《信息论基础详细课件.ppt》由会员分享，可在线阅读，更多相关《信息论基础详细课件.ppt（196页珍藏版）》请在三一办公上搜索。

1、信息论基础,李刚北京科技大学信息工程学院,信息论基础教程,李亦农 李梅 编著北京邮电大学出版社,目录,第一章 绪论第二章 信息的度量 第三章 信源及信息熵 第四章 信道及信道容量 第五章 无失真信源编码 第六章 有噪信道编码 第七章 限失真信源编码,1.1 信息的概念1.2 信息论研究对象、目的和内容,第一章 绪论,1.1 信息的概念,信息论是通信的数学基础，它是随着通信技术的发展而形成和发展起来的一门新兴横断学科。信息论创立标志是1948年Claude Shannon(香农)发表论文“A Mathematical Theory of Communication”。在这篇文章中香农创造性的采用

2、概率论的方法来研究通信中的问题，并且对信息给予了科学的定量描述，第一次提出了信息熵的概念。1928年，哈特莱(Hartley)首先提出了用对数度量信息的概念。一个消息所含有的信息量用它的可能值的个数的对数来表示。,香农,(香农)信息：信息是事物运动状态或存在方式的不确定性的描述。可运用研究随机事件的数学工具概率来测度不确定性大小。在信息论中，我们把消息用随机事件表示，而发出这些消息的信 源则用随机变量来表示。,我们把某个消息 出现的不确定性的大小，定义为自信息，用这 个消息出现的概率的对数的负值来表示：自信息同时表示这个消息所包含的信息量，也就是最大能够给予 收信者的信息量。如果消息能够正确传

3、送，收信者就能够获得这 么大小的信息量。,信源所含有的信息量定义为信源发出的所有可能消息的平均不确定性，香农把信源所含有的信息量称为信息熵。自信息的统计平均定义为信源熵，即：这里的q表示信源消息的个数。信息熵表示信源的平均不确定性的大小，同时表示信源输出的消息所含的平均信息量。因此，虽然信源产生的消息可能会含有不同的信息量。在收信端，信源的不确定性得到部分或全部消除，收信者就得到信息。信息在数量上等于通信前后“不确定性”的消除量(减少量),1.2 信息论研究对象、目的和内容,信息论研究对象 广义的通信系统，它把所有的信息流通系统都抽象成如下模型：,图1.1 通信系统模型,这个通信系统主要分成五

4、个部分：(1).信源 顾名思义，信源是产生消息和消息序列的源。(2).编码器 编码就是把消息变成适合在信道传输的物理量信号。编码器可分为信源编码器和信道编码器。信源编码目的是提高通信系统有效性 和提高信息传输的可靠性。实际通信系统中，可靠性和有效性常常相互矛盾。(3).信道 信道是指通信系统把载荷消息的信号从发送端送到接收端的媒介或通道，是包括收发设备在内的物理设施。(4).译码器 译码就是把信道输出的已迭加了干扰的编码信号进行反变换，变成信宿 能够接受的消息。译码器也可分成信源译码器和信道译码器。(5).信宿 信宿是消息传送的对象，即接受消息的人或机器。,信息论研究的是关于这个通信系统的最根

5、本、最本质的问题。例如：.什么是信息？如何度量信息？.怎样确定信源中含有多少信息量？.对于一个信道，它传输信息量的最高极限(信道容量)是多少？.为了能够无失真的传输信源信息，对信源编码时所需的最少的码 符号数是多少？(无失真信源编码即香农第一定理).在有噪信道中有没有可能以接近信道容量的信息传输率传输信息 而错误概率几乎为零？(有噪信道编码即香农第二定理).如果对信源编码时允许一定量的失真，所需的最少的码符号数又 是多少？(限失真信源编码即香农第三定理),目前，对信息论的研究内容一般有三种理解：(1)狭义信息论：又称香农信息论。主要通过数学描述与定量分析，研究通信系统从信源到信宿的全过程，包括

6、信息的测度、信道容量以及信源和信道编码理论等问题，强调通过编码和译码使收、发两端联合最优化，并且以定理的形式证明极限的存在这部分内容是信息论的基础理论。(2)一般信息论：也称工程信息论。主要也是研究信息传输和处理问题，除香农信息论的内容外，还包括噪声理论信号滤波和预测、统计检测和估计、调制理论、信息处理理论以及保密理论等(3)广义信息论：不仅包括上述两方面内容，而且包括所有与信息有关的自然和社会领域，如模式识别、计算机翻译、心理学、遗传学、神经生理学、语言学、语义学甚至包括社会学中有关信息的问题。,2.1 自信息和互信息 2.2 平均自信息 2.3 平均互信息,第二章 信息的度量,关于信息的度

7、量有几个重要的概念：（1）自信息：一个事件(消息)本身所包含的信息量，它是由事件的不确定性决定的。比如抛掷一枚硬币的结果是正面这个消息所包含的信息量（2）互信息：一个事件所给出关于另一个事件的信息量，比如今天下雨所给出关于明天下雨的信息量。（3）平均自信息（信息熵）：事件集（用随机变量表示）所包含的平均信息量，它表示信源的平均不确定性。比如抛掷一枚硬币的试验所包含的信息量。（4）平均互信息：一个事件集所给出关于另一个事件集的平均信息量比如今天的天气所给出关于明天的天气的信息量。,2.1 自信息和互信息,2.1.1 自信息 随机事件的自信息量 是该事件发生概率 的函数，并且应该满足以下公理化条件

8、：1.是 的严格递减函数。当 时，概率 越小，事件发生的不确定性越大，事件发生后所包含的自信息量越大 2极限情况下当=0时，；当=1时，=0。3另外，从直观概念上讲，由两个相对独立的不同的消息所提供的 信息量应等于它们分别提供的信息量之和。可以证明，满足以上公理化条件的函数形式是对数形式。,定义2.1 随机事件的自信息量定义为该事件发生概率的对数的负值。事件 的概率为，则它的自信息定义为：从图2.1种可以看到上述信息量的定义正是满足上述公理性条件的函数形式。代表两种含义：当事件发生以前，等于事件发生的不确定性的大小；当事件发生以后，表示事件所含有或所能提供的信息量。,图2.1 自信息量,自信息

9、量的单位与所用对数的底有关。（1）常取对数的底为2，信息量的单位为比特(bit，binary unit)。当=1/2时，=1比特，即概率等于1/2的事件具有1比特的自信 息量。（2）若取自然对数（对数以e为底），自信息量的单位为奈特（nat，natural unit）。1奈特=比特=1.443比特（3）工程上用以10为底较方便。若以10为对数底，则自信息量的单位 为哈特莱（Hartley）。1哈特莱=比特=3.322比特（4）如果取以r为底的对数（r1），则=进制单位 1r进制单位=比特,2.1.2 互信息,定义2.2 一个事件 所给出关于另一个事件 的信息定义为互信息，用 表示。互信息 是已

10、知事件 后所消除的关于事件 的不确定性，它等于事件 本身的不确定性 减去已知事件 后对 仍然存在的不确定性。互信息的引出，使信息得到了定量的表示，是信息论发展的一个重要的里程碑。,2.2 平均自信息,2.2.1 平均自信息(信息熵)的概念自信息量是信源发出某一具体消息所含有的信息量，发出的消息不同所含有的信息量不同。因此自信息量不能用来表征整个信源的不确定度。我们定义平均自信息量来表征整个信源的不确定度。平均自信息量又称为信息熵、信源熵，简称熵。因为信源具有不确定性，所以我们把信源用随机变量来表示，用随机变量的概率分布来描述信源的不确定性。通常把一个随机变量的所有可能的取值和这些取值对应的概率

11、 称为它的概率空间。,定义2.3 随机变量X的每一个可能取值的自信息 的统计平均值定义为随机变量X的平均自信息量:这里q为的所有X可能取值的个数。熵的单位也是与所取的对数底有关，根据所取的对数底不同，可以是比特/符号、奈特/符号、哈特莱/符号或者是r进制单位/符号。通常用比特/符号为单位。一般情况下，信息熵并不等于收信者平均获得的信息量，收信者不能全部消除信源的平均不确定性，获得的信息量将小于信息熵。,2.2.2 熵函数的性质,信息熵 是随机变量X的概率分布的函数，所以又称为熵函数。如果把概率分布，记为，则熵函数又可以写成概率矢量 的函数的形式，记为。熵函数 具有以下性质：1.对称性：对称性说

12、明熵函数仅与信源的总体统计特性有关。,2.确定性：在概率矢量中，只要有一个分量为1，其它分量必为0，它们对熵的 贡献均为0，因此熵等于0。也就是说确定信源的不确定度为0。3.非负性：对确定信源，等号成立。信源熵是自信息的数学期望，自信息是非 负值，所以信源熵必定是非负的。4.扩展性：这个性质的含义是增加一个基本不会出现的小概率事件，信源的熵 保持不变。5.连续性：即信源概率空间中概率分量的微小波动，不会引起熵的变化。,6.递增性 这性质表明，假如有一信源的n个元素的概率分布为，其中某个元素 又被划分成m个元素，这m个元素的概率之和等于元素 的概率，这样得到的新信源的熵增加，熵增加了一项是由于划

13、分产生的不确定性。7.极值性：式中n是随机变量X的可能取值的个数。极值性表明离散信源中各消息等概率出现时熵最大，这就是最大离散熵定理。连续信源的最大熵则与约束条件有关。,8.上凸性:是严格的上凸函数，设 则对于任意小于1的正数 有以下不等式成立：凸函数在定义域内的极值必为极大值，可以利用熵函数的这个性质 可以证明熵函数的极值性。,直观来看，随机变量的不确定程度并不都是一样的。香农指出，存在这样的不确定性度量，它是随机变量的概率分布的函数，而且必须满足三个公理性条件 1.连续性条件：应是 的连续函数；2.等概时为单调函数：应是 的增函数；3.递增性条件：当随机变量的取值不是通过一次试验而是若干次

14、试验才最 后得到时，随机变量在各次试验中的不确定性应该可加，且其和始终与 通过一次试验取得的不确定程度相同，即：其中,2.2.3 联合熵与条件熵,一个随机变量的不确定性可以用熵来表示，这一概念可以方便地推广到多个随机变量。定义2.4 二维随机变量 的概率空间表示为其中：满足概率空间的非负性和完备性：,二维随机变量 的联合熵定义为联合自信息的数学期望，它是二维随机变量 的不确定性的度量。定义2.5 给定 时，的条件熵：其中，表示已知 时，的平均不确定性。,各类熵之间关系：,1联合熵与信息熵、条件熵的关系：这个关系可以方便地推广到N个随机变量的情况：称为熵函数的链规则。推论：当二维随机变量X,Y相

15、互独立时，联合熵等于X,Y各自熵之和：2条件熵与信息熵的关系：3联合熵和信息熵的关系：当X、Y相互独立时等号成立。,2.3 平均互信息,2.3.1 平均互信息的概念 为了从整体上表示从一个随机变量Y所给出关于另一个随机变量 的信息量，我们定义互信息 在的 联合概率空间中的统计平均值为随机变量X和Y间的平均互信息：定义2.6,2.3.2 平均互信息的性质,1.非负性:平均互信息是非负的，说明给定随机变量Y后，一般来说总能消除一 部分关于X的不确定性。2.互易性(对称性)：对称性表示从Y中获得的关于X信息量等于从X中获得的关于Y信息量3.平均互信息和各类熵的关系:当 统计独立时，,4.极值性：极值

16、性说明从一个事件提取关于另一个事件的信息量，至多只能是另一个 事件的平均自信息量，不会超过另一事件本身所含的信息量。5.凸函数性：定理2.1 当条件概率分布 给定时，平均互信息 是输入分 布 的上凸函数。定理2.2 对于固定的输入分布，平均互信息量 是条件概率 分布 的下凸函数。,2.3.3 数据处理定理,为了表述数据处理定理，需要引入三元随机变量 的平均条件互信息和平均联合互信息的概念。定义2.7 平均条件互信息 它表示随机变量 给定后，从随机变量 所得到的关于随机变量 的信息量定义2.8 平均联合互信息 它表示从二维随机变量 所得到得关于随机变量 的信息量。,定理2.3(数据处理定理)如果

17、随机变量 构成一个马尔可夫链，则有以下关系成立：等号成立的条件是对于任意的，有：数据处理定理再一次说明，在任何信息传输系统中，最后获得的信息至多是信源所提供的信息，如果一旦在某一过程中丢失一些信息，以后的系统不管如何处理，如不触及丢失信息的输入端，就不能再恢复已丢失的信息，这就是信息不增性原理，它与热熵不减原理正好对应，反映了信息的物理意义。,3.1 信源的分类及其数学模型 3.2 离散单符号信源 3.3 离散多符号信源*3.4 连续信源,第三章 信源及信息熵,信源(Information Source)是信息的来源，是产生消息(符号)、时间离散的消息序列(符号序列)以及时间连续的消息的来源。

18、信源输出的消息都是随机的，因此可用概率来描述其统计特性。在信息论中，用随机变量X、随机矢量X、随机过程 分别表示 产生消息、消息序列以及时间连续消息的信源。信源的主要问题：1如何描述信源（信源的数学建模问题）2怎样计算信源所含的信息量 3怎样有效的表示信源输出的消息，也就是信源编码问题,3.1 信源的分类及其数学模型,信源分类有多种方法，根据信源输出的消息在时间和取值上是离散或连续进行分类：,表3.1 信源的分类,我们还可以根据各维随机变量的概率分布是否随时间变化将信源分为平稳信源和非平稳信源，根据随机变量间是否统计独立将信源分为有记忆信源和无记忆信源。一个实际信源的统计特性往往是相当复杂的，

19、要想找到精确的数学模型很困难。实际应用时常常用一些可以处理的数学模型来近似。随机序列，特别是离散平稳随机序列是我们研究的主要内容。,随机序列,3.2 离散单符号信源,输出单个离散取值的符号的信源称为离散单符号信源。它是最简单、最基本的信源，是组成实际信源的基本单元。用离散随机变量表示。信源所有可能输出的消息及其对应的概率组成的二元序对 称为信源的概率空间：信源输出的所有消息自信息的统计平均值定义为信源的平均自信息量(信息熵)，它表示离散单符号信源的平均不确定性：,3.3 离散多符号信源,定义3.1：对于随机变量序列，在任意两个不同时刻 和(和 为大于1的任意整数)信源发出消息的概率分布完全相同

20、即对于任意的，和具有相同的概率分布。也就是即各维联合概率分布均与时间起点无关的信源称为离散平稳信源。,对于离散多符号信源,我们引入熵率的概念，它表示信源输出的符号序列中，平均每个符号所携带的信息量。定义3.2 随机变量序列中，对前N个随机变量的联合熵求平均：称为平均符号熵。如果当 时上式极限存在，则 称为熵率，或称为极限熵，记为：,3.3.1 离散平稳无记忆信源,离散平稳无记忆信源输出的符号序列是平稳随机序列，并且符号之间是无关的，即是统计独立的。假定信源每次输出的是N长符号序列，则它的数学模型是N维离散随机变量序列：，并且每个随机变量之间统计独立。同时，由于是平稳信源，每个随机变量的统计特性

21、都相同，还可把一个输出N长符号序列的信源记为：根据统计独立的多维随机变量联合熵与信息熵之间的关系，可推出：离散平稳无记忆信源的熵率：,3.3.2 离散平稳有记忆信源,实际信源往往是有记忆信源。对于相互间有依赖关系的N维随机变量的联合熵存在以下关系（熵函数的链规则）：定理3.1 对于离散平稳信源，有以下几个结论：（1）条件熵 随N的增加是递减的；（2）N给定时平均符号熵大于等于条件熵，即（3）平均符号熵 随N的增加是递减的；（4）如果，则 存在，并且,有一类信源，信源在某时刻发出的符号仅与在此之前发出的有限个符号有关，而与更早些时候发出的符号无关，这称为马尔可夫性，这类信源称为马尔可夫信源。马尔

22、可夫信源可以在N不很大时得到。如果信源在某时刻发出的符号仅与在此之前发出的m个符号有关，则称为m阶马尔可夫信源，它的熵率：,（马尔可夫性）,（平稳性）,通常记作,3.3.3 马尔可夫信源,马尔可夫信源是一类相对简单的有记忆信源，信源在某一时刻发出某一符号的概率除与该符号有关外，只与此前发出的有限个符号有关。因此我们把前面若干个符号看作一个状态，可以认为信源在某一时刻发出某一符号的概率除了与该符号有关外只与该时刻信源所处的状态有关，而与过去的状态无关。信源发出一个符号后，信源所处的状态即发生改变，这些状态的变化组成了马氏链。,图3.1 马尔可夫信源,对于一般的 阶马尔可夫信源，它的概率空间可以表

23、示成：令，从而得到马尔可夫信源的状态空间：状态空间由所有状态及状态间的状态转移概率组成。通过引入状态转移概率，可以将对马尔可夫信源的研究转化为对马尔可夫链的研究。,下面计算遍历的m阶马尔可夫信源的熵率。当时间足够长后，遍历的马尔可夫信源可以视作平稳信源来处理，又因为m阶马尔可夫信源发出的符号只与最近的m个符号有关，所以极限熵 等于条件熵。对于齐次遍历的马尔可夫链，其状态 由 唯一确定，因此有所以,3.3.4 信源的相关性和剩余度,根据定理3.1可得 由此看出，由于信源输出符号间的依赖关系也就是信源的相关性使信源的实际熵减小。信源输出符号间统计约束关系越长，信源的实际熵越小。当信源输出符号间彼此

24、不存在依赖关系且为等概率分布时，信源的实际熵等于最大熵。定义3.3 一个信源的熵率(极限熵)与具有相同符号集的最大熵的比值称为熵的相对率：信源剩余度为：,信源的剩余度来自两个方面，一是信源符号间的相关性，相关程度越大符号间的依赖关系越长，信源的实际熵越小，另一方面是信源符号分布的不均匀性使信源的实际熵越小。为更经济有效地传送信息，需要尽量压缩信源的剩余度，压缩剩余度的方法就是尽量减小符号间相关性，且尽可能的使信源符号等概率分布。从提高信息传输效率的观点出发，人们总是希望尽量去掉剩余度。但从提高抗干扰能力角度来看，却希望增加或保留信源的剩余度，因为剩余度大的消息抗干扰能力强。信源编码是减少或消除

25、信源的剩余度以提高信息的传输效率，而信道编码则通过增加冗余度来提高信息传输的抗干扰能力。,*3.4 连续信源,3.4.1 连续信源的微分熵连续随机变量的取值是连续的，一般用概率密度函数描述其统计特征单变量连续信源的数学模型为，并满足，是实数域，表示 的取值范围。对于取值范围有限的连续信源还可以表示成：，并满足，（a,b）是 的取值范围。通过对连续变量的取值进行量化分层，可以将连续随机变量用离散随机变量来逼近。量化间隔越小，离散随机变量与连续随机变量越接近当量化间隔趋于0时，离散随机变量就变成了连续随机变量。通过这种方式，我们来推导连续随机变量的熵。,定义连续信源的微分熵为：微分熵又称为差熵。虽

26、然已不能代表连续信源的平均不确定性，也不能代表连续信源输出的信息量，但是它具有和离散熵相同的形式，也满足离散熵的主要特性，比如可加性，但是不具有非负性。同样，我们可以定义两个连续随机变量的联合熵：以及条件熵,3.4.2 连续信源的最大熵,离散信源当信源符号为等概分布时有最大熵。连续信源微分熵也有极大值，但是与约束条件有关，当约束条件不同时，信源的最大熵不同我们一般关心的是下面两种约束下的最大熵。定理3.1 在输出幅度受限时，服从均匀分布的随机变量X具有最大输出熵。定理3.2 对于平均功率受限的连续随机变量，当服从高斯分布时具有最大熵。（对于均值为m，方差为 的连续随机变量，平均功率 p=直流功

27、率+交流功率=）,3.4.3 连续信源的熵功率,均值为零，平均功率限定为p的连续信源当服从高斯分布时达到最大熵也就是说，高斯信源的熵值与p有确定的对应关系：现在假定限定的平均功率为p，某连续信源的熵为h(X)，则与它具有相同熵的高斯信源的平均功率 定义为熵功率即 所以，当该连续信源为高斯信源时等号成立。的大小可表示连续信源剩余的大小。如果熵功率等于信源平均功率表示信源没有剩余；熵功率和信源平均功率相差越大，说明信源的剩余越大。信源平均功率和熵功率之差 称为连续信源的剩余度。,4.1 信道的分类 4.2 离散单符号信道及其信道容量 4.3 离散多符号信道及其信道容量 4.4 组合信道及其信道容量

28、*4.5 连续信道及其信道容量*4.6 波形信道及其信道容量,第四章 信道及其信道容量,信道是指信息传输的通道，包括空间传输和时间传输。我们在实际通信中所利用的各种物理通道是空间传输信道的最典型的例子，时间传输是指将信息保存，在以后读取，如磁带、光盘等在时间上将信息进行传输的信道。有时我们把为了某种目的而使信息不得不经过的通道也看作信道，这里最关键的是信道有一个输入以及一个与输入有关的输出。至于信道本身的物理结构可能是千差万别的，信息论研究的信道其输入点和输出点在一个实际物理通道中所处位置的选择完全取决于研究的目的。关于信道的主要问题有：1.信道的建模（信道的统计特性的描述）2.信道容量的计算

29、 3.在有噪信道中能不能实现可靠传输？怎样实现可靠传输？,4.1 信道的分类,信息论不研究信号在信道中传输的物理过程，假定信道的传输特性已知，这样信道就可以用图4.1所示的抽象的数学模型来描述。在信息论中，信道通常表示成：，即信道输入随机变量X、输出随机变量Y以及在输入已知的情况下，输出的条件概率分布。根据实际应用的需要，信道有几种分类方法：(1)按其输入/输出信号在幅度和时间 上的取值是离散或连续来划分 如表4.1所示：,图4.1 信道模型,表4.1 按其输入/输出信号在幅度和时间上的取值是离散或连续来划分（2）按其输入/输出信号之间关系的记忆特性分为有记忆信道和 无记忆信道。（3）按输入/

30、输出信号之间的关系是否确定关系分为有噪声信道 和无噪声信道。,（4）另外，根据信道输入和输出的个数可分为 两端信道（单用户信道）：只有一个输入端和一个输出端的单 向通信的信道。多端信道（多用户信道）：双向通信或三个或更多个用户之间 相互通信的情况。本课程主要研究两端信道的情况。（5）根据信道的统计特性是否随时间变化分为：恒参信道（平稳信道）：信道的统计特性不随时间变化。卫星通信信道在某种意义下可以近似为恒参信道。随参信道（非平稳信道）：信道的统计特性随时间变化。如短波通信中，其信道可看成随参信道。本课程主要研究恒参信道的情况。,4.2 离散单符号信道及其信道容量,4.2.1 离散单符号信道的数

31、学模型 信道的输入、输出都取值于离散符号集，且都用一个随机变量来表示的信道就是离散单符号信道。设离散单符号信道的输入随机变量为，输出随机变量为，由于信道中存在干扰，因此输入符号在传输中将产生错误，这种信道干扰对传输的影响可用传递概率 描述：信道传递概率实际上是一个传递概率矩阵，称为信道矩阵，记为：,为了表述简便，常常写成,下面推导一般离散单符号信道的一些概率关系：（1）输入输出随机变量的联合概率分布为 则有 其中，是信道传递概率，即输入为，通过信道传输输出 的概率，通常称为前向概率。它是由于信道噪声引起的，所 以通常用它描述信道噪声的特性。而 是已知信道输出符号，输入符号为 的概率，称为后向概

32、率。有时把 称为输入 符号的先验概率。而对应的把 称为输入符号的后验概率。,（2）由全概率公式，可从先验概率和信道传递概率求输出符号概率：写成向量的形式：或记成（3）根据贝叶斯公式，可由先验概率和信道的传递概率求后向概率：,4.2.2 信道容量的概念,平均互信息 是接收到输出符号集 后所获得的关于输入符号集 的信息量。信源的不确定性为，由于干扰的存在，接收端收到 后对信源仍然存在的不确定性为，又称为信道疑义度。信宿所消除的关于信源的不确定性，也就是获得的关于信源的信息为，它是平均意义上每传送一个符号流经信道的信息量，从这个意义上来说，平均互信息又称为信道的信息传输率，通常用 表示。即 有时我们

33、所关心的是信道在单位时间内平均传输的信息量。如果平均传输一个符号为t秒，则信道平均每秒钟传输的信息量为 一般称为信息传输速率。,比特/符号,比特/秒,对于固定的信道，总存在一种信源（某种输入概率分布），使信道平均传输一个符号接收端获得的信息量最大，也就是说对于每个固定信道都有一个最大的信息传输率，这个最大的信息传输率即为信道容量，而相应的输入概率分布称为最佳输入分布。定义4.1 信道容量为平均互信息对于输入概率分布的最大值：单位依所用的对数底不同可以是比特/符号、奈特/符号等。若平均传输一个符号需要t秒钟，则信道在单位时间内平均传输的最大信息量 信道容量是信道传送信息的最大能力的度量，信道实际

34、传送的信息量必然不大于信道容量。,图4.3 表示不同的二元对称信道，其传递概率p不同，信道容量也不同。当p=1/2时，是一种最坏的信道，这时C=0，即该信道不能传递任何信息，信息全部损失在信道中了。而当p=0 或p=1时，C=1，这是最好的情况，信道能够无失真传送信源信息。,图4.3 BSC的信道容量,4.2.3 几种特殊信道的信道容量,1.具有扩展性能的无损信道无损信道是一个输入对应多个输出。如图4.4所示，信道矩阵为 无损信道信道矩阵中每一列只有一个非零元素，接收到信道输出符号后对输入符号将不存在不确定性。,图4.4 无损信道,2.具有归并性能的无噪信道无噪信道是一个输出对应多个输入。如图

35、4.5所示，信道矩阵为 无噪信道每一行只有一个非零元素1，信道矩阵元素非零即1。已知信道输入符号，必能确定输出符号。,图4.5 无噪信道,3.具有一一对应关系的无噪无损信道 无噪无损信道输入、输出之间有确定的一一对应关系，即。信道传递概率为：如图4.6所示，信道矩阵为：无噪无损信道每一行、每一列只有一个“1”已知 X后对Y不存在不确定性，收到 Y后对X也不存在不确定性。,图4.6 无噪无损信道,4.2.4 离散对称信道的信道容量,离散信道中有一类特殊的信道，其特点是信道矩阵具有行对称性，利用这个对称性我们可以简化信道容量的计算。定义4.2 若信道矩阵中，每行都是第一行元素的不同排列，则称此类信

36、道为行对称信道。定义4.3 若信道矩阵中，不仅每行都是第一行元素的不同排列，而且每列都是第一列元素的不同排列，这类信道称为对称信道。定义4.4 若信道矩阵中，每行都是第一行元素的不同排列，每列并不都是第一列元素的不同排列，但是可以按照信道矩阵的列将信道矩阵划分成若干对称的子矩阵，则称这类信道为准对称信道。,定义4.5 若对称信道中输入符号和输出符号个数相同，且信道中总的错误概率为p，对称地平均分配给r-1个输出符号，r为输入输出符号的个数，即信道矩阵为 则称此信道为强对称信道或均匀信道。,二元对称信道就是r=2的均匀信道。一般信道的信道矩阵中各行之和为1但各列之和不一定等于1，而均匀信道中各列

37、之和亦等于1。定理4.1 对于对称信道，当输入分布为等概分布时，输出分布必能达到等概分布。定理4.2 若一个离散对称信道具有r个输入符号，s个输出符号，则当输入为等概分布时达到信道容量，且 其中 为信道矩阵中的任一行。推论：均匀信道的信道容量为,当输入为等概分布时，输出为等概分布，信道达到信道容量。当r=2 时的均匀信道常称为二元对称信道，这时C=1H(p)。对于一般的离散行对称信道，信道容量C仍然可以写成：但不一定存在一种输入分布能使输出达到等概分布，此时信道容量 而离散对称信道的信道矩阵中每一列都是由同一组元素的不同排列组成所以保证了当输入符号X为等概分布时，输出符号Y一定也是等概分布输出

38、随机变量熵可以达到。对于离散准对称信道，但是可以证明当输入为等概分布时，可以达到信道容量,4.2.5 一般离散信道的信道容量,平均互信息 是输入概率分布p(x)的上凸函数，因此必存在极大值在信道固定的条件下，平均互信息是r个变量 的多元函数，且满足约束条件，故可用拉格朗日乘子法来求这个条件极值。即在 设辅助函数：，当 时求得的的值即为信道容量。通过计算可得平均互信息的极大值，即,的条件下求 的极值。,这样得到的信道容量有一个参数。在某些情况下可以消去 得到信道容量值。1当输入概率分布只有一个变量时，例如r=2，可以设输入概率分布为 和，因此输入概率分布只有一个变量，这时我们可以直接对 求导求出

39、，从而得出 的极大值C。2对于信道矩阵为可逆矩阵的信道，我们可以采用解方程组的方法。在一般信道的信道容量的推导中我们推出了下式：,移项得当r=s，且信道矩阵是可逆矩阵时，该方程组有唯一解。这时就可以求出，然后根据 求出信道容量：,令,则,所以,由 和C就可以求得输出概率分布：（1）由 列方程组求出；（2）由 求出C；（3）由 求出；（4）由 列方程组求。,再根据,列方程组求,将计算步骤总结如下：,4.2.6 信道容量定理,从以上的讨论可知，求信道容量的问题实际上是在约束条件下求多元函数极值问题，在通常情况下，计算量是非常大的。下面我们介绍一般离散信道的平均互信息 达到信道容量的充要条件，在某些

40、情况下它可以帮助我们较快地找到极值点。定理4.3 设有一般离散信道，它有r个输入信号，s个输出信号。当且仅当存在常数C使输入分布 满足：(1)当(2)当其中，它表示信道输入 时，所给出关于输出Y的信息量。常数C即为所求的信道容量。,时，达到最大值。,信道容量定理告诉我们，平均互信息 取到极大值也就是信道容量时，对于任意，只要它出现的概率大于0，都相等。信道容量定理只给出了达到信道容量时，最佳输入概率分布应满足的条件，并没有给出最佳输入概率分布值，也没有给出信道容量的数值另外，定理本身也隐含着达到信道容量的最佳分布不一定是唯一的，只要输入概率分布满足充要条件式，就是信道的最佳输入分布。在一些特殊

41、情况下，我们常常利用这一定理寻求输入分布和信道容量值。,4.3 离散多符号信道及其信道容量,实际离散信道的输入和输出常常是随机变量序列，用随机矢量来表示称为离散多符号信道，如图4.8所示。实际离散信道往往是有记忆信道为了简化起见，我们主要研究离散无记忆信道。定义4.6 若在任意时刻信道的输出只与此时刻信道的输入有关，而与其他时刻的输入和输出无关，则称之为离散无记忆信道，简称为DMC(discrete memoryless channel)。输入、输出随机序列的长度为N的离散无记忆平稳信道通常称为离散无记忆信道的N次扩展信道。N次扩展信道的信道矩阵是一个的矩阵。,图4.8 离散多符号信道,离散无

42、记忆信道的数学模型仍然表示为：，注意：这时输入、输出均为随机矢量。根据信道无记忆的特性，其转移概率 定理4.4 若信道的输入和输出分别是N长序列X和Y，且信道是无记忆的，则存在 这里Xk、Yk分别是序列X和Y中第k位随机变量。,对于离散无记忆N次扩展信道，当信源是平稳无记忆信源时，其平均互信息 等于单符号信道的平均互信息的N倍。离散无记忆信道的N次扩展信道的信道容量为因为现在输入随机序列在同一信道中传输，所以任何时刻通过离散无记忆信道传输的最大信息量都相同，即所以当信源也是无记忆信源并且每一时刻的输入分布各自达到最佳输入分布时，才能达到这个信道容量NC。一般情况下，消息序列在离散无记忆N次扩展

43、信道中传输时，其平均互信息量,4.4 组合信道及其信道容量,前面我们分析了离散单符号信道和离散无记忆信道的扩展信道。实际应用中常常会遇到两个或更多个信道组合在一起使用的情况。例如，待发送的消息比较多时，可能要用两个或更多个信道并行发送，这种组合信道称为并联信道；有时消息会依次地通过几个信道串联发送，例如无线电中继信道，数据处理系统，这种组合信道称为级联信道。在研究较复杂信道时，为使问题简化，往往可以将它们分解成几个简单的信道的组合。这一节我们将讨论这两种组合信道的信道容量与其组成信道的信道容量间关系。,4.4.1 独立并联信道,一般独立并联信道如图4.10所示。可以把定理4.2的结论推广到N个

44、独立并联信道中来：只有当每个输入随机变量的概率分布均达到各自信道的最佳输入分布时，独立并联信道的信道容量才等于各信道容量之和：当N个独立并联信道信道容量都相同时，,图4.10 独立并联信道,4.4.2 级联信道,级联信道是信道最基本的组合形式，许多实际信道都可以看成是其组成信道的级联。图4.11是由两个单符号信道组成的最简单的级联信道 XYZ 组成一个马尔可夫链。根据马尔可夫链的性质，级联信道的总的信道矩阵等于这两个串接信道的信道矩阵的乘积。求得级联信道的总的信道矩阵后，级联信道的信道容量就可以用求离散单符号信道的信道容量的方法计算。,图4.11 级联信道,*4.5 连续信道及其信道容量,4.

45、5.1 连续随机变量的互信息 连续随机变量和之间的平均互信息定义为 连续随机变量的平均互信息具有和离散随机变量的平均互信息一样的性质：1对称性：2非负性：当且仅当随机变量和统计独立时等号成立,4.5.2 高斯加性信道的信道容量,高斯信道是最差的信道，实际应用中往往把噪声视为高斯噪声。噪声源为高斯白噪声的加性信道。其信道容量 如果噪声N是均值为0、方差为 的高斯随机变量，即 表示噪声N的平均功率。这种信道称为高斯加性连续信道。,当输入随机变量X的概率密度是均值为0、方差为 的高斯随机变量，加性信道的噪声N是均值为0、方差为 的高斯随机变量时，输出随机变量Y也是一个高斯随机变量，其均值为0、方差为

46、此时输出随机变量的熵 达到最大，而信道达到信道容量：其中,称为信道的信噪比。,4.5.3 多维高斯加性信道的信道容量,当信道为多维高斯加性信道时，由于加性噪声信道必然是一个无记忆信道，所以 当且仅当输入随机矢量X中各分量统计独立，并且均为高斯变量时达到信道容量。如果在每个抽样时刻信源和噪声是均值为0、方差分别为 和 的高斯随机变量，,因此,则,比特/n个样值,*4.6 波形信道及其信道容量,波形信道通常根据抽样定理转化成多维连续信道进行处理。一般来说，信道的带宽总是有限的。假设某信道的频带限于（0，B）则其输入、输出信号和噪声都是限频的随机过程，频带限于（0，B）根据抽样定理，可把一个时间连续

47、的信道变换成时间离散的随机序列信道来处理，即用每隔 秒时间的采样值来表示输入、输出信号和噪声。我们把一次采样看成信道的一次传输，由于每秒传送2B个样值，所以单位时间的信道容量为当噪声是双边功率谱密度为 的高斯白噪声时，,比特/秒,这就是著名的香农公式，它适用于加性高斯白噪声信道。从前面的讨论可知，只有当输入信号为功率受限的高斯白噪声信号时，才能达到该信道容量。香农公式说明，当信道容量一定时，增大信道的带宽，可以降低对信噪功率比的要求；反之，当信道频带较窄时，可以通过提高信噪功率比来补偿。上式表明当频带很宽时，信道容量正比于信号功率与噪声谱密度之比上式是加性高斯噪声信道信息传输率的极限值。,当

48、时，则,5.1 信源编码的相关概念5.2 定长码及定长编码定理5.3 变长码及变长编码定理5.4 变长码的编码方法5.5 实用的无失真信源码方法,第五章 无失真信源编码,5.1 信源编码的相关概念,5.1.1 编码器 信源输出的符号序列，需要变换成适合信道传输的符号序列，一般称为码序列，对信源输出的原始符号按照一定的数学规则进行的这种变换称为编码，完成编码功能的器件，称为编码器。接收端有一个译码器完成相反的功能。信源编码器的输入是信源符号集，共有q个信源符号。同时存在另一个符号集，称为码符号集，共有r个码符号，码符号集中的元素称为码元或码符号，编码器的作用就是将信源符号集 中的符号 变换成由

49、个码符号组成的一一对应的码符号序列。编码器输出的码符号序列称为码字，并用 来表示，它与信源符号 之间是一一对应的关系，如图5.1所示。,码字的集合C称为码，即。信源符号 对应的码字 包含 个码符号，称为码字长度，简称码长。所以，信源编码就是把信源符号序列变换到码符号序列的一种映射。若要实现无失真编码，那么这种映射必须是一一对应的、可逆的。一般来说，人们总是希望把信源所有的信息毫无保留地传递到接收端，即实现无失真传递，所以首先要对信源实现无失真编码。,图5.1 信源编码器,信源编码有以下3种主要方法：(1)匹配编码根据信源符号的概率不同，编码的码长不同：概率大的信源符号，所编的代码短；概率小的信

50、源符号所编的代码长，这样使平均码长最短。将要讲述的香农编码、哈夫曼编码、费诺码都是概率匹配编码，都是无失真信源编码。(2)变换编码 先对信号进行变换，从一种信号空间变换为另一种信号空间，然后针对变换后的信号进行编码。(3)识别编码识别编码主要用于印刷或打字机等有标准形状的文字符号和数据的编码，比如中文文字和语音的识别。后两种信源编码均为有失真的信源编码。无失真信源编码主要针对离散信源，连续信源在量化编码的过程中必然会有量化失真，所以对连续信源只能近似地再现信源的消息。,5.1.2 码的分类,1.分组码和非分组码 定义5.1 将信源符号集中的每个信源符号 固定地映射成一个码字，这样的码称为分组码