第8章无失真的信源编码优秀PPT.ppt

《第8章无失真的信源编码优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第8章无失真的信源编码优秀PPT.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第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如何构造

2、一个最佳码，香农第一定理并如何构造一个最佳码，香农第一定理并没有直接给出，本节将讲解具体的编码没有直接给出，本节将讲解具体的编码方法。方法。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位数作为位数作为该消息符号的二进制码

3、字。该消息符号的二进制码字。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：也可先求出每个码字的码长后，在利用树

4、图法求出二进制代码组：也可先求出每个码字的码长后，在利用树图法求出二进制代码组7现在学习的是第7页，共28页费诺费诺(Fano)编码方法编码方法u编码步骤：n将信源符号以概率递减的次序排列；n将排列好的信源符号划分成两大组，使每组概率和尽量接近相同，并各赋予一个二元码符号“0”和“1”；n将每一大组的信源符号再分成两组，使同一组的两个小组的概率和近于相同，并又分别赋予一个二元符号。依次下去，直到每个小组只剩一个信源符号为止。8现在学习的是第8页，共28页例例1：试对上例的信源用费诺编码方法，求其二进制代码组及试对上例的信源用费诺编码方法，求其二进制代码组及其编码效率。其编码效率。解解：先先将将

5、消消息息符符号号按按概概率率大大小小排排列列，再再按按步步骤骤进进行行子子集集分分解，本题经过解，本题经过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

6、费诺码考虑了信源的统计特性，使经常出现的信源符号对应短码字。但是，不一定能使短码得到充分利用。u费诺码不一定是最佳码。15现在学习的是第15页，共28页霍夫曼霍夫曼（Huffman）编码u编码步骤：n将q个信源符号以概率递减的次序排列；n用0和1码符号分别代表概率最小的两个信源符号，并合并成一个符号，从而得到只包含q-1个信源符号的新信源，称为信源的缩减信源。n将缩减信源的符号仍以概率递减的次序排列，再将其最后二个概率最小的符号分别用0和1表示，并合并成一个符号，形成了q-1个符号的缩减信源。n依次继续下去，直到信源最后只剩两个符号为止，将最后这两个符号分别用0和1表示。然后从最后一级缩减信源

7、开始，向前返回，就得出各信源符号所对应的码符号序列，即对应的码字。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编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，而且短

8、码得到充分利用。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编码（游程编码）编码（游程编码）主要用于黑白二值文件、传真的数据压缩。由于传真文件

9、主要用于黑白二值文件、传真的数据压缩。由于传真文件中连中连“0”和连和连“1”较多，这些连较多，这些连“0”和连和连“1”的的 字符串称为游程。字符串称为游程。MH编码是一种实用的游程编码算法，其根据不同的黑编码是一种实用的游程编码算法，其根据不同的黑白游程长度有结尾码表和组合码表。其基本的编码规则白游程长度有结尾码表和组合码表。其基本的编码规则见书见书174页。页。25现在学习的是第25页，共28页算术编码算术编码它是一种非分组码，无需计算出所有它是一种非分组码，无需计算出所有N长信源序列的长信源序列的概率分布及码表，可以直接对输入的信源符号序列编概率分布及码表，可以直接对输入的信源符号序列

10、编码输出。码输出。编码方法：将累计分布函数的编码方法：将累计分布函数的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页