信息论与编码(第三章)-160329-讲课教材

*1信息论与编码

曹雪虹，张宗橙编

北京邮电大学出版社

北京工商大学计算机与信息工程学院廉小亲*北京工商大学计算机与信息工程学院信息论与编码2第3章无失真信源编码3.1编码的定义3.2定长编码定理3.3变长编码定理3.4最佳编码

3.4.1香农编码方法

3.4.2费诺编码方法

3.4.3哈夫曼编码方法习题*北京工商大学计算机与信息工程学院信息论与编码3引言

编码信源编码信道编码无失真信源编码限失真信源编码主要用于连续信源或模拟信号，如语音、图像等适用于离散信源或数字信号，如文件传真等*北京工商大学计算机与信息工程学院信息论与编码43.1编码的定义信道信宿信源图1简单的通信系统模型X∈{x1,x2}二元信道（可传输的符号为0,1）信源编码信源解码*北京工商大学计算机与信息工程学院信息论与编码53.1编码的定义编码：设信源X输出的符号集｛x1,x2,x3,x4｝，将信源发出的符号xi转换成0，1符号组成的码符号序列(码字)。问题提出：如何用0,1符号组成的码符号序列来表示xi？信道信源解码信宿信源图2复杂的通信系统模型X∈{00,01,10,11}信源编码二元信道（可传输的符号为0,1）X∈{x1,x2,x3,x4}*北京工商大学计算机与信息工程学院信息论与编码63.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同码字*北京工商大学计算机与信息工程学院信息论与编码73.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同码字*北京工商大学计算机与信息工程学院信息论与编码83.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同码字奇异码1、引出奇异码和非奇异码的概念。*北京工商大学计算机与信息工程学院信息论与编码93.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同码字1、引出奇异码和非奇异码的概念。非奇异码*北京工商大学计算机与信息工程学院信息论与编码103.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同码字非奇异码1、引出奇异码和非奇异码的概念。*北京工商大学计算机与信息工程学院信息论与编码113.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同码字非奇异码1、引出奇异码和非奇异码、唯一可译码和非唯一可译码的概念。2、唯一可译码必须满足什么条件？*北京工商大学计算机与信息工程学院信息论与编码123.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同码字非奇异码，非唯一可译码1、引出奇异码和非奇异码、唯一可译码和非唯一可译码的概念。2、唯一可译码必须满足什么条件？*北京工商大学计算机与信息工程学院信息论与编码133.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同码字1、引出奇异码和非奇异码、唯一可译码和非唯一可译码的概念。2、唯一可译码必须满足什么条件？非奇异码，唯一可译码*北京工商大学计算机与信息工程学院信息论与编码143.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同码字1、引出奇异码和非奇异码、唯一可译码和非唯一可译码的概念。2、唯一可译码必须满足什么条件？非奇异码，唯一可译码、非即时码*北京工商大学计算机与信息工程学院信息论与编码153.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同码字1、引出奇异码和非奇异码、唯一可译码和非唯一可译码的概念。2、唯一可译码必须满足什么条件？非奇异码唯一可译码即时码*北京工商大学计算机与信息工程学院信息论与编码163.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同码字1、引出奇异码和非奇异码、唯一可译码和非唯一可译码、非即时码和即时码及延长码的概念。2、唯一可译码必须满足什么条件？*北京工商大学计算机与信息工程学院信息论与编码173.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同码字1、引出奇异码和非奇异码、唯一可译码和非唯一可译码、非即时码和即时码及延长码的概念。2、唯一可译码必须满足什么条件？非奇异码唯一可译码即时码*北京工商大学计算机与信息工程学院信息论与编码183.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同码字1、引出奇异码和非奇异码、唯一可译码和非唯一可译码、非即时码和即时码及延长码的概念。

2、唯一可译码必须满足什么条件？*北京工商大学计算机与信息工程学院信息论与编码193.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同码字1、引出奇异码和非奇异码、唯一可译码和非唯一可译码、非即时码和即时码及延长码、定长码和可变长度码的概念。

2、唯一可译码必须满足什么条件？*北京工商大学计算机与信息工程学院信息论与编码203.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同码字1、引出奇异码和非奇异码、唯一可译码和非唯一可译码、非即时码和即时码及延长码、定长码和可变长度码的概念。

2、唯一可译码必须满足什么条件？3、引入平均码长的概念。*北京工商大学计算机与信息工程学院信息论与编码213.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x11/4001100x21/41110100101x31/4000010000110x41/411011000000111表3-1不同码字3、引入平均码长的概念。平均码长=2平均码长=2.5*北京工商大学计算机与信息工程学院信息论与编码223.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x18/16001100x24/161110100101x33/16000010000110x41/1611011000000111表3-1不同码字3、引入平均码长的概念。平均码长=2平均码长=29/16*北京工商大学计算机与信息工程学院信息论与编码233.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3码4码5x11/16001100x23/161110100101x34/16000010000110x48/1611011000000111表3-1不同码字3、引入平均码长的概念。平均码长=2平均码长=51/16*北京工商大学计算机与信息工程学院信息论与编码243.1编码的定义信源符号xi符号出现的概率p(xi)码1码2码3-1码4-1码5x11/16001000000100x23/16111010000101x34/160000100110x48/1611011111表3-1不同码字3、引入平均码长的概念说明：符号概率不等时变长编码的必要性。

平均码长=2平均码长=29/16*北京工商大学计算机与信息工程学院信息论与编码253.1编码的定义总结：（1）编码的定义，引出无失真信源编码的定义（3）唯一可译码必须满足的条件（2）编码的分类码奇异码非奇异码非唯一可译码唯一可译码非即时码即时码1）单个符号对应不同的码字（非奇异码）2）符号序列对应的码元序列在信源译码时必须能唯一的分割成所发的符号序列。（4）符号概率不等时变长编码的必要性。

*北京工商大学计算机与信息工程学院信息论与编码263.1编码的定义定长码和可变长度码:固定长度的码，码中所有码字的长度都相同，是定长码。奇异码和非奇异码：若信源符号和码字是一一对应的，则该码为非奇异码。反之为奇异码。唯一可译码：任意有限长的码元序列，只能被唯一地分割成一个个的码字，便称为唯一可译码。非即时码和即时码：如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码开始接收后才能判断是否可以译码，这样的码叫做非即时码。编码总结：*北京工商大学计算机与信息工程学院信息论与编码273.1编码的定义码树图及时码构造可通过码树来构造：00001110*北京工商大学计算机与信息工程学院信息论与编码283.1编码的定义用树的概念可导出唯一可译码存在的充分和必要条件，即各码字的长度Ki应符合克劳夫特不等式：式中，m是进制数，n是信源符号数，Ki是各码字的长度。*北京工商大学计算机与信息工程学院信息论与编码293.1编码的定义例3.1.1设二进制码树中X∈｛x1，x2，x3,x4｝，K1=1，K2=2，K3=2，K4=3，应用上述判断定理，可得因此，不存在满足这种Ki的唯一可译码,用树码进行检查如右图。码字分别为{0，10，11，110}树码0001111010011*北京工商大学计算机与信息工程学院信息论与编码303.1编码的定义例3.1.1设二进制码树中X∈｛x1，x2，x3,x4｝，K1=1，K2=2，K3=3，K4=3，应用上述判断定理，可得因此，存在满足这种Ki的唯一可译码,用树码进行检查如下图。a树码000111101001111码字分别为{0，10，110，111}码字分别为{0，10，010，111}b树码0001101001111110*北京工商大学计算机与信息工程学院信息论与编码31本节内容回顾作业：3－1

编码的含义、编码的种类。重点强调以下几个问题：

1、奇异码和非奇异码；定长码和可变长度码；唯一可译码和唯一可译码；非即时码和即时码及延长码的概念。

2、唯一可译码必须满足什么条件？

3、符号概率不等说明可变长度码编码的必要性。*北京工商大学计算机与信息工程学院信息论与编码323.2定长编码定理定长编码定理：

由L个符号组成的、每个符号的熵为的无记忆平稳信源符号序列，可用KL个符号（每个符号有m种可能值）进行定长编码。对任意ε＞0，δ＞0，只要

则当L足够大时，必可使译码差错小于δ；反之，当

时，译码差错一定是有限值，而当L足够大时，译码几乎必定出错定理证明略。举例:信源序列X=X1X2（每个Xi可取a1-a4）分别用3、4、5位二元编码（可传输的符号为0,1）

，说明定理含义。*北京工商大学计算机与信息工程学院信息论与编码333.2定长编码定理只要码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真.能达到差错率要求,源序列长度L需满足（由切比雪夫不等式得到的）

定义:编码效率最佳编码效率

信源序列的自信息方差*北京工商大学计算机与信息工程学院信息论与编码343.2定长编码定理例3-2-1设离散无记忆信源概率空间为

对该信源进行定长二元编码，要求编码效率η=90%，并要求译码错误概率δ≤10-6进行能达到差错率要求,求信源序列长度L应满足的条件，才能满足上述要求。

解（1）若对L=1的信源X1进行编码，码长为3。求η，δ。信源熵：

比特/符号平均码长：

码元/信源符号译码错误概率δ=0.效率：*北京工商大学计算机与信息工程学院信息论与编码353.2定长编码定理例3-2-1

解（2）现在要求η

，δ

需要对信源序列进行定长二元编码。信源序列的自信息方差：*北京工商大学计算机与信息工程学院信息论与编码363.2定长编码定理例3-2-1

解（2）现在要求η

，δ

需要对信源序列进行定长二元编码。信源序列的编码效率：无记忆信源有HL(X)=H(X)=2.55说明：当L有限时，高传输效率的定长编码往往要引入一定的失真和错误。从而引出变长编码。*北京工商大学计算机与信息工程学院信息论与编码373.3变长编码定理单个符号变长编码定理：

若一离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式

离散平稳无记忆序列变长编码定理（香农第一定理）:

对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式

*北京工商大学计算机与信息工程学院信息论与编码383.3变长编码定理设用m进制码元作变长编码，序列长度为L个信源符号，序列平均码字长度满足下列不等式

已知平均输出信息率为

编码效率的下界：码的剩余度:*北京工商大学计算机与信息工程学院信息论与编码393.3变长编码定理例3.3.1设离散无记忆信源的概率空间如下,求编码效率?

解:其信源熵为

(1)定长编码

若用二元定长编码(0，1)来构造一个即时码：x1→0,x2→1。这时平均码长

编码效率为输出的信息率为

R=0.811比特/二元码符号*北京工商大学计算机与信息工程学院信息论与编码403.3变长编码定理例3.3.1设离散无记忆信源的概率空间如下,求编码效率?

解:其信源熵为

(2)变长编码假定信源序列的长度为L=2,其即时码如下表。

序列序列概率即时码

x1x1

9/16

x1x2

x2x1

x2x2

1/16

3/16

3/16*北京工商大学计算机与信息工程学院信息论与编码413.3变长编码定理例3.3.1设离散无记忆信源的概率空间如下,求编码效率?

解:其信源熵为

(2)变长编码假定信源序列的长度为L=2,其即时码如下表。

序列序列概率即时码

x1x1

9/160

x1x2

x2x1

x2x2

1/16

3/16

3/16

111

110

10*北京工商大学计算机与信息工程学院信息论与编码423.3变长编码定理例3.3.1设离散无记忆信源的概率空间如下,求编码效率?

解:(2)变长编码

这个码的码字平均长度

编码效率为

输出的信息率为R=0.961比特/二元码符号*北京工商大学计算机与信息工程学院信息论与编码433.3变长编码定理例3.3.1设离散无记忆信源的概率空间如下,求编码效率?

解:(2)变长编码

将信源序列的长度增加，L＝3或L=4，对这些信源序列X进行编码，并求出其编码效率为

信息传输率分别为：

R3＝0.985比特／二元码符号

R4＝0.991比特／二元码符号*北京工商大学计算机与信息工程学院信息论与编码443.3变长编码定理例3.3.1设离散无记忆信源的概率空间如下,求编码效率?

解:讨论

如果对这一信源采用定长二元码编码，要求编码效率达到96％时，允许译码错误概率

。则自信息的方差:

所需要的信源序列长度*北京工商大学计算机与信息工程学院信息论与编码453.4最佳编码(1)最佳码定义是什么?

凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合都可称为最佳码。

(2)最佳编码思想是什么?

将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。

(3)最佳码的编码主要方法有哪些?

香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码等。

*北京工商大学计算机与信息工程学院信息论与编码463.4最佳编码3.4.1香农编码方法香农第一定理指出，选择每个码字的长度Ki满足下式I(xi)≤Ki＜I(xi)+1，这种编码方法称为香农编码。编码方法如下：(1)

将信源消息符号概率按大小依次排列

(2)

确定满足下列不等式的整数码长Ki：(3)

为了编成唯一可译码，计算第i个消息的累加概率(4)

将累加概率Pi变换成二进制数。(5)

取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。*北京工商大学计算机与信息工程学院信息论与编码473.4最佳编码3.4.1香农编码方法例3-4-1设信源共7个符号消息，其概率和累加概率如表3-4-1所示。*北京工商大学计算机与信息工程学院信息论与编码48xiP(xi)Pi-logp2(xi)Ki码字x1x2x3x4x5x6x70.200.190.180.170.150.100.0100.20.390.570.740.890.992.342.412.482.562.743.346.66333334700000101110010111101111110*北京工商大学计算机与信息工程学院信息论与编码493.4.2费诺编码方法编码过程如下：

(1)将信源消息符号按其出现的概率大小依次排列：

p(x1)≥p(x2)≥…≥p(xn)。(2)将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。(3)将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。(4)如此重复，直至每个组只剩下一个信源符号为止。(5)信源符号所对应的码字即为费诺码。*北京工商大学计算机与信息工程学院信息论与编码503.4.3哈夫曼编码方法编码过程如下：

(1)将n个信源消息符号按其出现的概率大小依次排列，

p(x1)≥p(x2)≥…≥p(xn)

(2)取两个概率最小的字母分别配以0和1两码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。(3)对重排后的两个概率最小符号重复步骤(2)的过程。

(4)不断继续上述过程，直到最后两个符号配以0和1为止。

(5)从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。*北京工商大学计算机与信息工程学院信息论与编码513.4.3哈夫曼编码方法该哈夫曼码的平均码长为：信息传输速率：

10

11

000

0111*北京工商大学计算机与信息工程学院信息论与编码523.4.3哈夫曼编码方法哈夫曼编码方法得到的码并非是唯一的。造成非唯一的原因如下：

每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。*北京工商大学计算机与信息工程学院信息论与编码533.4.3哈夫曼编码方法例设有离散无记忆信源哈夫曼编码方法1*北京工商大学计算机与信息工程学院信息论与编码543.4.3哈夫曼编码方法例设有离散无记忆信源哈夫曼编码方法2*北京工商大学计算机与信息工程学院信息论与编码553.4.3哈夫曼编码方法哈夫曼码的平均码长相等,编码效率也相等但是两种码的质量不完全相同，可用码方差来表示：可见，第二种哈夫曼编码方法得到的码方差要比第一种哈夫曼编码方法得到的码方差小许多。故第二种哈夫曼码的质量要好。*北京工商大学计算机与信息工程学院信息论与编码563.4.3哈夫曼编码方法哈夫曼码是用概率匹配方法进行信源编码。它有两个明显特点：一是哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；二是缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。作业：3-2、3-11[1、2、3、4、6、7]3-12(1)（注意：3-12中的1文字描述内容、3-11的2-4后加上相应码字）*北京工商大学计算机与信息工程学院信息论与编码57第4章限失真信源编码4.1平均失真和信息率失真函数

4.1.1失真函数

4.1.2平均失真

4.1.3信息率失真函数

4.1.4信息率失真函数的性质4.2离散信源和连续信源的计算4.3限失真信源编码定理4.4常用信源编码方法简介

4.4.1游程编码

4.4.2算术编码

4.4.3矢量量化

4.4.4预测编码

4.4.5变换编码习题*北京工商大学计算机与信息工程学院信息论与编码584.1平均失真和信息率失真函数4.1.1失真函数失真函数定义:失真矩阵*北京工商大学计算机与信息工程学院信息论与编码594.1.1失真函数

例设信源符号X∈｛0，1｝,编码器输出符号Y∈｛0,1,2｝,规定失真函数为d(0,0)＝d(1,1)＝0;d(0,1)＝d(1,0)=1;d(0,2)＝d(1,2)＝0.5,求失真矩阵。解:由式得失真矩阵*北京工商大学计算机与信息工程学院信息论与编码604.1.1失真函数常用失真函数均方失真：绝对失真：相对失真：

误码失真：失真函数的定义的推广*北京工商大学计算机与信息工程学院信息论与编码614.1.2平均失真平均失真对于连续随机变量的平均失真*北京工商大学计算机与信息工程学院信息论与编码624.1.3信息率失真函数D允许信道（D允许的试验信道）对于离散无记忆信道信息率失真函数R(D)对于离散无记忆信源等效试验信道*北京工商大学计算机与信息工程学院信息论与编码634.1.3信息率失真函数例设信源的符号表为A=｛a1,a2,…,a2n｝,概率分布为p(ai)＝1/2n，i＝1，2，…，2n，失真函数规定为由信源概率分布可求出信源熵为设想采用下面的编码方案：平均失真D为等效试验信道*北京工商大学计算机与信息工程学院信息论与编码644.1.3信息率失真函数由该信道模型知，它是一个确定信道由互信息公式可得

I(X;Y)=H(Y)-H(Y/X)=H(Y)信道输出概率分布为所以概率分布为则输出熵H(Y)为*北京工商大学计算机与信息工程学院信息论与编码654.1.4信息率失真函数的性质1.R(D)函数的定义域

R(D)的定义域为D∈［0，Dmax］2.R(D)函数的下凸性和连续性3.R(D)函数的单调递减性例:R(D)在定义域内是下凸的,连续的。R(D)的单调递减性可以作如下理解：容许的失真度越大，所要求的信息率越小。*北京工商大学计算机与信息工程学院信息论与编码664.1.4信息率失真函数的性质得出如下结论：R(D)是非负的实数，即R(D)≥0。其定义域为0～Dmax，其值为0～H(X)。当D＞Dmax时,R(D)≡0。R(D)是关于D的下凸函数，因而也是关于D的连续函数。R(D)是关于D的严格递减函数。*北京工商大学计算机与信息工程学院信息论与编码674.2离散信源和连续信源的计算某些特殊情况下R(D)的表示式为：率失真函数*北京工商大学计算机与信息工程学院信息论与编码684.2离散信源和连续信源的计算例4.2.1设输入输出符号表为X=Y=｛0，1｝，输入概率分布p(x)=｛p，1-p｝，0＜p≤1/2，失真矩阵为

求信息率失真函数R(D).

解:简记

(1)按下式解方程

解得*北京工商大学计算机与信息工程学院信息论与编码694.2离散信源和连续信源的计算(2)按下式解方程解得(3)得转移概率分布*北京工商大学计算机与信息工程学院信息论与编码704.2离散信源和连续信源的计算(4)求s(s=logα)*北京工商大学计算机与信息工程学院信息论与编码714.2离散信源和连续信源的计算(5)计算R(D)，将上面各式代入，则有(D)=H(p)-H(D)，p为参数*北京工商大学计算机与信息工程学院信息论与编码724.3限失真信源编码定理限失真信源编码定理：设离散无记忆信源X的信息率失真函数R(D)，则当信息率R＞R(D)，只要信源序列长度L足够长，一定存在一种编码方法，其译码失真小于或等于D+ε，ε为任意小的正数；反之，若R＜R(D)，则无论采用什么样的编码方法，其译码失真必大于D。如果是二元信源，对于任意小的ε＞0，每一个信源符号的平均码长满足如下公式在失真限度内使信息率任意接近R(D)的编码方法存在。*北京工商大学计算机与信息工程学院信息论与编码734.4常用信源编码方法简介4.4.1游程编码游程长度在二元序列中，只有两种符号，即“0”和“1”，这些符号可连续出现，连“0”这一段称为“0”游程，连“1”这一段称为“1”游程。它们的长度分别称为游程长度L(0)和L(1).

对于多元序列也存在相应的游程序列。例如m元序列中，可有m种游程。连着出现符号ar的游程，其长度L(r)就是“r”游程长度。设有多元信源序列(x1，x2，…，xm1，y，y，…，y，xm1+1，xm1+2，…xm2，y，y，…其中x是含有信息的代码，取值于m元符号集A，可称为信息位；y是冗余位，它们可为全零，即使未曾传送在收端也能恢复。这样的序列可用下列两个序列来代替：

111，…，100，…，000111，…，111000和

x1，x2，…，xm1，xm1+1，xm1+2，…xm2，…

前一个序列中，用“1”表示信息位，用“0”表示冗余位；后一个序列是取消冗余位后留下的所有信息位。*北京工商大学计算机与信息工程学院信息论与编码744.4.2算术编码算术编码的基本思路从全序列出发，将各信源序列的概率映射到［0，1］区间上，使每个序列对应这区间内的一点，也就是一个二进制的小数。积累概率则例如有一序列S=011，这种三个二元符号的序列可按自然二进数排列，000，001，010，……，则S的积累概率为

P(S)=p(000)+p(001)+p(010)如果S后面接一个“0”，积累概率就成为

P(S0)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101)=p(000)+p(001)+p(010)=P(S)

信源的符号概率和积累概率*北京工商大学计算机与信息工程学院信息论与编码754.4.2算术编码如果S后面接一个“1”，则其积累概率是

P(S1)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101)+p(0110)=P(S)+p(0110)=P(S)+p(S)p0上面两式可统一写作一般的递推公式序列的概率的公式

*北京工商大学计算机与信息工程学院信息论与编码764.4.2算术编码实用中，采用积累概率P(S)表示码字C(S)，符号概率p(S)表示状态区间A(S)，则有实际编码过程:

先置两个存储器C和A，起始时可令其中代表空集。每输入一个信源符号，存储器C和A就按照上式更新一次，直至程序结束，就可将存储器C的内容作为码字输出。*北京工商大学计算机与信息工程学院信息论与编码774.4.2算术编码例4.4.1有简单的四个符号a，b，c，d构成序列S=abda，各符号及其对应概率如表算术编解码过程如下:设起始状态为空序列φ，则A(φ)=1，C(φ)=0。表4-4-1各符号及其对元概率符号符号符号概率pi符号概率pi符号累积概率Pj符号累积概率Pjabcd0.100(1/2)0.010(1/4)0.001(1/8)0.001(1/8)0.0000.1000.1100.111*北京工商大学计算机与信息工程学院信息论与编码784.4.2算术编码算术码编码过程*北京工商大学计算机与信息工程学院信息论与编码794.4.2算术编码据递推公式的相反过程译出符号。具体译码顺序是后编的先译，故称为LIFO算术码，步骤如下：C(abda)=0.010111＜01∈［0,0.1)第一个符号为a；放大至［0,1)