第8章无失真的信源编码精选PPT.ppt
第8章无失真的信源编码1第1页，本讲稿共28页第8章 无失真信源编码u8.1 编码器u8.2定长码u8.3唯一可译定理u4.4 等长信源编码定理u4.5 变长码u4.6 变长信源编码定理u4.7 几种典型的信源编码方法（变长编码几种典型的信源编码方法（变长编码方法）方法）2第2页，本讲稿共28页8.18.1香农编码方法香农编码方法u香农第一定理指出了平均码长与信源信香农第一定理指出了平均码长与信源信息熵之间的关系，同时也指出了可以通息熵之间的关系，同时也指出了可以通过编码使平均码长达到极限值，这是一过编码使平均码长达到极限值，这是一个很重要的极限定理。个很重要的极限定理。u如何构造一个最佳码，香农第一定理并如何构造一个最佳码，香农第一定理并没有直接给出，本节将讲解具体的编码没有直接给出，本节将讲解具体的编码方法。方法。3第3页，本讲稿共28页香农编码方法香农编码方法（1）把信源的）把信源的n个消息按概率递减次序排列，即个消息按概率递减次序排列，即P(x1)P(x2)P(xn)（2）确定满足下列不等式的整数码长）确定满足下列不等式的整数码长 满足满足b1 b2 bn（3）计算计算 （4 4）将累加概率）将累加概率 变换成二进制数。变换成二进制数。4第4页，本讲稿共28页u（5 5）取）取 二进制的小数点后二进制的小数点后bi位数作为位数作为该消息符号的二进制码字。该消息符号的二进制码字。5第5页，本讲稿共28页例例：某信源具有某信源具有7个消息符号，其概率分别为：个消息符号，其概率分别为：0.20,0.19,0.18,0.17,0.15,0.10,0.01。欲对其进行香农方法的二。欲对其进行香农方法的二进制编码，求其二进制代码组及其编码效率。进制编码，求其二进制代码组及其编码效率。解：解：先计算每一个码字的码长，先计算每一个码字的码长，分别为：分别为：3,3,3,3,3,4,7；再计算累加概率。再计算累加概率。有关的数据和编码结果列见下表。有关的数据和编码结果列见下表。6第6页，本讲稿共28页法法2：也可先求出每个码字的码长后，在利用树图法求出二进制代码组：也可先求出每个码字的码长后，在利用树图法求出二进制代码组7第7页，本讲稿共28页费诺费诺(Fano)编码方法编码方法u编码步骤：n将信源符号以概率递减的次序排列；n将排列好的信源符号划分成两大组，使每组概率和尽量接近相同，并各赋予一个二元码符号“0”和“1”；n将每一大组的信源符号再分成两组，使同一组的两个小组的概率和近于相同，并又分别赋予一个二元符号。依次下去，直到每个小组只剩一个信源符号为止。8第8页，本讲稿共28页例例1：试对上例的信源用费诺编码方法，求其二进制代码组及其编试对上例的信源用费诺编码方法，求其二进制代码组及其编码效率。码效率。解解：先先将将消消息息符符号号按按概概率率大大小小排排列列，再再按按步步骤骤进进行行子子集集分分解解，本本题题经过经过4次分解完成编码，整个过程列于下表次分解完成编码，整个过程列于下表9第9页，本讲稿共28页10第10页，本讲稿共28页u例2：一离散无记忆信源S的费诺码如下.11第11页，本讲稿共28页u该信源的熵u平均码长u编码效率12第12页，本讲稿共28页u例3：一离散无记忆信源的费诺码如下.13第13页，本讲稿共28页u该信源的熵u平均码长u编码效率14第14页，本讲稿共28页u从以上几例看出，费诺码的编码方法实际上是构造码树的一种方法，所以费偌码是非续长码。u费诺码考虑了信源的统计特性，使经常出现的信源符号对应短码字。但是，不一定能使短码得到充分利用。u费诺码不一定是最佳码。15第15页，本讲稿共28页霍夫曼霍夫曼（Huffman）编码u编码步骤：n将q个信源符号以概率递减的次序排列；n用0和1码符号分别代表概率最小的两个信源符号，并合并成一个符号，从而得到只包含q-1个信源符号的新信源，称为信源的缩减信源。n将缩减信源的符号仍以概率递减的次序排列，再将其最后二个概率最小的符号分别用0和1表示，并合并成一个符号，形成了q-1个符号的缩减信源。n依次继续下去，直到信源最后只剩两个符号为止，将最后这两个符号分别用0和1表示。然后从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即对应的码字。16第16页，本讲稿共28页u例1：一离散无记忆信源的Huffman编码17第17页，本讲稿共28页18第18页，本讲稿共28页u例2：一离散无记忆信源的Huffman编码19第19页，本讲稿共28页20第20页，本讲稿共28页u上2例两种编码有相同的平均码长，所以有相同的编码效率，但每个信源符号的码长却不相同。选择哪个码好呢？u分别计算这两个编码的方差：u选择第二种编码方法更好些。21第21页，本讲稿共28页uHuffman编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，而且短码得到充分利用。u每次缩减信源的最长两个码字总是最后一位码元不同，前面各位码元相同（二元编码情况）。u每次缩减信源的最长两个码字有相同的码长。uHuffman编码是最佳码22第22页，本讲稿共28页u费诺编码费诺编码例例3 3的Huffman编码码字：1 001 011 0000 0100 0101 00010 0001123第23页，本讲稿共28页u与费诺编码费诺编码例例3 3比较，Huffman编码比Fano编码效率高。24第24页，本讲稿共28页实用的无失真信源实用的无失真信源编码方法MH编码（游程编码）编码（游程编码）主要用于黑白二值文件、传真的数据压缩。由于传真文件主要用于黑白二值文件、传真的数据压缩。由于传真文件中连中连“0”和连和连“1”较多，这些连较多，这些连“0”和连和连“1”的的 字符字符串称为游程。串称为游程。MH编码是一种实用的游程编码算法，其根据不同的编码是一种实用的游程编码算法，其根据不同的黑白游程长度有结尾码表和组合码表。其基本的编码黑白游程长度有结尾码表和组合码表。其基本的编码规则见书规则见书174页。页。25第25页，本讲稿共28页算术编码算术编码它是一种非分组码，无需计算出所有它是一种非分组码，无需计算出所有N长信源序列的概长信源序列的概率分布及码表，可以直接对输入的信源符号序列编码输率分布及码表，可以直接对输入的信源符号序列编码输出。出。编码方法：将累计分布函数的编码方法：将累计分布函数的0，1分成许多互不重叠的小分成许多互不重叠的小区件，每个信源符号对应于各个小区间，每一小区间的长度区件，每个信源符号对应于各个小区间，每一小区间的长度等于这个信源符号的概率分布值，在此区间内取一点，取该等于这个信源符号的概率分布值，在此区间内取一点，取该点二进制小数点后点二进制小数点后l位作为这个信源的码字。位作为这个信源的码字。26第26页，本讲稿共28页编码方法：编码方法：（1）用递推公式计算信源序列的累积分布函数）用递推公式计算信源序列的累积分布函数F(s)和和对应区间的宽度对应区间的宽度A(s)二元信源（二元信源（r=2）为为 F(sr)=F(s)+P(s).F(r)A(sr)=P(s).P(r)对于二元信源，可从二元整树来计算对于二元信源，可从二元整树来计算F(s)（2）确定信源序列）确定信源序列s的码长的码长l27第27页，本讲稿共28页（3）将）将F(s)写成二进位小数，取小数后写成二进位小数，取小数后l位，若有位，若有尾数，进位到第尾数，进位到第l位，得位，得s的码字。的码字。28第28页，本讲稿共28页
