信息论第四章

信息论第四章第1页，课件共78页，创作于2023年2月信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。信道编码：是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。密码：是以提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。第一节引言第2页，课件共78页，创作于2023年2月信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。无失真信源编码定理：是离散信源/数字信号编码的基础；限失真信源编码定理：是连续信源/模拟信号编码的基础。信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类。离散信源编码：独立信源编码，可做到无失真编码；连续信源编码：独立信源编码，只能做到限失真信源编码；相关信源编码：非独立信源编码。第一节引言第3页，课件共78页，创作于2023年2月第二节码的分类编码器可以看作这样一个系统，它的输入端为原始信源S，其符号集为；而信道所能传输的符号集为编码器的功能是用符号集X中的元素，将原始信源的符号变换为相应的码字符号，所以编码器输出端的符号集为

称为码字，为码字的码元个数，称为码字的码字长度，简称码长。编码器第4页，课件共78页，创作于2023年2月1、二元码：码符号集X={0,1}，如果要将信源通过二元信道传输，必须将信源编成二元码，这也是最常用的一种码。2、等长码：若一组码中所有码字的长度都相同，称为等长码。3、变长码：若一组码中所有码字的长度各不相同，称为变长码。4、非奇异码：若一组码中所有码字都不相同，称为非奇异码。第二节码的分类第5页，课件共78页，创作于2023年2月5、奇异码：若一组码中有相同的码字，称为奇异码。6、码的N次扩展：若码，码则称码B为码C的N次扩展码。7、唯一可译码：若码的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列，则称此码为唯一可译码。第二节码的分类第6页，课件共78页，创作于2023年2月例：如果有四个信源符号{s1，s2，s3，s4}，采用二元编码，l=2，则可以编成s1=00，s2=01，s3=10，s4=11。第三节等长信源编码定理如果我们要对信源的N次扩展信源进行编码，也必须满足，两边取对数得：表示平均每个信源符号所需的码符号个数。若对信源进行等长编码，则必须满足其中，l是码长，r是码符号集中的码元数，q信源符号个数。第7页，课件共78页，创作于2023年2月第二节等长码例：对英文电报得32个符号进行二元编码，根据上述关系：我们继续讨论上面得例子，我们已经知道英文的极限熵是1.4bit,远小于5bit，也就是说，5个二元码符号只携带1.4bit的信息量，实际上，5个二元符号最多可以携带5bit信息量。我们可以做到让平均码长缩短，提高信息传输率第8页，课件共78页，创作于2023年2月第二节等长码我们举例说明：

设信源而其依赖关系为：第9页，课件共78页，创作于2023年2月第二节等长码若不考虑符号间的依赖关系，可得码长l＝2若考虑符号间的依赖关系，则对此信源作二次扩展可见，由于符号间依赖关系的存在，扩展后许多符号出现的概率为0，此信源只有4个字符，可得码长，但平均每个信源符号所需码符号为第10页，课件共78页，创作于2023年2月第二节等长码我们仍以英文电报为例，在考虑了英文字母间的相关性之后，我们对信源作N次扩展，在扩展后形成的信源（也就是句子）中，有些句子是有意义的，而有些句子是没有意义的，我们可以只对有意义的句子编码，而对那些没有意义的句子不进行编码，这样就可以缩短每个信源符号所需的码长。等长信源编码定理给出了进行等长信源编码所需码长的极限值。第11页，课件共78页，创作于2023年2月定理4.3（等长信源编码定理）一个熵为H(S)的离散无记忆信源，若对其N次扩展信源进行等长r元编码，码长为l，对于任意大于0，只要满足当N无穷大时，则可以实现几乎无失真编码，反之，若：则不可能实现无失真编码，当N趋向于无穷大是，译码错误率接近于1。第三节等长信源编码定理第12页，课件共78页，创作于2023年2月定理4.3的条件式可写成：左边表示长为的码符号所能载荷的最大信息量，而右边代表长为N的序列平均携带的信息量。因此，只要码字传输的信息量大于信源序列携带的信息量，总可以实现无失真编码。第三节等长信源编码定理定理4.3的条件式也可写成：令：称之为编码信息率。可见，编码信息率大于信源的熵，才能实现无失真编码。第13页，课件共78页，创作于2023年2月最佳编码效率为：第三节等长信源编码定理为了衡量编码效果，引进称为编码效率。第14页，课件共78页，创作于2023年2月例：设离散无记忆信源：若采用等长二元编码，要求编码效率，允许错误率，则：也就是长度要达到4130万以上。第三节等长信源编码定理第15页，课件共78页，创作于2023年2月1、唯一可译变长码与及时码信源符号出现概率码1码2码3码4s1s2s3s41/21/41/81/80110011010000111010010001010010001第四节变长信源编码定理第16页，课件共78页，创作于2023年2月第五节变长码码1是一个奇异码，不是唯一可译码；码2也不是唯一可译码，因为收到一串序列是，无法唯一译出对应的原符号序列，如0100，即可译作s4s3s1,也可译作s4s1s3,s1s2s3或s1s2s1s1；码3和码4都是唯一可译的。但码3和码4也不太一样，码4称作逗点码，只要收到1，就可以立即作出译码；而码3不同，当受到一个或几个码是，必须参考后面的码才能作出判断。

定义，在唯一可译码中，有一类码，它在译码是无须参考后面的码字就可以作出判断，这种码称为即时码。第17页，课件共78页，创作于2023年2月定义：如果一个码组中的任一个码字都不是另一个码字的续长，或者说，任何一个码字后加上若干码元后都不是码组中另一个码字，则称为即时码。所有的码非奇异码唯一可译码即时码第四节变长信源编码定理第18页，课件共78页，创作于2023年2月2、即时码的树图构造法我们可以用树图的形式构造即时码，如01001111010010001码4的树图10110000101001000码3的树图第四节变长信源编码定理树根——码字的起点树枝数——码的数节点数——码字的一部分节数——码长端点——码字满树——等长码非满树——变长码第19页，课件共78页，创作于2023年2月在每个节点上都有r个分枝的树称为整树，否则称为非整树。即时码的树图还可以用来译码第四节变长信源编码定理第20页，课件共78页，创作于2023年2月3、克拉夫特（Kraft）不等式定理4.4对于码符号为的任意即时码，所对应的码长为，则必定满足：反之，若码长满足上式，则一定存在这样的即时码。可以根据即时码的树图构造法来证明。后来，B.McMillan证明了对于唯一可译码也必须满足上面的不等式，第四节变长信源编码定理第21页，课件共78页，创作于2023年2月定理4.6若存在一个码长为唯一可译码，则一定存在一个同样长度的即时码。这说明，其他唯一可译码在码长方面并不比即时码占优。所以在讨论唯一可译码时，只需要讨论即时码就可以了。第四节变长信源编码定理第22页，课件共78页，创作于2023年2月设信源编码后的码字为：码长为：则这个码的平均长度为：平均每个码元携带的信息量即编码后的信息传输率为：若有一个唯一可译码，它的平均码长小于其他唯一可译码的长度，则称此码为紧致码或最佳码，无失真信源编码的基本问题就是寻找紧致码。第四节变长信源编码定理第23页，课件共78页，创作于2023年2月定理4.8无失真变长信源编码定理（香农第一定理）离散无记忆信源S的N次扩展信源，其熵为，并且编码器的码元符号集为A：对信源进行编码，总可以找到一种编码方法，构成单义可译码，使信源S中每个符号si所需要的平均码长满足当则得：第四节变长信源编码定理第24页，课件共78页，创作于2023年2月这个定理是香农信息论中非常重要得一个定理，它指出，要做到无失真得信源编码，信源每个符号所需要的平均码元数就是信源的熵值，如果小于这个值，则唯一可译码不存在，可见，熵是无失真信源编码的极限值。定理还指出，通过对扩展信源进行编码，当N趋向于无穷时，平均码长可以趋进该极限值。还可以证明，如果我们不确切知道信源的概率分布，我们用估计的概率分布去进行编码时，平均码长会加长，但是如果估计的偏差不大的话，平均码长也不会增加太多（定理4.9的内容）。第四节变长信源编码定理第25页，课件共78页，创作于2023年2月由得：就是编码后每个信源符号所携带的平均信息量第一定理可以表述如下：若就存在唯一可译变长码，若则不存在唯一可译变长码。第四节变长信源编码定理定义：若从信道角度讲，信道的信息传输率因为：所以当平均码长达到极限值时，编码后信道的信息传输率为：第26页，课件共78页，创作于2023年2月无噪信道编码定理若信道的信息传输率R不大于信道容量C，总能对信源的输出进行适当的编码，使的在无噪无损信道上能无差错的以最大信息传输率C传输信息，若R小于C，则无差错传输是不可能的。第四节变长信源编码定理编码效率：码的剩余度：在二元无噪无损信道中：在二元无噪无损信道中信息传输率：第27页，课件共78页，创作于2023年2月例：其熵为：H(S)=0.811我们令s1=0，s2=1，这时平均码长，编码的效率为。第四节变长信源编码定理二次扩展信源进行编码：即时码s1s19/160s1s23/1610s2s13/16110s2s21/16111第28页，课件共78页，创作于2023年2月第五节香农编码设离散无记忆信源二进制香农码的编码步骤如下：将信源符号按概率从大到小的顺序排列，为方便起见，令p(x1)≥p(x2)≥…≥p(xn)令p(x0)=0，用pa(xj)，j=i+1表示第i个码字的累加概率，则：确定满足下列不等式的整数ki，并令ki为第i个码字的长度－log2

p(xn)≤ki<－log2

p(xn)+1将pa(xj)用二进制表示，并取小数点后ki位作为符号xi的编码。第29页，课件共78页，创作于2023年2月第五节香农编码例有一单符号离散无记忆信源对该信源编二进制香农码。其编码过程如下表所示。第30页，课件共78页，创作于2023年2月第五节香农编码计算出给定信源香农码的平均码长若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用3个比特表示。相比较，香农编码对信源进行了压缩。由离散无记忆信源熵定义，可计算出：对上述信源采用香农编码的信息率为编码效率为信源熵和信息率之比。则可以看出，编码效率并不是很高。第31页，课件共78页，创作于2023年2月第六节费诺编码费诺编码也是一种常见的信源编码方法。编码步骤如下：将概率按从大到小的顺序排列，令p(x1)≥p(x2)≥…≥p(xn)按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编m进制码就分成m组。给每一组分配一位码元。将每一分组再按同样原则划分，重复步骤2和3，直至概率不再可分为止。第32页，课件共78页，创作于2023年2月第六节费诺编码例设有一单符号离散信源对该信源编二进制费诺码。编码过程如下表。第33页，课件共78页，创作于2023年2月第六节费诺编码该信源的熵为平均码长为编码效率为本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。第34页，课件共78页，创作于2023年2月第六节费诺编码题中码字还可用码树来表示，如图所示。第35页，课件共78页，创作于2023年2月第七节霍夫曼编码霍夫曼(Huffman)编码是一种效率比较高的变长无失真信源编码方法。编码步骤二进制哈夫曼编码m进制哈夫曼编码第36页，课件共78页，创作于2023年2月第七节霍夫曼编码——编码步骤将信源符号按概率从大到小的顺序排列，令p(x1)≥p(x2)≥…≥p(xn)给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n－1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n－2)个符号的缩减信源S2。重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。第37页，课件共78页，创作于2023年2月第七节霍夫曼编码——二进制哈夫曼编码例设单符号离散无记忆信源如下，要求对信源编二进制霍夫曼码。编码过程如下图（后页）。在图中读取码字的时候，一定要从后向前读，此时编出来的码字才是可分离的异前置码。若从前向后读取码字，则码字不可分离。第38页，课件共78页，创作于2023年2月第七节霍夫曼编码——二进制哈夫曼编码第39页，课件共78页，创作于2023年2月第七节霍夫曼编码——二进制哈夫曼编码将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树。第40页，课件共78页，创作于2023年2月信源熵为：平均码长为编码效率为若采用定长编码，码长K=3，则编码效率可见哈夫曼的编码效率提高了12.7%。第七节霍夫曼编码——二进制哈夫曼编码第41页，课件共78页，创作于2023年2月第七节霍夫曼编码——二进制哈夫曼编码注意：哈夫曼的编法并不惟一。每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。不同的码元分配，得到的具体码字不同，但码长ki不变，平均码长也不变，所以没有本质区别；缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的编法得到的码字长度ki也不尽相同。第42页，课件共78页，创作于2023年2月例：单符号离散无记忆信源，用两种不同的方法对其编二进制哈夫曼码。siliWi概率s1s2s3s4s512344101000001000110.40.20.20.10.10.40.20.20.20.40.40.20.60.4010101方法一：合并后的新符号排在其它相同概率符号的后面。第七节霍夫曼编码——二进制哈夫曼编码第43页，课件共78页，创作于2023年2月siliWi概率s1s2s3s4s512344101000001000110.40.20.20.10.10.40.20.20.20.40.40.20.60.4010101这两种编码哪一种更好呢，我们来计算一下二者的码长。方法二：合并后的新符号排在其它相同概率符号的前面。第七节霍夫曼编码——二进制哈夫曼编码第44页，课件共78页，创作于2023年2月两种编码的平均码长是一样的，都是2.2，那一种更好呢，我们可以计算一下平均码长的方差。定义码字长度的方差σ2：第七节霍夫曼编码——二进制哈夫曼编码第45页，课件共78页，创作于2023年2月第七节霍夫曼编码——二进制哈夫曼编码可见：第二种编码方法的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。第一种方法编出的5个码字有4种不同的码长；第二种方法编出的码长只有两种不同的码长；显然，第二种编码方法更简单、更容易实现，所以更好。结论：在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。第46页，课件共78页，创作于2023年2月第七节霍夫曼编码——m进制哈夫曼编码“全树”概念定义：码树图中每个中间节点后续的枝数为m时称为全树；若有些节点的后续枝数不足m，就称为非全树。二进制码不存在非全树的情况，因为后续枝数是一时，这个枝就可以去掉使码字长度缩短。对m进制编码：若所有码字构成全树，可分离的码字数（信源个数）必为m+k(m－1)。k为信源缩减次数。若信源所含的符号数n不能构成m进制全树，必须增加s个不用的码字形成全树。显然s<m－1，若s=m－1，意味着某个中间节点之后只有一个分枝，为了节约码长，这一分枝可以省略。第47页，课件共78页，创作于2023年2月第七节霍夫曼编码——m进制哈夫曼编码在编m进制哈夫曼码时为了使平均码长最短，必须使最后一步缩减信源有m个信源符号。非全树时，有s个码字不用：第一次对最小概率符号分配码元时就只取(m－s)个，分别配以0,1,…,m－s－1，把这些符号的概率相加作为一个新符号的概率，与其它符号一起重新排列。以后每次就可以取m个符号，分别配以0,1,…,m－1；…；如此下去，直至所有概率相加得1为止，即得到各符号的m进制码字。第48页，课件共78页，创作于2023年2月第七节霍夫曼编码——m进制哈夫曼编码例：对如下单符号离散无记忆信源(例5.4.1)编三进制哈夫曼码。这里：m=3，n=8令k=3，m+k(m－1)=9，则s=9－n=9－8=1所以第一次取m－s=2个符号进行编码。第49页，课件共78页，创作于2023年2月第七节霍夫曼编码——m进制哈夫曼编码第50页，课件共78页，创作于2023年2月第七节霍夫曼编码——m进制哈夫曼编码平均码长为：信息率为：编码效率为：可见：哈夫曼的编码效率相当高，对编码器的要求也简单得多。第51页，课件共78页，创作于2023年2月一些结论香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩；香农码有系统的、惟一的编码方法，但在很多情况下编码效率不是很高；费诺码和哈夫曼码的编码方法都不惟一；费诺码比较适合于对分组概率相等或接近的信源编码；哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。第52页，课件共78页，创作于2023年2月第八节游程编码、算术编码香农编码、费诺编码、哈夫曼编码主要是针对无记忆信源。当信源有记忆时上述编码效率不高；游程编码对相关信源编码更有效；香农编码、费诺编码、哈夫曼编码属于无失真信源编码；游程编码属于限失真信源编码。第53页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码游程：数字序列中连续出现相同符号的一段。二元序列的游程：只有“0”和“1”两种符号。连“0”这一段称为“0”游程，它的长度称为游程长度L(0)；连“1”这一段称为“1”游程，它的游程长度用L(1)表示。游程编码①二元独立序列游程长度概率若规定二元序列总是从“0”开始。对于随机序列，游程长度是随机的其取值可为1,2,3,…，直至无穷。游程长度序列/游程序列：用交替出现的“0”游程和“1”游程长度表示任意二元序列。游程变换：是一种一一对应的变换，也是可逆变换。例如：二元序列：000101110010001…，可变换成如下游程序列：31132131第54页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码游程变换减弱了原序列符号间的相关性。游程变换将二元序列变换成了多元序列；这样就适合于用其他方法，如哈夫曼编码，进一步压缩信源，提高通信效率。编码方法：首先测定“0”游程长度和“1”游程长度的概率分布，即以游程长度为元素，构造一个新的信源；对新的信源（游程序列）进行哈夫曼编码。游程编码第55页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码②二元独立序列游程长度的熵若二元序列的概率特性已知，由于二元序列与游程变换序列的一一对应性，可计算出游程序列的概率特性。令“0”和“1”的概率分别为p0和p1，则“0”游程长度L(0)的概率为p[L(0)]=p0L(0)－1p1式中L(0)=1,2,…,在计算p[L(0)]时必然已有“0”出现，否则就不是“0”游程，若下一个符号是“1”，则游程长度为1，其概率是p1=1－p0；若下一个符号为“0”、再下一个符号为“1”，则游程长度为2，其概率将为p0p1；依此类推。游程编码第56页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码游程编码游程长度至少是1，理论上，游程长度可以是无穷，但很长的游程实际出现的概率非常小。同理可得“1”游程长度L(1)的概率为：P[L(1)]=p1L(1)-1p0“0”游程长度的熵：第57页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码③二元独立序列的平均游程长度“0”游程序列的平均游程长度同理可得“1”游程长度的熵和平均游程长度游程编码第58页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码游程编码④二元独立序列的熵“0”游程序列的熵与“1”游程长度的熵之和除以它们的平均游程长度之和，即为对应原二元序列的熵H(X)游程变换后符号熵没有变。因为游程变换是一一对应的可逆变换，所以变换后熵值不变。第59页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码游程变换有较好的去相关效果，因而对游程序列进行哈夫曼编码可获得较高的编码效率。假设“0”游程长度的哈夫曼编码效率为η0，“1”游程长度的哈夫曼编码效率为η1，由编码效率的定义和式(5.4.9)可得对应二元序列的编码效率（信源熵和信息率之比为编码效率η=H(X)/R）当“0”游程和“1”游程的编码效率都很高时，采用游程编码的效率也很高，至少不会低于较小的那个效率。要想编码效率尽可能高，应尽可能提高熵值较大的游程编码效率。游程编码第60页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码算术编码算术编码不同于哈夫曼码，它是非分组（非块）码。它从全序列出发，考虑符号之间的关系来进行编码。算术编码利用了累积概率的概念。算术码主要的编码方法是计算输入信源符号序列所对应的区间。因为在编码过程中，每输入一个符号要进行乘法和加法运算，所以称此编码方法为算术编码。二元序列的算术编码可用于黑白图像的编码，例如传真。第61页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码算术编码设信源符号集A={a1,a2,…,an}，其相应概率分布为P(ai)，P(ai)>0(i=1,2,…,n)信源符号的累积分布函数为：所得累积分布函数为每台级的下界值，则其区间为[0,1)左闭右开区间。

F(a1)=0

F(a2)=P(a1)

F(a3)=P(a1)+P(a2)

…当A={0,1}二元信源时：F(0)=0，F(1)=P(0)第62页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码算术编码计算二元无记忆信源序列的累积分布函数初始时：在[0,1)区间内由F(1)划分成二个子区间[0,F(1))和[F(1),1)，F(1)=P(0)。子区间[0,F(1))的宽度为A(0)=P(0)，对应于信源符号“0”；子区间[F(1),1)的宽度为A(1)=P(1)，对应于信源符号“1”；若输入符号序列的第一个符号为s=“0”，落入[0,F(1))区间，得累积分布函数F(s=“0”)=F(0)=0；

第63页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码算术编码输入第二个符号为“1”，s=“01”s=“01”所对应的区间是在区间[0,F(1))中进行分割；符号序列“00”对应的区间宽度为:A(00)=A(0)P(0)=P(0)P(0)=P(00)；对应的区间为[0,F(s=“01”))。符号序列“01”对应的区间宽度为A(01)=A(0)P(1)=P(0)P(1)=P(01)=A(0)－A(00)；对应的区间为[F(s=“01”),F(1))。累积分布函数F(s=“01”)=P(00)=P(0)P(0)第64页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码算术编码第65页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码算术编码输入第三个符号为“1”：输入序列可记做s1=“011”（若第三个符号输入为“0”，可记做s0=“010”）；现在，输入序列s1=“011”对应的区间是对区间[F(s),F(1))进行分割；序列s0=“010”对应的区间宽度为A(s=“010”)=A(s=“01”)P(0)=A(s)P(0)其对应的区间为[F(s),F(s)+A(s)P(0))；序列s1=“011”对应的区间宽度为

A(s=“011”)=A(s)P(1)=A(s=“01”)－A(s=“010”)=A(s)－A(s0)其对应的区间为[F(s)+A(s)P(0),F(1))；符号序列s1=“011”的累积分布函数为F(s1)=F(s)+A(s)P(0)；若第三个符号输入为“0”，符号序列s0=“010”的区间下界值仍为F(s)，得符号序列s0=“010”的累积分布函数为F(s0)=F(s)。第66页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码算术编码归纳当已知前面输入符号序列为s，若接着再输入一个符号“0”，序列s0的累积分布函数为：F(s0)=F(s)对应区间宽度为：A(s0)=A(s)P(0)若接着输入的一个符号是“1”，序列的累积分布函数为：F(s1)=F(s)+A(s)P(0)对应区间宽度为：A(s1)=A(s)P(1)=A(s)－A(s0)第67页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码算术编码符号序列对应的区间宽度A(s=“0”)=P(0)A(s=“1”)=1－A(s=“0”)=P(1)A(s=“00”)=P(00)=A(0)P(0)=P(0)P(0)A(s=“01”)=A(s=“0”)－A(s=“00”)=P(01)=A(0)P(1)=P(0)P(1)A(s=“10”)=P(10)=A(1)P(0)=P(1)P(0)A(s=“11”)=A(s=“1”)－A(s=“10”)=P(11)=A(s=“1”)P(1)=P(1)P(1)A(s=“010”)=A(s=“01”)P(0)=P(01)P(0)＝P(010)A(s=“011”)=A(s=“01”)-A(s=“010”)=A(s=“01”)P(1)=P(01)P(1)=P(011)

信源符号序列s所对应区间的宽度等于符号序列s的概率P(s)。第68页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码算术编码二元信源符号序列的累积分布函数的递推公式F(sr)=F(s)+P(s)F(r)(r=0,1)

sr表示已知前面信源符号序列为s，接着再输入符号为rF(0)=0，F(1)=P(0)F(s0)=F(s)F(s1)=F(s)+P(s)F(1)=F(s)+P(s)P(0)A(sr)=P(sr)=P(s)P(r)(r=0,1)A(s0)=P(s0)=P(s)P(0)A(s1)=P(s1)=P(s)P(1)第69页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码算术编码举例：已输入二元符号序列为s=“011”，接着再输入符号为“1”，得序列累积分布函数为：

F(s1)=F(0111)=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)=P(s=“011”)P(1)=P(011)P(1)=P(0111)上述整个分析过程可用图5.6.1描述式(5.6.1)和(5.6.2)是可递推运算，在实际中，只需两个存储器，把P(s)和F(s)存下来，然后，根据输入符号和式(5.6.1)、(5.6.2)更新两个存储器中的数值。因此在编码过程中，每输入一个符号要进行乘法和加法运算，所以称为算术编码。第70页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码算术编码第71页，课件共78页，创作于2023年2月第八节游程编码、算术编码、冗余编码算术编码通过关于信源符号序列的累积分布函数的计算，把区间分割成许多小区间，不同的信源符号序列对应不同的区间为[F(s),F(s)+P(s))。可取小区间内的一点来代表