信息论与编码原理第6章信源编码.ppt

信息论与编码原理（第六章）（第六章）信源编码信源编码2/15/20231Department of Electronics and Information,NCUT Song Peng第六章第六章 信源编码信源编码6.1 引引 言言6.2 香农编码香农编码6.3 费诺编码费诺编码6.4 哈夫曼编码哈夫曼编码6.8 LZW 码码6.7 LZ 码码6.6 算术编码算术编码6.5 游程编码游程编码6.9 信源编码总结信源编码总结2/15/20232Department of Electronics and Information,NCUT Song Peng6.1 引引 言言6.1.1 编码的目的编码的目的6.1.2 信源编码概论信源编码概论2/15/20233Department of Electronics and Information,NCUT Song Peng6.1.1 编码的目的编码的目的香农编码定理虽然指出了理想编码器的存在性，但是并没香农编码定理虽然指出了理想编码器的存在性，但是并没有给出实用码的结构及构造方法；有给出实用码的结构及构造方法；编码理论正是为了解决这一问题而发展起来的科学理论；编码理论正是为了解决这一问题而发展起来的科学理论；编码的目的是为了编码的目的是为了优化通信系统优化通信系统，使这些指标达到最佳；，使这些指标达到最佳；通信系统的性能指标主要是通信系统的性能指标主要是有效性有效性、可靠性可靠性、安全性安全性和和经经济性济性，除了经济性外，这些指标正是信息论研究的对象。，除了经济性外，这些指标正是信息论研究的对象。按不同的编码目的，编码分为三类：按不同的编码目的，编码分为三类：信源编码信源编码、信道编码信道编码和和安全编码安全编码（密码）。（密码）。6.1引言2/15/20234Department of Electronics and Information,NCUT Song Peng6.1.1 编码的目的编码的目的信源编码：信源编码：提高通信有效性提高通信有效性为目的的编码。通常通过压缩为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是信源的冗余度来实现。采用的一般方法是压缩压缩 每个信源每个信源符号的符号的平均比特数平均比特数或信源的或信源的码率码率。即同样多的信息用较少。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。提高通信的有效性。信道编码：信道编码：提高信息传输的可靠性提高信息传输的可靠性为目的的编码。通常通为目的的编码。通常通过过增加增加 信源的信源的冗余度冗余度来实现。采用的一般方法是来实现。采用的一般方法是增大码增大码率（带宽）率（带宽）。与信源编码正好相反。与信源编码正好相反。保密编码：保密编码：提高通信系统的安全性提高通信系统的安全性为目的的编码。通常通为目的的编码。通常通过过加密加密和和解密解密来实现。从信息论的观点出发，来实现。从信息论的观点出发，“加密加密”可可视为增熵的过程，视为增熵的过程，“解密解密”可视为减熵的过程。可视为减熵的过程。返回目录6.1引言2/15/20235Department of Electronics and Information,NCUT Song Peng6.1.2 信源编码概述信源编码概述(1)信源编码的理论基础信源编码的理论基础信源编码理论是信息论的一个重要分支，其理论基础是信信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。源编码的两个定理。无失真信源编码定理：无失真信源编码定理：是离散信源是离散信源/数字信号编码的基础；数字信号编码的基础；限失真信源编码定理：限失真信源编码定理：是连续信源是连续信源/模拟信号编码的基础。模拟信号编码的基础。6.1引言2/15/20236Department of Electronics and Information,NCUT Song Peng6.1.2 信源编码概述信源编码概述(2)信源编码的分类信源编码的分类根据信源特性根据信源特性q离散信源编码：离散信源编码：独立信源编码，可做到无失真编码；独立信源编码，可做到无失真编码；q连续信源编码：连续信源编码：独立信源编码，只能做到限失真信源编码；独立信源编码，只能做到限失真信源编码；q相关信源编码：相关信源编码：非独立信源编码。非独立信源编码。根据压缩的特性根据压缩的特性q冗余度压缩编码：冗余度压缩编码：可逆压缩，经编译码后可以无失真地恢复。可逆压缩，经编译码后可以无失真地恢复。q熵压缩编码：熵压缩编码：不可逆压缩。不可逆压缩。6.1引言2/15/20237Department of Electronics and Information,NCUT Song Peng6.1.2 信源编码概述信源编码概述(3)数据压缩概貌数据压缩概貌KLT：Karhunen-Loeve TransformDCT：Discrete Cosine TransformDST：Discrete Sinusoid TransformDFT：Discrete Fourier TransformWHT：Walsh-Hadamard TransformSLT：Slant TransformHAAR：Haar TransformLPC-10：Government Standard Linear Predictive Coding Algorithm:LPC-10MELP：Mixed Excited Linear Predictive CodingCELP：Codebook Excited Linear Predictive Coding ACELP：Algebraic Cocebook Excitation LPCQCELP：Qualcom Cocebook Excitation LPCEVRC：Enhanced Variable Rate CodecLD-CELP：Low Delay-CELP28 种6.1引言2/15/20238Department of Electronics and Information,NCUT Song Peng6.1.2 信源编码概述信源编码概述(3)数据压缩概貌数据压缩概貌CS-ACELP：Conjugate-Structure Algebraic CELPVSELP：Vector Sum Excitation LPC RPE-LT：Long Time Predictive Regular-Pulse Excitation LPCMPLPC：Multi-Pulse Excitation LPC MP-MLQ：Multipulse Maximum Likelihood QuantizationMBE：Multi-Band Excitation Speech CoderSTC：Sinusoid Transform CocingCVSD：Continuously Variable Slope Delta ModulatorSB-ADPCM：Sub-Band Adaptive Differential Pulse Code Modulation PTC：PictureTel Transform CoderAC-2；AC-3：Digital Audio Compression Standard，美国，美国 Dolby公司公司AAC：Advanced Audio Coding,日本日本138187,MPEG-2 MUSICAM：Masking Pattern Adapted Universal Subband Integrated Coding and MultiplexingATRAC：Adaptive Transform Acoustic Coder6.1引言2/15/20239Department of Electronics and Information,NCUT Song Peng6.1.2 信源编码概述信源编码概述(3)数据压缩概貌数据压缩概貌6.1引言2/15/202310Department of Electronics and Information,NCUT Song Peng6.1.2 信源编码概述信源编码概述 有些编码原理和技术在通信原理和信号处理等相关课有些编码原理和技术在通信原理和信号处理等相关课程中已经介绍过。例如：程中已经介绍过。例如：返回目录连续信源编码：连续信源编码：脉冲编码调制脉冲编码调制(PCM)、矢量量化技术、矢量量化技术相关信源编码：相关信源编码：预测编码：预测编码：增量编码、差分脉冲调制增量编码、差分脉冲调制(DPCM)、自、自适应差分脉冲调制适应差分脉冲调制(ADPCM)、线性预测声码器；、线性预测声码器；变换编码：变换编码：KL 变换、离散变换、子带编码、小变换、离散变换、子带编码、小波变换。波变换。6.1引言2/15/202311Department of Electronics and Information,NCUT Song Peng6.2 香农编码香农编码 设离散无记忆信源：设离散无记忆信源：二进制香农码的编码步骤如下：二进制香农码的编码步骤如下：q 将信源符号按概率从大到小的顺序排列，为方便起见，令：将信源符号按概率从大到小的顺序排列，为方便起见，令：p(x1)p(x2)p(xn)q 令令 p(x0)=0，用，用 pa(xj)，j=i+1 表示第表示第 i 个码字的个码字的累加概率累加概率，则：，则：2/15/202312Department of Electronics and Information,NCUT Song Peng6.2 香农编码香农编码 设离散无记忆信源：设离散无记忆信源：二进制香农码的编码步骤如下：二进制香农码的编码步骤如下：q 确定满足下列不等式的整数确定满足下列不等式的整数 ki，并令，并令 ki 为第为第 i 个码字的长度个码字的长度log2 p(xi)ki 1 log2 p(xi)q 将将 pa(xj)用二进制表示，并取小数点后用二进制表示，并取小数点后 ki 位作为符号位作为符号 xi 的编码。的编码。2/15/202313Department of Electronics and Information,NCUT Song Peng6.2 香农编码香农编码例例6.1.1：有一单符号离散无记忆信源：有一单符号离散无记忆信源：对该信源编二进制香农码。其编码过程如表对该信源编二进制香农码。其编码过程如表5.2.1 所示。所示。2/15/202314Department of Electronics and Information,NCUT Song Peng6.2 香农编码香农编码例例6.1.1：计算出给定信源香农码的平均码长：计算出给定信源香农码的平均码长：若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用 3 个比特表示。相比较，香农编码对信源进行了压缩。个比特表示。相比较，香农编码对信源进行了压缩。2/15/202315Department of Electronics and Information,NCUT Song Peng6.2 香农编码香农编码例例6.1.1：由离散无记忆信源熵定义，可计算出信源上熵为：由离散无记忆信源熵定义，可计算出信源上熵为：对上述信源采用香农编码的信息率为：对上述信源采用香农编码的信息率为：编码效率为信源熵和信息率之比。则：编码效率为信源熵和信息率之比。则：可以看出，编码效率并不是很高。可以看出，编码效率并不是很高。返回目录2/15/202316Department of Electronics and Information,NCUT Song Peng6.3 费诺编码费诺编码将概率按从大到小的顺序排列，令：将概率按从大到小的顺序排列，令：p(x1)p(x2)p(xn)按编码进制数将概率分组，使每组概率尽可能接近或相按编码进制数将概率分组，使每组概率尽可能接近或相等。如等。如编二进制码就分成两组，编二进制码就分成两组，编编 m 进制码就分成进制码就分成 m 组。组。给每一组分配一位码元。给每一组分配一位码元。将每一分组再按同样原则划分，重复步骤将每一分组再按同样原则划分，重复步骤 2 和和 3，直至，直至概率不再可分为止。概率不再可分为止。2/15/202317Department of Electronics and Information,NCUT Song Peng6.3 费诺编码费诺编码例例6.3.1：设有一单符号离散信源：设有一单符号离散信源对该信源编二进制费诺码。编码过程如表对该信源编二进制费诺码。编码过程如表。2/15/202318Department of Electronics and Information,NCUT Song Peng6.3 费诺编码费诺编码例例6.3.1该信源的熵为：该信源的熵为：平均码长为：平均码长为：对上述信源采用费诺编码的信息率为：对上述信源采用费诺编码的信息率为：编码效率为：编码效率为：本例中费诺编码有较高的编码效率。费诺码比较适合于本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概每次分组概率都很接近率都很接近的信源。特别是对每次的信源。特别是对每次分组概率都相等分组概率都相等的信源进行编码的信源进行编码时，可达到理想的编码效率。时，可达到理想的编码效率。2/15/202319Department of Electronics and Information,NCUT Song Peng6.3 费诺编码费诺编码例例6.3.2：有一单符号离散无记忆信源：有一单符号离散无记忆信源对该信源编二进制费诺码，编码过程如表。对该信源编二进制费诺码，编码过程如表。2/15/202320Department of Electronics and Information,NCUT Song Peng6.3 费诺编码费诺编码例例5.3.2信源熵为：信源熵为：H(X)=2.75(比特比特/符号符号)平均码长为：平均码长为：编码效率为编码效率为=1。之所以如此，因为每次所分两组的概率恰好相等。之所以如此，因为每次所分两组的概率恰好相等。返回目录2/15/202321Department of Electronics and Information,NCUT Song Peng6.4 哈夫曼编码哈夫曼编码 哈夫曼哈夫曼(Huffman)编码是一种效率比较高的变长无失编码是一种效率比较高的变长无失真信源编码方法。真信源编码方法。6.4.1 编码步骤编码步骤6.4.2 二进制哈夫曼编码二进制哈夫曼编码6.4.3 m 进制哈夫曼编码进制哈夫曼编码2/15/202322Department of Electronics and Information,NCUT Song Peng6.4.1 编码步骤编码步骤(1)将信源符号按概率从大到小的顺序排列，令：将信源符号按概率从大到小的顺序排列，令：p(x1)p(x2)p(xn)(2)信源的第一次缩减信源：信源的第一次缩减信源：给两个概率最小的信源符号给两个概率最小的信源符号 p(xn1)和和 p(xn)各分配一个码位各分配一个码位“0”和和“1”，将这两个信源符号合并成一个，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含一个只包含(n1)个信源符号的新信源，用个信源符号的新信源，用 S1 表示。表示。(3)将缩减信源将缩减信源 S1 的符号仍按概率从大到小顺序排列，重复步骤的符号仍按概率从大到小顺序排列，重复步骤(2)，得到只含，得到只含(n2)个符号的缩减信源个符号的缩减信源 S2。(4)重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为符号的概率之和必为 1。然后从最后一级缩减信源开始，依编码路。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。径向前返回，就得到各信源符号所对应的码字。6.4哈夫曼编码返回目录2/15/202323Department of Electronics and Information,NCUT Song Peng6.4.2 二进制哈夫曼编码二进制哈夫曼编码例例6.4.1 设单符号离散无记忆信源如下，要求对信源编二进制哈夫曼设单符号离散无记忆信源如下，要求对信源编二进制哈夫曼码。编码过程如图。码。编码过程如图。在图中读取码字的时候，一定要从后向前读，此时编出来的码字才在图中读取码字的时候，一定要从后向前读，此时编出来的码字才是可分离的异前置码。若从前向后读取码字，则码字不可分离。是可分离的异前置码。若从前向后读取码字，则码字不可分离。6.4哈夫曼编码2/15/202324Department of Electronics and Information,NCUT Song Peng6.4.2 二进制哈夫曼编码二进制哈夫曼编码例例6.4.16.4哈夫曼编码2/15/202325Department of Electronics and Information,NCUT Song Peng6.4.2 二进制哈夫曼编码二进制哈夫曼编码例例6.4.1信源熵为：信源熵为：平均码长为：平均码长为：编码效率为：编码效率为：若采用定长编码，码长若采用定长编码，码长 K=3，则编码效率：，则编码效率：哈夫曼的编码效率提高了哈夫曼的编码效率提高了 12.7%。6.4哈夫曼编码2/15/202326Department of Electronics and Information,NCUT Song Peng6.4.2 二进制哈夫曼编码二进制哈夫曼编码 注意：注意：哈夫曼的编法并不惟一。哈夫曼的编法并不惟一。q 每次对缩减信源两个概率最小的符号分配每次对缩减信源两个概率最小的符号分配“0”和和“1”码元是码元是任意的，所以可得到不同的码字。只要任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元在各次缩减信源中保持码元分配的一致性，分配的一致性，即能得到可分离码字。即能得到可分离码字。q 不同的码元分配，得到的具体码字不同，但码长不同的码元分配，得到的具体码字不同，但码长 ki 不变，平均不变，平均码长码长 也不变，所以没有本质区别；也不变，所以没有本质区别；q 缩减信源时，若合并后的新符号概率与其他符号概率相等，从缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，编码方法上来说，这几个符号的次序可任意排列，编出的码都是正这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的编法得到的码字长度确的，但得到的码字不相同。不同的编法得到的码字长度 ki 也不尽也不尽相同。相同。6.4哈夫曼编码2/15/202327Department of Electronics and Information,NCUT Song Peng6.4.2 二进制哈夫曼编码二进制哈夫曼编码 例例6.4.2：单符号离散无记忆信源：单符号离散无记忆信源 用两种不同的方法对其编二进制哈夫曼码。用两种不同的方法对其编二进制哈夫曼码。方法一：方法一：合并后的新符号排在其它相同概率符号的后面。合并后的新符号排在其它相同概率符号的后面。6.4哈夫曼编码2/15/202328Department of Electronics and Information,NCUT Song Peng6.4.2 二进制哈夫曼编码二进制哈夫曼编码 例例6.4.2：单符号离散无记忆信源：单符号离散无记忆信源 用两种不同的方法对其编二进制哈夫曼码。用两种不同的方法对其编二进制哈夫曼码。方法二：方法二：合并后的新符号排在其它相同概率符号的前面。合并后的新符号排在其它相同概率符号的前面。6.4哈夫曼编码2/15/202329Department of Electronics and Information,NCUT Song Peng6.4.2 二进制哈夫曼编码二进制哈夫曼编码 例例6.4.2：单符号信源编二进制哈夫曼码，编码效率主要决定于信源熵和平均单符号信源编二进制哈夫曼码，编码效率主要决定于信源熵和平均码长之比。对相同的信源编码，其熵是一样的，采用不同的编法，码长之比。对相同的信源编码，其熵是一样的，采用不同的编法，得到的平均码长可能不同。平均码长越短，编码效率就越高。得到的平均码长可能不同。平均码长越短，编码效率就越高。编法一的平均码长为：编法一的平均码长为：编法二的平均码长为：编法二的平均码长为：可见可见 ，本例两种编法的平均码长相同，所以编码效率相，本例两种编法的平均码长相同，所以编码效率相同。同。6.4哈夫曼编码2/15/202330Department of Electronics and Information,NCUT Song Peng6.4.2 二进制哈夫曼编码二进制哈夫曼编码讨论：讨论：q码字长度的方差码字长度的方差2：长度长度 ki 与平均码长与平均码长 之差的平方的数学期之差的平方的数学期望，即：望，即：q编法一码字长度方差：编法一码字长度方差：q编法二码字长度方差：编法二码字长度方差：哪种方哪种方法更好？法更好？6.4哈夫曼编码2/15/202331Department of Electronics and Information,NCUT Song Peng6.4.2 二进制哈夫曼编码二进制哈夫曼编码比较：比较：第二种编码方法的码长方差要小许多。第二种编第二种编码方法的码长方差要小许多。第二种编码方法的码长变化较小，比较接近于平均码长。码方法的码长变化较小，比较接近于平均码长。q第一种方法编出的第一种方法编出的 5 个码字有个码字有 4 种不同的码长；种不同的码长；q第二种方法编出的码长只有两种不同的码长；第二种方法编出的码长只有两种不同的码长；q第二种编码方法更简单、更容易实现，所以更好。第二种编码方法更简单、更容易实现，所以更好。结论结论：在哈夫曼编码过程中，对缩减信源符号按概率由在哈夫曼编码过程中，对缩减信源符号按概率由在哈夫曼编码过程中，对缩减信源符号按概率由在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能大到小的顺序重新排列时，应使合并后的新符号尽可能大到小的顺序重新排列时，应使合并后的新符号尽可能大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次排在靠前的位置，这样可使合并后的新符号重复编码次排在靠前的位置，这样可使合并后的新符号重复编码次排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。数减少，使短码得到充分利用。数减少，使短码得到充分利用。数减少，使短码得到充分利用。返回目录6.4哈夫曼编码2/15/202332Department of Electronics and Information,NCUT Song Peng6.4.3 m 进制哈夫曼编码进制哈夫曼编码(1)“全树全树”概念概念(2)举举 例例(3)结结 论论6.4哈夫曼编码2/15/202333Department of Electronics and Information,NCUT Song Peng6.4.3 m 进制哈夫曼编码进制哈夫曼编码(1)“全树全树”概念概念定义：定义：码树图中每个中间节点后续的枝数为码树图中每个中间节点后续的枝数为 m 时称为时称为全树全树；若有；若有些节点的后续枝数不足些节点的后续枝数不足 m，就称为，就称为非全树非全树。二进制码不存在非全树的情况，因为后续枝数是二进制码不存在非全树的情况，因为后续枝数是 1 时，这个枝就可时，这个枝就可以去掉使码字长度缩短。以去掉使码字长度缩短。m 进制编码：进制编码：若所有码字构成全树，可分离的码字数（信源个数）若所有码字构成全树，可分离的码字数（信源个数）必为必为 m+k(m1)。k 为信源缩减次数。为信源缩减次数。若信源所含的符号数若信源所含的符号数 n 不能构成不能构成 m 进制全树，必须增加进制全树，必须增加 s 个不用个不用的码字形成全树。显然的码字形成全树。显然 s0(i=1,2,n)信源符号的累积分布函数为：信源符号的累积分布函数为：所得累积分布函数为每台级的下界值，则其区间为所得累积分布函数为每台级的下界值，则其区间为 0,1)左闭右开左闭右开区间。区间。F(a1)=0 F(a2)=P(a1)F(a3)=P(a1)+P(a2)当当 A=0,1二元信源二元信源时：时：F(0)=0 F(1)=P(0)6.6算术编码2/15/202357Department of Electronics and Information,NCUT Song Peng6.6.2 累积分布函数累积分布函数 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)的宽度为：的宽度为：A(1)=P(1)，对应于信源符号，对应于信源符号“1”；若输入符号序列的第一个符号为若输入符号序列的第一个符号为 s=“0”，落入，落入0,F(1)区间，区间，得累积分布函数得累积分布函数 F(s=“0”)=F(0)=0；图示6.6算术编码2/15/202358Department of Electronics and Information,NCUT Song Peng6.6.2 累积分布函数累积分布函数 F(s)及对应的区间及对应的区间 计算计算二元无记忆信源序列二元无记忆信源序列的累积分布函数的累积分布函数q 输入第二个符号为输入第二个符号为“1”，s=“01”s=“01”所对应的区间是在区间所对应的区间是在区间 0,F(1)中进行分割；中进行分割；符号序列符号序列“00”对应的区间宽度为：对应的区间宽度为：A(00)=A(0)P(0)=P(0)P(0)=P(00)对应的区间为：对应的区间为：0,F(s=“01”)符号序列符号序列“01”对应的区间宽度为：对应的区间宽度为：A(01)=A(0)P(1)=P(0)P(1)=P(01)对应的区间为：对应的区间为：F(s=“01”),F(1)累积分布函数累积分布函数：F(s=“01”)=P(0)P(0)=P(00)图示6.6算术编码2/15/202359Department of Electronics and Information,NCUT Song Peng6.6.2 累积分布函数累积分布函数 F(s)及对应的区间及对应的区间 计算计算二元无记忆信源序列二元无记忆信源序列的累积分布函数的累积分布函数q 输入第三个符号为输入第三个符号为“1”：输入序列可记做输入序列可记做 s1=“011”，对应的区间是对区间对应的区间是对区间 F(s),F(1)进行分割；进行分割；序列序列 s0=“010”对应的区间宽度为：对应的区间宽度为：A(s=“010”)=A(s=“01”)P(0)=A(s)P(0)其对应的区间为：其对应的区间为：F(s),F(s)+A(s)P(0)序列序列 s1=“011”对应的区间宽度为：对应的区间宽度为：A(s=“011”)=A(s)P(1)其对应的区间为：其对应的区间为：F(s)+A(s)P(0),F(1)符号序列符号序列 s1=“011”的累积分布函数为：的累积分布函数为：F(s1)=F(s)+A(s)P(0)若第三个符号输入为若第三个符号输入为“0”，符号序列，符号序列s0=“010”的区间下界的区间下界值仍为值仍为F(s)，得符号序列，得符号序列 s0=“010”的累积分布函数为的累积分布函数为F(s0)=F(s)。图示6.6算术编码2/15/202360Department of Electronics and Information,NCUT Song Peng6.6.2 累积分布函数累积分布函数 F(s)及对应的区间及对应的区间 计算计算二元无记忆信源序列二元无记忆信源序列的累积分布函数的累积分布函数q 归纳归纳 当已知前面输入符号序列为当已知前面输入符号序列为 s，若接着再输入一个符号若接着再输入一个符号“0”，序列序列 s0 的累积分布函数为：的累积分布函数为：F(s0)=F(s)对应区间宽度为：对应区间宽度为：A(s0)=A(s)P(0)若接着输入的一个符号是若接着输入的一个符号是“1”，序列的累积分布函数为：序列的累积分布函数为：F(s1)=F(s)+A(s)P(0)对应区间宽度为：对应区间宽度为：A(s1)=A(s)P(1)图示6.6算术编码2/15/202361Department of Electronics and Information,NCUT Song Peng6.6.2 累积分布函数累积分布函数 F(s)及对应的区间及对应的区间 计算计算二元无记忆信源序列二元无记忆信源序列的累积分布函数的累积分布函数q 归纳归纳 符号序列对应的区间宽度符号序列对应的区间宽度 A(s=“0”)=P(0)A(s=“1”)=1A(0)=P(1)A(s=“00”)=P(00)=A(0)P(0)=P(0)P(0)A(s=“01”)=P(01)=A(0)P(1)=P(0)P(1)A(s=“10”)=P(10)=A(1)P(0)=P(1)P(0)A(s=“11”)=P(11)=A(1)P(1)=P(1)P(1)A(s=“010”)=A(01)P(0)=P(01)P(0)P(010)A(s=“011”)=A(01)P(1)=P(01)P(1)=P(011)信源符号序列信源符号序列 s 所对应区间的宽度等于符号序列所对应区间的宽度等于符号序列 s 的概率的概率 P(s)。返回目录6.6算术编码2/15/202362Department of Electronics and Information,NCUT Song Peng6.6.3 信源序列累积分布函数的递推公式信源序列累积分布函数的递推公式6.6算术编码二元信源符号序列的累积分布函数的递推公式二元信源符号序列的累积分布函数的递推公式qF(sr)=F(s)+P(s)F(r)(r=0,1)(5.6.1)sr 表示已知前面信源符号序列为表示已知前面信源符号序列为 s，接着再输入符号为，接着再输入符号为 rF(0)=0，F(1)=P(0)F(s0)=F(s)F(s1)=F(s)+P(s)F(1)=F(s)+P(s)P(0)qA(sr)=P(sr)=P(s)P(r)(r=0,1)(5.6.2)A(s0)=P(s0)=P(s)P(0)A(s1)=P(s1)=P(s)P(1)2/15/202363Department of Electronics and Information,NCUT Song Peng举例：举例：已输入二元符号序列为已输入二元符号序列为 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)=P(s=“011”)P(1)=P(011)P(1)=P(0111)F(s1)=F(s)+P(s)P(0)A(s1)=P(s1)=P(s)P(1)6.6.3 信源序列累积分布函数的递推公式信源序列累积分布函数的递推公式图示6.6算术编码2/15/202364Department of Electronics and Information,NCUT Song Peng上述整个分析过程可用图描述上述整个分析过程可用图描述6.6.3 信源序列累积分布函数的递推公式信源序列累积分布函数的递推公式图示返回6.6算术编码2/15/202365Department of Electronics and Information,NCUT Song Peng式式(5.6.1)和和(5.6.2)是可递推运算，在实际中，只需两是可递推运算，在实际中，只需两个存储器，把个存储器，把 P(s)和和 F(s)存下来，然后，根据输入符存下来，然后，根据输入符号和式号和式(5.6.1)、(5.6.2)更新两个存储器中的数值。因更新两个存储器中的数值。因此在编码过程中，每输入一个符号要进行此在编码过程中，每输入一个符号要进行乘法乘法和和加法加法运运算，所以称为算，所以称为算术编码。算术编码。F(sr)=F(s)+P(s)F(r)(r=0,1)(5.6.1)A(sr)=P(sr)=P(s)P(r)(r=0,1)(5.6.2)6.6.3 信源序列累积分布函数的递推公式信源序列累积分布函数的递推公式返回目录6.6算术编码2/15/202366Department of Electronics and Information,NCUT Song Peng 通过关于信源符号序列的累积分布函数的计算，把区间分割成许多通过关于信源符号序列的累积分布函数的计算，把区间分割成许多小区间，不同的信源符号序列对应不同的区间小区间，不同的信源符号序列对应不同的区间。可取小区间内的。可取小区间内的一点来代表这序列。一点来代表这序列。编码方法：编码方法：将符号序列的累积分布函数写成二进位的小数，取小将符号序列的累积分布函数写成二进位的小数，取小数点后数点后 k 位，若后面有尾数，就进位到第位，若后面有尾数，就进位到第 k 位，这样得到的一个数位，这样得到的一个数 C，并使，并使 k 满足：满足：举例：举例：6.6.4 算术编码方法算术编码方法6.6算术编码2/15/202367Department of Electronics and Information,NCUT Song Peng 编码效率编码效率q 算术编码的编码效率很高。当信源符号序列很长时，算术编码的编码效率很高。当信源符号序列很长时，L 很大时，很大时，平均码长接近信源的熵。平均码长接近信源的熵。6.6.4 算术编码方法算术编码方法返回目录6.6算术编码2/15/202368Department of Electronics and Information,NCUT Song Peng译码就是一系列比较过程，每一步比较译码就是一系列比较过程，每一步比较 CF(s)与与 P(s)P(0)。F(s0)=F(s)F(s1)=F(s)+P(s)P(0)s前面已译出的序列串前面已译出的序列串 P(s)序列串序列串 s 对应的宽度对应的宽度F(s)是序列串是序列串 s 的累积分布函数，即为的累积分布函数，即为 s 对应区间的下界；对应区间的下界；P(s)P(0)是此区间内下一个输入为符号是此区间内下一个输入为符号“0”所占的子区间宽度；所占的子区间宽度；若若 CF(s)P(s)P(0)则译输出符号为则译输出符号为“1”。6.6.5 算术编码的译码算术编码的译码6.6算术编码2/15/202369Department of Electronics and Information,NCUT Song Peng举例：设二元无记忆信源举例：设二元无记忆信源 S=0,1，其，其 P(0)=1/4，P(1)=3/4。对二元。对二元序列