《编码理论》课件第3章

第3章无失真信源编码方法

3.1霍夫曼码和其他编码方法

3.2算术编码

3.3游程编码

3.4通用编码

3.1霍夫曼码及其他编码方法

3.1.1二元霍夫曼码

1952年霍夫曼提出了一种构造最佳码的方法，它是一种逐个符号的编码方法。所得的码字是异前置码的变长码，其平均码长最短，是最佳变长码，又称霍夫曼码，二元霍夫曼码编码步骤如下：

(1)将n元信源U的各个符号ui按概率分布p（ui）以递减次序排列起来。

(2)将两个概率最小的信源符号合并成一个新符号，新符号的值为两个信源符号值的和，从而得到只包含n－1个符号的新信源，称为U信源的缩减信源U1。

(3)把缩减信源U1的符号仍按概率大小以递减次序排列，然后将其中两个概率最小的符号合并成一个符号，这样又形成了n－2个符号的缩减信源U2。

(4)依次继续下去，直至信源最后只剩下１个符号为止。(5)将每次合并的两个信源符号分别用0和1码符号表示。(6)从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即得各信源符号对应的码字。

［例3-1］离散无记忆信源

对应的霍夫曼编码如图3－1所示。

信源熵：

(比特/信源符号)平均码长：

(码符号/信源符号)编码效率：

图3－1例3－1霍夫曼编码

【例3－2】离散无记忆信源

的两种霍夫曼编码如图3－2所示。

图3－2例3－2的两种霍夫曼编码

图3-3中（a）、（b)所示两种方案的霍夫曼编码平均码长都为

(码符号/信源符号)信源熵：

(比特/信源符号)编码效率：

图3－3例3－2对应的霍夫曼树

两种码有相同的平均码长，有相同的编码效率，但每个信源符号的码长却不相同，其均方差也不同。下面分别计算两种码的均方差σ2，即

(方法a方差)(方法b方差)可见，方法（a）的方差比方法（b）的方差要小许多。方法(a）的具体编码原则是把合并后的概率总是放在其他相同概率的信源符号之上（或之左）;方法（b)的编码原则是把合并后的概率放在其他相同概率的信源符号之下（或之右）。从上面的分析可以看出，方法（a)要优于方法（b)。

可见，霍夫曼码得到的码并非是惟一的。因为对缩减信源的两个概率最小的符号，可以任意的用0和1码，所以可得到不同的码，但它们只是码字具体结构不同，而其码长不变，平均码长也不变，因此没有本质区别。另外，若当缩减信源中缩减合并后的符号的概率与其他信源符号概率相同时，从编码方法上来说，对等概率的符号哪个放在上面、哪个放在下面是没有区别的，但得到的码是不同的。对这两种不同的码，它们的码长各不同，然而平均码长是相同的。在编码中，对等概率消息，若将新合并的消息排列到上支路，可以证明它将缩短码长的方差，即编出的码更接近等长码；同时可使合并的元素重复编码次数减少，使短码得到充分利用。

3.1.2

m元霍夫曼码

前面讨论的二元霍夫曼码的编码方法可以推广到m元编码中，不同的只是每次把概率最小的m个符号合并成一个新的信源符号，并分别用0，1，…，m－1等码元来表示。

为了使短码得到充分利用，使平均码长最短，必须使最后一步的缩减信源有m个信源符号。因此，对于m元编码，信源U的符号个数n必须满足：n＝（m－1）Q＋m

（3-1）

式中：n—信源符号个数；m—进制数（码元数）；Q—缩减次数。

对于二元码，总能找到一个Q满足式（3－1）。但对于m元码，n为任意正整数时不一定能找到一个Q满足式（3－1），此时，可以人为地增加一些概率为零的符号，以满足式（3－1），然后取概率最小的m个符号合并成一个新符号（结点），并把这些符号的概率相加作为该结点的概率，重新按概率由大到小顺序排队，再取概率最小的m个符号（结点）合并；如此下去直至树根。

下面给出m元霍夫曼的编码步骤：

(1)验证所给n是否满足式（3－1），若不满足该式，可以人为地增加一些概率为零的符号，以使最后一步有m个信源符号。

(2)将信源符号按概率递减次序排列，取概率最小的m个符号合并成一个新结点，并分别用0，1，…，m－１给各分支赋值,把这些符号的概率相加作为该新结点的概率。

(3)将新结点和剩下结点重新排队，重复步骤（2），如此下去直至树根。

(4)取树根到叶子（信源符号对应结点）的各树枝上的值，得到各符号码字。【例3－3】已知信源

其三元霍夫曼编码如图3-4所示.，四元霍夫曼编码如图（3-5）所示。

图3-4例3-3三元霍夫曼编码图3－5例3－3四元霍夫曼编码

信源熵：

(比特/信源符号)两种编码的平均码长分别为：

因为lb3＝1.58(比特/信源符号),lb4＝2(比特/信源符号)，所以它们的编码效率分别为：

可见，要发挥霍夫曼编码的优势，一般情况下，信源符号集的元数应远大于码元数。对例3－3，若编五元码，只能对每个信源符号赋予一个码数，等于没有编码，当然也无压缩可言。那么，什么样的编码能获得最佳的压缩效果呢？下面将讨论这个问题。

3.1.4香农编码

香农第一定理指出了平均码长与信源信息熵之间的关系，同时也指出了可以通过编码使平均码长达到极限值，这是一个很重要的极限定理。至于如何去构造一个紧致码(最佳码)，定理并没有直接给出。香农第一定理指出，选择每个码字的长度li使之为满足式-logp(ui)≤li<-logp(ui)+1的整数，就可以得到惟一可译码，这种编码方法称为香农编码。按照香农编码方法编出来的码可以使平均码长L不超过上界，但并不一定能使L为最短，即编出来的不一定是紧致码。

可见，香农编码方法剩余度稍大，实用性不强，但有其重要的理论意义。二元香农码的编码过程如下：

（1）将信源发出的n个消息（符号）按其概率的递减次序依次排列。

(2)为了编成惟一可译码，首先计算第i个信源符号的累加概率：

(3)将累加概率pi(为小数)变换成二进制数。

(4)根据码长li，取小数点后li位数作为第i个信源符号的码字,li可由下式确定：

式中：［X］——取大于或等于X的最小整数。

(3－2)(3－3)【例3－4】已知

求香农编码。

解计算第i个信源符号的码字。设i=4，首先求第4个信源符号的二元码字长l4：再计算累加概率p4：

将累加概率p4变换成二进制数：

故变换成二进制数为0.100…，根据码长l4=3取小数点后三位100,作为第4个信源符号的码字。其他信源符号的二元码字可用同样方法求得，如表3－1所示。

表3－1香农编码

由表3－1可以看出，一共有5个三位的码字，各码字之间至少有一位数字不相同，故是惟一可译码。

信源符号概率累加概率码字长度二元码字0.200.002.3430000.190.202.4130010.180.392.4830110.170.572.5631000.150.742.7431010.100.893.34411100.010.996.6671111110平均码长：

(码符号/信源符号)平均信息传输速率：

(比特/码符号)由上面的编码过程和例题分析可知，利用香农编码方法求表3－1中信源符号的码字比较繁琐。能否紧紧把握香农编码的核心思想而改进其具体的编码过程呢?香农编码方法的核心思想是：每个码字的码长li满足-logp(ui)≤li<-logp(ui)+1并取整。在此基础上，不采用累加概率转换为二进制数的编码方法，而是求出每个码字码长后，利用树图法找到一组码长满足要求的树码。这样，改进的香农编码方法的具体内容如下：

（1）根据每个信源符号的概率大小，按式(3－3)计算其码字的码长li。

(2)利用二元树图法，根据所求码字码长的大小，构造出即时码。图3－6二元树图

根据二元树图，可以得到满足要求的即时码。

上面所讨论的是二元香农编码，利用改进的香农编码方法可以把它推广到r元香农编码中，即

（1）根据每个信源符号的概率大小，按式(3－3)计算其码字的码长li。

（2）利用r元树图法，根据所求码字码长的大小，构造出即时码。3.1.5费诺编码

费诺编码属于统计匹配编码，但它不是最佳的编码方法。费诺编码步骤如下：

(1)将信源消息（符号）按其出现的概率由大到小依次排列。

(2)将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组分别赋予一个二进制码元“0”和“1”。

(3)将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又分别赋予一个二进制符号“0”和“1”。

(4)如此重复，直至每个组只剩下一个信源符号为止。

(5)信源符号所对应的码字即为费诺码。

【例3－5】离散独立信源

其费诺编码如图3－7所示。

图3－7例3－5的费诺编码

信源熵：

(比特/信源符号)平均码长：

(码符号/信源符号)编码效率：

【例3－6】离散无记忆信源

信源熵：

(比特/信源符号)平均码长：

(码符号/信源符号)编码效率：

图3－8例3－6的费诺编码

由上述分析可见，费诺码考虑了信源的统计特性，使经常出现的信源符号能对应码长短的编码字。显然，费诺码仍然是一种相当好的编码方法。但是，这种编码方法不一定能使短码得到充分利用。尤其当信源符号较多，并有一些符号概率分布很接近时，分两大组的组合方法就很多。可能某种分配结果会使得后面小组的“概率和”相差较远，因而使平均码长增加，所以费诺码不一定是最佳码。费诺码的编码方法实际上是构造码树的一种方法，所以费诺码是一种即时码。

3.1.6香农－费诺－埃利斯码

香农－费诺－埃利斯码不是分组码，它根据信源符号的积累概率分配码字，不是最佳码，但它的编码和译码效率都很高。

设信源

定义信源符号积累概率

(3－4)式中：ui,uk∈{u1,u2,…,un}。

定义信源符号修正的积累概率函数：

（3－5）

由信源符号积累概率定义可知，F(uk＋1)和F(uk)都是小于1的正数，可将这些小于1的正数映射到区间（0，1]内，图3-9描绘了积累概率分布。

图3－9积累概率分布图

由式（3－7）可得香农－费诺－埃利斯码平均码长L为

可见，此码也是熵编码，且平均码长比霍夫码的平均码长要多1位码元。

【例3－7】离散无记忆信源

的香农－费诺－埃利斯码编码如表3－2所示。

表3－2例3－7的香农－费诺－埃利斯码码表

用霍夫曼码对例3－7编码，其编码效率为100%。可见，香浓－费诺－埃利斯码不是最佳码，它比霍夫曼码每位信源符号多1位码元。

前面讨论了信源编码原理及各种编码方法,霍夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，而且所有短码得到充分利用；且每次缩减信源的最后两个码字总是最后一位不同，前面各位相同，这两个特点保证了所得的霍夫曼码一定是最佳码。对信源的N次扩展信源同样可以采用霍夫曼编码方法，因为霍夫曼码是最佳码，所以编码后单个信源符号所编得的平均码长随N的增加很快接近于极限值—信源的熵。

费诺码不一定是最佳码，但有时也可获得最佳的编码效果。费诺码也是统计匹配码，但这种方法不一定能使短码得到充分利用，这种编码方法得到码字是即时码。费诺编码方法同样适合于m元编码，只需每次分成m组即可。

前面讨论了信源编码原理及各种编码方法。霍夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，而且所有短码得到充分利用；且每次缩减信源的最后两个码字总是最后一位不同，前面各位相同。这两个特点保证了所得的霍夫曼码一定是最佳码。对信源的N次扩展信源同样可以采用霍夫曼编码方法，因为霍夫曼码是最佳码，所以编码后单个信源符号所编得的平均码长随N的增加很快接近于极限值——信源的熵。

费诺码不一定是最佳码，但有时也可获得最佳的编码效果。费诺码也是统计匹配码，但这种方法不一定能使短码得到充分利用，这种编码方法得到码字是即时码。费诺编码方法同样适合于m元编码，只需每次分成m组即可。

霍夫曼码编码构造出来的码不是惟一的，可是其平均码长却是相同的，所以不影响编码效率和数据压缩性能。霍夫曼码对不同信源其编码效率也不尽相同。当信源概率是2的负次幂时，霍夫曼码的编码效率达到100％；当信源概率相等时，其编码效率最低。这就告诉我们，在使用霍夫曼码方法编码时，只有当信源概率分布很不均匀时，霍夫曼码才会收到显著的效果。应用霍夫曼码时，需要与其他编码结合起来使用，才能进一步提高数据压缩比。例如，在JPEG(静态图像处理标准)中，先对图像像素进行DCT变换、量化、Z形扫描、游程编码后，再进行霍夫曼编码。因为霍夫曼码是变长码，所以它有变长码的缺点。最后，因为信源符号与码字之间不能用某种有规律的数字方法对应起来，所以只能通过某种查表方法建立它们的对应关系。当N增大时，信源符号增多，所需存储的容量增大，使设备复杂化，同时也使编译码时查表搜索时间增加。尽管如此，霍夫曼方法还是一种较具体和有效的无失真信源编码方法，它可以编制成在计算机上实现的程序。

3.2算术编码

3.2.1积累概率的递推公式

设信源

定义信源符号的积累概率：

ui，u

k∈U

（3-11）由式（3－11）可知：

F（u

k）∈〔0，1）由式（3－11）得:F（u1）＝0，F（u2）＝p（u1），F（u3）＝p（u1）＋p（u2），…且p（ui）＝F（ui＋1）－F（ui）

因为F（ui）和F（ui＋1）都是小于1的正数，因此可用［0，1）区间的两个点来表示，p（ui）就是这两点间的小区间的长度。不同的符号对应不同的小区间，这些小区间互不重叠，小区间内的任意的一个点可作为该符号的编码，且此编码为即时码。

设基本离散独立信源序列：

S＝s1s2…sk…sn，(Sk∈U,k＝1，2，…，n则信源序列的积累概率的递推公式：

（3－12）

式中：F（Su

r）—信源序列S添加一个新的信源符号u

r后所得到的新序列Su

r的积累概率；

p（S）—信源序列S

的概率；

F（u

r）—信源符号ur的积累概率；

p（Su

r）—信源序列S添加一个新的信源符号u

r后所得到的新序列Su

r的概率；

p（u

r）—信源符号u

r的概率。

3.2.2算术编码原理

由前面的讨论可知，信源符号的积累概率将区间［0，1）分成许多互不重叠的小区间，每个信源符号对应一个不同的小区间，每个小区间的长度等于这个信源符号的概率，在此小区间内取一点，该点的取值可作为这个信源符号的码字。这个原理同样适用于信源序列。把信源序列的积累概率映射到［0，1）区间上，使每个序列对应该区间内的一个点，这些点把区间［0，1)分成许多不同的小区间，这些小区间的长度等于对应序列的概率，在小区间内取一个浮点小数，使其长度与该序列的概率相匹配，因而达到高效编码的目的。

设小区间左、右端点的值分别用low和high表示，用range表示小区间的长度，则小区间左、右端点的递推公式：

式中：low（Sur）—信源序列S添加一个新符号ur后所得到的新序列Sur对应区间的左端点值；

high（Sur）—信源序列S添加一个新信源符号ur后所得到的新序列Sur对应区间的右端点值；

low（S）—信源序列S对应区间的左端点值；

range（S）—信源序列S对应区间的宽度值；

low（ur）—信源符号ur对应区间的左端点值；

high（ur）—信源符号ur对应区间的右端点值。

（3－13）

使用公式（3-13）计算小区间端点值的步骤：

(1)给出信源符号对应的区间；

(2)初始时设S＝Φ（Φ代表空集），low（Φ）＝0，high（Φ）＝1，range（Φ）＝1；

(3)输入信源序列的一个符号ur，根据公式（3-13）计算序列Sur的左右端点值。依次下去，直至全部信源序列对应的区间被确定为止。

【例3－8】设信源

求信源序列abda对应的小区间。

解各个信源符号对应的小区间如表3－3所示。

表3－3例3－8信源符号对应的小区间

不同的信源符号分别对应不同的小区间,哪个符号被设在哪个区段并不重要,也就是说不需要各符号按概率顺序排列,只要编码和解码都以同样的方式进行就可以。

信源序列abda对应小区间的左、右端点的值如表3－4所示,信源序列abda对应区间端点值的计算如下。

表3－4信源序列abda对应小区间的端点值

输入信源序列的第1个符号a：

设low(Φ)＝0，high(Φ)＝1，range(Φ)＝1；

low(Φa)＝low(Φ)＋range(Φ)×low(a)＝0＋10＝0.000

high(Φa)＝low(Φ)＋range(Φ)high(a)＝0＋10.5＝0.500

输入信源序列的第2个符号b：

low(ab)＝low(a)＋range(a)low(b)＝0.00＋0.50.5＝0.250

high(ab)＝low(a)＋range(a)high(b)＝0.00＋0.50.75＝0.375

同理可计算出其它数据。图3－10信源序列abda对应区间划分

解码是编码的逆过程，即根据接收到的码字翻译出对应的信源序列。解码步骤如下：

(1)判断码字落在哪个符号区间，翻译出1个符号。

(2)将码字减去刚翻译出的符号的左端点值。

(3)用刚翻译出的符号对应的区间的长度去除步骤

（2）的结果，判断此值落在哪个符号区间，翻译出1个新符号。

(4)重复步骤（2）、（3），直至全部信源序列被翻译完为止。

下面以码字0.359375为例,说明解码过程。

码字0.359375落在［0，0.5）之间,即0.359375∈［0，0.5），于是翻译出第1个符号为a；用符号a对应区间的长度0.5去除码字与符号a的左端点值的差得0.71875,

即(0.359375－0)／０.5＝0.71875∈［0.5,0.75)，则翻译出第2个符号为b；用符号b对应区间的长度0.25去除码字0.71875与符号b的左端点值的差得0.875,于是翻译出第3个符号为d；用符号d对应区间的长度0.125去除码字0.875与符号d的左端点值的差得0,码字0落在［0，0.5）之间,即0∈［0,0.5),于是翻译出第4个符号为a。因此，码字0.359375对应的序列为abda,解码正确。

【例3－9】已知信源

求信源序列efbfcafdcc对应的区间端点值。

解信源符号区间划分如表3－5所示。例3－9信源序列对应的小区间端点值如表3－6所示。

表3－5例3-9信源符号对应区间的端点值

表3－6信源序列efbfcafdcc对应区间的端点值

3.2.3算术编码是熵编码

从上面的分析可知，不同的信源系列对应不同的小区间，可取小区间内的一点作为该序列的码字。怎样选取该点呢？可以选区间的左端点的值作为码字，也可以选取区间的中点作为码字。码字长度选取的原则主要是使其与该序列的概率匹配，所以可根据下式选码长L：

取信源序列码字的前L位，若后面有尾数就进位到第L位,这样得到的数就是序列的编码C。

例如：p（S）＝3/16，序列S左端点的值为0.011011,则L＝3,得序列S的码字C＝100。

下面证明这样得到的码字C必然在序列对应的小区间内,因此是可以惟一解码的码字。

根据码字C的选取可以知道，当F（S）在L位以后没有尾数时C＝F（S），否则C>F（S）,所以

C≥F（S）

（3－15）

由式（3－14）可知：

（3－16）

则信源序列S对应区间的右端点的值：

（3－17）

根据二进制小数截去位数的影响得：

（3－18）

由式（3－17）和式（3－18）得：

C<F（S）＋p（S）

（3－19）因此信源序列S码字C落在该序列对应的区间［F（S），F（S）＋p（S））内。

根据信源编码定理可知信源序列S的平均码长满足：

平均每个信源符号的码长：

（3－20）对于无记忆信源有H（Sn）＝nH（S），则（3－21）

3.2.4算术编码方法

实际编码时，用递推公式可逐位计算序列的积累概率，只要存储器容量允许，无论序列有多长，皆可一直计算下去，直至序列结束。

下面给出用序列积累概率的递推公式进行序列的算术编码的计算步骤：

(1)根据式(3-11)计算信源符号的积累概率；

(2)初始时设S＝Φ，F（Φ）＝0，p（Φ）＝1（Φ代表空集）；

(3)根据式（3－12）计算序列的积累概率F（Sui）和序列的概率p（Sui）。

(4)根据式（3－14）计算码长L。

(5)将F(S)写成二进制数的形式,如果小数点后只有L位数据，则取其前L位作为序列S的码字；如果小数点后有多于L位数据，则取其前L位加1作为序列S的码字。【例3－10】设二元独立信源

求信源序列1010的算术编码。

解信源符号的积累概率：F（0）＝0；F（1）＝0.25,则信源序列1010算术编码的相关数据如表3－7所示，表中数据为二进制形式。表3－7信源序列1010算术编码

表3-7中数据的计算：因为F(Φ)＝0,

p(Φ)＝1，则输入信源序列的第1个符号1：

F(Φ1)＝F(Φ)＋p(Φ)F(1)＝0＋10.25＝0.01

P(Φ1)＝p(Φ)p(1)＝0.11

输入信源序列的第2个符号0：

F(10)＝F(1)＋p(1)F(0)＝0.01＋０．７５０＝０．０１

P(10)＝p(1)p(0)＝０．７５０．２５＝0.0011

同理可计算出其它数据，信源序列1010算术编码对应图解如图3-11所示。

图3-11信源序列1010算术编码图解

【例3－11】设二元独立信源

求信源序列11111100的算术编码。

表3－8信源序列11111100算术编码

【例3－12】已知信源

求信源序列abda的算术编码。

解信源符号的积累概率如表3－9所示。信源序列abda的算术编码如表3－10所示。表3－9例3－12信源符号的积累概率

表3－10信源序列abda算术编码

表3-10中数据的计算，设F(Φ)＝0,

p(Φ)＝1，则

输入信源序列的第1个符号a：

F(Φa)＝F(Φ)＋p(Φ)F(a)＝0＋1×0＝(0.0)2

P(Φ1)＝p(Φ)p(a)＝１×0.5＝(0.1)2

输入信源序列的第2个符号b：

F(ab)＝F(a)＋p(a)F(b)＝０＋0.5×0.5＝(0.01)2

P(ab)＝p(a)p(b)＝0.5×0.25＝(0.001)2

同理可计算出其它数据，由此得序列abda的编码为0101110。编码图解如图3-12所示。

图3－12信源序列abda算术编码图解

每次递推运算中都有乘法,当序列概率和符号的积累概率展开成二进位小数后的位数较多且要求精度较高时，就有一定的运算量。这种运算必须在输入一个信源符号的时间内完成，以保证实时编译码。要消除乘法，有两种方法:一种方法是，编码对象是二元序列，而且其符号概率较小的一个为2-k的形式，其中k是正整数，此时乘以2-k等于移位，乘以1-2-k等于移位和相减,这样就可做到完全没有乘法运算，可加快运算速度；另一种方法就是采用3.2.5节中介绍的不做乘法的算术编码。关于计算精度问题，即使在二元序列的情况下，精度问题仍存在。随着递推运算的延续，F(S)和p(S)的小数位数也将逐步增加，若不能随时输出和加以截断，运算器将难于容纳,但有所截断必然降低精度,而精度不够会影响编、译码的正确性。这是因为随着序列长度增大，小区间数目越来越多，长度越来越短,计算精度不够，会使有些小区间互相重叠或消失(即长度零)。

前者使惟一性丧失，后者使无码字可编。这当然会造成差错，因此算术编码也就不是无损编码，而且这些差错还会扩散。另一个问题是存储量问题。编成的码字的长度也是随序列占的长度增加而不断增长,若不及时输出，存储量将非常大；但若输出过早，运算过程中可能还需调整已输出的部分，那就来不及了。但当未输出部分的前面各位都是“1”时，后面在计算时略有增加，就可能进位到已输出部分。尤其当这种连“1”很长时，原以为保留很多位应已足够，但仍会影响已输出部分。从理论上说，这种连“1”的长度可以达到无限，当然出现这种情况的概率也接近零。这类问题常称为进位问题，在实际应用时也必须设法解决。

3.2.5不做乘法的算术编码

从上面的讨论可知，信源序列不同，其积累概率的值不同。这些相异的值对应区间［0，1）上不同的点，它们把区间［0，1）分成许多小区间段，这些小区间的长度等于对应序列的概率。一般情况下，取小区间的左端点的值作为序列的编码，使其长度与该序列的概率相匹配，这样便可求得序列的码字C（S），并达到高效编码的目的。由于每次使用递推公式进行计算时都有乘法运算，因而若要求精度较高，就有一定的计算量。这种运算必须在输入一个信源符号的时间内完成，以保证实时编、解码，但有时会造成困难。那么怎样才能消除乘法?下面讨论这个问题。

信源序列积累概率的递推公式为

F（Sur）＝F（S）＋p（S）F（ur）p（Sur）＝p（S）p（ur）

则二元信源序列积累概率的递推公式如下：

F（S0）＝F（S）＋p（S）F（0）＝F（S）F（S1）＝F（S）＋p（S）F（1）p（S1）＝p（S）p（1）

p（S0）＝p（S）p（0）

且

p（S）＝p（S0）＋

p（S1），F（1）＝p（0）

如果令p（S1）≈2-qp（S）,则不做乘法的二进制算术编码的递推公式为p（S0）＝p（S）－p（S1）

F（S0）＝F（S）

F（S1）＝F（S）＋p（S）F（1）＝

F（S）＋p（S）p（0）＝

F（S）＋

p（S0）

即

p（S1）≈2-qp（S）（3-22）p（S0）＝p（S）－p（S1）（3-23）F（S0）＝F（S） （3-24）

F（S1）＝

F（S）＋

p（S0）

（3-25）

不做乘法的算术编码步骤：

（1）初始时，设S＝Φ，P（Φ）＝0.111…1,F（Φ）＝0.000…0

（2）输入1个信源个符号，用递推公式（3-22）~（3-25）计算p（S1）、p（S0）、F（S0）、F（S1）；

（3）重复步骤（2），直至信源序列结束。由于序列S是用子区间[F(S),F(S)＋p(S))中的一个点表示其编码的,因此解码时只要判断序列的码字落在哪个区间,就一定能正确的译码。与编码过程相对应，下面给出不做乘法的二进制算术译码步骤：

（1）

设P（S*）＝0.1111,C(S*)就是已编出的码字。

（2）

计算：

p（S*1）＝2-qp（S*）

p（S*0）＝p（S*）－p（S*1）

（3）将码字C(S*)与p（S*0）比较，确定当前字符是1还是0：

若C(S*)－p（S*0）<０，则当前字符为0

若C(S*)－p（S*0）≥０，则当前字符为1

（4）重复步骤（2）、（3）直到解码结束。

由于右移q位后使p（S）前面出现了越来越多的0，这种情况在具体实现时是很不经济的，如果用浮点数表示就可解决此问题。若p（S）前面出现了m个0，可将其左移m位，以保留足够的有效位数，同时F（S）也左移m位，然后再用递推公式进行计算。

由不做乘法的二进制算术编码、译码的过程看到，q的确定是非常重要的。根据p（S1）≈2-qp（S）可知，实际应用时，可以取2-q近似等于二元序列中小概率符号的概率值。在实际问题中,小概率符号不可能正好等于2-q,只能使2-q的值接近小概率符号的值。这样对编码有什么影响呢？当序列很长时，序列的概率已很小，码字长度将接近此概率倒数的对数。按2-q编码时，每个符号“0”需要q比特，每个符号“1”需要-lb（1-2-q）比特，所以每个符号的平均码长L为信源的熵为

H(U)＝－p(0)lbp(0)－（1－p（0））lb（1－p(0)）当p(0)＝2-q时,L＝H(U),此时编码效率等于1。一般实际编码中，p（0）≈2-q，此时编码效率可在95%以上。可见，用2-q来近似所造成的损失并不大，但近似后的计算量却减小很多，尤其是当符号的小概率值很小时，损失更小。所以在用算术编码对二元信源序列编码时，经常采用这种近似。 3.3游程编码

3.3.1游程和游程序列

算术编码是解决小消息信源问题的一种很好的方案，另外，游程编码也是解决小消息信源问题的一种很好的方案。下面介绍游程编码的相关知识。

二元序列只有两种值，分别用“0”和“1”表示，这两种符号可连续出现，就形成了“0”游程和“1”游程。“0”游程和“1”游程总是交替出现的，连“0”符号的个数称“0”游程长度，连“1”符号的个数称“1”游程长度。这样可把二元序列变换为游程长度序列，且二者是可逆的。例如：二元序列为 000011111001111110000000111111…

对应的游程长度序列为

452676…如果规定序列从“0”开始，那么很容易将游程长度序列恢复成二元序列。游程长度序列是多元序列，如果计算出各个游程长度的概率，就可对各游程长度进行霍夫曼编码或用其他编码方法进行处理，以达到压缩编码的目的。

多元信源序列也存在相应的游程长度序列。m元序列有m种游程，且某个游程L（ur）的前面和后面出现什么符号对应的游程是无法确定的，因此这种变换必须再加一些符号，才能使m元序列和其对应的游程长度序列是可逆的。

3.3.2游程编码是熵编码

二元序列中，不同的“0”游程长度对应不同的概率；不同的“1”游程长度也对应不同的概率，这些概率叫游程长度概率。对不同的游程长度，按其不同的发生概率，分配不同的码字，这就是游程编码的基本思想。游程编码可以将两种符号游程分别按其概率进行编码，也可以将两种游程长度混合起来一起编码。下面讨论游程长度编码平均码长的极限值。

考虑两种游程分开编码的情况。为了讨论方便，规定两种游程分别用白、黑表示。白游程熵：

(3－26)式中：lw—白游程长度；

p(lw)—白游程长度概率；

L—白游程最大长度。根据信源编码定理可知白游程平均码长LW应满足：

(3－27)令为白游程长的平均像素值，则

（3－28）

由式（3－27）和（3－28）得：

(3－29)令每个白像素的熵值为hＷ,则

每个白像素的平均码长：

代入式（3－29）得：

（3－30）

同理对黑游程可求出：

(3－31)(3－32)每个像素平均码长：

3.4通用编码

3.4.1分段编码

设m元信源序列：

S＝s1,s2,…,sn，si∈{u1，u2，…，um},i＝1,2,…，n。

所谓分段编码,就是将序列分成不同的几段。分段规则是尽可能取最少个连着的信源符号，并保证各段都不相同。设信源序列按此规则分段的结果为

y1,y2,y3,…，

yc

(3－38)式中：c——序列段数。

若j>i,则

yj

＝yiur

（3－39）

即第j段是由第i段后续一个信源符号ur构成的，或者说第j段可用两个数字i和r来确定。由于r<m，这两个数可用一个数Nj来表示，即Nj＝mi＋r

(3－40）

式中：m—信源符号集中元素个数；

i—信源序列的第i段段号；

r—信源符号集中第r个信源符号的序号；

Nj—第j段的码字。

第j段编码的码长

(3－41)将Nj编成二进制码，取lj位传送出去；在接收端，由i可以找到第i段，再加上一个信源符号ur就可无差错地恢复第j段。用m除以Nj后所得的商为i,余数为r。下面举例说明这种编码方法。[例3-13]设信源符号集为：U＝｛a0,a1,a2,a3｝,求信源序列a0

a0a2

a3

a1

a1

a0

a0

a0a3

a2

的LZ编码？

解:将信源序列按上述规则分成7段：

a0，a0a2，a3，a1，a1

a0，a0

a0，a3a2

各段参量如表3-11所示。

表3－11例3－13分段编码表

3.4.2段匹配码

段匹配码实质上也是一种分段编码，编码规则也是尽可能取最少个连着的信源符号，并保证各段都不相同。段匹配码将段号和信源符号分别进行编码，这样处理后，在实际应用时比较容易处理。若组成二元码，段号所需码长：

(3－42)式中:c——信源序列所分段数。每个信源符号所需码长：

(3－43)式中：m——信源符号集中元素个数。

[例3-14]

信源符号集为U＝｛a0,a1,a2,a3｝，求信源序列a0

a0

a2

a3

a1

a1

a0

a0

a0

a3

a2的段匹配码。

解:根据上述分段原则信源序列分为7段：

a0,a0

a2,a3,a1,a1

a0,a0

a0,a3

a2

编码字典表如表3-12所示。

表3－12例3－14的编码字典表

若组成二元码，段号所需码长l1＝［lb7］＝3,即3位二进制数。m＝4,由式（3－43）得每个信源符号需用2位二进制数，即a0，a1，a2，a3编码分别为00，01，10，11。段号1～7编码分别为

000，001，010，011，100，101，110则信源序列对应编码序列为

0000000100100101101101100010010100001101110由上述编码方法可知，长为n的信源序列被分成了c段，每段二元码符号长度为l1＝［lbc］,每个信源符号二元码长l2＝［lbm］。每段所需二元符号的码长为［lbc］＋［lbm］，则c段所需二元码的码长为c（［lbc］+［lbm］）。所以每个信源符号所需码长L为

则

设长度为k的段有mk种。若把长度为n的序列分成c段后，设最大的段的长度为K,且所有长度小于或等于K的段型都存在，则有

(3－46)及

(3－47)当Ｋ→∞时，式（3－46）和式（3－47）可分别近似为

(3－48)(3－49)则

n≈Kc

(3－50)将式(3－50)代入式（3－45）,得

(3－51)现考虑平稳无记忆m元信源序列。设信源符号概率为pi(i＝0,1,…,m－1)。当最长的段长K→∞时，典型的段中ai将出现piK个。这种段型共有N种,则

(3－52)则

(3－53)忽略较短的段型，则

n＝NK＝K2KH(U)

(3－54)所以

C≈N≈2KH(U)

(3－55)将式（3－55）代入式（3－51）得

(3－56)所以当K→∞时,(3－57)3.4.3

LZW码

LZW算法首先用于UNIX等操作系统作为标准文件压缩命令，然后运用在数据通信系统，形成有专利保护的数据压缩工具。LZW算法已经作为一种通用压缩方法，广泛应用于任何二值数据的压缩。LZW压缩算法的基本思想是建立一个编码表(转换表)，韦尔奇称之为串表，该表将输入字符串映射成定长的码字输出，通常码长设为12bit。可以把数字图像当做一个一维比特串，算法在产生输出串的同时动态地更新编码表，这样码表与串表对应产生压缩信源的特殊性质。LZW编码形成经过了两个阶段：LZ编码和LZW编码。LZ码将变长的输入符号串映射成定长或长度可测的码字，LZ算法将长度不同的符号串(短语)编码成一个一个的新“单词”，它们形成了一本“短语词典”的索引。若单词的码字短于它所代表的短语，就达到