信息理论与编码4

第4章离散无记忆信源无失真编码信息传输系统编码和译码示意图噪声信道信源编码信源信宿等效无噪信道信源译码信道编码信道译码信息传输系统编码和译码示意图信息理论与编码1第4章离散无记忆信源无失真编码信源编（译）码和信道编（译）码信源发出的消息序列通常不能直接送给信道传输，需要经过两次变换，分别称为信源编码和信道编码，然后送给信道传送，信道输出经过两次反变换，即信道译码和信源译码，就可送给信宿接受了。信息理论与编码2第4章离散无记忆信源无失真编码无失真编码和有失真编码信源编码可分为无失真编码和有失真编码两类。无失真编码只对信源的冗余度进行压缩，而不会改变信源的熵，又称冗余度压缩编码。与之相对的是有失真编码，又称熵压缩编码。信息理论与编码3第4章离散无记忆信源无失真编码无失真信源编码的作用（1）符号变换：使信源的输出符号与信道的输入符号相匹配；（2）冗余度压缩：使编码之后的新信源概率分布均匀化，信息含量效率等于或接近于100%。信息理论与编码4第4章离散无记忆信源无失真编码本章主要内容4.1信源编码概论4.2码的唯一可译性4.3定长编码定理和定长编码方法4.4变长编码定理4.5变长编码方法4.6几种实用的无失真信源编码信息理论与编码5第4章离散无记忆信源无失真编码4.1信源编码概论信源编码器示意图定长编码和变长编码平均码长编码效率信息理论与编码6第4章离散无记忆信源无失真编码信源编码器示意图

——信源符号集合；

——码元组成的集合；

——信道能够传送的符号，称为码元；

——信源编码，一一对应映射，

——把信源输出的符号变换成的码元序列，称为码字；

——所有码字组成的集合，称为码或码字集。

——所含码元的个数，称为该码字的码长，单位“码元/符号”或“r进制单位/符号”。编码器信源信源编码器示意图信息理论与编码7第4章离散无记忆信源无失真编码定长编码和变长编码

如果所有码字均有相同的码长，即则称为定长编码；否则，称为变长编码。平均码长对码W中所有码字的码长求统计平均，码元/符号对于定长码，平均码长与各码字的码长相等，即码元/符号小说明平均一个码元所携带的信息量大，信息的冗余就小。信息理论与编码8第4章离散无记忆信源无失真编码例设DMS的概率空间为对其单个符号进行二进制编码，即码元集合为。定义编码为码元/符号信息理论与编码9第4章离散无记忆信源无失真编码定义编码为

码元/符号信息理论与编码10第4章离散无记忆信源无失真编码编码效率信源编码器输出可视为一个新信源，该信源若以码字集作为符号集，则为信源W，若以码元集当作符号集，则为信源X，如图所示。

将信源编码器的输出视为新信源W或X

无失真编码信源符号与码字是一一对应的，故，所以编码前后的熵保持不变：

bit/码字或bit/符号即无失真信源编码是保熵的。编码器信源信息理论与编码11第4章离散无记忆信源无失真编码将信源编码器输出视为新信源X，则有

bit/码元编码后的信息率，记为R，就是X的熵，

bit/码元定义编码后的实际信息率与编码后的最大信息率之比为编码效率，记为，冗余度：信息理论与编码12第4章离散无记忆信源无失真编码4.2码的唯一可译性4.2.1常见码及其唯一可译性4.2.2码树和Kraft不等式信息理论与编码13第4章离散无记忆信源无失真编码4.2.1常见码及其唯一可译性唯一可译码和非唯一可译码码W是唯一可译码的充分必要条件奇异码和非奇异码非续长码和续长码及时码或立即码各种码的关系信息理论与编码14第4章离散无记忆信源无失真编码唯一可译码和非唯一可译码若码的码字组成的任意有限长码字序列都能恢复成唯一的信源序列，则称该码为唯一可译码（UDC，UniquelyDecodableCode），否则称为非唯一可译码。码是唯一可译码的充分必要条件由W中的码字组成的任意有限长的码字序列（也是码元序列），都能唯一划分成一个个的码字，且任一码字只与唯一一个信源符号对应。信息理论与编码15第4章离散无记忆信源无失真编码下表中，对信源U编了5种不同的码，码的特征各有不同。W1和W2是定长码，其余是变长码。这5种码中，有些能唯一译码，有些不能。表5种不同的码信息理论与编码16第4章离散无记忆信源无失真编码奇异码和非奇异码含相同码字的码称为奇异码，否则称为非奇异码。奇异码肯定不是UDC。定长非奇异码肯定是UDC。非续长码和续长码任一码字都不是另一码字的续长（加长），这种码称为非续长码；有些码字是在另一些码字后面添加码元（续长）得来的，称为续长码。及时码或立即码码字的最后一个码元出现时，译码器能立即判断一个码字已经结束，可以立即译码。信息理论与编码17第4章离散无记忆信源无失真编码各种码的关系各种码的关系图非续长码不但唯一可译，而且即时可译；而续长码中只有一部分是唯一可译的，并且不是即时可译的。唯一可译码定长非奇异码非续长码非奇异码信息理论与编码18第4章离散无记忆信源无失真编码4.2.2码树和Kraft不等式码树非续长码可用码树表示。码树从树根开始向上长出树枝，树枝代表码元，树枝与树枝的交点叫做节点。经过l根树枝才能到达的节点称为l阶节点。向上不长出树枝的节点称为终端节点或端点。

r进制码树各节点（包括树根）向上长出的树枝数不会超过r，若等于r则称为整树。信息理论与编码19第4章离散无记忆信源无失真编码下图中，(a)和(b)是整树，(c)为非整树。二进制码树：（a）W1

的码树；（b）W4

的码树；（c）W5

的码树一阶节点二阶节点三阶节点信息理论与编码20第4章离散无记忆信源无失真编码定理对于任一r进制非续长码，各码字的码长，，必须满足Kraft不等式：反过来，若上式成立，就一定能构造一个r进制非续长码。本定理是非续长码的存在性定理。不满足Kraft不等式的码肯定不是非续长码，而满足Kraft不等式的码也不一定是非续长码。信息理论与编码21第4章离散无记忆信源无失真编码定理对于任一r进制唯一可译码（UDC），各码字的码长，，必须满足Kraft不等式：反过来，若上式成立，就一定能构造一个r进制唯一可译码（UDC）。奇异码肯定不是唯一可译码；非续长码一定是唯一可译码。信息理论与编码22第4章离散无记忆信源无失真编码4.3定长编码定理和定长编码方法定长编码惟一可译条件定长无失真编码定理信息理论与编码23第4章离散无记忆信源无失真编码定长编码惟一可译条件

假设DMS为，发出的长符号序列或的单个符号总共有个，因此要找个r进制码字与之对应。对于定长编码，平均码长与各码字的码长相等。码长为的r进制定长非奇异码总共含个码字，可用的码字数不少于的符号数，即就可做到唯一译码。信息理论与编码24第4章离散无记忆信源无失真编码将上式整理一下得

式中，代表的一个符号所用去的码元数目，量纲为“码元/符号”；代表的最大r进制熵，量纲为“r进制单位/符号”。物理意义：对的长符号序列进行等长编码，若要求所编的码唯一可译，则的一个符号所需用去的码元数目以的最大r进制熵为下界，再小就不能唯一可译了。信息理论与编码25第4章离散无记忆信源无失真编码定长无失真编码定理

用r元符号表对离散无记忆信源的长符号序列进行定长编码，长符号序列对应的码长为，若对于任意小的正数，有不等式

就几乎能做到无失真编码，且随着序列长度的增大，译码差错率趋于0。反过来，若

就不可能做到无失真编码，且随着的增大，译码差错率趋于1。信息理论与编码26第4章离散无记忆信源无失真编码几点说明：（1）码长的界。用r元符号表对信源进行定长编码，是定长无失真编码单符号码长的下界。（2）定理是针对离散无记忆信源给出的，对更一般的信源也有类似结论。（3）定长编码的效率为信息理论与编码27第4章离散无记忆信源无失真编码例1

DMS为用码元表对的单个符号进行编码，即对的单个符号进行2进制编码。解用的两个码元对的七个符号进行编码，

码元/符号取l=3；码长为3的2进制码字有8个，取其中任意7个码字分别赋给7个信源符号即可，

信息理论与编码28第4章离散无记忆信源无失真编码如容易算出信源的熵为

bit/符号平均码长和编码效率分别为码元/符号显然，编码效率是不高的。信息理论与编码29第4章离散无记忆信源无失真编码若要提高编码效率，可对的符号序列进行编码，同时引入一定的失真。定长编码定理限定了定长编码码长的最小值，因此最佳的定长编码效率为

可以证明，差错率满足如下关系式中，为信源自信息量的方差信息理论与编码30第4章离散无记忆信源无失真编码对于任一正数，只要就可使信息理论与编码31第4章离散无记忆信源无失真编码例2对上例所给信源的符号序列进行2进制编码，要求编码效率，允许的差错率为。解已求出信源的熵，自信息量的方差为所以由此可见，要达到要求的编码效率，必须取很长的信源序列（），这在实际中是很难实现的。信息理论与编码32第4章离散无记忆信源无失真编码4.4变长编码定理无失真变长编码定理（香农第一定理）用r元符号表对离散无记忆信源U的N长符号序列进行变长编码，记N长符号序列对应的平均码长为，那么，要做到无失真编码，平均码长必须满足信息理论与编码33第4章离散无记忆信源无失真编码另一方面，一定存在唯一可译码，其平均码长满足

当信源序列长度趋于无穷时平均码长的极限：由此可得编码效率的极限为信息理论与编码34第4章离散无记忆信源无失真编码4.5变长编码方法最佳码对给定的信源，使平均码长达到最小的编码方法称为最佳编码，编出的码称为最佳码。本节介绍三种变长编码方法：霍夫曼编码、费诺编码以及香农编码。其中只有霍夫曼编码是真正意义下的最佳编码。信息理论与编码35第4章离散无记忆信源无失真编码本节主要内容4.5.1霍夫曼编码4.5.2费诺编码4.5.3香农编码信息理论与编码36第4章离散无记忆信源无失真编码4.5.1霍夫曼编码二进制霍夫曼编码编码效果分析r进制霍夫曼编码符号序列的霍夫曼编码信息理论与编码37第4章离散无记忆信源无失真编码二进制霍夫曼编码

二进制霍夫曼编码过程如下：（1）将信源符号按概率大小排序；（2）对概率最小的两个符号求其概率之和，同时给两符号分别赋予码元“0”和“1”；（3）将“概率之和”当作一个新符号的概率，与剩下符号的概率一起，形成一个缩减信源，再重复上述步骤，直到“概率之和”为1为止；（4）按上述步骤实际上构造了一个码树，从树根到端点经过的树技即为码字。

信息理论与编码38第4章离散无记忆信源无失真编码符号概率码字码长1101200130001400001500000160000006霍夫曼编码步骤示意1

1111

1

0000001.00信息理论与编码39第4章离散无记忆信源无失真编码采用霍夫曼编码方法重新进行变长编码，其平均码长和编码效率分别为码元/符号由此可见，平均码长缩短了，达到了编码定理所给的下界值，即等于信源的熵，因此编码效率达到最大，为100%。信息理论与编码40第4章离散无记忆信源无失真编码编码效果分析（1）有效的信源编码可取得较好的冗余压缩效果。原信源的冗余度为经过单符号无失真定长编码，新信源X的冗余度为经过符号序列有失真定长编码，新信源X的冗余度为信息理论与编码41第4章离散无记忆信源无失真编码经过单符号霍夫曼编码之后，新信源X的冗余度为一般来说，定长编码只有在引入失真且取很长的序列编码时，才会取得一定的冗余压缩效果，而变长编码在无失真的前提下，只须取较短的序列编码就可取得满意的冗余压缩效果。信息理论与编码42第4章离散无记忆信源无失真编码（2）有效的信源编码可使输出码元概率均匀化。设单符号无失真定长编码的码字为把编码器的输出看作一个新的信源，其取值符号表就是码元表X={0,1}，概率空间为现在求X的概率分布。信息理论与编码43第4章离散无记忆信源无失真编码设平均每个码字所含码元“0”和“1”的个数为分别为和，根据上面的等长码字可求得码元/符号码元/符号于是原信源7个符号的概率从到，差别很大，编码之后所得的新信源2个符号的概率分别为0.6和0.4，差别缩小，概率得到一定程度的均匀。信息理论与编码44第4章离散无记忆信源无失真编码再看霍夫曼编码，

码元/符号码元/符号于是此时，码元的概率分布完全均匀化了。信息理论与编码45第4章离散无记忆信源无失真编码霍夫曼编码过程中，由于码元分配的任意性，会造成码字不唯一。但平均码长是相同的，因而编码效率是相同的，看下例。例1对如下DMS进行2进制霍夫曼编码。解采用霍夫曼编码方法，会出现两种情况。信息理论与编码46第4章离散无记忆信源无失真编码符号概率码字码长0.35110.300120.2000130.10000140.040000150.00500000160.0050000006霍夫曼编码之一1

1111

1

0000001.000.010.050.150.350.65信息理论与编码47第4章离散无记忆信源无失真编码符号概率码字码长0.351120.301020.200120.1000130.04000140.0050000150.005000005霍夫曼编码之二1

1111

1

0000001.000.010.050.150.350.65信息理论与编码48第4章离散无记忆信源无失真编码分别求得平均码长为码元/符号和码元/符号两种情况下，码字不同，码长也不同，但平均码长是相同的，因此编码效率是相同的。信息理论与编码49第4章离散无记忆信源无失真编码两种码的其它性能还是有差别的。在相同的编码效率下，我们希望得到码长变化小的码，于是引入码长的方差：大，说明码长变化大。分别计算两种码的：因此后者的码较好，其码长变化相对较小。信息理论与编码50第4章离散无记忆信源无失真编码r进制霍夫曼编码每次求缩减信源时，改为求r个最小概率之和，即将r个概率最小的符号缩减为一个新符号，直到概率之和为1终止。为保证平均码长最小，希望缩减到最后刚好还剩下r个符号，为达到此目的，可给信源添加几个无用的符号，这些无用的符号概率为零，使得信源符号数q满足其中为信源缩减的次数。信息理论与编码51第4章离散无记忆信源无失真编码符号概率码字码长0.32210.22110.180220.160120.0800230.0400130.00三元霍夫曼编码21211

0001.0020.120.46例2信息理论与编码52第4章离散无记忆信源无失真编码平均码长和编码效率分别为

码元/符号信息理论与编码53第4章离散无记忆信源无失真编码符号序列的霍夫曼编码一般来说，对序列编码比对单个符号编码更为有效，这与编码定理的结论是一致的。例3对如下DMS进行2进制霍夫曼编码，分别对单个符号和二元符号序列进行编码。信息理论与编码54第4章离散无记忆信源无失真编码解

霍夫曼编码之一（单个符号情形）符号概率码字码长0.45110.350120.200020.551.000011信息理论与编码55第4章离散无记忆信源无失真编码可求出平均码长：码元/符号信源熵为

bit/符号编码效率为信息理论与编码56第4章离散无记忆信源无失真编码霍夫曼编码之二（2元符号序列情形）符号概率码字码长0.20251120.157501130.157500130.122500030.0910130.09010140.07010040.07100140.04100040.110.160.280.200.37150.59750.40251.000000000011111111信息理论与编码57第4章离散无记忆信源无失真编码对二元符号序列进行编码相当于对2次扩展信源的单个符号进行编码，得到二元符号序列对应的平均码长为码元/二元符号编码效率为因此，与单个符号编码相比，对二元符号序列编码的效率更高。信息理论与编码58第4章离散无记忆信源无失真编码4.5.2费诺编码费诺编码的步骤费诺编码的基本特点信息理论与编码59第4章离散无记忆信源无失真编码费诺编码的步骤（1）将信源符号按概率从大到小的排序；（2）将信源符号分成2组，使2组信源符号的概率之和近似相等，并给2组信源符号分别赋码元“0”和“1”；（3）接下来再把各小组的信源符号细分为2组并赋码元，方法与第一次分组相同；（4）如此一直进行下去，直到每一小组只含一个信源符号为止；（5）由此即可构造一个码树，所有终端节点上的码字组成费诺码。信息理论与编码60第4章离散无记忆信源无失真编码设DMS

为采用费诺编码方法，用码元表X={0,1}对U进行编码。信息理论与编码61第4章离散无记忆信源无失真编码符号概率码字码长0.200020.1901030.1801130.171020.1511030.10111040.0111114费诺编码步骤示意1

1111

1

000000信息理论与编码62第4章离散无记忆信源无失真编码可求出费诺编码的平均码长和编码效率码元/符号

bit/符号信息理论与编码63第4章离散无记忆信源无失真编码如对该信源进行霍夫曼编码，码元/符号

费诺编码的平均码长比霍夫曼编码略长，编码效率稍有下降。因此，费诺编码不是平均码长最短意义下的最佳编码，可将其看作准最佳编码。信息理论与编码64第4章离散无记忆信源无失真编码费诺编码的基本特点（1）费诺编码在构造码树时，是从树根开始到终端节点结束，这与霍夫曼编码相反；（2）由于赋码元时的任意性，因此费诺编码编出的码字也不唯一；（3）费诺编码虽属概率匹配范畴，但并未严格遵守匹配规则，因此平均码长一般不会最小。信息理论与编码65第4章离散无记忆信源无失真编码4.5.3香农编码香农编码二进制编码步骤（1）将信源符号按概率从大到小的排序；（2）按下式求i个信源符号对应的码长，并取整；（3）按下式求i个信源符号的累加概率；（4）将累加概率转换成二进制数；（5）取二进制数小数点后个二进制数字作为第i个信源符号的码字。信息理论与编码66第4章离散无记忆信源无失真编码例设信源有7个符号，其二进制香农编码过程如下。符号概率累加概率自信息量码长码字0.2002.3430000.190.202.4130010.180.392.4830110.170.572.5631000.150.742.7431010.100.893.34411100.010.996.6671111110表香农编码信息理论与编码67第4章离散无记忆信源无失真编码表中信源符号已按概率大小排序，设i=3，由于则码长满足取。为了决定码字，先计算累加概率：信息理论与编码68第4章离散无记忆信源无失真编码将转换成二进制数：取二进制数小数点后位二进制数作为码字，即为“011”。计算出平均码长和编码效率：码元/符号比较可知，霍夫曼编码效率最高，费诺编码效率次之，香农编码效率最低，甚至低于定长编码的效率。信息理论与编码69第4章离散无记忆信源无失真编码4.6几种实用的无失真信源编码4.6.1游程编码4.6.2算术编码4.6.3基于字典的编码信息理论与编码70第4章离散无记忆信源无失真编码4.6.1游程编码游程编码基本原理MH码MH码编码规则MH码与霍夫曼码存在的差异信息理论与编码71第4章离散无记忆信源无失真编码游程编码基本原理

游程编码是霍夫曼编码的一种改进和应用，主要用于黑、白二值文件的传真。以文本文件的传真为例，白纸黑字的二值文件采用二元码进行编码，即表示背景（白色）时像素为码元“0”，表示内容（黑字）时像素为码元“1”。参照国际标准：一张A4幅面的二值文件共可分1188行，每行有1728个像素，则整幅总共有2.05M个像素。分析各类传真文件可知:任意一个扫描行的像素序列均是由若干个连“0”像素序列及若干连“1”像素序列组合而成。对大量出现的连“0”或连“1”（黑或白）像素序列在传输时,可通过像素类别（黑、白像素）加重复次数的方式来加以表示，即称为游程编码（RLC）。而重复出现的同类像素的长度则称为游程长度。信息理论与编码72第4章离散无记忆信源无失真编码信源的符号中重复出现的连“0”或连“1”像素序列经游程编码表示后，可归一化为统一的编码单元。其单元结构如下：其中，符号码表示当前的像素类别是“0”（白底）或“1”（黑字）；标识码是一种有别于符号码的区分符号（如#符号）。例如，若信源的字符序列为其游程编码的格式表达为:字符数量由38个减少为13个。符号码标识码游程长度信息理论与编码73第4章离散无记忆信源无失真编码MH码

MH码是国际电话电报咨询委员会提出的文件、传真类一维数据压缩编码的国际标准。

MH码在编码中对游程长度进行分割，并相应将长游程码（游程长度>64）分割为结尾码（终止码）和组合码（形成码）两部分，如下页表所示。信息理论与编码74第4章离散无记忆信源无失真编码RL长度白游程码字黑游程码字RL长度白游程码字黑游程码字RL长度白游程码字黑游程码字0001101010000110111220000011000001101114300101100000011011011100011101023000010000000101000440010110100000101010020111112401010000000001011145000001000000010101013100010250101011000000110004600000101000001010110410110112600100110000110010104700001010000001010111511000011270100100000011001011480000101100000110010061110001028001100000001100110049010100100000011001017111100011290000001000001100110150010100110000010100108100110010130000000110000011010005101010100000001010011910100000100310001101000000110100152010101010000001001001000111000010032000110110000011010105300100100000000110111110100000001013300010010000001101011540010010100000011100012001000000011134000100110000110100105501011000000000100111130000110000010035000101000000110100115601011001000000101000141101000000011136000101010000110101005701011010000001011000151101010000110003700010110000011010101580101101100000101100116101010000001011138000101110000110101105901001010000000101011171010110000011000390010100000001101011160010010110000001011001801001110000001000400010100100000110110061001100100000010110101900011000000110011141001010100000011011016200110011000001100110200001000000011010004200101011000011011010630011010000000110011121001011100001101100表MH码表(一)结尾码信息理论与编码75第4章离散无记忆信源无失真编码RL长度白游程码字黑游程码字RL长度白游程码字黑游程码字64110110000001111960011010100000000111001112810010000011001001024011010101000000111010019201011100001100100110880110101100000001110101256011011100000101101111520110101110000001110110320001101100000001100111216011011000000000111011138400110111000000110100128001101100100000010100104480110010000000011010113440110110100000001010011512011001010000001101100140011011011000000101010057601101000000000110110114720100110000000001010101640011001110000001001010153601001100100000010110107040110011000000001001011160001001101000000010110117680110011010000001001100166401100000000011001008320110100100000001001101172801001101100000011001018960110100110000001110010EOL000000000001000000000001表MH码表（二）组合基干码信息理论与编码76第4章离散无记忆信源无失真编码而对于加宽的纸型规定了一套加宽的组合码，如下表所示。游程长度组合基干码码字游程长度组合基干码码字1792000000010002240000000010110185600000001100230400000001011119200000000110123680000000111001984000000010010243200000001110120480000000100112496000000011110211200000001010025600000000111112176000000010101

MH码表（三）供加大纸宽用的组合基干码（1792～2560，黑、白相同）信息理论与编码77第4章离散无记忆信源无失真编码MH编码规则（1）游程长度在0~63之间时，码字直接由相应的终止码表示；（2）游程长度在64~1728之间时，码字由一个组合码加上一个终端码构成；（3）每行必须以白游程开始，以一个同步码EOL结束，且每页文件也必须以同步码EOL开始（用以清洗系统，防止误差扩散）；（4）每行游程总和必须为1728个像素，否则该行出错；（5）为达成同步操作，每行编码的传输时间最短为20mS,最长为5s；不足20ms的行,需在EOL码之前填入足够的“0”码元；（6）连续6个EOL表示文件页传输的结束。信息理论与编码78第4章离散无记忆信源无失真编码例若传真文件某行的扫描像素序列如表所示白游程22，黑游程6，白游程53，黑游程22均可查表直接获得编码。黑游程66和白游程1559则需采用组合码与终端码进行合成编码。其中，黑游程66的编码由长度为64的黑游程组合码与长度为2的黑游程终端码共同构成，码字为000000111111。白游程1559的编码由长度为1536的白游程组合码与长度为23的白游程终端码组成，码字为0100110010000100。白游程黑游程白游程黑游程白游程黑游程

2265366155922EOL00000110010001001000000001111101001100100001000000011000000000001信息理论与编码79第4章离散无记忆信源无失真编码MH码与霍夫曼码存在的差异（1）MH码的编码表是由各类文件的平均统计特性指标得到的，并且固定不变，因而多数情况下，MH码并非紧制码（最佳码）。（2）游程的码字由形成码和中止码组成，可使码字大大缩短。信息理论与编码80第4章离散无记忆信源无失真编码4.6.2算术编码编码过程

将各信源符号序列依累积概率分布函数的大小映射到[0,1)区间，将[0,1)区间分成许多互不重叠的小区间。此时每个符号序列均有一个小区间与之对应，因而可在小区间内取点来代表该符号序列。为达到与信源符号序列在概率上的匹配，选取编码的码长与信源序列的概率成反比，即取码长l为其中:表示信源符号序列的概率，符号表示取大于或等于该值的最小整数。信息理论与编码81第4章离散无记忆信源无失真编码例设一信源符号集为，若各信源符号相互统计独立,则信源符号序列的概率为，现对信源符号序列进行算术编码。定义信源符号的累积概率分布函数为信息理论与编码82第4章离散无记忆信源无失真编码现输入信源符号序列，则即:信源符号集的累积概率分布函数将区间分割为与信源序列相对应的四个大区间。序列首个信源符号确定本序列的相应区间，后续信源符号则是对选定区间的再分割。信息理论与编码83第4章离散无记忆信源无失真编码计算分割过程如下：（1）信源符号输入，序列对应区间为区间，且，。（2）符号输入，确定相应区间为区间。序列的累积概率分布函数值序列的概率序列相应区间长度信息理论与编码84第4章离散无记忆信源无失真编码（3）符号输入，确定相应区间为区间。序列的累积概率分布函数序列的概率序列相应区间长度（4）经符号输入引起再一次分割，得到全序列的累积概率分布函数及其对应的区间，且此时序列累积概率分布函数

序列的概率序列相应区间长度信息理论与编码85第4章离散无记忆信源无失真编码A(u1)=p(u1)A(u2)=p(u2)A(u3)=p(u3)F(u1)F(u2)F(u3)F(u4)A(u4)=p(u4)1F(u1u1)F(u1u2)F(u1u3)F(u1u4)A(u1u2)=A(u1)p(u1)A(u1)p(u2)A(u1)p(u3)A(u1)p(u4)A(u1u2)p(u3)A(u1u1)p(u4)F(u1u2u2)F(u1u2u3)F(u1u2u4)A(u1u2)p(u1)A(u1u2)p(u2)F(u1u2u1)F(u1u2u4u4)A(u1u2u4)p(u3)A(u1u2u4)p(u4)F(u1u2u4u2)F(u1u2u4u3)A(u1u2u4)p(u1)A(u1u2u4)p(u2)F(u1u2u4u1)算术编码过程图信息理论与编码86第4章离散无记忆信源无失真编码将结论推广到任意序列，则可得通用的递推计算公式为

采用递推公式进行映射和计