信息论与编码第5章.doc

第五章 信源编码
第五章 信源编码（第十讲）
（2课时）
主要内容：（1）编码的定义（2）无失真信源编码
重点：定长编码定理、变长编码定理、最佳变长编码。
难点：定长编码定理、哈夫曼编码方法。
作业：5。2，5。4，5。6；
说明：本堂课推导内容较多，枯燥平淡，不易激发学生兴趣，要注意多讨论用途。另外，注意，解题方法。多加一些内容丰富知识和理解。

通信的实质是信息的传输。而高速度、高质量地传送信息是信息传输的基本问题。将信源信息通过信道传送给信宿，怎样才能做到尽可能不失真而又快速呢？这就需要解决两个问题：第一，在不失真或允许一定失真的条件下，如何用尽可能少的符号来传送信源信息；第二，在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大。为了解决这两个问题，就要引入信源编码和信道编码。
一般来说，提高抗干扰能力（降低失真或错误概率）往往是以降低信息传输率为代价的；反之，要提高信息传输率常常又会使抗干扰能力减弱。二者是有矛盾的。然而在信息论的编码定理中，已从理论上证明，至少存在某种最佳的编码或信息处理方法，能够解决上述矛盾，做到既可靠又有效地传输信息。这些结论对各种通信系统的设计和估价具有重大的理论指导意义。
§3.1 编码的定义
编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。
讨论无失真信源编码，可以不考虑干扰问题，所以它的数学描述比较简单。图3.1是一个信源编码器，它的输入是信源符号，同时存在另一符号，一般来说，元素xj是适合信道传输的，称为码符号（或者码元）。编码器的功能就是将信源符号集中的符号si（或者长为N的信源符号序列）变换成由xj(j=1,2,3,…r)组成的长度为li的一一对应的序列。
输出的码符号序列称为码字，长度li称为码字长度或简称码长。可见，编码就是从信源符号到码符号的一种映射。若要实现无失真编码，则这种映射必须是一一对应的，并且是可逆的。
码符号的分类：
下图是一个码分类图

下面，我们给出这些码的定义。
1. 二元码
若码符号集为X={0;1}，所有码字都是一些二元序列，则称为二元码。二元码是数字通信和计算机系统中最常用的一种码。
2. 等长码：
若一组码中所有码字的码长都相同，即li=l(i=1,2,…q)，则称为等长码。
3. 变长码：
若一组码组中所有码字的码长各不相同，则称为变长码。
4. 非奇异码：
若一组码中所有码字都不相同，则称为非奇异码。
5. 奇异码：
若一组码中有相同的码字，则称为奇异码。
6. 唯一可译码：
若码的任意一串有限长的码符号序列只能唯一地被译成所对应的信源符号序列，则此码称为唯一可译码，否则就称为非唯一可译码。
7. 非即时码和即时码：
如果接收端收到一个完整的码字后，不能立即译码，还要等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。
如果收到一个完整的码字以后，就可以立即译码，则叫做即时码。即时码要求任何一个码字都不是其他码字的前缀部分，也叫做异前缀码。
n 码树：
即时码的一种简单构造方法是树图法。对给定码字的全体集合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。可以看出，按树图法构成的码一定满足即时码的定义（一一对应，非前缀码）。
从码树上可以得知，当第i阶的节点作为终端节点，且分配码字，则码字的码长为i。
任一即时码都可以用树图法来表示。当码字长度给定后，用树图法安排的即时码不是唯一的。如图3.2中，如果把左树枝安排为1，右树枝安排为0，则得到不同的结果。
对一个给定的码，画出其对应的树，如果有中间节点安排了码字，则该码一定不是即时码。
每个节点上都有r个分支的树称为满树，否则为非满树。
即时码的码树图还可以用来译码。当收到一串码符号序列后，首先从根节点出发，根据接收到的第一个码符号来选择应走的第一条路径，再根据收到的第二个符号来选择应走的第二条路径，直到走到终端节点为止，就可以根据终端节点，立即判断出所接收的码字。然后从树根继续下一个码字的判断。这样，就可以将接收到的一串码符号序列译成对应的信源符号序列。
n 克拉夫特（Kraft）不等式
定理3.1 对于码符号为X={x1,x2,…xr}的任意唯一可译码，其码字为W1,W2,…Wq，所对应的码长为l1,l2…lq，则必定满足克拉夫特不等式

反之，若码长满足上面的不等式，则一定存在具有这样码长的即时码。
注意：克拉夫特不等式只是说明唯一可译码是否存在，并不能作为唯一可译码的判据（可以排除，不能肯定）。如{0，10，010，111}满足克拉夫特不等式，但却不是唯一可译码。
例题：设二进制码树中X={x1,x2,x3,x4}，对应的l1=1,l2=2,l3=2,l4=3，由上述定理，可得

因此不存在满足这种码长的唯一可译码。可以用树码进行检查。
n 唯一可译码的判断法（变长）：
将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，则可判断此码C为唯一可译码。
集合F的构成方法：
首先，观察码C中最短的码字是否是其它码字的前缀，若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又有可能是某些码字的前缀，再将这些尾随后缀产生的新的尾随后缀列出，
然后再观察这些新的尾随后缀是否是某些码字的前缀，再将产生的尾随后缀列出，依此下去，直到没有一个尾随后缀是码字的前缀为止。这样，首先获得了由最短的码字能引起的所有尾随后缀，接着，按照上述步骤将次短码字、…等等所有码字可能产生的尾随后缀全部列出。由此得到由码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，编码的目的，就是要是信源的信息率最小，也就是说，要用最少的符号来代表信源。
在定长编码中，对每一个信源序列，KL都是定值，设等于K，我们的目的是寻找最小K值。要实现无失真的信源编码，要求信源符号Xi(i=1,2,…q)与码字是一一对应的，并求由码字组成的符号序列的逆变换也是唯一的（唯一可译码）。
定长编码定理：
由L个符号组成的、每个符号熵为HL(X)的无记忆平稳信源符号序列X1X2X3…XL用KL个符号Y1Y2…YKL（每个符号有m种可能值）进行定长变码。对任意，只要则当L足够大时，必可使译码差错小于；反之，当

时，译码差错一定是有限值，当L足够大时，译码几乎必定出错。
式中，左边是输出码字每符号所能载荷的最大信息量
所以等长编码定理告诉我们，只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真的编码。条件时所取得符号数L足够大。
设差错概率为，信源序列的自方差为

则有：

当和均为定值时，只要L足够大，可以小于任一整数，即

此时要求：

只要足够小，就可以几乎无差错地译码，当然代价是L变得更大。
令

为码字最大平均符号信息量。
定义编码效率为：

最佳编码效率为

无失真信源编码定理从理论上阐明了编码效率接近于1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1，但要在实际中实现，则要求信源符号序列的L非常大进行统一编码才行，这往往是不现实的。
例如：
例题：设离散无记忆信源概率空间为

信源熵为

自信息方差为

对信源符号采用定长二元编码，要求编码效率，无记忆信源有，因此
可以得到
如果要求译码错误概率，则
由此可见，在对编码效率和译码错误概率的要求不是十分苛刻的情况下，就需要个信源符号一起进行编码，这对存储和处理技术的要求太高，目前还无法实现。
如果用3比特来对上述信源的8个符号进行定长二元编码，L=1，此时可实现译码无差错，但编码效率只有2.55/3=85%。因此，一般说来，当L有限时，高传输效率的定长码往往要引入一定的失真和译码错误。解决的办法是可以采用变长编码。
§3.3 最佳编码
最佳码：对于某一信源和某一码符号集来说，若有一唯一可译码，其平均码长小于所有其他唯一可译码的平均长度。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。
能获得最佳码的编码方法：
香农（Shannon）
费诺（Fano）
哈夫曼（Huffman）
1、香农编码方法
香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值，这是一个很重要的极限定理。
香农第一定理指出，选择每个码字的长度Ki满足下式：
Ki= []——取整
即： －log2pi ≤Ki≤1－log2pi
就可以得到这种码。这种编码方法称为香农编码。
例：设无记忆信源的概率空间为：

计算各符号的码字长度：
K1= log2=1
K2= log4=2
K3= K4 =log8=3
用图示码树，可得各自的码字：
u1:（0），u2:（10），u3:（110），u4:（111）
信息熵H(U):

信源符号的平均码长:

编码效率

对于这种信源，香农编码是最佳编码。码树达到满树。
l 香农编码法多余度稍大，实用性不大，但有重要的理论意义。
编码方法如下：
⑴ 将信源消息符号按其出现的概率大小依次排列
p(u1)≥p(u2)≥…≥ p(un)
⑵ 确定码长Ki (整数) ：
Ki= []——取整
⑶ 为了编成唯一可译码，计算第i个消息的累加概率

⑷ 将累加概率Pi变换成二进制数。
⑸ 取pi二进制数的小数点后Ki位即为该消息符号的二进制数。
例：
信源符号ui
符号概率p(ui)
累加概率Pi
-log p(ui)
码字长度Ki
码字
u1
0.4
0
1.32
2
00
u2
0.3
0.4
1.73
2
01
u3
0.2
0.7
2.32
3
101
u4
0.05
0.9
4.3
5
11100
u5
0.05
0.95
4.3
5
11101

以i = 3为例，计算各符号的码字长度：
K3 = [－log0.2] = 3
累加概率P4 = 0.7 —— 0.10110… —— 101

由图，这些码字没有占满所有树叶，所以是非最佳码。
平均码长：

编码效率：

为了提高编码效率，首先应达到满树；例如把u4u5换成A、B这些前面的节点，就可减小平均码长。所以不应先规定码长，而是由码树来规定码字，可得更好的结果。
2、费诺编码方法
费诺编码属于概率匹配编码，但它不是最佳的编码方法。编码过程如下：
⑴将信源符号接概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。
⑵将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。
⑶如此重复，直至每个组只剩下一个信源符号为止。
信源符号所对应的码字即为费诺码。
例：

信源符号
ui
符号概率
p(ui)
第1次
分组
第2次
分组
第3次
分组
码字
码长
u 1
0.4
0

0

00
2
u 4
0.05
1
0
010
3
u 5
0.05
1
011
3
u 2
0.3
1
0

10
2
u 3
0.2
1

11
2
该费诺码的平均码长

编码效率：

显然，费诺码比香农码的平均码长小，编码效率高。其实这样编码的效率还不是最高的，现用另一种分割方法：
信源符号
ui
符号概率
p(ui)
第1次
分组
第2次
分组
第3次
分组
第4次
分组
码字
码长
u 1
0.4
0

0
1
u 2
0.3
1
0

10
2
u 3
0.2
1

0

110
3
u 4
0.05
1
0
1110
4
u 5
0.05
1
1111
4
该费诺码的平均码长

编码效率：

可见编码效率又有所提高。事实上这已是最佳编码，就是说编码效率已不能再提高。但这样试探寻找分割方法总不是办法，因而赫夫曼提出一种编码方法，并证明这种编码在块码中已是最佳的。
3、哈夫曼编码方法
哈夫曼编码也是用码树来分配各符号的码字。费诺码是从树根开始，把各节点分给某子集；若子集已是单点集，它就是一片叶而作为码字。而赫夫曼编码是先给每一符号一片树叶，逐步合并成节点直到树根。
哈夫曼编码的步骤如下：
⑴ 将信源消息符号按其出现的概率大小依次排列
p(u1)≥p(u2)≥…≥ p(un)
⑵取两个概率最小的字母分别配以0和1两码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。
⑶ 对重排后的两个概率最小符号重复步骤⑵的过程。
⑷不断继续上述过程，直到最后两个符号配以0和1为止。
⑸ 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。
例： 给定离散信源如下：

平均码长：
编码效率

哈夫曼编码方法得到的码并非是唯一的。非唯一的原因：
·每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。
·对信源进行缩减时两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。
例：给定离散信源如下：

有两种哈夫曼编码方法如下图所示：

平均码长：

因为这两种码有相同的平均码长，所以有相同的编码效率，但每个信源符号的码长却不相同。
在这两种不同的码中，选择哪个码好呢？我们引进码字任度Ki偏离平均码长K的方差σ2，即

分别计算上例中两种码的方差

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

第五章 信源编码（第十一讲）
（2课时）
主要内容：（1）限失真信源编码定理（2）常用信源编码方法简介（游程编码、矢量量化编码、算术编码）
重点：常用信源编码方法简介。
难点：限失真信源编码定理、限失真信源编码定理。
特别提示：运用
说明：本堂课推导内容较多，枯燥平淡，不易激发学生兴趣，要注意多讨论用途。另外，注意，解题方法。多加一些内容丰富知识和理解。
作业：灵活运用。课外仍以学生复习。

§限失真信源编码定理
定理（限失真信源编码定理） 设R(D)为离散无记忆信源X的信息率失真函数，R为信息传输率，则当信息率R>R（D），只要信源序列长度L足够长，一定存在一种编码方法，其译码失真小于或等于D＋ε，ε为任意小的正数；反之，若R<R（D），则无论采用什么样的编码方法，其译码失真必大于D。
如果是二元信源，对于任意小的ε>0，每一个信源符号的平均码长满足如下公式：

该定理指出，在失真限度内使信息率任意接近R（D）的编码方法存在,然而，若信息率小于R（D），平均失真一定会超过失真限度D。
对于连续平稳无记忆信源，虽然无法进行无失真编码，但在限失真情况下，有与该定理一样的编码定理。
该定理只说明最佳编码是存在的，但对于如何进行编码却一无所知，因而就不能像无损编码那样从证明过程中引出概率匹配的编码方法，一般只能从优化的思路去求最佳编码。  这个定理证明了允许失真D确定后，总存在一种编码方法，使信息传输率R大于R（D）且可任意接近R（D），而平均失真小于允许失真D。反之，若R<R（D），那么该编码的平均失真将大于D。如果用二进制符号进行编码的话，在允许一定失真D的情况下，平均每个信源符号所需的二元码符号的下限值就是
R（D）。由此可见，信息率失真函数R（D）确实是在允许失真度为D的情况下信源信息压缩的下限值。当信源给定后，无失真信源压缩的极限值是信源熵H（U）；有失真信源压缩的极限值是信息率失真函数R（D）。  
在给定某D后，一般R（D）<H（U）。
同样，该定理只是一个存在定理。至于如何寻找最佳压缩编码方法，定理中并没有给出。在实际应用中，该定理主要存在以下两大类问题。
第一类问题是,符合实际信源的R(D)函数的计算相当困难。首先，需要对实际信源的统计特性有确切的数学描述。其次，需要对符合主客观实际的失真给予正确的度量，否则不能求得符合主客观实际的R(D)函数。
例如，通常采用均方误差来表示信源的平均失真度。但对于图像信源来说，均方误差较小的编码方法，人们视觉感到失真较大。所以，人们仍采用主观观察来评价编码方法的好坏。因此，如何定义符合主客观实际情况的失真测度就是件较困难的事。第三，即便对实际信源有了确切的数学描述，又有符合主客观实际情况的失真测度，而信息率失真函数R(D)的计算还是比较困难的。
第二类问题是，即便求得了符合实际的信息率失真函数，还需研究采用何种实用的最佳编码方法才能达到R(D)。
目前，这两方面工作都有进展。尤其是对实际信源的各种压缩方法，如对语音信号、电视信号和遥感图像等信源的各种压缩方法有了较大进展。相信随着数据压缩技术的发展，限失真编码理论中存在的问题将会得到解决。
§限失真信源编码常用信源编码方法
一、游程编码
游程：指数字序列中连续出现相同符号的一段。
二元序列只有两种符号：“0”和“1”：
连“0”段称为“0”游程，游程长度为L(0)
连“1”段称为“1”游程，游程长度为L(1)
由于是二进制序列，“0”游程和“1”游程总是交替出现。若规定二元序列总是从“0”开始，第一个游程是“0”游程，则第二个游程必为“1” 游程，第三个又是“0”游程……对于随机序列，游程的长度是随机的，其取值为1，2，3…自至无穷。
游程序列：用交替出现的“0”游程和“1”游程的长度，来表示任意二元序列。
例如二元序列
00010111001000l …
可变换成如下游程序列
31132131…
己规定游程序列从“0”开始，由上述游程序列，很容易恢复出原来的二元序列。
游程序列已是多元序列，各长度就可按哈夫曼编码或其它方法处理以达到压缩码率的目的。这种从二元序列转换成多元序列的方法，在实现时比以前的并元法简单；因为游程长度的计数比较容易，得到游程长度后就可从码表中找出码字输出，同时去数下一个游程长度。此外，在减弱原有序列的符号间的相关性方面采用游程变换一般也比并元法更有效。
当然，要对二元序列进行哈夫曼编码时应先测定“0”游程长度和“1”游程长度的概率分布，或由二元序列的概率特性去计算各种游程长度的概率。
设二元序列为独立序列，“0”和“1”的概率分别为 p0和p1，则“0”游程长度L(0)的概率为

式中L(0)=1，2，…，游程长度至少是1。从理论上来说，游程长度可以是无穷，但很长的游程实际出现的概率非常小。

则“1”游程长度L(1)的概率为

“0”游程长度的熵：
“0”游程序列的平均游程长度

同理，“1”游程长度的熵和平均游程长度：
变换后的游程序列是独立序列

游程变换后符号熵没有变。因为游程变换是一一对应的可逆变换。所以变换后熵值不变。
由于游程变换有较好的去相关效果，因而对游程序列进行哈夫曼编码，可获得较高的编码效率。
假设“0”游程长度的哈夫曼编码效率为η0，“1”游程长度的哈夫曼编码效率为η1,由编码效率的定义得二元序列的编码效率

假设η0＞η1，则有η0＞η＞η1
当“0”游程和“1”游程的编码效率都很高时，采用游程编码的效率也很高，至少不会低于较小的那个效率。要想编码效率η尽可能高，应使上式的分母尽可能小，这就要求尽可能提高熵值较大的游程的编码效率，因为它在往分母中占的比重较大。
理论上来说游程长度可从1到无穷。要建立游程长度和码字之间的一一对应的码表是困难的。一般情况下，游程越长，出现的概率就越小；当游程长度趋向于无穷时，出现的概率也趋向于0。
按哈夫曼码的编码规则，概率越小码字越长，但小概率的码字对平均码长影响较小，在实际应用时常对长码采用截断处理的方法
取一个适当的n值，游程长度为1,2,…,2n-1, 2n，所有大于2n 者都按2n 来处理。然后按照哈夫曼码的编码规则，将上列2n 种概率从大到小排队，构成码树并得到相应的码字。
二、矢量量化编码
要想得到性能好的编码，仅采用标量量化是不可能的。在最佳编码中，如将离散信源的多个符号进行联合编码可提高效率，这对连续信源也是如此。当把多个信源符号联合起来形成多维矢量，再对矢量进行标量量化时，自由度将更大，同样的失真下，量化级数可进一步减少，码率可进一步压缩。这种量化叫做矢量量化。
实验证明，即使各信源符号相互独立，多维量化通常也可压缩信息率。因而矢量量化引起人们的兴趣而成为当前连续信源编码的一个热点。可是当维数较大时，矢量量化尚无解析方法，只能求助于数值计算；而且联合概率密度也不易测定，还需采用诸如训练序列的方法。一般来说，高维矢量的联合是很复杂的，虽已有不少方法，但其实现尚有不少困难，有待进一步研究。
设矢量量化器输入集为 X＝{X1，X2，…，XN}，Xj∈X，Xj＝（xj1，xj2，…,xjk）， X∈R k（k维欧几里德空间），把R k划分成J＝2 n个互不相交的子空间R1，R2，…，RＪ，求出每个子空间的质心Yi，所有的 Yi构成 Y＝{Y1，Y2，…，YＪ}，Y为量化器的输出空间，也叫码书（或码本），Yi叫码字或码矢，J叫码书的长度。  
对J阶K维的矢量量化，实质上是判断输入Xj∈ Rk属于哪个子空间Ri，然后输出该子空间代表码字 Yi，即：
  Yi＝Q（Xj）, 1≤i≤J，1≤j≤N （4―42）
这里 Yi就是Xj的编码。
实际编码时，在发送端只需记录代表码字Yi的下标i，所以编码过程是把X映射到I＝{1，2，…，J}；而译码过程是在接收端依据收到的I代码，查找码书Y，获得码字Yi，用来代替Xj。由于总的码字个数J一般远小于总的输入信号N×K，所以矢量量化的压缩能力非常大。
传输或存储一个矢量所需比特为lbJ（一般J＝2n），它是一个K维矢量，就是K个输入信号，所以每个输入信号的平均比特只有lbJ/K，称之为压缩比。适当选取码书长度J和码字维数K，可以获得很大压缩比。矢量量化中码书的码字越多，维数越大，失真就越小。只要适当地选择码字数量，就能控制失真量不超过某一给定值，因此码书控制着矢量的大小。矢量量化时每输入一个 Xj，都要和J个码字 Yi逐一比较，搜索与其最接近的码字 Yi。由于两者均为K维矢量，所以工作量很大。矢量量化是定长码，容易处理。
矢量量化由码书 Y和划分Ri的条件惟一确定。当码书确定后，通过最近邻域准则可以惟一确定区域分割。因此，最佳量化器的设计也就是最佳码书Y的设计。前面，在讨论一维标量的最佳设计时，引入了MaxLivod的迭代算法，1980年Linde、Buzo和Gray将此算法推广到了多维空间，称作LBG算法。因LBG算法由于理论上的严密性和实现的简便性以及较好的设计效果而得到了广泛的应用，并成为各种改进算法的基础。有关LBG算法等知识请参阅有关文献。
三、算术编码
1、算术码的主要概念：
把信源输出序列的概率和实数段[0，1]中的一个数ρ联系起来。设信源字母表为{a1, a2}，其发生概率为p(a1)=0.6 ,p(a2)=0.4。将[0，1]分成两个与概率比例相应的区间，[0，0.6] [0.6，l]当信源输出的第一个符号s1 = a1时，数ρ的值处在[0，0.6] ，s1 = a2时，[0.6，l]。
根据信源字母s1的情况,把ρ所在的段再次按概率比例分成
[0，1] → [0，0.6] [0.6，l]
[0,0.36] [0.36,0.6] [0.6,0.84] [0.84,1]
s1 = a1 s1 = a2
根据信源输出的第二个字母s2的取值情况，可以更精确地确定出数ρ所在的区间位置。在信源输出第n－1个符号后，若ρ所在的位置为
[An-1 ，Bn-1]
则当信源输出的第n个符号为：
sn= a1时， sn= a2
An= An-1 An= An-1+0.6(B n-1－An-1)
Bn= An-1+0.6(B n-1－An-1) Bn= Bn-1
按照这一方法，序列的概率刚好等于ρ所在区间的长度。随着序列的长度不断增加，ρ所在区间的长度就越短，也就可以更加精确地确定ρ的位置。当信源字母序列长度趋于无限时，ρ所在区间成为一点。
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）的累积概率
以二元无记忆信源为例：
初始时：在[0，l]由F(1)划分成二个子区间：
[0，l] →[0,F(1)] [ F(1),1]， F(1) = p(0)
0 1
子区间[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 =“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，若接着再输入一个符号“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) = 1－A(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) = 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)
┊
信源符号序列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) = 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)存下来，然后根据输入符号和上式，更新两个存储器中的数值。
因为在编码过程中，每输入一个符号要进行乘法和加法运算，所以称此编码方法为算术编码。
将上式推广到多元信源序列，得一般的递推公式
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)]。可取小区间内的一点来代表这序列。
代表大于等于的最小整数。

令
把累积概率F(s) 写成二进制的小数，取小数点后L位，以后如果有尾数，就进到第L位，这样得到一个数C。
例F(s) = 0.10110001，p(s) 1/17，则L = 5，
得C = 0.10111，s的码字为10111
这样选取的数值C，一般根据二进小数截去位数的影响,得
C－F(s)＜2-L
当F(s)在L位以后没有尾数时C=F(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(sr) = C(s) + A(s ) F(r)
A(sr) = A(s ) p(r)
因为信源符号序列s的码长满足，所以得
若信源是无记忆的
H(Sn)=nH(S)

平均每个信源符号的码长

例：设二元无记忆信源A={0,1}，p(0)=1/4 ，p(1)=3/4
对二元序列s=11111100做算术编码
解：根据上述的编码规则，可得
p(s=11111100) = p2(0) p6(1) =(3/4)2(1/4)6
= 7

F(a3) = p(a1)+ p(a2)
F(s) = p(00000000) + p(00000001) + p(00000010) + …
　　 + p(11111011)
= 1－ p(11111111)－ p(11111110)
－ p(11111101) － p(11111100)
= 1－ p(111111) =1－(3/4)6= 0.110100100111
得 C = 0.1101010 s的码字为1101010
编码效率
这种按全序列进行编码，随着信源序列n的增长，效率还会增高。
递推编码过程可列表如下：

得s的码字为1101010。此时s =11111100对应的区间为［0.110100100111,0.1101010101001001］。可见C是区间内一点。
实际编码是用硬件或计算机软件实现