信息论及编码第5章

1、第五章信源编码（第十讲）（2课时）主要内容：（1）编码的定义（2）无失真信源编码重点：定长编码定理、变长编码定理、最佳变长编码。难点：定长编码定理、哈夫曼编码方法。作业：5。2，5。4，5。6；说明：本堂课推导内容较多，枯燥平淡，不易激发学生兴趣，要注意多讨论用途。另外，注意，解题方法。多加一些内容丰富知识和理解。通信的实质是信息的传输。而高速度、高质量地传送信息是信息传输的基本问题。将信源信息通过信道传送给信宿，怎样才能做到尽可能不失真而又快速呢？这就需要解决两个问题：第一，在不失真或允许一定失真的条件下，如何用尽可能少的符号来传送信源信息；第二，在信道受干扰的情况下，如何增加信号的抗干扰能

2、力，同时又使得信息传输率最大。为了解决这两个问题，就要引入信源编码和信道编码。一般来说，提高抗干扰能力（降低失真或错误概率）往往是以降低信息传输率为代价的；反之，要提高信息传输率常常又会使抗干扰能力减弱。二者是有矛盾的。然而在信息论的编码定理中，已从理论上证明，至少存在某种最佳的编码或信息处理方法，能够解决上述矛盾，做到既可靠又有效地传输信息。这些结论对各种通信系统的设计和估价具有重大的理论指导意义。§3.1编码的定义编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。讨论无失真信源编码，可以不考虑干扰问题，所以它的数学描述比较简单。图3.1是一个信源编码器，它的输入是信源符

3、号Ss1,s2,sq，同时存在另一符号Xx1,x2,xr，一般来说，元素xj是适合信道传输的，称为码符号（或者码元）。编码器的功能就是将信源符号集中的符号Si（或者长为N的信源符号序列）变换成由xj（j=1,2,3,r）组成的长度为li的一一对应的序列。输出的码符号序列称为码字，长度li称为码字长度或简称码长。可见，编码就是从信源符号到码符号的一种映射。若要实现无失真编码，则这种映射必须是一一对应的，并且是可逆的。码符号的分类：下图是一个码分类图下面，我们给出这些码的定义。1. 二元码若码符号集为X=0;1，所有码字都是一些二元序列，则称为二元码。二元码是数字通信和计算机系统中最常用的一种码。

4、2. 等长码：若一组码中所有码字的码长都相同，即li=l（i=1,2,q），则称为等长码。3. 变长码：若一组码组中所有码字的码长各不相同，则称为变长码。4. 非奇异码：若一组码中所有码字都不相同，则称为非奇异码。5. 奇异码：若一组码中有相同的码字，则称为奇异码。6. 唯一可译码：若码的任意一串有限长的码符号序列只能唯一地被译成所对应的信源符号序列，则此码称为唯一可译码，否则就称为非唯一可译码。7. 非即时码和即时码：如果接收端收到一个完整的码字后，不能立即译码，还要等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。如果收到一个完整的码字以后，就可以立即译码，则叫做即时码。即

5、时码要求任何一个码字都不是其他码字的前缀部分，也叫做异前缀码。码树：即时码的一种简单构造方法是树图法。对给定码字的全体集合C=W1,W2,Wq来说,可以用码树来描述它。所谓树，就是既有根、枝，又有节点，如图5.2（80业）所示，图中，最上端A为根节点，A、B、C、D、E皆为节点，E为终端节点。A、B、C、D为中间节点，中间节点不安排码字，而只在终端节点安排码字，每个终端节点所对应的码字就是从根节点出发到终端节点走过的路径上所对应的符号组成，如图5.2中的终端节点E,走过的路径为ABCDE，所对应的码符号分别为0、0、0、1，则E对应的码字为0001。可以看出，按树图法构成的码一定满足即时码的定

6、义（一一对应，非前缀码）。从码树上可以得知，当第i阶的节点作为终端节点，且分配码字，则码字的码长为i任一即时码都可以用树图法来表示。当码字长度给定后，用树图法安排的即时码不是唯一的。如图3.2中，如果把左树枝安排为1，右树枝安排为0，则得到不同的结果。对一个给定的码，画出其对应的树，如果有中间节点安排了码字，则该码一定不是即时码。每个节点上都有r个分支的树称为满树，否则为非满树。即时码的码树图还可以用来译码。当收到一串码符号序列后，首先从根节点出发，根据接收到的第一个码符号来选择应走的第一条路径，再根据收到的第二个符号来选择应走的第二条路径，直到走到终端节点为止，就可以根据终端节点，立即判断出

7、所接收的码字。然后从树根继续下一个码字的判断。这样，就可以将接收到的一串码符号序列译成对应的信源符号序列。克拉夫特（Kraft）不等式定理3.1对于码符号为X=Xi,X2,Xr的任意唯一可译码，其码字为Wl,W2,Wq，所对应的码长为ll,|2lq,则必定满足克拉夫特不等式反之，若码长满足上面的不等式，则一定存在具有这样码长的即时码。注意：克拉夫特不等式只是说明唯一可译码是否存在，并不能作为唯一可译码的判据（可以排除，不能肯定）。如0，10，010，111满足克拉夫特不等式，但却不是唯一可译码。例题：设二进制码树中X=X1,X2,X3,X4，对应的I1=1,12=2,13=2,14=3，由上述

8、定理，可得因此不存在满足这种码长的唯一可译码。可以用树码进行检查。唯一可译码的判断法（变长）：将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，则可判断此码C为唯一可译码。集合F的构成方法：首先，观察码C中最短的码字是否是其它码字的前缀，若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又有可能是某些码字的前缀，再将这些尾随后缀产生的新的尾随后缀列出，然后再观察这些新的尾随后缀是否是某些码字的前缀，再将产生的尾随后缀列出，依此下去，直到没有一个尾随后缀是码字的前缀为止。这样，首先获得了由最短的码字能引起的所有尾随后缀，接着，按照上述步骤将次短码字、等等所有码字可能产生

9、的尾随后缀全部列出。由此得到由码C的所有可能的尾随后缀的集合F。例题：设码C=0,10,1100,1110,1011,1101，根据上述测试方法，判断是否是唯一可译码。解：1.先看最短的码字：“0”，它不是其他码字前缀，所以没有尾随后缀。2.再观察码字“10”，它是码字“1011的”前缀，因此有尾随后缀。所以，集合F=11，00，10，01，其中“10”为码字，故码C不是唯一可译码。§3.2定长编码定理前面已经说过，所谓信源编码，就是将信源符号序列变换成另一个序列（码字）。设信源输出符号序列长度为L,码字的长度为Kl,编码的目的，就是要是信源的信息率最小，也就是说，要用最少的符号来代

10、表信源。在定长编码中，对每一个信源序列，Kl都是定值，设等于K，我们的目的是寻找最小K值。要实现无失真的信源编码，要求信源符号Xi（i=1,2,q）与码字是一一对应的，并求由码字组成的符号序列的逆变换也是唯一的（唯一可译码）。定长编码定理：由L个符号组成的、每个符号熵为Hl(X)的无记忆平稳信源符号序列X1X2X3Xl用Kl个符号Y1Y2Ykl(每个符号有m种可能值)进行定长变码。对任意0,0,只要KllogmLHl(X)则当L足够大时，必可使译码差错小于；反之，当时，译码差错一定是有限值，当L足够大时，译码几乎必定出错。式中，左边是输出码字每符号所能载荷的最大信息量所以等长编码定理告诉我们，

11、只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真的编码。条件时所取得符号数L足够大。设差错概率为P，信源序列的自方差为贝U有：22当(X)和均为定值时，只要L足够大，P可以小于任一整数，即此时要求：只要足够小，就可以几乎无差错地译码，当然代价是L变得更大。令为码字最大平均符号信息量。定义编码效率为：最佳编码效率为无失真信源编码定理从理论上阐明了编码效率接近于1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1，但要在实际中实现，则要求信源符号序列的L非常大进行统一编码才行，这往往是不现实的。例如：例题：设离散无记忆信源概率空间为信源熵为自信息方差为对信源符号采用定

12、长二元编码，要求编码效率90%,无记忆信源有Hl(X)H(X)，因此Hl(X)H(X)，因此册90%可以得到0.28如果要求译码错误概率如果要求译码错误概率106，则L2(x)2789.81010由此可见，在对编码效率和译码错误概率的要求不是十分苛刻的情况下，就需要8L10个信源符号一起进行编码，这对存储和处理技术的要求太高，目前还无法实现。如果用3比特来对上述信源的8个符号进行定长二元编码，L=1,此时可实现译码无差错，但编码效率只有2.55/3=85%。因此，一般说来，当L有限时，高传输效率的定长码往往要引入一定的失真和译码错误。解决的办法是可以采用变长编码。§3.3最佳编码最佳

13、码：对于某一信源和某一码符号集来说，若有一唯一可译码，其平均码长K小于所有其他唯一可译码的平均长度。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。能获得最佳码的编码方法：香农(Shannon)费诺(Fano)哈夫曼(Huffman)1、香农编码方法香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值，这是一个很重要的极限定理。香农第一定理指出，选择每个码字的长度Ki满足下式：1Ki=log取整Pi即：log2pi<Ki<1log2pi就可以得到这种码。这种编码方法称为香农编码。例：设无记忆信源的概率空间为

14、：计算各符号的码字长度：K1=log2=1K2=log4=2K3=K4=log8=3用图示码树，可得各自的码字：U1：(0),U2：(10),U3：(110),U4：(111)信息熵H(U):信源符号的平均码长：编码效率对于这种信源，香农编码是最佳编码。码树达到满树。香农编码法多余度稍大，实用性不大，但有重要的理论意义。编码方法如下：将信源消息符号按其出现的概率大小依次排列P(U1)>P(U2)p(Un)确定码长Ki(整数)：1Ki=log取整Pi为了编成唯一可译码，计算第i个消息的累加概率将累加概率Pi变换成二进制数。取Pi二进制数的小数点后Ki位即为该消息符号的二进制数。例：UU1U

15、2U3U4U5信源符号Ui符号概率p(u)累加概率Pi-logp(u)码字长度Ki码字U10.401.32200U20.30.41.73201U30.20.72.323101U40.050.94.3511100U50.050.954.3511101以i=3为例，计算各符号的码字长度:K3=Iog0.2=3累加概率P4=0.70.10110101由图，这些码字没有占满所有树叶，所以是非最佳码。H(U)平均码长：1.95编码效率：为了提高编码效率，首先应达到满树；例如把U4U5换成A、B这些前面的节点，就可减小平均码长。所以不应先规定码长，而是由码树来规定码字，可得更好的结果。2、费诺编码方法费诺

16、编码属于概率匹配编码，但它不是最佳的编码方法。编码过程如下：将信源符号接概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。如此重复，直至每个组只剩下一个信源符号为止。信源符号所对应的码字即为费诺码。徇UU1U2U3U4U5例：信源符号Ui符号概率p(u)第1次分组第2次分组第3次分组码字码长U10.400002U40.05100103U50.0510113U20.310102U30.21112该费诺码的平均码长编码效率：显然，费诺码比香农码

17、的平均码长小，编码效率高。其实这样编码的效率还不是最高的，现用另一种分割方法:信源符号Ui符号概率P（U）第1次分组第2次分组第3次分组第4次分组码字码长U10.4001U20.30102U30.2101103U40.0511011104U50.05111114该费诺码的平均码长编码效率：可见编码效率又有所提高。事实上这已是最佳编码，就是说编码效率已不能再提高。但这样试探寻找分割方法总不是办法，因而赫夫曼提出一种编码方法，并证明这种编码在块码中已是最佳的。3、哈夫曼编码方法哈夫曼编码也是用码树来分配各符号的码字。费诺码是从树根开始，把各节点分给某子集；若子集已是单点集，它就是一片叶而作为码字。

18、而赫夫曼编码是先给每一符号一片树叶，逐步合并成节点直到树根。哈夫曼编码的步骤如下：将信源消息符号按其出现的概率大小依次排列P（U1）P（U2）P（Un）取两个概率最小的字母分别配以0和1两码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。对重排后的两个概率最小符号重复步骤的过程。不断继续上述过程，直到最后两个符号配以0和1为止。从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。例：给定离散信源如下：平均码长：7Kp（uJKii10.220.1920.1830.1730.1530.1040.014编码效率2.72哈夫曼编码方法得到的码并非是唯一

19、的。非唯一的原因：每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。对信源进行缩减时两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。例：给定离散信源如下：有两种哈夫曼编码方法如下图所示：平均码长：因为这两种码有相同的平均码长，所以有相同的编码效率，但每个信源符号的码长却不相同。在这两种不同的码中，选择哪个码好呢？我们引进码字任度Ki偏离平均码长K的方差b2，

20、即卩分别计算上例中两种码的方差可见，第一种编码方法的方差要小许多。所以，对于有限长的不同信源序列，用第一种方法所编得的码序列长度变化较小。因此相对来说选择第一种编码方法要更好些。由此得出，在哈夫曼编码过程中，当缩减信源的概率分布重新排列时，应使合并得来的概率和尽量处于是高的位置。这样可使合并的元素重复编码次数减少，使短码得到充分利用从以上实例中可以看出，哈夫曼码具有以下三个特点：哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，即Pi>pj有KiVKj,充分利用了短码。缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同（二元编码情况），从而保证了哈夫曼是即

21、时码。每次缩减信源的最长两个码字有相同的码长。这三个特点保证了所得的哈夫曼码一定是最佳码。第五章信源编码（第十一讲）（2课时）主要内容：（1）限失真信源编码定理（2）常用信源编码方法简介（游程编码、矢量量化编码、算术编码)重点：常用信源编码方法简介。难点：限失真信源编码定理、限失真信源编码定理。特别提示：运用说明：本堂课推导内容较多，枯燥平淡，不易激发学生兴趣，要注意多讨论用途。另外，注意，解题方法。多加一些内容丰富知识和理解。作业：灵活运用。课外仍以学生复习。§限失真信源编码定理定理(限失真信源编码定理)设R(D)为离散无记忆信源X的信息率失真函数，R为信息传输率，则当信息率R&g

22、t;R(D)，只要信源序列长度L足够长，一定存在一种编码方法，其译码失真小于或等于D+为任意小的正数；反之，若R<R(D),则无论采用什么样的编码方法，其译码失真必大于D。如果是二元信源，对于任意小的&>0,每一个信源符号的平均码长满足如下公式：该定理指出，在失真限度内使信息率任意接近R(D)的编码方法存在，然而，若信息率小于R(D),平均失真一定会超过失真限度D。对于连续平稳无记忆信源，虽然无法进行无失真编码，但在限失真情况下，有与该定理一样的编码定理。该定理只说明最佳编码是存在的，但对于如何进行编码却一无所知，因而就不能像无损编码那样从证明过程中引出概率匹配的编码方法,

23、损编码那样从证明过程中引出概率匹配的编码方法,般只能从优化的思路去求最佳编码。这个定理证明了允许失真D确定后，总存在一种编码方法,使信息传输率R大于R(D)且可任意接近R(D),而平均失真小于允许失真且可任意接近R(D),而平均失真小于允许失真D。反之，若R<R(D),那么该编码的平D的情况下，平均每均失真将大于D。如果用二进制符号进行编码的话，在允许一定失真个信源符号所需的二元码符号的下限值就是R(D)。由此可见，信息率失真函数R(D)确实是在允许失真度为D的情况下信源信息压缩的下限值。当信源给定后，无失真信源压缩的极限值是信源熵H(U);有失真信源压缩的极限值是信息率失真函数R(D)

24、。在给定某D后，一般R(D)<H(U)。同样，该定理只是一个存在定理。至于如何寻找最佳压缩编码方法，定理中并没有给出。在实际应用中，该定理主要存在以下两大类问题。第一类问题是，符合实际信源的R(D)函数的计算相当困难。首先，需要对实际信源的统计特性有确切的数学描述。其次，需要对符合主客观实际的失真给予正确的度量，否则不能求得符合主客观实际的R(D)函数。例如，通常采用均方误差来表示信源的平均失真度。但对于图像信源来说，均方误差较小的编码方法，人们视觉感到失真较大。所以，人们仍采用主观观察来评价编码方法的好坏。因此，如何定义符合主客观实际情况的失真测度就是件较困难的事。第三，即便对实际信源

25、有了确切的数学描述，又有符合主客观实际情况的失真测度，而信息率失真函数R(D)的计算还是比较困难的。第二类问题是，即便求得了符合实际的信息率失真函数，还需研究采用何种实用的最佳编码方法才能达到R(D)。目前，这两方面工作都有进展。尤其是对实际信源的各种压缩方法，如对语音信号、电视信号和遥感图像等信源的各种压缩方法有了较大进展。相信随着数据压缩技术的发展，限失真编码理论中存在的问题将会得到解决。§限失真信源编码常用信源编码方法一、游程编码游程：指数字序列中连续出现相同符号的一段。二元序列只有两种符号：“0”和“1”：连“0”段称为“0”游程，游程长度为L(0)连“1”段称为“1”游程，

26、游程长度为L(1)由于是二进制序列，“0”游程和“1”游程总是交替出现。若规定二元序列总是从“0”开始，第一个游程是“0”游程，则第二个游程必为“1”游程，第三个又是“0”游程对于随机序列，游程的长度是随机的，其取值为1,2,3自至无穷。游程序列：用交替出现的“0”游程和“1”游程的长度，来表示任意二元序列。例如二元序列0001可变换成如下游程序列己规定游程序列从“0”开始，由上述游程序列，很容易恢复出原来的二元序列。游程序列已是多元序列，各长度就可按哈夫曼编码或其它方法处理以达到压缩码率的目的。这种从二元序列转换成多元序列的方法，在实现时比以前的并元法简单；因为游程长度的计数比较容易，得到游

27、程长度后就可从码表中找出码字输出，同时去数下一个游程长度。此外，在减弱原有序列的符号间的相关性方面采用游程变换一般也比并元法更有效。当然，要对二元序列进行哈夫曼编码时应先测定“0”游程长度和“1”游程长度的概率分布，或由二元序列的概率特性去计算各种游程长度的概率。设二元序列为独立序列，“0”和“1”的概率分别为P0和P1，则“0”游程长度L(0)的概率为式中L(0)=1,2，游程长度至少是1。从理论上来说，游程长度可以是无穷，但很长的游程实际出现的概率非常小。则“1”游程长度L(1)的概率为“0”游程长度的熵：L(0)1L(0)1H(P0)HL(O)pL(0)log2pL(0)popilog2

28、poPi-“0”L(0)1L(0)1Pi游程序列的平均游程长度同理，“1”游程长度的熵和平均游程长度：变换后的游程序列是独立序列游程变换后符号熵没有变。因为游程变换是一一对应的可逆变换。所以变换后熵值不变。由于游程变换有较好的去相关效果，因而对游程序列进行哈夫曼编码，可获得较高的编码效率。假设“0”游程长度的哈夫曼编码效率为n0,“1”游程长度的哈夫曼编码效率为n1,由编码效率的定义得二兀序列的编码效率假设n0>n1，则有n0>n>n1当“0”游程和“1”游程的编码效率都很高时，采用游程编码的效率也很高，至少不会低于较小的那个效率。要想编码效率n尽可能高，应使上式的分母尽可能

29、小，这就要求尽可能提高熵值较大的游程的编码效率，因为它在往分母中占的比重较大。理论上来说游程长度可从1到无穷。要建立游程长度和码字之间的一一对应的码表是困难的。一般情况下，游程越长，出现的概率就越小；当游程长度趋向于无穷时，出现的概率也趋向于0。按哈夫曼码的编码规则，概率越小码字越长，但小概率的码字对平均码长影响较小，在实际应用时常对长码采用截断处理的方法取一个适当的n值，游程长度为1,2,2n-1,2n，所有大于2n者都按2n来处理。然后按照哈夫曼码的编码规则，将上列2n种概率从大到小排队，构成码树并得到相应的码字。二、矢量量化编码要想得到性能好的编码，仅采用标量量化是不可能的。在最佳编码中

30、，如将离散信源的多个符号进行联合编码可提高效率，这对连续信源也是如此。当把多个信源符号联合起来形成多维矢量，再对矢量进行标量量化时，自由度将更大，同样的失真下，量化级数可进一步减少，码率可进一步压缩。这种量化叫做矢量量化。实验证明，即使各信源符号相互独立，多维量化通常也可压缩信息率。因而矢量量化引起人们的兴趣而成为当前连续信源编码的一个热点。可是当维数较大时，矢量量化尚无解析方法，只能求助于数值计算；而且联合概率密度也不易测定，还需采用诸如训练序列的方法。一般来说，高维矢量的联合是很复杂的，虽已有不少方法，但其实现尚有不少困难，有待进一步研究。设矢量量化器输入集为X=X1,x2,，XN,XjX

31、,Xj=(Xj1,Xj2，,Xjk),XRk(k维欧几里德空间)，把Rk划分成J=2n个互不相交的子空间R1,R2，Rj.Yi，所有的Yi构成,Yi叫码字或码矢，对J阶K维的矢量量化，实质上是判断输入子空间代表码字Yi，即：Yi=Q(Xj),1wiwJ,这里Yi就是Xj的编码。实际编码时，在发送端只需记录代表码字求出每个子空间的质心间，也叫码书(或码本)Y=Y1,丫2，Yj,Y为量化器的输出空J叫码书的长度。XjRk属于哪个子空间Ri，然后输出该Yi的下标i，所以编码过程是把X映射到I=1,2，J;而译码过程是在接收端依据收到的I代码，查找码书Y,获得码字Yi,NXK，所以矢量量化的压缩用来代

32、替Xj。由于总的码字个数J一般远小于总的输入信号能力非常大。传输或存储一个矢量所需比特为IbJ(一般J=2n)，它是一个K维矢量，就是K个输入信号，所以每个输入信号的平均比特只有IbJ/K，称之为压缩比。适当选取码书长度和码字维数K，可以获得很大压缩比。矢量量化中码书的码字越多，维数越大，失真就越小。只要适当地选择码字数量，就能控制失真量不超过某一给定值，因此码书控制着矢量的大小。矢量量化时每输入一个Xj，都要和J个码字Yi逐一比较，搜索与其最接近的码字Yi。由于两者均为K维矢量，所以工作量很大。矢量量化是定长码，容易处理。矢量量化由码书Y和划分Ri的条件惟一确定。当码书确定后，通过最近邻域准

33、则可以惟一确定区域分割。因此，最佳量化器的设计也就是最佳码书Y的设计。前面，在讨论一维标量的最佳设计时，引入了此算法推广到了多维空间，称作MaxLivod的迭代算法，1980年Linde、Buzo和Gray将LBG算法。因LBG算法由于理论上的严密性和实现的简便性以及较好的设计效果而得到了广泛的应用,便性以及较好的设计效果而得到了广泛的应用,并成为各种改进算法的基础。有关LBG算法等知识请参阅有关文献。法等知识请参阅有关文献。三、算术编码1、算术码的主要概念：把信源输出序列的概率和实数段0,1中的一个数p联系起来。设信源字母表为a1,a2,其发生概率为p(a”=0.6,p(a2)=0.4。将0

34、,1分成两个与概率比例相应的区间,其发生概率为p(a”=0.6,p(a2)=0.4。将0,1分成两个与概率比例相应的区间,0,0.60.6,S1=a1时，数p的值处在0,0.6,S1=a2时，0.6,I。0,1t0,0.60.6,l0,0.360.36,0.60.6,0.840.84,1S1=a1S1=a2根据信源输出的第二个字母S2的取值情况，可以更精确地确定出数p所在的区间位置。在信源输出第n1个符号后，若p所在的位置为I当信源输出的第一个符号根据信源字母S1的情况，把p所在的段再次按概率比例分成An-1,Bn-1则当信源输出的第n个符号为：sn=ai时，sn=a2产n=An-1An=An

35、-1+06(Bn-1一An-1)_Bn=An-1+0.6(Bn-1一An-1)Bn=Bn-1按照这一方法，序列的概率刚好等于p所在区间的长度。随着序列的长度不断增加,P所在区间的长度就越短，也就可以更加精确地确定P的位置。当信源字母序列长度趋于无限时，p所在区间成为一点。2、累积概率设信源字母表为A=a1,a2,ai,am,字母ai的概率p(ai)修正的累积概率为定义字母ak的累积概率为F(a1)=0,F(a2)=p(a1),F(a3)=p(a1)+p(a2)p(ak)=F(ak+1)-F(ak)当A=0,l二元信源时：F(0)=0,F(1)=p(0)计算信源序列S=(S1,S2,Sn)的累积

36、概率以二元无记忆信源为例：初始时：在0,1由F(1)划分成二个子区间：0,1t0,F(1)F(1),1,F(1)=p(0)01子区间0,F(1)F(1),1的宽度为A(0)=p(0)A(1)=p(1)若输入序列的第一个符号为s=“0”，即落入对应的区间0,F(1)F(s=“0”)=F(0)=0当输入第二个符号为“1”,s=“01”对应的区间在0,F(1)中进行分割A(00)=A(0)p(0)=p(0)p(0)=p(00)A(01)=A(0)p(1)=p(0)p(1)=p(01)=A(0)-A(00)00”对应的区间0,F(01);01”对应的区间F(01),F(1)s=“01”的累积概率F(s

37、=“01”)=F(01)=p(0)p(0)当输入第三个符号为“1”，s1=“011”，所对应的区间在F(01),F(1)中进行分割对应的区间F(s),F(s)+A(s)p(0)对应的区间F(s)+A(s)p(0),F(1)A(010)=A(01)p(0)=A(s)p(0)A(011)=A(01)p(1)=A(s)p(1)=A(01)A(010)=A(s)A(s0)F(s1)=F(s)+A(s)p(0)F(s0)=F(s)现已输入三个符号串，将这符号序列标为s,接着输入第四个符号为“0”或“1”。可计算出s0=“0110”或s1=“0111”对应的子区间及其累积概率。当已知前面输入符号序列为s，

38、若接着再输入一个符号“0”累积概率区间宽度F(s0)=F(s)A(s0)=A(s)p(0)若接着输入的一个符号是“1”，对序列s1的累积概率为F(s1)=F(s)+A(s)p(0)A(s1)=A(s)p(1)=A(s)A(s0)由前分析又知，符号序列对应的区间宽度为A(0)=p(0)A(1)=1A(0)=p(1)A(00)=p(00)=A(0)p(0)=p(0)p(0)A(01)=A(0)A(00)=p(01)=A(0)p(1)=p(0)p(1)A(10)=p(10)=A(1)p(0)=p(1)p(0)A(11)=A(1)A(10)=p(11)=A(1)p(1)=p(1)p(1)A(010)=

39、A(01)p(0)=p(01)p(0)=p(010)A(011)=A(01)A(010)=A(01)p(1)=p(01)p(1)=p(011)III信源符号序列s所对应区间的宽度等于符号序列s的概率p(s)二元信源符号序列的累积概率的递推公式为F(sr)=F(s)+p(s)F(r)(r=0,1)其中sr表示已知前面信源符号序列为s接着再输入符号为r。而F(r):F(0)=0,F(1)=p(0)同样可得信源符号序列所对应区间的宽度的递推公式为A(sr)=p(sr)=p(s)p(r)(r=0,1)已输入的二元符号序列为s=“011”，若接着输入符号为1得序列的累积概率:F(s1)=F(0111)=

40、F(s=011)+p(011)p(0)=F(s=01)+p(01)p(0)+p(011)p(0)=F(s=0)+p(0)p(0)+p(01)p(0)+p(011)p(0)=0+p(00)+p(010)+p(0110)其对应区间宽度A(s1)=A(s=011)p(1)=p(011)p(1)=p(0111)由于F(sr)=F(s)+p(s)F(r)A(sr)=p(sr)=p(s)p(r)是可递推运算，因此适合于实用。实际中，只需两个存储器，把p(s)和F(s)存下来,然后根据输入符号和上式，更新两个存储器中的数值。因为在编码过程中，每输入一个符号要进行乘法和加法运算，所以称此编码方法为算术编码。将

41、上式推广到多元信源序列，得一般的递推公式F(sak)=F(s)+p(s)F(ak)A(sak)=p(sak)=p(s)p(ak)通过关于信源符号序列的累积概率的计算，F(s)把区间0,1分割成许多小区间，不同的信源符号序列对应于不同的区间为F(s),F(s)+p(s)。可取小区间内的一点来代表这序列。代表大于等于的最小整数。1令Llogp(s)把累积概率F(s)写成二进制的小数，取小数点后L位，以后如果有尾数，就进到第L位，这样得到一个数C。例F(s)=0.，p(s)1/17，则L=5，得C=0.10111，s的码字为10111这样选取的数值C，一般根据二进小数截去位数的影响，得丄CF(s)V

42、2L当F(s)在L位以后没有尾数时C=F(s)。而由Llogp(s)可知F(s)>2-L则信源符号序列s对应区间的上界F(s)+p(s)>F(s)+2-L>C可见数值C在区间F(s),F(s)+p(s)内。信源符号序列对应的不同区间是不重叠的，所以编得的码是即时码。实用中，采用累积概率F(s)表示码字C(s)，符号概率p(s)表示状态区间A(s)，则有C(sp=C(s)+A(s)F(r)A(sJ)=A(s)p(r)因为信源符号序列因为信源符号序列s的码长满足Llogp(s)，所以得若信源是无记忆的H(Sn)=nH(S)平均每个信源符号的码长例：设二元无记忆信源A=0,1，p(

43、0)=1/4，p(1)=3/4对二元序列s=做算术编码解：根据上述的编码规则，可得p(s=)=p2(0)p6(1)=(3/4)2(1/4)F(a3)=p(a1)+p(a2)F(s)=p(00000000)+p(00000001)+p(00000010)+p()=1p()p()p()p()=1p(111111)=1(3/4)6=0.1得C=0.1101010s的码字为1101010编码效率081192.7%L7/8这种按全序列进行编码，随着信源序列n的增长，效率还会增高。递推编码过程可列表如下：得s的码字为1101010。此时s=对应的区间为0.1,0.1。可见C是区间内一点。实际编码是用硬件或

44、计算机软件实现，所以采用速推公式来进行编码。只要存储量允许，这种编码，可以不论s有多长，一直进行计算下去，直至序列结束。2-2或1本例题中p(0)=2-2，又F(0)=0,F(1)=p(0)=2-2在递推公式中每次需乘以乘以(I2-2)。在计算机中，乘以2-Q(Q为正整数)，就可用右移Q位采取代；乘以2-Q就可用此数减去右移Q位数取代。这样简捷快速。译码就是一系列比较过程。每一步比较CF(s)与p(s)p(0)若CF(s)vp(s)p(0)则译输出符号为“0”若CF(s)>p(s)p(0)则译输出符号为“1”s为前面已译出的序列串p(s)是序列串s对应的宽度F(s)是序列串s的累积概率，

45、即为s对应区间的下界。p(s)p(0)是此区间内下一个输入为符号“0”所占的子区间宽度。由上面分析可知，算术编码效率高，编译码速度也快。前面叙述了算术编码的基本方法。在实用中还需考虑计算精度问题、存储量问题、近似相2-Q中Q的选择问题等等。所以，算术编码的编码效率很高、当信源符号序列很长时。很大时，平均码长接近信源的一般情况下，F(ak)为实数，若用二进制数精确表示，则有可能需要无穷多位，但作为码字只需有足够的位数，使其能与ak一一对应就够了，所以只需用L位来表示F(ak)，即取例：设离散无记忆信源字母表为a1,a2,a3,a4，p(a1)=0.25p(a2)=0.5，p(a3)=0.125，

46、p(a4)=0.125。求：字母ak的累积概率F(ak)及F(ak)的二进制表示和相应的码字。如表所示:akp(ak)F(ak)F(ak)二进制表示L码字al0.2500a20.500.250.01a30.1250.750.11a40.1250.8750.111在上面两个例子中，算术编码的效果并不很好，这是因为仅用算术编码方法对婚字母进行编码、若对源字母序列进行编码，则算术编码有独特的优点它和以随若序列长度N的增加而自然地改进压缩效果。第五章信源编码(第十二讲)(2课时)主要内容：(1)常用信源编码方法简介(预测编码)(2)常用信源编码方法简介(变换编码)。重点：常用信源编码方法简介(预测编码

47、)。难点：常用信源编码方法简介(预测编码)。特别提示：运用说明：本堂课推导内容较多，枯燥平淡，不易激发学生兴趣，要注意多讨论用途。另外，注意，解题方法。多加一些内容丰富知识和理解。作业：灵活运用。课外仍以学生复习。§限失真信源编码常用信源编码方法四、预测编码预测编码的基本原理对于有记忆信源，信源输出的各个分量之间是有统计关联的，这种统计关联性可以加以充分利用。预测编码：在这种编码方法中，编码器和译码器都存贮有过去的信号值，并以此来预测或估计未来的信号值。在编码器发出的不是信源信号本身，而是信源信号与预测值之差；在译码端，译码器将接收到的这一差值与译码器的预测值相加，从而恢复信号。设信

48、源第i瞬间的输出为ui，根据信源ui的前K个样值，给出的预测值为其中f为预测函数，它可以是线性也可以是非线性函数，线性预测函数实现比较简单，比如图5-4-2所示，这时预测值为：贝怫i个样值的预测误差值为根据信源编码定理，若直接对信源输出进行编码，则其平均码长Ku应趋于信源熵:若对预测变换后的误差值e进行编码，其平均码长Ke应趋于误差信号熵：显然，从信息论观点，预测编码能压缩信源数码率的必要条件为：这里Ku表示预测前的信源编码平均码长，Ke表示预测后误差信号编码的码长。由于信息熵是概率分布的泛函数，故概率分布越均匀，熵越大；概率分布越不均匀，比如越集中，熵就越小，即H(E)H(U)，信源通过预测

49、以后数据压缩(或连续时的频带压缩)倍数就越大。实现预测编码要进一步考虑3个方面的问题：预测误差准则的选取：预测函数的选取：预测器输入数据的选取。预测误差准则：预测误差所依据的标准如何选取预测值U?，以使预测误差ei满足某种意义上的最佳是预测编码设计中的核心问题。按照不同的最佳准则，可得到比较重要的3种最佳预测器：最小均方误差预测器：最佳准则：使预测误差的均方值达到最小最小平均绝对误差预测器最佳准则：使预测器的绝对误差的均值达到最小最大零误差概率预测器预测编码的基本原理最佳准则：预测值具有零误差的概率或概率密度为最大DPCM信源的话音信号为u(t)，其iTs时刻的抽样值为u(iTs),简写为ui

50、。DPCM基本思想：将“话音信号样值同预测样值的差”作量化、编码。K和aj是预测器的参数，为常数。该式表示？是先前K个样值的加权和，aj称为预测器系数。u:Ui的预测值。发端的预测器和相加器用来获得当前的预测值u?i预测器的输出样值U?与其输入样值i的关系满足下式：图中编码器的“预测器和相加器”组成结构同解码器的“预测器和相加器”的组成结构完全一样：显然，信道信息传输无误码时，两个相加器输入端的信号完全一样：Xi=yi。此时图中解码器的输出信号i与编码器信号i是相同的：DPCM系统的量化误差应该定义为输入信号样值ui与解码器输出信号样值i之差。DPCM系统信噪比Gp:预测增益SNRq:量化器所

51、产生的信噪比五、变换编码众所周知，信源序列往往具有很强的相关性，要提高信源的效率首先要解除信源的相关性。解除相关性可以在时域上进行（这就是上节中介绍的预测编码），也可以在频域，甚至在广义频域内进行，这就是要在本节中介绍的变换编码。在信号分析中，对连续的模拟信号，如果它是周期性的,则可采用傅氏级数展开，若是非周期性的,则可采用傅氏积分（变换）来表示，但无论是级数还是积分,都属于一类正交变换，是从时域展开成频域的变换。同理,对离散的数据序列信号也可引入同样的离散傅氏变换。而且，还可以进一步将其推广为广义的频域变换。在这一节中，首先从解除相关性的需求入手，寻求最佳的域变换。上一节讨论的在空间和时间域

52、上压缩信源数据冗余量的预测编码的最大特点是直观、简洁、易于实现，特别是容易设计出具有实时性的硬件结构。但是预测编码的不足在于压缩能力有限。具有更高压缩能力的方法和目前最为成熟的方法是变换编码，特别是正交变换编码方法和目前尚处于研究阶段的小波变换编码，这两种方法都具有很强的数据压缩能力。变换编码的基本原理就是将原来在空间域上描述的信号，通过一种数学变换（例如，傅里叶变换、正交变换等）变换到变换域（如频率域、正交矢量空间）中进行描述。简单地讲，即把信号由空间域变换到变换域中，用变换系数来描述。这些变换系数之间的相关性明显下降，并且能量常常集中于低频或低序系数区域中，这样就容易实现码率的压缩，而且还

53、大大降低了实现的难度。变换编码的基本原理设信源输出为一个一维消息U=(u1,u2,，un),经变换后输出为X=(x1,x2,，xn),故有：X=PU由正交性ATA=A一1A=I，则有：U=1X=PTX式中：P实正交变换矩阵；PT矩阵P的转置矩阵；P一1矩阵P的逆矩阵；I单位矩阵。如果经正交变换后，只传送M(M<n)个样值，而将余下的n-M个较小的样值丢弃。这时接收端恢复的信号为式中：如何选择正交矩阵P，使M值较小，且使被丢弃的n-M个取值足够地小，以至于既能得到最大的信源压缩率，同时又使丢弃掉n-M个取值以后，所产生的误差不超过允许的失真范围是我们关心的问题。因此，正交变换的主要问题可归

54、结为在一定的误差准则下，寻找最佳或准最佳的正交变换，以达到最大限度地消除原消息源之间的相关性。正交变换为什么能解除相关性呢？下面讨论这个问题。由矩阵代数理论可知：对于任意两个随机变量x,y间的相关性可以用x,y的协方差(相关距)表示。一个信源U的各分量间的相关性可以用信源各分量间协方差矩阵U表示，其定义为式中：u信源输出U的协方差矩阵；E:数学期望；0ijUi、Uj协方差。可以证明U的协方差矩阵U是一个实对称矩阵，它能反映矢量U各分量间的相关性。若各分量之间互不相关，则协方差矩阵U只在主对角线上有非零元素。主对角线上的非零元素代表各分量间的方差，即自相关性；非对角线上的元素表示各分量之间的协方

55、差，即互相关性。由矩阵代数可知，对于一个实对称矩阵A(A=AT的矩阵)，必存在一个正交矩阵P,使得：式中：入1,入2,，入n实对称矩阵A的n个特征根。可见正交变换能解除相关性。信源U经正交变换后的输出X协方差矩阵可定义为X=E:(X-E:X:)(X-E:X)T:=E:(PU-E:PU:)(PU-E:PU:)T=PE:(U-E:U:)(U-E:U:)丁PT=PuPT式中：X信源U正交变换后的信号X的协方差矩阵；X信源U经正交变换后的矢量；P正交变换矩阵；PT正交变换矩阵P的转置矩阵。为了达到信源压缩的目的，希望通过矩阵P的正交变换后，X只保留主对角线上的部分自相关值，即希望其值随i与j值的增大而迅速减小，从而只需取M(M<n)个数值