信息论与编码第2.ppt
126页
第2章 无失真信源编码原理 第2章 无失真信源编码原理 2.1 离散信源及其信息测度 离散信源及其信息测度 2.2 信源编码的基本概念 信源编码的基本概念 2.3 惟一可译码 惟一可译码 2.4 信源变长编码 信源变长编码 2.5 统计匹配码 统计匹配码 第2章 无失真信源编码原理 2.12.1 离散信源及其信息测度 离散信源及其信息测度 2.1.12.1.1 信源概述 信源概述 1 1．消息、信号和信息．消息、信号和信息 信源的输出被称做消息(message)，消息一般不能被直接传输，需要经过发送器的变换才能转换成适于信道传输的信号(signal)消息和信号的这种区别对信息传输系统来讲是有一定意义的 第2章 无失真信源编码原理 在一般情况下，消息和信号既是相互区别的，又是相互联系的一方面，消息和信号的定义与含义不同当信源的输出连同语义学上的意义一并加以理解时则称为消息例如，播音员播送的一段新闻，记者拍摄的一段录像，歌手演唱的一首歌曲等，都应该说是消息而当信源的输出只被看做是随时间变化的某一物理量f（t）或随时间、空间位置变化的某一物理量f（x，y，t）时，则称为信号。
另一方面，信源的输出在收到、看到、听到之前都是随机的、不确定的，属于随机现象因此，从信息论的观点来看，信源的输出无论是被看做消息，还是被看做信号，它均含有信息 第2章 无失真信源编码原理 消息、信号和信息这三者都可以说是信源的输出，或者说它们是信源输出的三个方面由于信息论关心的是信源输出的信息，因此可将信源称为信息源通常，统计信息论是不研究消息、信号和信息三个方面在语义学上的意义的，它只考虑信源输出的后两个方面，即信号和信息应该说，信号是信息的载体和具体表达形式，信息必须借助信号才能得以表现，信息不能离开信号而单独存在所以，研究信源就是要研究信号和信息的关系，特别是信号如何才能有效地携带信息 第2章 无失真信源编码原理 2 2．信源的分类．信源的分类 按信号取值的集合和信号取值时刻的集合是离散的或连续的进行分类，信源可分为数字信源(DigitalSource)或离散信源(DiscreteSource)、模拟信源(AnalogSource)或波形信源(WaveformSource)、连续信源(ContinuousSource) 第2章 无失真信源编码原理 信源输出的信息从数学角度来看就是一种随机过程。
有些信源输出的是单个符号(或代码)的消息，它们符号集的取值是有限的或可数的，即可用一维离散型随机变量来描述这些信源的输出，这样的信源称为离散信源在实际情况中，存在着很多这样的信源例如投硬币、书信文字、计算机的代码、电报符号、阿拉伯数字码等等当我们掷一个六面质地均匀的骰子时，每次出现朝上一面的点数都是随机的，如把出现朝上一面的点数作为这个随机试验的结果，并把试验的结果看做信源的输出消息，无可置疑，这个随机试验可看做是一个信源这个信源输出有限种离散数字，其组成的集合为A={1，2，3，4，5，6}，而且每一个数字代表一个完整的消息， 第2章 无失真信源编码原理 所以，这个信源是单符号离散信源有的信源输出的虽是单个符号(或代码)的消息，但其可能出现的消息数是不可数的或无限的，即输出消息的符号集的取值是连续的，或取值范围是实数集(-∞，+∞)例如，语音信号、热噪声信号等某时间的连续取值数据，以及遥控系统中有关电压、温度、压力等测得的连续数据这些数据取值虽是连续的，但又是随机的，可用一维的连续型随机变量来描述这些消息，所以这种信源可称为连续信源 第2章 无失真信源编码原理 若信源只输出一个消息(符号)，则用一维随机变量来描述。
然而，很多实际信源输出的消息往往是由一系列符号序列所组成的例如，将中文自然语言文字作为信源，这时中文信源的样本空间是所有汉字与标点符号的集合由这些汉字和标点符号组成的序列即构成中文句子和文章因此，从时间上看，中文信源输出的消息是时间上离散的符号序列，其中每个符号的出现是不确定的、随机的，由此构成了不同的中文消息又例如，对离散化的平面灰度图像信源来说，从XY平面空间上来看每幅画面是一系列空间离散的灰度值符号，而空间每一点的符号（灰度值）又都是随机的，由此形成了不同的图像消息 第2章 无失真信源编码原理 这类信源输出的消息是按一定概率选取的符号序列,所以可以把这种信源输出的消息看做时间上或空间上离散的一系列随机变量，即随机矢量这样，信源的输出可用N维随机矢量来描述，这N维随机矢量有时也称为随机序列，其中，N可为有限正整数或可数的无限值若在信源输出的随机序列X＝X1X2…XN中，每个随机变量Xi(i=1,2,…,N)都是取值离散的离散型随机变量，即每个随机变量Xi的可能取值是有限的或可数的,而且随机变量X的各维概率分布都与时间起点无关，也就是在任意两个不同时刻，随机变量的各维概率分布都相同，这样的信源称为离散平稳信源。
前面所述的中文自然语言文字与离散化平面灰度图像都是这种离散型平稳信源 第2章 无失真信源编码原理 若信源输出的消息可用N维随机序列X＝X1X2…XN来描述，其中每个随机分量Xi(i=1,2,…,N)都是取值为连续的连续型随机变量(即Xi的可能取值是不可数或无限的)，并且满足随机变量X的各维概率密度函数与时间起点无关，也就是在任意两个不同时刻随机变量X的各维概率密度函数都相同，这样的信源称为连续平稳信源例如，语音信号与热噪声信号，它们在时间上取样离散化后的信源输出矢量在时间上是离散的，但输出矢量中的随机变量的取值都是连续的，所以它们是连续型平稳信源 第2章 无失真信源编码原理 某些简单的离散平稳信源先后发出的一个个符号是统计独立的也就是说，在信源输出的随机序列X＝X1X2…XN中，各随机变量Xi(i=1,2,…,N)之间是无依赖的、统计独立的，这样的信源称为离散无记忆信源该信源在不同时刻发出的各符号之间也是无依赖的、统计独立的离散无记忆信源输出的随机变量X所描述的信源称为离散无记忆信源的N次扩展信源可见，N次扩展信源是由离散无记忆信源输出N长的随机序列构成的信源一般情况下，信源在不同时刻发出的各符号之间是相互依赖的，也就是在信源输出的平稳随机序列X＝X1X2…XN中,各随机变量Xi之间是相互依赖的。
第2章 无失真信源编码原理 例如，在汉字组成的序列中，只有根据中文的语法、习惯用语、修辞制约和表达实际意义的制约所构成的中文序列才是有意义的句子或文章所以，在汉字序列中前后文字的出现是有依赖的，不能认为是彼此不相关的，其他如英文、德文等自然语言都是如此，将这种信源称为有记忆信源对这类信源需要在N维随机矢量的联合概率分布中引入条件概率分布来说明它们之间的关联 第2章 无失真信源编码原理 表述有记忆信源要比表述无记忆信源困难得多实际上，信源发出的符号往往只与前若干个符号的依赖关系强，而与其更前面的符号依赖关系弱，为此，可以限制随机序列的记忆长度当记忆长度为m+1时，称这种有记忆信源为m阶马尔可夫信源也就是信源每次发出的符号只与前m个符号有关，与更前面的符号无关假设m阶马尔可夫信源输出的随机序列为X＝X1X2…Xi-1XiXi+1…XN在这序列中某i时刻的随机变量Xi取什么符号只与前m个随机变量Xi-1Xi-2…Xi-m取什么符号有关，而与其更前面的随机变量以及后面的随机变量取什么符号都无关 第2章 无失真信源编码原理 这样，就可用马尔可夫链来描述此信源如果描述随机序列中各随机变量之间依赖关系的条件概率都与时间起点i无关，即信源输出的符号序列可看成时齐马尔可夫链，则此信源称为时齐马尔可夫信源。
第2章 无失真信源编码原理 一般来说，实际信源输出的消息常常是时间和取值都是连续的，如语音信号、热噪声信号和电视图像信号等时间连续函数同时，在某一固定时间，它们的可能取值又是连续的和随机的这种信源输出的消息可用随机过程来描述，所以称其为随机波形信源分析一般随机波形信源的过程比较复杂和困难常见的随机波形信源输出的消息是时间上或频率上为有限的随机过程根据取样定理，只要是时间上或频率上受限的随机过程，都可以把随机过程用一系列时间(或频率)域上离散的取样值来表示，而每个取样值都是连续型随机变量这样，就可把随机过程转换成时间(或频率)上离散的随机序列来处理甚至在某种条件下可以转换成随机变量间统计独立的随机序列如果随机过程是平稳的随机过程，时间离散化后可转换成平稳的随机序列这样，随机波信源可以转换成连续平稳信源来处理若再对每个取样值(连续型的)经过分层(量化)，就可将连续的取值转换成有限的或可数的离散值也就可把连续信源转换成离散信源来处理 第2章 无失真信源编码原理 2.1.22.1.2 信源的数学模型 信源的数学模型 根据信源输出信息所对应的不同的随机过程可以导出不同的信源模型例如，根据随机过程具有的随机变量前后独立与否可分为独立随机信源(或称无记忆信源)和不独立随机信源(或称有记忆信源)；根据随机过程平稳与否可分为平稳(稳恒)信源和非平稳(非稳恒)信源。
与特殊的随机过程相对应又有特殊的信源模型，例如，与高斯过程相对应的高斯信源，与马尔可夫过程相对应的马尔可夫信源等,其中，马尔可夫信源是有记忆信源中最简单且最具代表性的一种信源的类型不同其对应的模型也不同，限于篇幅，这里只介绍基本离散信源的数学模型及其无记忆扩展信源的数学模型 第2章 无失真信源编码原理 在信息传输系统中收信者在未收到消息以前，对信源发出什么消息是不确定的和随机的，所以可用随机变量、随机矢量或随机过程来描述信源输出的消息或者说,用一个样本空间及其概率测度，也就是概率空间来描述信源 第2章 无失真信源编码原理 一个基本离散信源的数学模型 （2-1） 第2章 无失真信源编码原理 【例2－1】 随机掷一个六面质地均匀的骰子，每次出现朝上一面的点数与其概率分布为 式（2－1）描述了信源基本特征，即一个信源符号就代表一个完整的消息,这样的信源也叫单符号离散信源但实际信源发出的消息往往不止一个符号，而是由多个符号的时间(或空间)序列组成的由多个符号组成的时间(或空间)序列称为多符号离散信源设序列由N个符号组成,且先后发出的符号间彼此统计独立,这样的多符号离散信源可看做离散无记忆信源的N次扩展信源，其数学模型为N维概率空间。
第2章 无失真信源编码原理 由信源U的信源空间可得信源U的N次扩展信源的信源空间为 （2-2） 第2章 无失真信源编码原理 [例2-2] 已知二元信源 分别计算信源U的2次扩展信源及3次扩展信源模型 解解 由式（2－2）可得信源U的2次扩展信源的模型为 同理，由式（2－2）可得信源的3次扩展信源的模型为 第2章 无失真信源编码原理 2.1.32.1.3 自信息量 自信息量 信息论不研究信源的内部结构，不研究信源为什么产生和怎样产生各种不同的、可能的消息，而只研究信源的各种可能的输出，以及输出各种可能消息的不确定性 由于信源发出的消息是不确定的，只有当信源发出的消息通过信道传输给信宿后，才能消除不确定性并获得信息事件发生的不确定性与事件发生的概率有关事件发生的概率越小，猜测它有没有发生的困难程度就越大，不确定性也就越大；而事件发生的概率越大，猜测这事件发生的可能性就越大，不确定性也就越小对于发生概率等于1的必然事件，就不存在不确定性 第2章 无失真信源编码原理 1.1.自信息量自信息量 自信息量是针对信源发出的某一个消息而言所得出的信息量，不同的消息对应不同的自信息。
如果事件ui已发生，则信息ui包含的自信息量为 I(ui)＝－logap（ｕｉ）（2-3） 第2章 无失真信源编码原理 1bit≈0.693nat≈0.301det 第2章 无失真信源编码原理 第2章 无失真信源编码原理 2.联合自信息量联合自信息量 式（2-3）的自信息量是针对一维空间的，可把它推广到二维空间,设概率空间X为： （2－4） 第2章 无失真信源编码原理 设概率空间Y为 （2－5） （2-6） 第2章 无失真信源编码原理 第2章 无失真信源编码原理 第2章 无失真信源编码原理 2.1.4 平均自信息量平均自信息量 1.基本离散信源基本离散信源 自信息量是针对信源发出的某一个消息而言所得出的信息量，不同的消息对应不同的自信息，自信息I(ui)是一个随机变量，其中任何一个消息的自信息都代表不了信源所包含的平均自信息量不能作为整个信源的信息测度，因此定义基本离散信源自信息的数学期望为信源的平均自信息量，即： (2-9) 第2章 无失真信源编码原理 这个平均自信息量的表达式和统计物理学中“热熵”的表达式很相似在统计物理学中，“热熵”是一个物理系统杂乱性（无序性）的度量，在概念上两者也有相似之处。
因而就借用“熵”这个词把平均自信息量H（U）称为“信息熵”信息熵的单位由自信息的单位决定，即取决于对数底的选取，当底分别为2、e、10时，信息熵的单位分别为比特(bit)、奈特(nat)/符号、笛特（det)/符号，今后如不特殊说明，信息熵的单位为比特/符号 第2章 无失真信源编码原理 信源的信息熵是从整个信源的统计特性来考虑的，它是从平均意义上来表征信源的总体信息测度的对于某特定的信源（概率空间给定），其信息熵是一个特定的值不同的信源因统计特性不同，其熵也不同信息熵是表征信息源的平均不确定性，平均自信息量是消除信源不确定性时所需的信息的量度，即收到一个信源符号可全部解除这个符号的不确定性或者说，获得这样大的信息量后，信源不确定性就被消除了信息熵和平均自信息量两者在数值上相等，但含义不同某一信源，不管它是否输出符号，只要这些符号具有某些概率特性，必有信源的熵值； 第2章 无失真信源编码原理 同时，这个熵值在总体平均上才有意义，因而是一个确定的值而另一方面，信息量则只有当信源输出的符号被接收者收到后才有意义，信息量就是给予接收者的信息度量，这值本身可以是随机量，也可以与接收者的情况有关。
因此说信息熵是信源的平均不确定性的描述，一般情况下它并不等于平均获得信息量只有在无噪情况下，接收者才能正确无误地接收到信源所发出的信息，从而消除了信息熵H（U）值大小的平均不确定性，因此所获得的平均信息量就等于信息熵H（U）的值通常情况下获得的信息量是两熵之差，并不是信息熵本身 第2章 无失真信源编码原理 [例2-4] 有一布袋内放100个球，其中70个球是红色的，30个球是白色的若随机摸取一个球，猜测其颜色，求平均摸取一次所能获得的自信息量 解解: 设a1表示摸出的是红球； a2表示摸出的是白球,则这一随机事件的概率空间为 如果被告知摸出的是红球，那么获得的信息量是： 第2章 无失真信源编码原理 如果被告知摸出的是白球，那么获得的信息量是： 这样，平均摸取一次所能获得的信息量约为 (比特／符号) 第2章 无失真信源编码原理 第2章 无失真信源编码原理 [ [例例2-5]2-5]有一离散无记忆信源U，其概率空间为 第2章 无失真信源编码原理 解解 由于信源U共有3个不同的消息符号，所以由信源U中每两个符号组成的不同排列共有32=9种，即二次扩展信源共有9个不同的符号。
又因为信源U是无记忆的，则二次扩展信源的概率空间为 第2章 无失真信源编码原理 于是，得： 说明，此处单位中的“符号”是指扩展信源的输出符号它是由2个组成) 第2章 无失真信源编码原理 说明：此处单位中的“符号”是指扩展信源的输出符号αi,它由两个αi组成 由此可得H(U2)=2H(U)对于上述结论也可以直观地进行理解因为扩展信源UN的每一个输出符号αi是由N个αi所组成的序列，并且序列中前后符号是统计独立的现已知每个信源符号αi含有的平均自信息量为H(U)，那么，N个αi组成的无记忆序列平均含有的自信息量就为NH(U)(依据熵的可加性)因此信源UN每个输出符号αi含有的平均自信息量为NH(U) 第2章 无失真信源编码原理 3.3.联合熵与条件熵联合熵与条件熵 信息熵讨论的是单个的概率空间不确定性的度量问题,当将此概率空间看做离散信源时，相当于讨论离散信源的平均信息含量在实际应用中，常常需要考虑两个或两个以上的概率空间之间的关系，这就需要引入联合熵与条件熵的概念 在联合集XY上，每对元素xiyj的自信息量的概率加权平均值定义为联合熵（Joint Entropy)。
即 （2－11） 第2章 无失真信源编码原理 由式（2－7）和式（2－11）得： （2－12） 在联合集XY上，条件自信息量I（xi|yj）的概率加权平均值定义为条件熵（ConditionalEntropy)即 （2-13） 由式（2-8）和式（2-13）得 （2-14） 条件熵与联合熵的单位同自信息量一样 第2章 无失真信源编码原理 2.1.5 平均互信息量平均互信息量 信息熵H（X）代表接收到输出符号以前关于输入X的平均不确定性，而H（X|Y）代表接收到所有输出符号后关于输出X的平均不确定性通过信道传输消除了一些不确定性，获得了一定的信息，所以定义信道输入X和信道输出Y之间平均互信息为： I（X；Y）＝H（X）－H（X|Y）＝H（Y）—H（Y|X） ＝H（X）＋H（Y）—H（XY） （2－15） 第2章 无失真信源编码原理 可见，X和Y之间的平均互信息量代表接收到输出符号后平均每个符号获得的关于X的信息量，也表明了输入X和输出Y之间的统计约束程度平均互信息量具有如下性质： （1）交互性：I(X;Y)＝I（Y；X）； （2）非负性和极值性：0≤I(X;Y)≤min(H(X),H(Y))； （3）凸状性：I(X;Y)是信源P(X)的上凸函数（∩形凸函数），I(X;Y)是信道传递概率P(Y|X)的下凸函数（∪形凸函数）。
第2章 无失真信源编码原理 因为 因此和是随机变量X和Y之间相互提供的信息量，称互信息是全确切的 第2章 无失真信源编码原理 因此,I(X;Y)和I(Y;X)是随机变量X和Y之间相互提供的信息量，称互信息量是完全确切的 由于H(X)≥H(X|Y),H(Y)≥H(Y|X)，于是由互信息量定义可得I(X;Y)≥0，由于H(X|Y)≥0，H(Y|X)≥0，又由互信息量定义可知I(X;Y)≤H(X),I(Y;X)≤H(Y)于是可以得到I(X;Y)≤min(H(X),H(Y))，当随机变量X和Y之间统计独立时，有H(X|Y)=H(X),H(Y|X)=H(Y)，于是得到I(X;Y)=0 第2章 无失真信源编码原理 当信道固定时，对于不同的信源概率分布，信道输出端获得的信息量是不同的因此，对于每一个固定信道，一定存在一种概率信源(一种分布)，使输出端获得的信息量最大，即I(X；Y)是信源P(X)的上凸函数（∩形凸函数）；信源固定以后，用不同的信道来传输同一信源符号时，在信道输出端获得的信息量是不同的对每一种信源一定存在一种最差的信道，此信道的干扰最大，而使输出端获得的信息量最小，即I(X;Y)是信道传递概率P(Y|X)的下凸函数（∪形凸函数）。
第2章 无失真信源编码原理 2.1.62.1.6 各种熵之间的关系 各种熵之间的关系 为了讨论各种熵之间的关系，首先需给出关于凸函数的一个结论 已知一个实值函数f，如果对任意x,y∈I都有 （2-16） 则称f在区间I上是凸的；如果对任意，都有式（2-16）中仅小于号成立，则称f为在区间I上是严格凸的 第2章 无失真信源编码原理 （2-17） 进一步，式(2-17)中的等号成立当且仅当 容易证明，对数函数 在区间 上是一个连续的严格凸函数 第2章 无失真信源编码原理 定理定理2-1 （2-18） H（X）=0当且仅当存在一个xi(1≤i≤n),有p(xi)=1，而对其他j≠i，有p(xj)=0，1≤j≤nH(X)=lbn当且仅当对任意i(1≤i≤n)，都有p(xi)=1/n 第2章 无失真信源编码原理 证明证明 根据H(X)的定义， H(X)≥0是显然的如果H(X) =0，则对任意i(1≤i≤n)，都有-p(xi)lbp(xi)=0从而对任意i都有p(xi)=0或p(xi)=1又因为,所以存在一个xi(1≤i≤n)，有p(xi) =1，而对其他j≠i，有p(xj)=0(1≤j≤n)。
根据Jensen不等式，有 ,进一步，若式中等号成立，当且仅当对任意i(1≤i≤n)，都有p(xi)=1/n 第2章 无失真信源编码原理 定理 定理2－－2 （2-19） 等号成立当且仅当X与Y相互独立 证明证明 因为 （2－20）（2－21） 第2章 无失真信源编码原理 所以 由式(2-12)和Jensen不等式知 第2章 无失真信源编码原理 等号成立当且仅当对任意i,j(1≤i≤n,1≤j≤m)，,c是一个常数因为 （2-22） 所以c＝1，即对任意的i和j，p(xiyj)= p(xi）（yj) 因此，等号成立当且仅当X与Y相互独立 第2章 无失真信源编码原理 定理定理2－－3 （2－23） 证明证明 同理可证， 第2章 无失真信源编码原理 推论推论2-1 （2-24） 由定理2－2和定理2－3可以立即得到此推论，等号成立当且仅当X与Y相互独立 第2章 无失真信源编码原理 【例2－6】 信源X,Y的概率空间分别为: 和 (x,y)联合分布如表2－1所示，求联合熵、条件熵及互信息量 第2章 无失真信源编码原理 表2－1 (x,y) 联合分布 第2章 无失真信源编码原理 解解 由熵定义可得: 第2章 无失真信源编码原理 对于条件熵及互信息量有： 第2章 无失真信源编码原理 2.2 信源编码的基本概念 信源编码的基本概念 2.2.12.2.1 信源研究的内容 信源研究的内容 对信息源或信源的研究一直是信息论研究的主要内容之一。
信息论对信源研究的内容包括以下三个方面： 1)信源的建模 信源输出信号的数学描述已有成熟的理论，即随机过程，因此，可以说信源的建模在一定程度上也就是用恰当的随机过程来描述信号然而，一般的随机过程理论并不涉及和讨论信号中所携带的信息，而信息论所关心的中心内容则是信号中所携带的信息 第2章 无失真信源编码原理 2)信源输出信号中携带信息的效率的计算 在信息论中，信源输出信号所携带信息的效率是用熵率或冗余度来表示的 3)信源输出信息的有效表示 一般地，信源输出信号中携带信息的效率并不很高，如何用适当的信号有效地表示信源输出的信息才是人们感兴趣的问题，这就是有关信源编码的问题在实际应用中，信源编码对信息的存储和传输两方面都有极大的价值 第2章 无失真信源编码原理 2.2.22.2.2 信源编码器 信源编码器 信源编码是指，将信源输出符号经信源编码器编码后变换成另外的压缩符号，然后将压缩后的信息经信道传送给信宿为了简化问题，研究无失真编码时，只考虑信源和信宿两个主要因素，忽略信道编、译码等的影响，这样信息传输系统模型可简化为图2－1所示的模型 第2章 无失真信源编码原理 图2－1 信息传输系统的简化模型 第2章 无失真信源编码原理 设信源U发出n种不同的符号，其符号集为U={u1,u2,…,un},其中 ui称为信源符号，若信源符号集中符号数等于2称为二元信源，等于3称为三元信源，…，等于n称为n元信源。
又若信道的输人符号集为X={a1,a2,…,ar}信源编码问题,就是用信道的输人符号集X={a1,a2,…,ar}作为码符号集，其中ai（i＝1，2，…，r）称为码符号或码元，用码符号集中的码符号,对信源U的每一种不同的符号进行一一对应变换，构成由码符号组成的序列，即码字所有码字的集合称为码组w={w1，w2，…，wn}；码字中所用的码符号的个数称为码长 第2章 无失真信源编码原理 信息传输有时要求信道必须无失真地传递信源发出的每一种不同的符号，以及由信源符号的序列代表的每一种不同的消息，来实施无失真信息传输要解决这个问题，当然首先要求信道是无噪信道在无噪信道的前提条件下，必须进一步要求信源编码编出的每一种码字要与信源发出的每一种不同的符号一一对应，而且同时还要求信源的N个符号组成的序列所代表的消息，与之相对应的码字组成的码字序列也必须一一对应只有这样，才能保证任何一个码字或码字序列唯一地翻译成相对应的信源符号或符号序列，达到无失真传递信源发出的消息的目的无失真信源编码必须具有这种单义可译性,我们将单义可译的码称为单义可译码，也称为惟一可译码由此可见，信源编码就是从信源符号到码符号的一种映射；译码是从码符号到信源符号的映射。
若要实现无失真编码，这种映射必须是一一对应且可逆的 第2章 无失真信源编码原理 2.2.3 码的类型码的类型 下面给出一些码的定义若码符号集中符号数等于2称为二元码，等于3称为三元码，…，等于r称为r元码二元码是数字通信和计算机系统中最常用一种码若一组码中所有码字的码长都相同，称为等长码,否则称为变长码若码组中所有码字都不相同则称为非奇异码，否则称为奇异码例如，信源U＝{u1，u2，u3，u4}，对应不同码字如表2-2所示 第2章 无失真信源编码原理 表表2－－2 信源 信源U对应的不同码字对应的不同码字 第2章 无失真信源编码原理 表2－2中码1的编码为等长码，其他的几种编码皆为变长码码3有两个符号的编码相同，码3是奇异码，而码1、码2和码4都为非奇异码 若每个码符号的传输时间都相同,则称为同价码;否则称为非同价码若码组的任意一串有限长的码符号只能被惟一地译成所对应的信源符号序列,则称为惟一可译码;否则称为非惟一可译码例如，码字{0，10，11}是一种惟一可译码因为任意一串有限长码序列，如100 111 000只能被分割成10，0，11，10，0，0任何其他分割法都会产生一些非定义的码字。
显然，奇异码不是惟一可译码，而非奇异码中有非惟一可译码和惟一可译码两种 第2章 无失真信源编码原理 惟一可译码又分为非即时码和即时码如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码表2－2中的码2是非即时码，而码4是即时码码4中只要收到符号1就表示该码字已完整，可以立即译码即时码又称为非延长码，若码组中没有任何完整的码字是其他码字的前缀，则称为异前缀码(或前缀条件码）表2－2中的码1和码4都是前缀条件码 第2章 无失真信源编码原理 表表2-2 信源信源U对应的不同码字对应的不同码字 第2章 无失真信源编码原理 在惟一可译变长码中，人们需要的是在译码时无需参考后续的码符号就能立即作出判断的一类即时码前缀条件码一定是即时码，这可以直接由即时码的定义得出事实上，如果没有一个码字是其他码字的前缀，那么在译码过程中，当收到一个完整码字的码符号序列，便能直接把它译成对应的信源符号，无需等待下一个符号到达后才作判断，这就是即时码反之，非异前缀码一定不是即时码设码中有一些码字，若码字Cj是另一码字Ci的前缀当收到的码符号序列正好是Cj时，则它既可能是码字Cj,也可能是码字Ci的前缀部分，因此不能立即对其作出判断，译出相应的信源符号来，必须等待其后一些符号的到达，才能作出正确判断，所以这就不是即时码。
即时码一定是惟一可译码，反之惟一可译码不一定是即时码，因为有些非即时码（延长码）也具有惟一可译性 第2章 无失真信源编码原理 2.3 惟一可译码 惟一可译码 2.3.12.3.1 KraftKraft不等式不等式 变长码有很多优点，但在真正使用时，往往又会遇到难题，这是由于编成的码字是不等长度的，将它传送至接收端时不能对其进行正确辨认所造成的对等长码，接收端只要根据约定的码组长度进行判决即可，而对变长码，由于编成的码长度是不一样的，因此就无法根据码组长度进行判决如何克服并解决这个难题，是变长码的主要矛盾这个问题一般有两种方法可解决，一种是类似于莫尔斯电报方法，即在码字间留空隙，或者加同步信号，但这种方法不经济，它直接影响到译码的效率；另一种是采用可分离码字 第2章 无失真信源编码原理 异前缀码是一种实时的惟一可译码，这类码无需另加同步信息，在接收端就能被分离出来在信源编码和数据压缩中这类编码无论在理论还是在实际上都有很大意义，对较简单的信源，可以很方便地用码树方法直接且直观地构造出可分离码（异前缀码），但是当信源较复杂时，直接画码树就比较复杂就这一问题，这里给出了一个与码树等效的，并在数学上表达码字可分离的充要条件，即著名的克拉夫特不等式。
第2章 无失真信源编码原理 定理定理2-4 对于n元信源编m元码，其码长分别为l1, l2，…，ln，则即时码存在的充要条件 (2－25) 式（2－25）是1949年由L.G.Kraft提出的，所以称之为克拉夫特（Kraft）不等式，该不等式指出了即时码的码长必须满足的条件在1956年，由麦克米伦（B.McMillan）证得对于惟一可译码也满足此不等式；在1961年,卡拉什（J.Karush)简化了麦克米伦的证明方法这说明惟一可译码在码长的选择上并不比即时码有什么更宽松的条件，所以在码长选择的条件上，即时码与惟一可译码是一致的 第2章 无失真信源编码原理 克拉夫特不等式给出了m元码中，信源序列中的消息数（符号数）n以及码字的各个码长li（i＝1，2，…，n）之间的关系如果三者满足式（2－25），则至少能够构成一种这样码长的即时码或惟一可译码，否则无法构造出即时码或惟一可译码但这个定理并不能作为判别一种码是否为即时码或惟一可译码的依据例如，码组中有长度相等的两个码字，则这两个码字无论是否相同，都有可能使不等式成立，然而，当这两个码字相同时，它们一定不是惟一可译码因此，惟一可译码一定满足克拉夫特不等式，反之，满足克拉夫特不等式的码不一定是惟一可译码。
第2章 无失真信源编码原理 例如在表2－2中，已知m＝2，n＝4 对码1,有l1＝2,l2＝2,l3＝2,l4＝2，则 满足式（2－25），则此码长的编码可能是惟一可译码 对码2有 l1＝1,l2＝2,l3＝2,l4＝2，则： 不满足式（2-25）则此码长的编码不能构成惟一可译码 第2章 无失真信源编码原理 对码4,有l1＝1,l2＝2,l3＝3,l4＝4，则 满足式（2－25），则此码长的编码可能是惟一可译码 第2章 无失真信源编码原理 2.3.22.3.2 惟一可译码的判别准则 惟一可译码的判别准则 惟一可译码的判断步骤如下： (1)观察是否是非奇异码若是奇异码则一定不是惟一可译码 (2)计算是否满足克拉夫特不等式若不满足则一定不是惟一可译码 (3)将码画成一棵树图，观察是否满足即时码的树图的构造，若满足则是惟一可译码 (4)用Sardinas和Patterson设计的判断准则计算出码组中所有可能的尾随后缀集合F，观察F中有没有包含任一码字，若无则为惟一可译码；若有则一定不是惟一可译码 第2章 无失真信源编码原理 在上述判断步骤中,Sardinas和Patterson设计的判断方法是能确切地判断出是否是惟一可译码的方法，所以可以跳过前三个步骤直接采用该判断准则。
该准则是萨得纳斯(A．A．Sardinas)和彼得森(G．W．Patterson)于1957年设计出来的，具体内容如下所述： 设S0为原始码字的集合,再构造一系列集合S1,S2,…，Sn为得到集合S1，首先分析S0中的所有码字若码字Wj是码字Wi的前缀，即Wi =WjA，则将后缀A列为S1中的元素，S1就是由所有具有这种性质的A构成的集合 第2章 无失真信源编码原理 一般地，要构成Sn(n>1)，则将S0与Sn-1比较若有码字W∈S0，且W是U∈Sn-1的前缀，即U=WA，则取后缀A为Sn中的元素；同样，若有码字U′∈Sn-1是W′∈S0的前缀，即W′=U′A′，则后缀A′，亦为Ｓn中的元素；如此便可构成集合Ｓn 依此类推，直至集合为空或者没有新的后缀产生为止可见，一种码是惟一可译码的充要条件是S1,S2,…，Sn中没有一个含有S0中的码字 第2章 无失真信源编码原理 【例2－7】 设消息集合共有7个元素｛x1,x2,x3,x4,x5,x6,x7｝，它们分别被编为{a,c,ad，abb,bad,deb,bbcde}码,判断其编码是否为惟一可译码？ 解解 按照Sardinas和Patterson设计的判断方法，可构造出如表2－3所列的码符号集序列。
第2章 无失真信源编码原理 表表2－－3 码符号集序列 码符号集序列 第2章 无失真信源编码原理 【例2－8】 现有码｛110,11,100,00,10｝，判断其编码是否为惟一可译码？ 解解 按照Sardinas和Patterson设计的判断方法，可构造出如表2－4所列的码符号集序列 第2章 无失真信源编码原理 表2－4 码符号集序列 第2章 无失真信源编码原理 2.3.32.3.3 即时码的树图构造 即时码的树图构造 树图法是构造即时码的一种简单方法树是n个结点的集合，这n个结点中有且仅有一个作为根的结点，其余的结点可分为m个互不相交的子集，每个子集本身又是一棵树，称为根的子树，m也叫根的树枝数如图2－2（a)中，结点A为树根，它的树枝数为2，结点B的树枝数为3 第2章 无失真信源编码原理 图2－2 树结构图 第2章 无失真信源编码原理 一个结点拥有的子树的个数称为该结点的度（Degree),一棵树的度是指该树中结点的最大度数度为零的结点称为叶子（Leaf)或终端结点如图2－2（a)中，结点A、B、E的度分别为2、3、0；树的度为3；D、E、F、H、I和J均为叶子。
度不为零的结点称为分支结点或非终端结点，除根结点之外的分支结点统称为内部结点，根结点又称为开始结点从一个结点到另一个结点之间的通路叫两个结点间路径，路径所经过的边（即连接两个结点的线段）的数目叫路径长度图2－2（a)中结点A到结点I的路径是ACGI，路径长度为3如果树中各个结点有相同的树枝数，此树称为满树，否则称为非满树图2－2中（b)为满树，（a）和（c)都为非满树下面给出树图与信源符号编码之间的对应关系： 第2章 无失真信源编码原理 第2章 无失真信源编码原理 构造树图的要点有以下两方面： (1)最上端为树根A，从根出发向下伸出树枝，树枝总数等于码符号数r，树枝的尽头为结点 (2)从每个结点再伸出r枝树枝，当某结点被安排为码字后，就不再伸枝，这个结点为终端结点能再伸枝的结点称为中间结点一直继续，直至都不能伸枝为止 第2章 无失真信源编码原理 用码树进行信源符号编码时，先将待编码的字符作为终端结点来构造码树；然后按一定规则给每个树枝分配一个码符号；最后将从根到终端结点的路径上的码符号依次相连，作为该终端结点所表示的字符的编码图2－3给出了几种码树图，图（a)对应等长二元码，图（b)对应变长二元码，图（c)对应变长三元码。
各符号对应码字如图2－3所示根据信源符号的编码可以求出信源序列的编码若二元信源系列为bacabd，则对应二元变长码（图2－3（b) 中的编码）码字序列为100110010111 第2章 无失真信源编码原理 码树可用于信源符号的编码，也可用于译码当接收到一串码符号序列后，首先从树根出发，根据接收到的第一个码字符号来选择应走的第一条路径，若沿着所选路径走到分支结点，再根据收到的第二个码符号来选择应走的第二条路径，直至走到终端结点为止最后，根据所走路径，立即判断出所接收的符号使系统重新返到树根，在作下一个接收码符号的判断，直至将接收到的一串码符号序列译成对应的信源符号序列若图2－3（b)的编码树对应的码符号序列为100110010111，按上述方法可译出对应信源符号序列为bacabd；码符号序列为100111110，可译出对应信源符号序列为badc 第2章 无失真信源编码原理 图2－3 码树图 第2章 无失真信源编码原理 2.4 信源变长编码 信源变长编码 2.4.12.4.1 等长码及其编码定理 等长码及其编码定理 若等长码是非奇异码，则它的任意有限长N次扩展码一定也是非奇异码。
因此等长非奇异码一定是惟一可译码 若对一个信源U进行等长编码，那么信源U存在惟一可译等长码的条件是： （2－26） 式中：q——信源U的符号个数；r——码符号个数；l——等长码的码长 第2章 无失真信源编码原理 表2－5 信源U的两种不同编码码字 第2章 无失真信源编码原理 信源U的N次扩展信源UN进行等长编码，若要使编得的等长码是惟一可译码，则必须满足: （2－27） 对式（2－27）两边取对数，可得： 或 （2-28） 式中，l/N是平均每个信源符号所需要的码符号个数该式表示对于等长惟一可译码，每个信源符号至少需要用lbq／lbr个码符号来变换 第2章 无失真信源编码原理 若N=1，则有 （2－29） 当r=2(二元码)时，lbr=1，则 （2－30） 例如，英文电报有32个符号(26个英文字母加上6个标点符号)，即q=32，若采用二元码时，则r=2对信源U的逐个符号ui(i=1，2，…，32)进行二元编码，则有lbq=lb32=5，这就是说，每个英文电报符号至少要用5位二元符号编码 第2章 无失真信源编码原理 定理2－5（等长信源编码定理）一个熵为H（U）的离散无记忆信源U，若用m元码对其N次扩展信源UN进行码长为L的等长编码。
对于任意ε>0，只要满足： （2－31） 则当N足够大时，几乎可实现无失真编码，即译码错误概率能为任意小反之，若 （2－32） 则不可能实现无失真编码，而当N足够大时，译码错误概率近似等于1对该定理的严格证明请参阅有关参考文献下面给出等长码的编码效率等公式 第2章 无失真信源编码原理 设一个熵为H（U）的离散无记忆信源U，若用m元码对其N次扩展信源UN进行码长为L的等长编码 定义编码信息率R′： （比特/信源符号） (2－33) R′编码后平均每个信源符号能载荷最大信息量 第2章 无失真信源编码原理 定义等长编码效率： (2－34) 由定理2－5可知，最佳等长编码效率η为 ε>0 (2－35) 对等长编码，若要实现几乎无失真编码，则信源长度N必须满足； （2－36） 式中：σ2——信源U的方差；η——编码效率；Pe——差错率 第2章 无失真信源编码原理 【例2－9】 设离散无记忆信源 信源熵： 方差： 第2章 无失真信源编码原理 若取差错率Pe＝10－6，编码效率为95%，则可计算出等长编码需联合的信源符号数N应满足： 可见，在差错率和编码效率要求并不十分苛刻的条件下，就需要近一百万个信源符号进行联合编码，这显然是没有必要实现的。
若对例2－9用变长码来实现，其效率可达100％这虽然是一个特例，但是一般情况下变长码的编码效率都很高，要优于等长编码 第2章 无失真信源编码原理 2.4.22.4.2 变长码的平均码长及编码效率 变长码的平均码长及编码效率 对式（2－1）基本离散信源进行编码，设编码后各码字的码长分别为l1,l2, …，ln,则定义该码的平均码长度为 码符号/信源符号 (2－37) 平均码长 是每个信源符号平均需用的码元数信源编码的目的是为了提高信息传输系统有效性，而 和编码后的压缩效果密切相关，若 平均码长大则压缩效果差，系统有效性差，若平均码长小则压缩效果好，系统有效性高，为此，人们感兴趣的码是平均码长最短码，这种编码可使信息传输系统更经济、简单，使信息传输效率更高 第2章 无失真信源编码原理 当信源给定时，信源的熵H（U）就确定了，编码后每个信源符号的平均码元数为L，那么平均每个码元携带的信息量即编码后信道的信息传输率R为 (比特/码符号) (2－38) 若传输一个码符号平均需要ｔ秒钟，则编码后信道每秒钟传输的信息量为： (比特/秒) (2－39) 第2章 无失真信源编码原理 设对信源U进行编码所得到的平均码长 ，因为 一定大于或者等于Hm(U)(m元码的熵)，所以定义编码的效率η为： (2－40) 式中： (码符号/信源符号)； (比特/信源符号)。
第2章 无失真信源编码原理 对同一信源来说，码的平均码长L越短，越接近极限值Hm（U），信道的信息传输率就越高，也就越接近无噪无损信道容量，这时的η越接近于1所以可用码的效率η来衡量各种信源编码的优劣 另外，为了衡量各种编码与最佳码的差距，定义码的剩余度为 (2－41) 在二元无噪无损信道中,m＝2，所以Hm(U)＝H(U)，式（2－40）为 （2－42） 第2章 无失真信源编码原理 所以在二元无噪无损信道中信息传输率为 （2－43） 注意:上式中R与η的数值相同，单位不同，η是个无单位的比值为此，在二元信道中可直接用码的效率来衡量编码后的信息传输率是否提高了当η＝1，即R＝1(比特／码符号)时，表明已达到了二元无噪无损信道的信道容量，其编码效率最高，码剩余度为零 第2章 无失真信源编码原理 2.4.32.4.3 变长码的特点 变长码的特点 1 1．使信道复杂化．使信道复杂化 一般情况下，信源符号以恒速输出信源输出经变长编码后，其输出的每秒比特数就不是常量，因而不能直接由信道来传送为了适应信道输出，必须有缓冲设备，将编码输出暂存在缓冲器中，然后再送到信道去传送。
从理论上说，信道传送速率应等于信源输出速率S与平均码长的乘积就是当存储器容量为无限时，信源输出与信道传送之间取得平衡在时间趋向于无限时，信源输出的比特数和信道上传送比特数接近相等 第2章 无失真信源编码原理 2 2．容易产生溢出或取空错误．容易产生溢出或取空错误 根据前面分析可知，当存储器容量无限时，信源输出与信道传送之间即可取得平衡;当存储器容量有限时，这种平衡则不一定能保持如当信源连续输出低概率符号时，由于每个符号的码长较长，输入到存储器的比特数将大于信道输出的比特数，可能造成存储器因存不下而产生溢出；反之，若高概率符号连续出现，输入比特数将小于信道中传送的比特数，以致存储器被取空，信道上将无信息可传送以上这两种情况都会造成不良后果,前者可使信息由于溢出而丢失，后者由于信息被取空而使信道上出现连0或连1，因译码被误译而造成差错所以，应合理估计所需存储器的容量，才能使上述现象发生的概率小至可以容忍 第2章 无失真信源编码原理 通常，变长码只适用于有限长的信息传送，也就是发送出一段信息后，信源能停止输出，如机发送出一张纸上的信息后就停止对于长信息，在实际使用时可分段发送。
也可通过检测存储器状态，发现将要溢出时就停止信源输出，发现将要取空时就插入空闲标志在信道上传送或加快信源输出 第2章 无失真信源编码原理 3 3．差错的扩散．差错的扩散 因采用异前置码来分解码字，所以一旦在传送中出现误码，使得某个码字的前置部分可能被认为是另一个码字而被错译为另一符号，而剩下的部分又与后面的码字的一部分译成某一符号这样的话，可能要经过一段信息被错译后，才能正确地分解码字 克服这种缺点的措施是力求信道不出现误码，如采用纠错或检错编码尤其是检错重发方式，若设计得好，可基本上不出差错或差错小至可以容忍的程度检错可用附加监督位的方式,也可在编码时有意识地不编成满树,导致某些树叶未被用来代表某个符号,一旦这种码字出现在接收端,说明传送中有误码,则要求发端重发 第2章 无失真信源编码原理 变长编码具有很高的编码效率，有时几乎接近于1但由于上述缺点限制了它的应用范围，因此在采用时常需有大容量的存储设备作为缓冲，以便于重发近年来存储器技术发展很快，不但容量越来越大，价格也越来越低，这使得变长码的应用范围不断扩大 第2章 无失真信源编码原理 2.4.42.4.4 变长信源编码定理 变长信源编码定理 由前面讨论可知，用变长码实现无失真编码时，平均码长越短越好，那么平均码长的极限是多少？下面的定理将回答这个问题。
定理2－6 一个熵为H（U）的基本离散无记忆信源U，若用m元码对其进行变长编码，则总可以找到一种无失真编码方法构成惟一可译码，使其平均码长满足： (2－44) 第2章 无失真信源编码原理 此编码定理给出了最佳变长码的平均码长的上限和下限它表明了码字的平均长度 不能小于极限H(U)/lbm，否则惟一可译码不存在；给出了最佳码的最短平均码长，并指出这个最短的平均码长与信源熵是有关的，在尚未编出码字之前就知道平均码长落在什么范围，这是很重要的同时，它还指出了最佳变长码应是与信源熵相匹配的编码，其下限也就更重要，因为该下限是信源压缩编码的极限，通常称达到下限的最佳变长码为熵编码定理的证明见有关文献 第2章 无失真信源编码原理 平均码长的界限定理清楚地表明，如要进一步降低非延长码的平均码长，提高无失真信源编码的有效性，单靠改善编码方法，已无潜力可挖必须把注意力转向信源本身，在信源上作文章，进一步挖掘信源本身的潜力 第2章 无失真信源编码原理 第2章 无失真信源编码原理 （2－45） 第2章 无失真信源编码原理 令 为信源U的每一个信源符号ui(i=1,2,…,n)所需要的平均码符号数，则 (2－46) 因为离散无记忆信源： H（UN）=NH（U） (2－47) 由式(2－45)～（２－47）得: (2－48) 第2章 无失真信源编码原理 则 (2－49) 因此 (2－50) 第2章 无失真信源编码原理 所以对离散无记忆信源U来说，若不把信源U的单个符号ui(i＝1，2，…，n)作为编码对象，而直接把信源U的N次扩展信源UN的单个“大符号”(消息) (i＝1，2，…，nN)作为编码对象，使非延长码的码字wi(i＝l，2，…，nN)与消息(i＝1，2，…，nN)一一对应，则当扩展次数N足够大(N→∞)时，信源U的每一信源符号ui(i＝1，2，…，n)所需的平均码符号数，即平均码长 可无限接近于下界值H(U)／lbm。
接近的程度随着扩展次数N的增加而增加这就是说，可以采用扩展信源的手段，达到数据压缩的目的，减少所需传输的码符号数量，提高通信的有效性 第2章 无失真信源编码原理 这样做的话就会使码字数从n增加到nN，特别当n和N都相当大时，编码会变得相当复杂而且这种复杂程度同样也随扩展次数N的增加而明显地加大由此可得无失真变长信源编码定理，即香农第一定理 第2章 无失真信源编码原理 定理 定理2－－7 无失真变长信源编码定理（香农第一定理）离散无记忆信源U的N次扩展信源UN，其熵为H(UN)，用m元码对信源UN进行编码，总可以找到一种编码方法，构成惟一可译码，使信源U中每个信源符号所需的平均码长满足： (2－51) 当N→∞时， （2－52）式中： (2－53) 第2章 无失真信源编码原理 LN/N的含义是为了得到这个平均值它并不是对单个信源符号ui进行编码，而是对N个信源符号的序列αi进行编码定理2－7指出，要做到无失真的信源编码，对每个信源符号编码平均所需最少的码元数就是信源的熵值若编码的平均码长小于信源的熵值，则惟一可译码不存在 由此可得，变长编码后平均每个信源符号能载荷的最大信息量为 (2－54） 这时，香农第一定理也可陈述为，若R＇〉H（U），就存在惟一可译变长编码；若R‘ 第2章 无失真信源编码原理 2.5 统计匹配码 统计匹配码 若对n元信源编m元码,设编码器输入序列的长为L,编码器输出码字序列的长为K,要实现无失真信源编码，则必须同时满足无失真和有效性两个条件如果不考虑信源统计特性，若要满足无失真，就必须使每个信源输出的消息（或符号）都能找到一个对应的码字，即满足： mK≥nL (2－55) 若取m＝n，由（2-55）得： K≥L 这说明码字序列的长度大于信源序列长度，显然不满足有效性 第2章 无失真信源编码原理 若选K＝L，由式（2－55）得： m≥n 说明：要想同时满足上述两个基本条件，就得考虑到信源的统计特性 由式（2－55）可得： (2－56) 式（2－56）中的logan和logam分别是在不考虑信源统计特性或等概率的条件下所得的消息熵H（U）＝logan和码熵H（X）＝logam当考虑信源的统计特性时，信源符号一般是不等概率的，这时消息熵 第2章 无失真信源编码原理 将其代入式（2－56）得： (2－57) 这样就可使有效性和无失真同时得到满足所以在具体实现无失真信源编码时，必须考虑信源的统计特性。
