第5章_信源编码

1、第1页2021-11-25Department of Electronics and Information, NCUT Song Peng Song Peng5.1 最佳变长编码最佳变长编码5.2 编码的实现编码的实现5.3 编码方法简介编码方法简介5.7 LZ (Lempel-Ziv ) 码码5.8 LZW 码码第2页2021-11-25编码的目的编码的目的香农编码定理虽然指出了理想编码器的存在性，但是并香农编码定理虽然指出了理想编码器的存在性，但是并没有给出实用码的结构及构造方法；没有给出实用码的结构及构造方法；编码理论是为了解决这一问题而发展起来的科学理论；编码理论是为了解决这一问题而

2、发展起来的科学理论；编码的目的是为了优化通信系统，使这些指标达到最佳；编码的目的是为了优化通信系统，使这些指标达到最佳；通信系统的性能指标主要是有效性、可靠性、安全性和通信系统的性能指标主要是有效性、可靠性、安全性和经济性，除了经济性外，这些指标是信息论研究的对象。经济性，除了经济性外，这些指标是信息论研究的对象。按不同的编码目的，编码分为三类：信源编码、信道编按不同的编码目的，编码分为三类：信源编码、信道编码和安全编码（密码）。码和安全编码（密码）。引言第3页2021-11-25编码的目的编码的目的信源编码：信源编码：提高通信有效性为目的的编码。通过压缩信源的冗余度实提高通信有效性为目的的编

3、码。通过压缩信源的冗余度实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。增加，从而提高通信的有效性。信道编码：信道编码：提高信息传输的可靠性为目的的编码。通过增加信源的冗提高信息传输的可靠性为目的的编码。通过增加信源的冗余度实现。采用的一般方法是增大码率（带宽）。与信源编码正好相余度实现。采用的一般方法是增大码率（带宽）。与信源编码正好相反。反。保密编码：保密编码：提高通

4、信系统的安全性为目的的编码。通过加密和解密实提高通信系统的安全性为目的的编码。通过加密和解密实现。从信息论的观点出发，现。从信息论的观点出发，“加密加密”可视为增熵的过程，可视为增熵的过程，“解密解密”可可视为减熵的过程。视为减熵的过程。引言第4页2021-11-25信源编码概述信源编码概述(1) 信源编码的理论基础信源编码的理论基础信源编码理论是信息论的一个重要分支，其理论基信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。础是信源编码的两个定理。无失真信源编码定理：无失真信源编码定理：是离散信源是离散信源/ /数字信号编码的数字信号编码的基础；基础；限失真信源编码定理：限

5、失真信源编码定理：是连续信源是连续信源/ /模拟信号编码的模拟信号编码的基础。基础。引言第5页2021-11-25信源编码概述信源编码概述(2) 信源编码的分类信源编码的分类根据信源特性根据信源特性q离散信源编码：离散信源编码：独立信源编码，可做到无失真编码；独立信源编码，可做到无失真编码；q连续信源编码：连续信源编码：独立信源编码，只能做到限失真信源编码；独立信源编码，只能做到限失真信源编码；q相关信源编码：相关信源编码：非独立信源编码。非独立信源编码。根据压缩的特性根据压缩的特性q冗余度压缩编码：冗余度压缩编码：可逆压缩，经编译码后可以无失真地恢复。可逆压缩，经编译码后可以无失真地恢复。q

6、熵压缩编码：熵压缩编码：不可逆压缩。不可逆压缩。 引言第6页2021-11-25信源编码概述信源编码概述(3) 数据压缩概貌数据压缩概貌引言第7页2021-11-255.1 最佳变长编码最佳变长编码 根据信源编码理论，将能够荷载一定信息量且码字的平根据信源编码理论，将能够荷载一定信息量且码字的平均长度最短、可分离的变长码字集合称为最佳变长码。均长度最短、可分离的变长码字集合称为最佳变长码。最佳变长码编码的基本原则是：最佳变长码编码的基本原则是： 概率大的信源符号分概率大的信源符号分配短的码字，概率小的信源符号分配长的码字，从而使配短的码字，概率小的信源符号分配长的码字，从而使平均码长最短。平均

7、码长最短。 具有代表性的变长编码方法有香农码、具有代表性的变长编码方法有香农码、 费诺码和哈夫费诺码和哈夫曼码等。曼码等。 第8页2021-11-255.1.1 香农编码香农编码 设离散无记忆信源：设离散无记忆信源： 二进制香农码的编码步骤如下：二进制香农码的编码步骤如下：q 将信源符号按概率从大到小的顺序排列，令：将信源符号按概率从大到小的顺序排列，令： p(x1) p(x2) p(xn)q 令令 P(x1)=0，用，用 Pa(xj)，j=i+1 表示第表示第 i 个码字的累加概率，则：个码字的累加概率，则：q 确定满足下列不等式的整数确定满足下列不等式的整数 ki ，并令，并令 ki 为第

8、为第 i 个码字的长度个码字的长度log2 p(xi) ki 1 log2 p(xi)q 将将 Pa(xj) 用二进制表示，并取小数点后用二进制表示，并取小数点后 ki 位作为符号位作为符号 xi 的编码。的编码。 niininixpxpxpxpxpxxxxXPX121211)(,)(,),(,),(),(,)(10( )( ),1,2,jajiiP xp xjn5.1最佳变长编码第9页2021-11-255.1.1 香农编码香农编码例例5.1.1 ：有一单符号离散无记忆信源：有一单符号离散无记忆信源：对信源编二进制香农码。其编码过程如表对信源编二进制香农码。其编码过程如表5.1.1所示。所示

9、。计算出给定信源香农码的平均码长：计算出给定信源香农码的平均码长：若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用 3 个比特表示。相比较，香农编码对信源进行了压缩。个比特表示。相比较，香农编码对信源进行了压缩。由离散无记忆信源熵定义，可计算出信源上熵为：由离散无记忆信源熵定义，可计算出信源上熵为： 05. 010. 015. 020. 025. 025. 0,)(654321xxxxxxXPX)/(7 . 2505. 0410. 03)15. 02 . 0(2225. 0符号符号比特比特 K)/(42. 2)(log)(

10、)(612符符号号比比特特 iiixpxpXH5.1最佳变长编码第10页2021-11-255.1.1 香农编码香农编码例例5.1.1 ：对信源采用香农编码的信息率为：对信源采用香农编码的信息率为：编码效率为信源熵和信息率之比。则：编码效率为信源熵和信息率之比。则： 编码效率并不是很高。编码效率并不是很高。2, 17 . 22log17 . 2log22 mLmLKR这这里里%63.897 . 242. 2)( RXH ）量量（符符号号能能载载荷荷的的最最大大信信息息是是编编码码后后平平均均每每个个信信源源89.log2PmLKR 5.1最佳变长编码第11页2021-11-255.1.2 费诺

11、编码费诺编码将概率按从大到小的顺序排列，令：将概率按从大到小的顺序排列，令：p(x1) p(x2) p(xn)按编码进制数将概率分组，使每组概率尽可能接近或按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编相等。如编二进制码就分成两组，编 m 进制码就分成进制码就分成 m 组。组。给每一组分配一位码元。给每一组分配一位码元。将每一分组再按同样原则划分，重复步骤将每一分组再按同样原则划分，重复步骤 2 和和 3，直，直至概率不再可分为止。至概率不再可分为止。5.1最佳变长编码第12页2021-11-255.1.2 费诺编码费诺编码例例5.1.2A：设有一单符号离散信源

12、：设有一单符号离散信源对信源编二进制费诺码。编码过程如表对信源编二进制费诺码。编码过程如表5.1.2A。信源的熵为：信源的熵为： 04. 008. 016. 018. 022. 032. 0,)(654321xxxxxxXPX)/(35. 2)(log)()(612符符号号比比特特 iiixpxpXH5.1最佳变长编码第13页2021-11-25例例5.1.2A平均码长为：平均码长为：对信源采用费诺编码的信息率为：对信源采用费诺编码的信息率为：编码效率为：编码效率为：本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信

13、源。特别是对每次分组概率都相等的信源进行概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。编码时，可达到理想的编码效率。)/( 4 . 2)(61符符号号比比特特 iiikxpK2, 14 . 22log14 . 2log22 mLmLKR这里这里%92.974 . 235. 2)( RXH 5.1.2 费诺编码费诺编码5.1最佳变长编码第14页2021-11-255.1.2 费诺编码费诺编码例例5.1.2B：有一单符号离散无记忆信源：有一单符号离散无记忆信源对该信源编二进制费诺码，编码过程如表对该信源编二进制费诺码，编码过程如表5.1.2B。信源熵为：信源

14、熵为：H(X)=2.75(比特比特/符号符号)平均码长为：平均码长为：编码效率为编码效率为=1。之所以如此，因为每次所分两组的概率恰好相等。之所以如此，因为每次所分两组的概率恰好相等。 16/116/116/116/18/18/14/14/1,)(87654321xxxxxxxxXPX（比比特特符符号号）75. 2440625. 03212. 02)25. 025. 0( K5.1最佳变长编码第15页2021-11-255.1.3 哈夫曼编码哈夫曼编码(1) 将信源符号按概率从大到小的顺序排列，令：将信源符号按概率从大到小的顺序排列，令：p(x1) p(x2) p(xn)(2) 信源的第一次缩

15、减：给两个概率最小的信源符号信源的第一次缩减：给两个概率最小的信源符号 p(xn1) 和和 p(xn) 各分配一个码元各分配一个码元“0”和和“1”，将这两个信源符号合并成一个新符，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含个只包含 (n1) 个信源符号的新信源，用个信源符号的新信源，用 S1 表示。表示。(3) 将缩减信源将缩减信源 S1 的符号仍按概率从大到小顺序排列，重复步骤的符号仍按概率从大到小顺序排列，重复步骤 (2)，得到只含得到只含 (n2) 个符号的缩减信源个符号的缩减信

16、源 S2。(4) 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为符号的概率之和必为 1。然后从最后一级缩减信源开始，依编码路。然后从最后一级缩减信源开始，依编码路径向前返回，可得各信源符号所对应的码字。径向前返回，可得各信源符号所对应的码字。编码步骤：编码步骤：5.1最佳变长编码第16页2021-11-251. 二进制哈夫曼编码二进制哈夫曼编码例例5.1.3 对以下信源进行哈夫曼编码对以下信源进行哈夫曼编码 。在读取码字时，一定要从后向前读，此时编出来的码字才是可分在读取码字时，一定要从后向前读，此时编出来的码

17、字才是可分离的异前置码。若从前向后读取码字，则码字不可分离。离的异前置码。若从前向后读取码字，则码字不可分离。信源符号信源符号ai概率概率p(ai)码字码字Wi码长码长Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.01011145.1最佳变长编码第17页2021-11-251. 二进制哈夫曼编码二进制哈夫曼编码例例5.1.3 对以下信源进行哈夫曼编码对以下信源进行哈夫曼编码 。0.20 0.20 0.26 0.35 0.39 0.61 1.00.19 0.19 0.20 0.26 0.35 0.390.18 0

18、.18 0.19 0.20 0.260.17 0.17 0.18 0.190.15 0.15 0.170.10 0.110.010101010101010.200.190.180.170.150.100.011011000001010011001115.1最佳变长编码第18页2021-11-251. 二进制哈夫曼编码二进制哈夫曼编码例例5.1.3A 设单符号离散无记忆信源如下，要求对信源编二进制哈夫设单符号离散无记忆信源如下，要求对信源编二进制哈夫曼码。曼码。 04. 005. 006. 007. 01 . 01 . 018. 04 . 0,)(87654321xxxxxxxxXPX 在在读取

19、码字读取码字时，一定要从后时，一定要从后向前读，此时编向前读，此时编出来的码字才是出来的码字才是可分离的异前置可分离的异前置码。若从前向后码。若从前向后读取码字，则码读取码字，则码字不可分离。字不可分离。5.1最佳变长编码第19页2021-11-251. 二进制哈夫曼编码二进制哈夫曼编码例例5.1.3A信源熵为：信源熵为：平均码长为：平均码长为：编码效率为：编码效率为：若采用定长编码，码长若采用定长编码，码长 K=3，则编码效率：，则编码效率：哈夫曼的编码效率提高了哈夫曼的编码效率提高了 12.7%。)/(55. 2)(log)()(812符符号号比比特特 iiixpxpXH（比比特特符符号号

20、）61. 25)04. 005. 0(4)06. 007. 010. 0(3) 1 . 018. 0(14 . 0)(81 iiikxpK%7 .9761. 255. 2)()( KXHRXH %85355. 2 04. 005. 006. 007. 01 . 01 . 018. 04 . 0,)(87654321xxxxxxxxXPX5.1最佳变长编码第20页2021-11-251. 二进制哈夫曼编码二进制哈夫曼编码 注意：注意：哈夫曼的编法并不惟一。哈夫曼的编法并不惟一。q 每次对缩减信源两个概率最小的符号分配每次对缩减信源两个概率最小的符号分配“0”和和“1”码元是任码元是任意的，所以可

21、得到不同的码字。只要在各次缩减信源中保持码元意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。分配的一致性，即能得到可分离码字。q 不同的码元分配，得到的具体码字不同，但码长不同的码元分配，得到的具体码字不同，但码长 ki 不变，平均不变，平均码长也不变，所以没有本质区别；码长也不变，所以没有本质区别；q 缩减信源时，若合并后的新符号概率与其他符号概率相等，从缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同

22、的编法得到的码字长度正确的，但得到的码字不相同。不同的编法得到的码字长度 ki 也也不尽相同。不尽相同。5.1最佳变长编码第21页2021-11-251. 二进制哈夫曼编码二进制哈夫曼编码 例例5.1.3B ：单符号离散无记忆信源：单符号离散无记忆信源 用两种不同的方法对其编二进制哈夫曼码。用两种不同的方法对其编二进制哈夫曼码。方法一：方法一：合并后的新符号排在其它相同概率符号的后面。合并后的新符号排在其它相同概率符号的后面。 1 . 01 . 02 . 02 . 04 . 0,)(54321xxxxxXPX5.1最佳变长编码第22页2021-11-251. 二进制哈夫曼编码二进制哈夫曼编码

23、例例5.1.3B ：单符号离散无记忆信源：单符号离散无记忆信源 用两种不同的方法对其编二进制哈夫曼码。用两种不同的方法对其编二进制哈夫曼码。方法二：方法二：合并后的新符号排在其它相同概率符号的前面。合并后的新符号排在其它相同概率符号的前面。 1 . 01 . 02 . 02 . 04 . 0,)(54321xxxxxXPX5.1最佳变长编码第23页2021-11-251. 二进制哈夫曼编码二进制哈夫曼编码 例例5.1.3B ：单符号信源编二进制哈夫曼码，编码效率主要决定于信源熵和平单符号信源编二进制哈夫曼码，编码效率主要决定于信源熵和平均码长之比。对相同的信源编码，其熵是一样的，采用不同的方均

24、码长之比。对相同的信源编码，其熵是一样的，采用不同的方法，得到的平均码长可能不同。平均码长越短，编码效率就越高。法，得到的平均码长可能不同。平均码长越短，编码效率就越高。方法一的平均码长为：方法一的平均码长为：方法二的平均码长为：方法二的平均码长为：可见可见 ，本例两种方法的平均码长相同，所以编码效率相，本例两种方法的平均码长相同，所以编码效率相同。同。（比比特特符符号号） 5122 . 23) 1 . 01 . 0(2)2 . 02 . 04 . 0()(iiikxpK21KK （比特符号）（比特符号） 5112 . 24)1 . 01 . 0(32 . 022 . 014 . 0)(iii

25、kxpK5.1最佳变长编码第24页2021-11-251. 二进制哈夫曼编码二进制哈夫曼编码讨论：讨论：q码字长度的方差码字长度的方差2：长度长度 ki 与平均码长与平均码长 之差的平方的数学之差的平方的数学期望，即：期望，即：q方法一码字长度方差：方法一码字长度方差：q方法二码字长度方差：方法二码字长度方差： niiiiKkxpKkE1222)()( 36. 1)2 . 24)(1 . 01 . 0()2 . 23(2 . 0)2 . 22(2 . 0)2 . 21(4 . 0222221 16. 0)2 . 23)(1 . 01 . 0()2 . 22)(2 . 02 . 04 . 0(2

26、222 哪种方哪种方法更好？法更好？K5.1最佳变长编码第25页2021-11-251. 二进制哈夫曼编码二进制哈夫曼编码比较：比较：第二种编码方法的码长方差要小许多。第二种编码方法的码第二种编码方法的码长方差要小许多。第二种编码方法的码长变化较小，比较接近于平均码长。长变化较小，比较接近于平均码长。q第一种方法编出的第一种方法编出的 5 个码字有个码字有 4 种不同的码长；种不同的码长；q第二种方法编出的码长只有两种不同的码长；第二种方法编出的码长只有两种不同的码长；q第二种编码方法更简单、更容易实现，所以更好。第二种编码方法更简单、更容易实现，所以更好。结论结论：在哈夫曼编码过程中，对缩减

27、信源符号按概率由大到小的顺在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。可使合并后的新符号重复编码次数减少，使短码得到充分利用。哈夫曼码是用概率匹配方法进行信源编码。哈夫曼码是用概率匹配方法进行信源编码。q 哈夫曼码的编码方法保证了概率大的符号对应于短码，概率哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；小的符号对应于长码，充分利用了短码；q 缩减信源的最后二个码字总是最后一位

28、不同，从而保证了哈缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。夫曼码是即时码。5.1最佳变长编码第26页2021-11-252. m 进制哈夫曼编码进制哈夫曼编码(1) “全树全树”概念概念定义：定义：码树图中每个中间节点后续的枝数为码树图中每个中间节点后续的枝数为 m 时称为全树；若有时称为全树；若有些节点的后续枝数不足些节点的后续枝数不足 m，就称为非全树。，就称为非全树。二进制码不存在非全树的情况，因为后续枝数是二进制码不存在非全树的情况，因为后续枝数是 1 时，这个枝就时，这个枝就可以去掉使码字长度缩短。可以去掉使码字长度缩短。m 进制编码：进制编码：若所有码字

29、构成全树，可分离的码字数（信源个数）若所有码字构成全树，可分离的码字数（信源个数）必为必为 n=m+q(m1)。q为信源缩减次数。为信源缩减次数。若信源所含的符号数若信源所含的符号数 n 不能构成不能构成 m 进制全树，必须增加进制全树，必须增加 s 个不用个不用的码字形成全树。显然的码字形成全树。显然 s0(i=1,2, ,n)信源符号的累积分布函数为：信源符号的累积分布函数为： 所得累积分布函数为每台级的下界值，则其区间为所得累积分布函数为每台级的下界值，则其区间为 0,1) 左闭左闭右开区间。右开区间。 F(a1)=0 F(a2)=P(a1) F(a3)=P(a1)+P(a2) 当当 A

30、=0,1二元信源时：二元信源时： F(0)=0 F(1)=P(0),()()(11AaaaPaFkikiik 算术编码第54页2021-11-252. 累积分布函数累积分布函数 F(s) 及对应的区间及对应的区间 计算二元无记忆信源序列的累积分布函数计算二元无记忆信源序列的累积分布函数q 初始时：在初始时：在 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) 的宽度为：的宽度

31、为：A(1)= P(1)，对应于信源，对应于信源符号符号“1”； 若输入符号序列的第一个符号为若输入符号序列的第一个符号为 s=“0”，落入，落入0,F(1)区间，得累积分布函数区间，得累积分布函数 F(s=“0”)= F(0)=0； 图示算术编码第55页2021-11-252. 累积分布函数累积分布函数 F(s) 及对应的区间及对应的区间 计算二元无记忆信源序列的累积分布函数计算二元无记忆信源序列的累积分布函数q 输入第二个符号为输入第二个符号为“1”，s s=“01” s s=“01”所对应的区间是在区间所对应的区间是在区间 0,F(1) 中进行分割；中进行分割； 符号序列符号序列“00”

32、对应的区间宽度为：对应的区间宽度为： A(00)=A(0)P(0)=P(0)P(0)=P(00) 对应的区间为：对应的区间为：0,F(s s=“01”) 符号序列符号序列“01”对应的区间宽度为：对应的区间宽度为： A(01)=A(0)P(1)=P(0)P(1)=P(01) 对应的区间为：对应的区间为：F(s s=“01”),F(1) 累积分布函数累积分布函数 ：F(s s=“01”)=P(0)P(0)= P(00)图示算术编码第56页2021-11-252. 累积分布函数累积分布函数 F(s) 及对应的区间及对应的区间 计算二元无记忆信源序列的累积分布函数计算二元无记忆信源序列的累积分布函数

33、q 输入第三个符号为输入第三个符号为“1”： 输入序列可记做输入序列可记做 s s1=“011” ，对应的区间是对区间，对应的区间是对区间 F(s s),F(1) 进行分割；进行分割； 序列序列 s s0=“010” 对应的区间宽度为：对应的区间宽度为： A(s s=“010”)=A(s s=“01”) P(0)=A(s s) P(0) 其对应的区间为：其对应的区间为：F(s s), F(s s)+ A(s s) P(0) 序列序列 s s1=“011” 对应的区间宽度为：对应的区间宽度为：A(s s=“011”)=A(s s) P(1) 其对应的区间为：其对应的区间为：F(s s)+A(s

34、s) P(0),F(1) 符号序列符号序列 s s1=“011”的累积分布函数为：的累积分布函数为：F(s s1)=F(s s)+A(s s) P(0) 若第三个符号输入为若第三个符号输入为“0”，符号序列，符号序列s s0=“010”的区间下界值仍的区间下界值仍为为F(s s)，得符号序列，得符号序列 s s0=“010”的累积分布函数为的累积分布函数为F(s s0)=F(s s)。图示算术编码第57页2021-11-252. 累积分布函数累积分布函数 F(s) 及对应的区间及对应的区间 计算二元无记忆信源序列的累积分布函数计算二元无记忆信源序列的累积分布函数q 归纳归纳 当已知前面输入符号

35、序列为当已知前面输入符号序列为 s s，若接着再输入一个符号，若接着再输入一个符号“0”，序列序列 s s0 的累积分布函数为：的累积分布函数为：F(s s0)=F(s s) 对应区间宽度为：对应区间宽度为：A(s s0)=A(s s) P(0) 若接着输入的一个符号是若接着输入的一个符号是“1”，序列的累积分布函数为：，序列的累积分布函数为：F(s s1)=F(s s)+A(s s) P(0) 对应区间宽度为：对应区间宽度为：A(s s1)=A(s s) P(1)图示算术编码第58页2021-11-252. 累积分布函数累积分布函数 F(s) 及对应的区间及对应的区间 计算二元无记忆信源序列

36、的累积分布函数计算二元无记忆信源序列的累积分布函数q 归纳归纳 符号序列对应的区间宽度符号序列对应的区间宽度 A(s s=“0”)=P(0) A(s s=“1”)=1A(0)=P(1) A(s s=“00”)=P(00)=A(0)P(0)=P(0)P(0) A(s s=“01”)=P(01)=A(0)P(1)=P(0)P(1) A(s s=“10”)=P(10)=A(1)P(0)=P(1)P(0) A(s s=“11”)=P(11)= A(1)P(1)=P(1)P(1) A(s s=“010”)=A(01)P(0)=P(01)P(0)P(010) A(s s=“011”)=A(01)P(1)=

37、P(01)P(1)=P(011) 信源符号序列信源符号序列 s s 所对应区间的宽度等于符号序列所对应区间的宽度等于符号序列 s s 的概率的概率 P(s s)。)()(ssPA算术编码第59页2021-11-253. 信源序列累积分布函数的递推公式信源序列累积分布函数的递推公式算术编码二元信源符号序列的累积分布函数的递推公式二元信源符号序列的累积分布函数的递推公式qF(s sr)=F(s s)+P(s s) F(r) (r=0,1)s sr 表示已知前面信源符号序列为表示已知前面信源符号序列为 s s，接着再输入符号为，接着再输入符号为 rF(0)=0， F(1)=P(0)F(s s0)=F

38、(s s)F(s s1)=F(s s)+P(s s) F(1)= F(s s)+P(s s) P(0)qA(s sr)=P(s sr)=P(s s) P(r) (r=0,1) A(s s0)=P(s s0)=P(s s) P(0) A(s s1)=P(s s1)=P(s s) P(1)第60页2021-11-25例例1：已输入二元符号序列为已输入二元符号序列为 s s=“011”，接着再输入符，接着再输入符号为号为“1”，得序列累积分布函数为：，得序列累积分布函数为： F(s s1)=F(0111)=F(s s=“011”)+P(011) P(0) =F(s s=“01”)+P(01) P(0

39、)+P(011) P(0) =F(s s=“0”)+P(0) P(0) +P(01) P(0)+P(011) P(0) =0+P(00)+P(010)+P(0110) 对应的区间宽度为：对应的区间宽度为： A(s s1)=P(s s=“011”) P(1)=P(011)P(1)=P(0111) F(s s1)=F(s s)+P(s s) P(0)A(s s1)=P(s s1)=P(s s) P(1)3. 信源序列累积分布函数的递推公式信源序列累积分布函数的递推公式图示算术编码第61页2021-11-25上述整个分析过程可用下图描述上述整个分析过程可用下图描述3. 信源序列累积分布函数的递推公式

40、信源序列累积分布函数的递推公式) 1 ()() 1() 1()0()()0()0()0()()() 1()()0(PPPAPPPAPPFFFFsssssssssss图示返回算术编码第62页2021-11-25在实际中，只需两个存储器，把在实际中，只需两个存储器，把 P(s s) 和和 F(s s) 存下来，存下来，然后，根据输入符号和递推公式更新两个存储器中的数然后，根据输入符号和递推公式更新两个存储器中的数值。因此在编码过程中，每输入一个符号要进行乘法和值。因此在编码过程中，每输入一个符号要进行乘法和加法运算，所以称为算术编码。加法运算，所以称为算术编码。递推公式如下：递推公式如下：F(s

41、sr)=F(s s)+P(s s) F(r) (r=0,1)A(s sr)=P(s sr)=P(s s) P(r) (r=0,1)3. 信源序列累积分布函数的递推公式信源序列累积分布函数的递推公式算术编码第63页2021-11-25 通过关于信源符号序列的累积分布函数的计算，把区间分割通过关于信源符号序列的累积分布函数的计算，把区间分割成许多小区间，不同的信源符号序列对应不同的区间成许多小区间，不同的信源符号序列对应不同的区间 。可取小区。可取小区间内的一点来代表这序列。间内的一点来代表这序列。编码方法：编码方法：将符号序列的累积分布函数写成二进位的小数，取将符号序列的累积分布函数写成二进位的

42、小数，取小数点后小数点后 k 位，若后面有尾数，就进位到第位，若后面有尾数，就进位到第 k 位，这样得到的一位，这样得到的一个数个数 C C，并使，并使 k 满足：满足：举例：举例：4. 算术编码方法算术编码方法 。的码字为的码字为得符号序列得符号序列设设整数整数代表大于或等于的最小代表大于或等于的最小kkkzzzzzzzPk21212,1 , 0. 0)(1logs sC Cs s 。的的码码字字为为，得得则则110110. 0371)(10110001. 0)(s sC Cs ss s kPF算术编码第64页2021-11-25 编码效率编码效率q 算术编码的编码效率很高。当信源符号序列很

43、长时，算术编码的编码效率很高。当信源符号序列很长时，L 很大时，很大时，平均码长接近信源的熵。平均码长接近信源的熵。 mLKRLSHRLKSH2log1)()(4. 算术编码方法算术编码方法)()(1)()(1)(log)()()()(log)()(1logsss222SLHSHLLSHLKLSHPPkPKPPPkLLL 若若信信源源是是无无记记忆忆，：平平均均每每个个符符号号的的码码长长为为得得：由由于于s ss ss ss ss ss ss s算术编码第65页2021-11-25译码就是一系列比较过程，每一步比较译码就是一系列比较过程，每一步比较 C CF(s s) 与与 P(s s)P(

44、0)。 F(s s0)=F(s s) F(s s1)=F(s s)+P(s s) P(0) s s前面已译出的序列串前面已译出的序列串 P(s s)序列串序列串 s s 对应的宽度对应的宽度F(s s) 是序列串是序列串 s s 的累积分布函数，即为的累积分布函数，即为 s s 对应区间的下界；对应区间的下界；P(s s)P(0) 是此区间内下一个输入为符号是此区间内下一个输入为符号“0”所占的子区间宽度；所占的子区间宽度；若若 C CF(s s)P(s s)P(0) 则译输出符号为则译输出符号为“1”。5. 算术编码的译码算术编码的译码算术编码第66页2021-11-255. 算术编码的译码

45、算术编码的译码算术编码n 例例2 设二元独立信源设二元独立信源 010.250.75Up求信源序列求信源序列S=1010的算术编码。的算术编码。 信源信源序列序列1010算术编码的相关数据算术编码的相关数据如下表所如下表所示。示。 解：解： 信源符号的积累概率信源符号的积累概率F(0)0；F(1)0.25,序列序列F(S)p(S)L序列码字序列码字01010.010.1111100.010.001130101010.0100110.001001301110100.0100110.00001001501010第67页2021-11-255. 算术编码的译码算术编码的译码算术编码010.250.7

46、5Up信源信源序列序列1010算术编码算术编码的过程如下。的过程如下。 （1）设设()0F ()1p （2）输入信源序列的第一个符号）输入信源序列的第一个符号1： 2( 1)()() (1)0 1 0.250.25(0.01)FFpF 2( 1)() (1)1 0.750.75(0.11)ppp （3）输入信源序列的第二个符号）输入信源序列的第二个符号0： 2(10)(1)(1) (0)0.250 0.750.25(0.01)FFpF 2(10)(1) (0)0.75 0.250.1875(0.0011)ppp（4）输入信源序列的第三个符号）输入信源序列的第三个符号1： 2222(101)(1

47、0)(10) (1)(0.01)(0.0011)(0.01)(0.010011)FFpF222(101)(10) (1)(0.0011)(0.11)(0.001001)ppp（5）输入信源序列的第四个符号）输入信源序列的第四个符号0： 2(1010)(101)(101) (0)(0.010011)FFpF2(1010)(101) (0)(0.00001001)ppp第68页2021-11-255. 算术编码的译码算术编码的译码算术编码信源序列信源序列1010的算术编码图解的算术编码图解 F(0)F(1)p(0)p(1)00.010.11F(10)F(11)p(10)p(11)0.010.011

48、1F(100)F(101)p(100)p(101)0.010 011F(1010)F(1011)p(1010)p(1011)0.010 0110.010 100.01110.01110.010.011010.250.75Up序列序列F(S)p(S)L序列码字序列码字01010.010.1111100.010.001130101010.0100110.001001301110100.0100110.00001001501010第69页2021-11-255. 算术编码的译码算术编码的译码算术编码例例3 离散无记忆信源离散无记忆信源X的概率空间为的概率空间为12341111( )2488aaaaX

49、p x信源输出符号序列信源输出符号序列a2a3a1a2，描述算术编码，描述算术编码实现的过程实现的过程。 (2) 对第二个符号对第二个符号x2=a3进行编码，得到进行编码，得到 C2=C1+A1P3=0.5+0.250.75=0.6875 A2=A1p3=0.250.125=0.031 25解解: 首先计算条件累计概率首先计算条件累计概率P3=p1+p2=0.5+0.25=0.75 P4=p1+p2+p3=0.5+0.25+0.125=0.875P1=0 P2=p1=0.5 令令C0=0（ ），A0=1（ ）。 (1) 对第一个符号对第一个符号x1=a2进行编码，得到进行编码，得到C1=C0+

50、A0P2=P2=0.5 A1=A0p2=p2=0.25()0F ()1p 4()log0.0039062588lb A 第70页2021-11-255. 算术编码的译码算术编码的译码算术编码(6) 因为因为C4=0.101 100 10， 取小数点后面取小数点后面8位二进制数据作为输出码字。位二进制数据作为输出码字。(3) 对第三个符号对第三个符号x3=a1进行编码，得到进行编码，得到C3=C2+A2P1=0.6875+0.031 250=0.6875 A3=A2p1=0.031 250.5=0.015 625(5) 求码长：求码长：(4) 对第三个符号对第三个符号x4=a2进行编码，得到进行

51、编码，得到 C4=C3+A3P2=0.6875+0.015 6250.5=0.695 312 5=(0.10110010)2 A4=A3p2=0.015 6250.25=0.003 906 25W=10110010整个编码过程用下图表示。整个编码过程用下图表示。 第71页2021-11-255. 算术编码的译码算术编码的译码算术编码译码：译码：(1)010.50.75 0.875a1a2a3a440.69531250.5,0.75)C 译为译为a2；(2)0.69531250.50.781250.75,0.875)0.25译为译为a3；用符号用符号a2对应区间的长度去除码字与符号对应区间的长度

52、去除码字与符号a2的的左端点值的差，即左端点值的差，即(3)0.781250.750.250,0.5)0.125译为译为a1；用符号用符号a3对应区间的长度去除码字与符号对应区间的长度去除码字与符号a3的的左端点值的差，即左端点值的差，即(4)0.2500.50.5,0.75)0.5译为译为a2；用符号用符号a1对应区间的长度去除码字与符号对应区间的长度去除码字与符号a1的的左端点值的差，即左端点值的差，即码字码字10110010（0.6953125）对应的序列为对应的序列为a2 a3 a1a2。第72页2021-11-25例例4：有四个符号：有四个符号a，b，c，d构成简单序列构成简单序列S

53、abda，各符号及其，各符号及其对应概率如下表，算术编解码过程如下：对应概率如下表，算术编解码过程如下：5. 算术编码的译码算术编码的译码算术编码符号符号符号概率符号概率pi符号累积概率符号累积概率Pja0.100(1/2)0.000b0.010(1/4)0.100c0.001(1/8)0.110d0.001(1/8)0.111设起始状态为空设起始状态为空序列序列，则，则A()1，C()0。1 . 01 . 01)()(0010)()()(aapAaAPACaC001. 001. 01 . 0)()(01. 01 . 01 . 00)()()(bbpaAabAPaAaCabC第73页2021-

54、11-255. 算术编码的译码算术编码的译码算术编码()()()0.01 0.001 0.1110.010111()()0.001 0.0010.000001ddC abdC abA ab PA abdA ab p()()()0.0101110.000001 00.010111()()0.000001 0.10.0000001aaC abdaC abdA abd PA abdaA abd pL=7，C(abda)即为编码后的码字即为编码后的码字0101110。 711111( )( ) ( ) ( ) ( )24822p Sp a p b p d p a7log( )log27Lp S 第74

55、页2021-11-255. 算术编码的译码算术编码的译码算术编码译码译码 C(abda)=0.0101110.1 0，0.1 ，第一个符号为，第一个符号为 a。 放大至放大至0,1(pa-1)： C(abda)210.10111 0.1，0.110 ，第二个符号为第二个符号为 b。去掉累积概率去掉累积概率Pb： 0.10111-0.1=0.00111 放大至放大至0，1(p b-1)： 0.0011122=0.111 0.111，1 ， 第三个符号为第三个符号为 d 。去掉累积概率去掉累积概率Pd： 0.111-0.111=0 放大至放大至0，1(p d-1)：0240 0，0.1 ，第四个符

56、号为第四个符号为 a。 第75页2021-11-255. 算术编码的译码算术编码的译码算术编码A( ) A(a) a b c d A(a,b) a b c da b c dA(a,b,d)C( ) 0(Pa) pa Pb pb Pc pc Pd pd 1C(0)C(a,b,d)C(a,b)算术编码过程算术编码过程第76页2021-11-25例例5：设二元无记忆信源：设二元无记忆信源 S=0,1，其，其 P(0)=1/4，P(1)=3/4。对二元。对二元序列序列11111100 做算术编码。做算术编码。解解：P(s s=11111100)=P2(0)P6(1)=(1/4)2(3/4)6 F(s

57、sr)=F(s s)+P(s s) F(r) F(s s0)=F(s s) F(s s1)=F(s s)+P(s s) F(1)= F(s s)+P(s s) P(0) F(s s)=P(0)+P(1)P(0)+P(1)2P(0)+P(1)3P(0)+P(1)4P(0)+P(1)5P(0) =0.82202=0.110100100111 得得 C C0.1101010 得得 s s 的码字为的码字为 1101010。 编码效率：编码效率：7) s (1log2 Pk5. 算术编码的译码算术编码的译码%7 .928/7811. 0)()( LKsHRsH 算术编码第77页2021-11-25举例

58、：举例：5. 算术编码的译码算术编码的译码) 1 ()() 1() 1()0()()0()0()0()()() 1()()0(PPPAPPPAPPFFFFs ss ss ss ss ss ss ss ss ss ss s 算术编码第78页2021-11-255.4 变换编码变换编码为了提高编码效率，同时降低编码复杂度，可以对信源输出的数据为了提高编码效率，同时降低编码复杂度，可以对信源输出的数据进行变换，以去除数据之间的相关性，即将数据之间的相关冗余变进行变换，以去除数据之间的相关性，即将数据之间的相关冗余变换为系数之间的统计冗余。换为系数之间的统计冗余。 由于变换后的系数相关性减弱，因此可以

59、使用简单编码算法实现高由于变换后的系数相关性减弱，因此可以使用简单编码算法实现高效率的数据压缩。效率的数据压缩。正交变换可以保持熵的不变性。如果变换后的系数是整型的，则不正交变换可以保持熵的不变性。如果变换后的系数是整型的，则不会损失任何信息。会损失任何信息。 但是一般情况下，变换后的系数是浮点的，就需但是一般情况下，变换后的系数是浮点的，就需要对系数进行量化，得到整型系数，然后再进行编码。要对系数进行量化，得到整型系数，然后再进行编码。变换的目变换的目是为了去除信源输出数据之间的相关性，或者说是将数据是为了去除信源输出数据之间的相关性，或者说是将数据之间的相关冗余映射为系数之间的统计冗余，从

60、而降低系统编码复之间的相关冗余映射为系数之间的统计冗余，从而降低系统编码复杂度，提高编码效率。杂度，提高编码效率。 第79页2021-11-255.4.1 变换的基本原理变换的基本原理变换编码 设信源输出一个一维消息设信源输出一个一维消息U(u1，u2，un)，经变换后输出，经变换后输出为为X(x1，x2，xn)， 故有：故有： XPU 由正交性由正交性 A T AA 1 AI，则有：，则有： UP 1XP T X 式中：式中： P实正交变换矩阵；实正交变换矩阵； P T 矩阵矩阵P的转置矩阵；的转置矩阵； P 1矩阵矩阵P的逆矩阵；的逆矩阵； I单位矩阵。单位矩阵。 如果经正交变换后，只传送