进制哈夫曼编码.pptx

5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码二进制哈夫曼码的编码方法：二进制哈夫曼码的编码方法：(1)将将 信信 源源 消消 息息 符符 号号 按按 其其 出出 现现 的的 概概 率率 大大 小小 依依 次次 排排 列列：。(2)取取两两个个概概率率最最小小的的符符号号分分别别配配以以0和和1两两个个码码元元，并并将将这这两两个个概概率率相相加加作作为为一一个个新新符符号号的的概概率率，与与未分配二进制码元的符号重新排队。未分配二进制码元的符号重新排队。11:43 上午5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码(3)对对重重排排后后的的两两个个概概率率最最小小符符号号重重复复步步骤骤(2)的的过过程。程。(4)不不断断继继续续上上述述过过程程，直直到到最最后后两两个个符符号号配配以以0和和1为止。为止。(5)从从最最后后一一级级开开始始，向向前前返返回回得得到到各各个个信信源源符符号号所对应的码元序列所对应的码元序列，即相应的码字。，即相应的码字。21:43 上午5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码（例）（例）例：例：对以下信源进行哈夫曼编码。对以下信源进行哈夫曼编码。P166习题习题5.3 信源符号信源符号ai概率概率p(ai)码字码字Wi码长码长Kia10.20102a20.19112a30180003a40.170013a50.150103a60.1001104a70.010111431:43 上午5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码（例续）编码（例续）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 0.19 0.20 0.260.17 0.17 0.18 0.190.15 0.15 0.170.10 0.110.0101010101010141:43 上午5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码（例续）编码（例续）51:43 上午5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码哈夫曼编码方法得到的码哈夫曼编码方法得到的码并非唯一并非唯一的。的。n每每次次对对信信源源缩缩减减时时，赋赋予予信信源源最最后后两两个个概概率率最最小小的的符符号号，用用0和和1是是可可以任意的，所以可以得到不同的哈夫曼码，但以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度不会影响码字的长度。n对对信信源源进进行行缩缩减减时时，两两个个概概率率最最小小的的符符号号合合并并后后的的概概率率与与其其它它信信源源符符号号的的概概率率相相同同时时，这这两两者者在在缩缩减减信信源源中中进进行行概概率率排排序序，其其位位置置放放置置次次序序是是可可以以任任意意的的，故故会会得得到到不不同同的的哈哈夫夫曼曼码码。此此时时将将影影响响码码字字的的长长度度，一般将一般将合并的概率放在上面合并的概率放在上面，这样可获得，这样可获得较小的码方差较小的码方差。n需需要要大大量量的的存存储储设设备备来来缓缓冲冲码码字字长长度度的的差差异异，这这是是码码方方差差小小的的码码质质量量好的原因。好的原因。61:43 上午5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码（例）编码（例2 2）例：例：对以下离散无记忆信源进行两种哈夫曼编码。对以下离散无记忆信源进行两种哈夫曼编码。(例例5.1.6)信源信源符号符号ai概率概率p(ai)码字码字Wi1码长码长Ki1码字码字Wi2码长码长Ki2a10.411002a20.2012102a30.20003112a40.1001040103a50.100114011371:44 上午5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码（例）编码（例2 2续）续）第第一一种种方方法法第第二二种种方方法法0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.2 0.10.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.20.10101010101010101码字码字010000010001100101101001181:44 上午5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码（例）编码（例2 2续）续）第一种方法码树图第二种方法码树图第一种方法码树图第二种方法码树图91:44 上午5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码（例）编码（例2 2续）续）101:44 上午5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码n进行哈夫曼编码时，为得到进行哈夫曼编码时，为得到码方差码方差最小的码，应使合并的最小的码，应使合并的信源符号位于缩减信源序列信源符号位于缩减信源序列尽可能高的位置尽可能高的位置上，以减少再上，以减少再次合并的次数，充分利用短码。次合并的次数，充分利用短码。n哈夫曼码是用概率匹配方法进行信源编码。它有两个明显哈夫曼码是用概率匹配方法进行信源编码。它有两个明显特点：一是哈夫曼码的编码方法保证了概率大的符号对应特点：一是哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；二于短码，概率小的符号对应于长码，充分利用了短码；二是缩减信源的最后两个码字总是最后一位不同，保证了哈是缩减信源的最后两个码字总是最后一位不同，保证了哈夫曼码是即时码。夫曼码是即时码。n哈夫曼码是最佳码。哈夫曼码是最佳码。111:44 上午m进制哈夫曼编码哈夫曼编码n二进制哈夫曼的编码方法可以很容易推广到m进制的情况。只是编码过程中构成缩减信源时，每次都是将m个概率最小的符号合并，并分别用0,1,m-1码符号表示。n为使平均码长最短，必须使最后一步缩减信源有m个信源符号。如果第一步给概率最小的符号分配码元时，所取的符号数就不一定是m个。5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码121:44 上午n全树全树：码树图中每个中间节点后续的枝数必为：码树图中每个中间节点后续的枝数必为m。若有些。若有些节点的后续枝数不足节点的后续枝数不足m，则称为，则称为非全树非全树。n对于对于m进制编码，若所有码字构成全树，可分离的码字数进制编码，若所有码字构成全树，可分离的码字数必为必为m+k(m-1)，式中，式中k为非负整数，即缩减次数。为非负整数，即缩减次数。n若信源所含的符号数若信源所含的符号数n不能构成不能构成m进制的全树，就必须增进制的全树，就必须增加加s（sm-1）个不用的码字来形成全树。）个不用的码字来形成全树。m进制哈夫曼编码哈夫曼编码5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码131:44 上午m进制哈夫曼编码步骤哈夫曼编码步骤(1)验证所给验证所给n是否满足是否满足n=(m-1)k+m，若不满足该式，可以人为地增加一，若不满足该式，可以人为地增加一些概率为零的符号，以使最后一步有些概率为零的符号，以使最后一步有m个信源符号；个信源符号；(2)取概率最小的取概率最小的m个符号合并成一个新结点，并分别用个符号合并成一个新结点，并分别用0,1,(m-1)给各给各分支赋值，把这些符号的概率相加作为该新结点的概率；分支赋值，把这些符号的概率相加作为该新结点的概率；(3)将新结点和剩下结点重新排队，重复将新结点和剩下结点重新排队，重复(2),如此下去直至树根；如此下去直至树根；(4)取树根到叶子取树根到叶子(信源符号对应结点信源符号对应结点)的各树枝上的赋值，则得到各符号的各树枝上的赋值，则得到各符号码字。码字。n后来新加的概率为零的符号，虽也赋予码字，实际上这是冗余码字，后来新加的概率为零的符号，虽也赋予码字，实际上这是冗余码字，并未用上，但这样编成的码，仍是最佳的，也就是平均码长最短，如并未用上，但这样编成的码，仍是最佳的，也就是平均码长最短，如果等概率符号排队时注意到顺序，则码长的方差也是最小的。果等概率符号排队时注意到顺序，则码长的方差也是最小的。141:44 上午m进制哈夫曼编码例哈夫曼编码例n设单符号离散无记忆信源如下，对信源编三进制设单符号离散无记忆信源如下，对信源编三进制哈夫曼码。哈夫曼码。151:44 上午m进制哈夫曼编码例（续）哈夫曼编码例（续）161:44 上午m进制哈夫曼编码例（续）哈夫曼编码例（续）三进制哈夫曼码树图三进制哈夫曼码树图171:44 上午m进制哈夫曼编码例哈夫曼编码例n设单符号离散无记忆信源如下其三进制哈夫曼编码如图(a)所示，四进制哈夫曼编码如图(b)所示。181:44 上午m进制哈夫曼编码例（续）哈夫曼编码例（续）图(a)三进制哈夫曼编码191:44 上午m进制哈夫曼编码例（续）哈夫曼编码例（续）图(b)四进制哈夫曼编码201:44 上午m进制哈夫曼编码例（续）哈夫曼编码例（续）211:44 上午三种最佳变长编码方法比较三种最佳变长编码方法比较n香农码香农码：有系统的、惟一的编码方法，但多数情况下编码：有系统的、惟一的编码方法，但多数情况下编码效率不是很高。效率不是很高。n费诺码费诺码：编码方法不惟一，比较适合于对分组概率相等或：编码方法不惟一，比较适合于对分组概率相等或接近的信源编码。接近的信源编码。n哈夫曼码哈夫曼码：编码方法不惟一，对信源的统计特性没有特殊：编码方法不惟一，对信源的统计特性没有特殊要求，编码效率比较高，综合性能优于香农码和费诺码。要求，编码效率比较高，综合性能优于香农码和费诺码。221:44 上午