信息论ppt课件.ppt

第六章无失真信源编码,信源编码是以提高通信的有效性为目的，包括无失真信源编码和限失真信源编码。,1,第一节信源编码的相关概念,一、编码器定义1：将信源符号序列按一定的数学规律映射成码符号序列的过程称为信源编码，完成编码功能是器件，称为编码器。接收端有一个译码器完成相反的功能。,2,信源编码器的输入是信源符号集，共有q个信源符号。同时存在另一个符号集，称为码符号集，共有r个码符号，码符号集中的元素称为码元或者码符号，编码器的作用就是将信源符号集S中的符号变换成由个码符号组成的一一对应的输出符号序列。编码器输出的符号序列又称为码字，并用来表示，称为码字长度，简称码长。所以，信源编码就是把信源符号序列变换到码符号序列的一种映射。若要实现无失真编码。那么这种映射必须是一一对应的、可逆的。一般来说，人们总是希望把信源输出的信息毫无保留地传递接收端，即实现无失真传递，所以要对信源实现无失真编码。,3,无失真信源编码主要针对离散信源，连续信源在量化编码的过程中必然会有量化失真，所以对连续信源只能近似地再现信源的消息。由第4章的讨论可知，由于信源概率分布的不均匀性和符号之间存在的相关性，使得信源存在冗余度，而实际上传送信源信息只需要传送信源极限熵大小的信息量。信源编码的主要任务就是减少冗余度，提高编码效率。具体地说，就是针对信源输出符号序列的统计特性寻找一定的方法把信源输出符号序列变换为最短的码字序列。去除冗余度的方法有两个：一是去除相关性，使编码后码序列的各个码符号尽可能地互相独立，这一般是利用对信源的符号序列进行编码而不是对单个的信源符号进行编码的方法实现；二是便编码后各个符号出现的概率尽可能地相等，即概率分布均匀化，这可以通过概率匹配的方法实现，也就是小概率消息对应长码，大概率消息对应短码。,4,例1信源概率空间为把信源符号编码为适合二元信道的二元码。二元信道是数字通信中最常用的一种信道，它的码符号集为。本章我们讨论的都是同价码，即每个码符号所占的传输时间都相同的码。一般说来，信源输出的是符号序列，把离散无记忆信源的N次扩展信源的概念加以引申便得到N次扩展码。假定把信源中的符号变换成码中的码字，则N次扩展信源对应N次扩展码。,5,二、码的分类,1.分组码和非分组码定义2：将信源符号集中的每个信源固定地映射成一个码字，这样的码称为分组码，又称为块码。直观地理解，分组码就是把信源的符号序列分成组，从信源符号序列到码字序列的变换是在分组的基础上进行的，特定的信源符号组唯一地确定了特定的码字组。与分组码相对应的分类是非分组码，又称为树码。树码编码器输出的码符号通常与编码器的所有输入的信源符号都有关，比如算术编码。,6,2.奇异码和非奇异码定义3：若一种分组码中的所有码字都不相同，则称此分组码为非奇异码，否则称为奇异码。分组码是非奇异码是正确译码的必要条件，而不是充分条件。在表1中，码1是奇异码，码2是非奇异码。例如传送分组码2时，如果接收端接收到00，并不能确定发送端的消息是，还是。3.唯一可译码和非唯一可译码定义4：任意有限长的码元序列，只能够唯一地分割成一个个码字，更称为唯一可译码。,7,唯一可译码的含义是指不仅要求不同的码字表示不同的信源符号，而且还进一步要求对由信源符号构成的符号序列进行编码时，在接收端仍能正确译码而不发生混淆。唯一可译码首先是非奇异码，且任意有限长的码字序列不会雷同。一个分组码若对于任意有限的整数N，其N次扩展码均为非奇异的，则为唯一可译码。4.即时码和非即时码定义5：无须考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一译码称为即时码。,8,如下表中列出的两组唯一可译码，其译码方法不同。当传送码1时，信道输出端接收到一个码字后不能立即译码，还须等到下一个码字接收到时才能判断是否可以译码。若传送码2，则无此限制，接收到一个完整码字扣立即可以译码，后一种码为即时码。,9,下面讨论唯一可译码成为即时码的条件。定义6：设为一码字，对于任意的，称码符号序列的前j个元素为码字的前缀。按照上述的前缀的定义，有下述结论：定理1.一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其它码字的前缀。这个很好理解，因为如果没有一个码字是其它码字的前缀，则在接收到一个相当于一个完整码字的符号序列后便可以立即译码，而无须考虑其后的码符号，反过来说，如果有一个码字是其它码字的前缀，假设是的前缀，则在收到相当于的码符号序列后还不能立即判定它是一个完整的码字，若想正确译码，还必须参考后续的码符号，这与即时码的定义相矛盾，所以即时码的必要条件是其中任何一个码字都不是其它的码字的前缀。,10,综上所述，可将码作如下分类：5.树图即时码可以方便地用树图来构造，树图中有树枝和节点。树图最顶部的节点称为根节点，没有再产生分支的节点称为终端点，其它称为中间节点。每个节点能够生出的树枝数目等于码符号数。在树枝旁边分别标以相应的码符号：。将从根节点到终端节点的各树枝代表的码符号顺次连接，就得到了编码码字。,11,树图中自根部经过一个分支到达的节点称为一阶节点，一阶节点最多有r个。它们的子节点称为二阶节点，二阶节点最多有个，N阶节点最多有个。如果指定某个N阶节点为终端节点，表示一个信源符号，则该节点就不再延伸，相应的码字即为从树根到此端点的树枝标号序列，其长度为N。这样构造的码满足即时码的条件，因为从树根到每一个终端节点所走的路径不相同，并且中间不安排码字，故一定满足对前缀的限制。如果有q个信源符号，那么在码树上就要选择q个终端节点，相应的有q个码字。,12,即时码的码树图还可以用来译码。当接收到一串码符号序列后，首先从树根出发，根据收到的第一个码符号来选择应走的第一条路径，沿着所选支路如果走到一个中间节点，再根据接收到的第二个码符号来选择应走的第二条路径，若又走到中间节点，就再依次继续下去，直到终端节点为止。走到终端节点，就可根据所走的支路立即判断出所接收的码字，同时使系统重新返回树根，再作下一个接收码字的判断。这样就可以将接收到的一串码符号序列译成对应的信源符号序列。,13,例2,14,三、唯一可以码的存在性与判断,对于一个给定信源的编码，Kraft不等式和McMillan不等式可以让我们从码长来判断它是不是满足即时码和唯一可译码的条件。这两个不等式在形式上是完全一样的。定理2(Kraft不等式)设信源符号集为，码符号集为，对信源进行编码，得到的码为，则即时码存在的充要条件是,15,定理3(McMillan不等式)唯一可译码存在的充要条件是其中，r为码符号个数，为码字长度，q为信源符号个数。这称为McMillan不等式。由定理2和定理3可知，任何一个唯一可译码均可用一个即时码来代替，而不改变任一码字，即：定理4.如果存在一个码长为的唯一可译码，则一定存在一个具有相同码长的即时码。定理3指出了唯一可译码中r、q、之间的关系，如果码长满足这个不等式，则一定能够构造至少一种唯一可译码，否则，无法构成唯一可译码。,16,一般地，判断给定码是否为唯一可译码有如下两种方法：(方法1)首先，观察是否是非奇异码，若是奇异码则一定不是唯一可译码；其次，计算给定码的码长是否满足Kraft不等式，若不满足一定不是唯一可译码；最后，将码画成一棵树图，观察是否满足即时码树图的构造，若满足则是唯一可以码。(方法2)尾随后缀法：A.A.Sardinas和G.W.Patterson于1957年提出了一种唯一可译码的判别准则，原理如图所示，其中都是码字。如果某个有限长的码符号序列能译成两种不同的码字序列时，此码不是唯一可译码，此时B1一定是A1的前缀，而A1的尾随后缀一定是另一码B2的前缀；而B2的尾随后缀又是其他码字的前缀。最后，码符号序列的尾部也一定是一个码字。,17,根据这个原理，该判别准则的判别方法如下：设C为码字的集合，我们要构造尾随后缀的集合（1）F1是C中所有码字尾随后缀的集合：若C中码字是码字的前缀，即，则将尾随后缀A列为中的元素，所有这样的尾随后缀构成了；（2）考察C和两个集合，如果C中任一码字是中元素的前缀，或者中任一元素是C中码字的前缀，则将其相应的尾随后缀放入集合；（3）；（4）一旦F中出现了C中的元素，则算法终止，判断C不是唯一可译码；若出现为空集或中的元素在F中已经全部存在了，算法终止，判断C是唯一可译码。即一个码是唯一可译码的充要条件是F中不含有C中的码字。,18,例2.设消息集合共有7个元素，它们分别被编码为，判断是否是唯一可译码。练习：给定一组编码如下，这些码是否满足Kraft不等式？并利用尾随后缀法判断它们是否为唯一可译码？(1)0，10，110，1110，1011，1101(2)0,100,101,110,111,011作业：给定一组编码如下，这些码是否满足Kraft不等式？并利用尾随后缀法判断它们是否为唯一可译码？(1)000,10,00,11(2)01,111,011,00,010,110,19,第二节定长码及定长信源编码定理,一、渐进等分割性和典型序列为了严格认证定长信源编码定理，需要介绍渐进等分割性和典型序列。在信息论的定量证明中，它是一种重要的数学工具。当随机试验次数很大时，事件发生的频率具有稳定性。比如多次抛掷硬币，出现正面或反面的次数是不定的，但是随着试验次数的增加，出现正面或反面的频率逐渐将稳定于1/2，这就是随机事件的统计规律性。,20,对于独立、等同分布的随机变量只要N足够大，其算术平均值接近其数学期望值，也就是说其算术平均值依概率收敛于数学期望。当N很大时，其算术平均值将几乎变成一个常数E(X)，这就是大数定理。,21,把看成一个随机变量，根据契比雪夫不等式可以推出，对于独立同分布的随机变量，它们具有相同的数学期望和方差，对于任意正数，有不等式成立，其中为随机变量的方差。,22,考虑一个离散无记忆信源的N次扩展信源这里是N维随机矢量，而,23,因为是离散无记忆信源的扩展信源，所以是一个随机变量，其数学期望就是的熵。,24,由于相互统计独立的随机变量的函数也是相互统计独立的随机变量，所以由是相互统计独立且服从同一概率分布的随机变量，可以推出其自信息也是相互统计独立且服从同一概率分布的随机变量。,25,离散无记忆信源的N次扩展信源，N维随机矢量中每一维随机变量相互独立，当序列长度N变得很大时，由于统计规律性，N个随机变量的算术平均，将变成一个常数（随机变量的数学期望），也就是N维随机矢量中平均每一维随机变量的自信息非常接近单符号信源熵。因为，根据契比雪夫定理，有以下不等式成立：,26,且。称为典型序列集，它表示N长序列中平均每一维随机变量的自信息非常接近单符号信源熵的一类序列的集合。而表示N长序列中不在集中的序列的集合，称为非典型序列集。它们的差别在于与H(S)的差是否小于任意小的正数。下面推导典型序列集的一些性质。,27,（1）和概率（2）和中序列的概率根据典型序列集的定义，中序列与H(S)的差小于正数，即,28,（3）和中序列的个数设中序列数为有所以，,29,30,因此，N次扩展信源中信源序列可分为两大类，一类是典型序列，是经常出现的信源序列。当时，这类序列出现的概率趋于1，并且，每个典型序列接近等概分布。另一类是低概率的非典型序列，是不经常出现的信源序列。当时，这类序列出现的概率趋于零。信源的这种划分性质就是渐进等分割性。中序列虽然是高概率序列，但是中序列数占信源序列总数的比值却很小：,31,因为一般情况，信源序列中大部分是不大可能出现的序列，因此如果只对高概率的典型序列进行一一对应的等长编码，码字总数减少，所需码长就可以减短了。二、定长信源编码定理定理1.离散无记忆信源的熵为H(S)，若对信源长为N的序列进行定长编码，码符号集中有r个码符号，码长为l，则对于任意0，只要满足，则当N足够大时，可实现几乎无失真编码，即译码错误概率为任意小。反之，如果，则不可能实现几乎无失真编码，且当N足够大时，译码错误概率为1。,32,注：定长信源编码定理给出了定长编码时每个信源符号最少所需的码符号的理论极限，该极限值由H(S)决定。当二元编码时r=2，有这是定长编码时平均每个信源符号所需的二元码符号数的理论极限。定理1是在离散平稳无记忆信源的条件下证明的，但它同样适合于平稳有记忆信源，只要将式中H(S)改为极限熵即可，条件是有记忆信源的极限熵和极限方差存在。,33,比较式与当信源符号等概分布时两式就完全一致，但一般情况下信源符号并非等概率分布，而且符号之间有很强的关联性，故信源的熵（极限熵）远小于。根据定长信源编码定理，每个信源符号平均所需的二元码符号可大大减少，从而使编码效率提高。以英文电报为例，由于英文信源的极限熵1.4比特/信源符号，所以码长l只要满足，即平均每个英文符号只需近似用1.4个二元码符号来表示，这比由计算的需要5个二元符号减少了许多，从而提高了信息传输效率。定理1的条件又可写成，这个式子表明只要l长码符号序列所能携带的最大信息量大于N长信源序列所携带的信息量，就可以实现无失真编码，当然条件是N足够大。,34,三、编码效率为了衡量编码效果，我们引进编码效率的概念。定义1：设熵为H(S)的离散无记忆信源，若对信源的长为N的符号序列进行定长编码，码符号集中码符号个数r，设码字长l，定义为编码效率。其中（比特/信源符号）表示平均每个信源符号编码后能载荷的最大信息量。因此，定理1的条件也可表述为，平均每个信源符号编码后能载荷的最大信息量大于信源的熵才能实现几乎无失真编码。,35,根据定理1，最佳编码效率可表示为在已知方差和信源熵的条件下，要达到最佳编码效率并且允许的译码错误概率小于任一给定的正数，信源序列长度N须满足从上式可以看出，当允许错误概率越小，编码效率又要高，那么信源序列长度N必须越长。在实际情况下，要实现几乎无失真的定长编码，N需要的长度将会大到难以实现。,36,例1.设有离散无记忆信源如果对信源符号采用定长二元编码，要求最佳编码效率，允许错误概率，求所需信源序列长度N。作业：设离散无记忆信源要求最佳编码效率，允许错误概率，求所需信源序列长度N。,37,第三节变长码及变长信源编码定理,一、紧致平均码长界限定理定义1：设有信源编码后的码字分别为，各码字相应的码长分别为。因为是唯一可译码信源符号和码字一一对应，则定义此码的平均码长为码符号/信源符号其中，表示每个信源符号平均需用的码元数。,38,定义2:当信源给定时，信源熵H(S)就确定了，而编码后每个信源符号平均用个码元来表示，编码后平均每个码元载荷的信息量H(X)定义为编码后的信息传输率R:比特/码符号如果传输一个码符号平均需要t秒，则编码后信源每秒钟提供的信息量为比特/秒越大，信息传输率就越高，因此我们感兴趣的码是使平均码长为最短的码。,39,定义3:对于给定的信源和码符号集，若有一个唯一可译码，其平均码长小于所有其他唯一可译码的平均码长，则称这个码为紧致码或最佳码。无失真信源编码的核心问题就是寻找紧致码。下面我们来看紧致码的平均码长可能达到的理论极限。定理1.若一个离散无记忆信源S，熵为H(S),码符号集，总可以找到一种唯一可译码，其平均码长满足注：定理告诉我们，平均码长不能小于极限值，否则唯一可译码不存在，同时定理又给出了平均码长的上界。这不是说大于这个上界不能构成唯一可译码，而是希望尽可能短，因此我们关心的是紧致码的平均码长的范围。是紧致码的平均码长，它与H(S)有关。另外还可以看到这个极限值与定长信源编码定理中的极限值是一致的。,40,二、无失真变长信源编码定理（香农第一定理）与无失真定长信源编码定理一样，这也是一个关于码长的极限定理，这个极限和定长编码的极限其实是一致的。定理2.设离散无记忆信源S的信源熵H(S),它的N次扩展信源，其熵H()。并用码符号对信源进行变长编码，那么总可以找到一种唯一可译码，使每个信源符号所需的平均码长满足或写成,41,当时式中，其中是扩展信源的信源符号所对应的码字长，因此，是扩展信源的信源符号的平均码长，而仍是单个信源符号所需的平均码长。这里要注意与的区别：它们两个都是单个信源符号所需的码符号的平均数，但是的含义是：为了得到这个平均值，不是对单个信源符号进行编码，而是对N个信源符号的序列进行编码，然后对N求算术平均。,42,注：定理1可以看作定理2在N=1时的特殊情况。定理2的结论推广到平稳遍历的有记忆信源（如马尔可夫信源）便有式中，为有记忆信源的极限熵。定理2是香农信息论的主要定理之一。定理指出，要做到无失真信源编码，每个信源符号平均所需最少的r元码符号数就是信源的熵值（以r进制单位为信息量单位）。若编码的平均码长小于信源的熵值，则唯一可译码不存在，在译码时必然要带来失真或差错。同时定理还指出，可以通过对扩展信源进行变长编码，当时,平均码长可达到这个极限值。可见，信源的信息熵是无失真信源编码平均码长的极限值，也可以认为信源的信息熵（H(S)或）是表示每个信源符号平均所需最少的二元码符号数。,43,我们可以看到，定长码和变长码的平均码长的理论极限是一致的，而且要达到这个极限，也就是平均单个信源符号所需的码符号数最少，所用的方法都是对信源的N次扩展信源进行编码，但是变长码与定长码的区别在于变长码在N不需很大时就能达到这个极限，而定长码的N值通常大到设备难以实现，而且定长码在达到这个码长极限时往往还会引入一定的失真，而变长码则不会引入失真。编码后的信息传输率,44,当平均码长达到极限值，编码后信源的信息传输率等于有r个码符号的无噪无损信道的信道容量C，这时信息传输效率最高。因此，无失真信源编码的实质就是对离散信源进行适当的变换，使变换后新的码符号信源（信道的输入）尽可能为无记忆等概率分布，使新信源的每个码符号平均所含的信息量达到最大，从而使信道的信息传输率R达到无噪无损信道的信道容量，实现信源与信道理想的统计匹配。这就是香农第一定理的物理意义。为了衡量各种编码是否已达到极限情况，我们定义变长码的编码效率。,45,定义4.设对信源S进行编码所得到的平均码长为，则。对同一信源来说，若码的平均码长越短，越接近极限，则信息传输率越高，越接近无噪无损信道的信道容量，这时也越接近于1，所以用编码效率来衡量各种编码的优劣。另外，为了衡量各种编码与最佳码的差距，引入码的剩余度的概念。,46,定义5.定义为码的剩余度。在二元无噪无损信道中，所以在二元无噪无损信道中信息传输率为注意这时它们数值相同，单位不同。是个无单位的比值，而R的单位是比特/码符号。因此在二元信道中可直接用码的效率来衡量编码后信道的信息传输率是否提高了。当=1时，即R=1，达到二元无噪无损信道的信道容量，编码效率最高，码剩余度为零。与定长码一样，通过对扩展信源进行编码，可以提高编码后信道的信息传输率。,47,例1.有一离散无记忆信源求其信息传输率及二次扩展信源的信息传输率。注：将此例与上节习题相比，对于同一信源，要求编码效率达到0.96时，变长码只需对二次扩展信源(N=2)进行编码，而等长码则要求。因此用变长码编码时，N不需要很大就可以达到相当高的编码效率，而且可实现无失真编码，随着扩展信源次数N的增加，编码效率越来越接近于1，编码后的信息传输率R也越来越接近于无噪无损二元信道的信道容量C=1比特/码符号，达到信源与信道匹配，使信道得到充分利用。,48,第四节变长码的编码方法,本节介绍的编码方法均为统计匹配编码，都是对出现概率较高的信源符号编短码，而对出现概率较高的信源符号编长码，从而使平均码长最短，达到最佳编码的目的。,49,一、香农编码香农第一定理指出了平均码长与信源熵之间的关系，同时也指出了可以通过编码使码长达到极限值。如何构造这种码？香农码的方法是选择每个码字长度满足其中，表示不小于x的整数，即x为整数时等于x,x不是整数时，等于x取整加1.这样选择的码长一定满足Kraft不等式，所以一定存在这样的即时码。按照香农编码方法构造的码，其平均码长不超过上界，即只有当信源符号的概率分布满足形式时，才能达到极限值。一般情况下，香农编码的不是最短，即编出来的码不是紧致码（最佳码）。,50,香农编码的具体方法如下：（1）将所有q个信源符号按其概率的递减次序排列。（2）按下式依次计算每个信源符号的二元码码长（3）计算每个信源符号的累加概率，并变换成二进制小数得到其码字。累加概率将累加概率变换成二进制小数，取小数点后位数作为第i个信源符号的码字。,51,例1.参见表1，按照以上步骤对一个有7个信源符号的信源编码。并计算编码后的信息传输率。,52,二、香农-费诺-埃利斯编码香农-费诺-埃利斯编码与香农编码方法大致相同，但有3点不同：一是它不需要对信源符号概率进行排序；二是它的累加概率是修正的累加概率；另外，码长的计算方法也不同。（1）修正的累加概率的计算方法：（2）码长的计算方法,53,三、二元霍夫曼码这是霍夫曼于1952年提出的一种构造紧致码的方法。具体方法：（1）将所有q个信源符号按其概率的递减次序排列（2）合并概率最小的两个信源符号的概率，从而得到只包含q-1个符号的新信源,称为缩减信源。在那两个概率最小的两个信源符号旁边用0、1码符号标注。（3）把缩减信源的符号仍按概率大小递减次序排列，再将两个概率最小的信源符号用0和1码符号标注，并且合并概率，这样又形成了q-2个信源符号的缩减信源。（4）依次继续下去，直至信源最后只剩下两个信源符号为止，将这最后两个信源符号分别用二元码符号0和1标注。（5）从最后一级缩减信源开始，向前回溯，将每次标注的码符号连接起来就得到各信源符号所对应的码符号序列，即相应的码字。,54,例2以例1信源为例编写二元霍夫曼码，并计算编码后的信息传输率。注：从霍夫曼码的编码方法可知，这样得到的码并非是唯一的，原因有两个：(1)在每次对信源缩减时，概率最小的两个信源符号多赢的码符号0和1是可以任意互换的，所以可得到不同的霍夫曼码。(2)对信源进行缩减时，如果两个概率最小的信源符号合并后的概率与其他信源符号的概率相同，则在缩减信源中进行概率排序的次序可以是任意的，因此会得到不同的霍夫曼码。,55,例3.表2给出了同一信源的两种霍夫曼编码，它们的平均码长和编码效率都相同，都是紧致码，但是质量不完全相同，因为它们的码长方差不同。,56,平均码长，编码效率，码1的码长方差，码2的码长方差，由此可见，码2的码长方差要比码1的码长方差小很多，因此码2的码长更均匀，质量更好。注：从此例可以看出，霍夫曼编码在信源缩减排列时，应使合并的信源符号位于缩减信源中尽可能高的位置上，这样可以使合并的信源符号码长较短，充分利用短码，而非合并的信源符号码长较长，所以得到方