进制哈夫曼编码复习过程

1、进制哈夫曼编码进制哈夫曼编码5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码（例）（例）例：例：对以下信源进行哈夫曼编码。对以下信源进行哈夫曼编码。 P166习题习题5.3 信源符号信源符号ai概率概率p(ai)码字码字Wi码长码长Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.01011145.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

2、.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.010101010101015.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码（例续）编码（例续）%K)X(HR)X(HKmlogLKR,mL.)p(alog)p(a)X(HK)a(pKiiiiii962.722.61/2.7221/612/2.727171 编编码码效效率率：码码元元比比特特所所需需的的信信息息率率：码码，则则信信源源采采用用哈哈夫夫曼曼编编码码，对对单单符符号号信信源源编编二二进进制制符符号号比比特特信信源源熵熵：符符号

3、号码码元元平平均均码码长长：5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码哈夫曼编码方法得到的码哈夫曼编码方法得到的码并非唯一并非唯一的。的。n每次对信源缩减时，赋予信源最后两个概率最小的符号，用每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和和1是可是可以任意的，所以可以得到不同的哈夫曼码，但以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度不会影响码字的长度。n对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次号的概率相同

4、时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将一般将合并的概率放在上面合并的概率放在上面，这样可获得，这样可获得较小的码方差较小的码方差。n需要大量的存储设备来缓冲码字长度的差异，这是码方差小的码质量需要大量的存储设备来缓冲码字长度的差异，这是码方差小的码质量好的原因。好的原因。 niiii)K)(Kp(xKKE1222 码码字字长长度度的的方方差差：5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码（例）编码（例2 2）例：例：对以下离散无记忆信源

5、进行两种哈夫曼编码。对以下离散无记忆信源进行两种哈夫曼编码。(例例5.1.6) 信源信源符号符号ai概率概率p(ai)码字码字Wi1码长码长Ki1码字码字Wi2码长码长Ki2a10.411002a20.2012102a30.20003112a40.1001040103a50.10011401135.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

6、.4 0.40.2 0.2 0.20.1 0.20.10101010101010101码字码字01000001000110010110100115.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码（例）编码（例2 2续）续）第一种方法码树图第二种方法码树图第一种方法码树图第二种方法码树图5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码（例）编码（例2 2续）续） 量量好好。故故第第二二种种哈哈夫夫曼曼码码的的质质第第二二种种方方法法：第第一一种种方方法法：码码字字长长度度的的方方差差：率率相相等等：两两种种编编码码方方法法的的编编码码效效符符号号码码元元等等：两两种

7、种方方法法的的平平均均码码长长相相1602.2)-0.1)(3(0.12.2)-0.2)(20.2(0.43612.2)-0.1)(4(0.12.2)-0.2(32.2)-0.2(22.2)-0.4(1596/22 2222222221122271.)K)(Kp(xKKE%.K)X(H.)Kp(xKniiiiiii 5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码n进行哈夫曼编码时，为得到进行哈夫曼编码时，为得到码方差码方差最小的码，应使合并的最小的码，应使合并的信源符号位于缩减信源序列信源符号位于缩减信源序列尽可能高的位置尽可能高的位置上，以减少再上，以减少再次合并的次

8、数，充分利用短码。次合并的次数，充分利用短码。n哈夫曼码是用概率匹配方法进行信源编码。它有两个明显哈夫曼码是用概率匹配方法进行信源编码。它有两个明显特点：一是哈夫曼码的编码方法保证了概率大的符号对应特点：一是哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；二于短码，概率小的符号对应于长码，充分利用了短码；二是缩减信源的最后两个码字总是最后一位不同，保证了哈是缩减信源的最后两个码字总是最后一位不同，保证了哈夫曼码是即时码。夫曼码是即时码。n哈夫曼码是最佳码。哈夫曼码是最佳码。m进制哈夫曼编码哈夫曼编码n二进制哈夫曼的编码方法可以很容易推广到m进制的情况。只

9、是编码过程中构成缩减信源时，每次都是将m个概率最小的符号合并，并分别用0,1,m-1码符号表示。n为使平均码长最短，必须使最后一步缩减信源有m个信源符号。如果第一步给概率最小的符号分配码元时，所取的符号数就不一定是m个。5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码n全树全树：码树图中每个中间节点后续的枝数必为：码树图中每个中间节点后续的枝数必为m。若有些。若有些节点的后续枝数不足节点的后续枝数不足m，则称为，则称为非全树非全树。n对于对于m进制编码，若所有码字构成全树，可分离的码字数进制编码，若所有码字构成全树，可分离的码字数必为必为m+k(m-1)，式中，式中k为非

10、负整数，即缩减次数。为非负整数，即缩减次数。n若信源所含的符号数若信源所含的符号数n不能构成不能构成m进制的全树，就必须增进制的全树，就必须增加加s（sm-1）个不用的码字来形成全树。）个不用的码字来形成全树。m进制哈夫曼编码哈夫曼编码5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码m进制哈夫曼编码步骤哈夫曼编码步骤(1)验证所给验证所给n是否满足是否满足n=(m-1)k+m，若不满足该式，可以人为地增加一，若不满足该式，可以人为地增加一些概率为零的符号，以使最后一步有些概率为零的符号，以使最后一步有m个信源符号；个信源符号；(2)取概率最小的取概率最小的m个符号合并成一

11、个新结点，并分别用个符号合并成一个新结点，并分别用0,1,(m-1)给各给各分支赋值，把这些符号的概率相加作为该新结点的概率；分支赋值，把这些符号的概率相加作为该新结点的概率；(3)将新结点和剩下结点重新排队，重复将新结点和剩下结点重新排队，重复(2),如此下去直至树根；如此下去直至树根；(4)取树根到叶子取树根到叶子(信源符号对应结点信源符号对应结点)的各树枝上的赋值，则得到各符号的各树枝上的赋值，则得到各符号码字。码字。n后来新加的概率为零的符号，虽也赋予码字，实际上这是冗余码字，后来新加的概率为零的符号，虽也赋予码字，实际上这是冗余码字，并未用上，但这样编成的码，仍是最佳的，也就是平均码

12、长最短，如并未用上，但这样编成的码，仍是最佳的，也就是平均码长最短，如果等概率符号排队时注意到顺序，则码长的方差也是最小的。果等概率符号排队时注意到顺序，则码长的方差也是最小的。m进制哈夫曼编码例哈夫曼编码例n设单符号离散无记忆信源如下，对信源编三进制设单符号离散无记忆信源如下，对信源编三进制哈夫曼码。哈夫曼码。符符号号进进行行编编码码。个个次次只只需需取取不不用用的的码码字字，所所以以第第一一个个则则须须增增加加则则令令。其其中中，21-3s-m1n-9s9,1)-k(mm3,83,0500505005001010204087654321 knm.xxxxxxxx)p(xXim进制哈夫曼编码

13、例（续）哈夫曼编码例（续）m进制哈夫曼编码例（续）哈夫曼编码例（续）%.91772352/7723logLKR/751)Kp(xK281iii 编码效率编码效率符号符号比特比特相应的信息率相应的信息率符号符号码元码元其平均码长其平均码长三进制哈夫曼码树图三进制哈夫曼码树图m进制哈夫曼编码例哈夫曼编码例n设单符号离散无记忆信源如下其三进制哈夫曼编码如图(a)所示，四进制哈夫曼编码如图(b)所示。05.005.02.03.04.054321xxxxx)p(xXim进制哈夫曼编码例（续）哈夫曼编码例（续）图(a)三进制哈夫曼编码m进制哈夫曼编码例（续）哈夫曼编码例（续）图(b)四进制哈夫曼编码m进制

14、哈夫曼编码例（续）哈夫曼编码例（续）缩缩可可言言。于于没没有有编编码码，当当然然无无压压数数，等等个个信信源源符符号号赋赋予予一一个个码码若若编编五五元元码码，只只能能对对每每大大于于码码元元数数。上上例例中中，数数应应远远下下，信信源源符符号号集集的的元元素素编编码码的的优优势势，一一般般情情况况可可见见，要要发发挥挥哈哈夫夫曼曼编编码码效效率率分分别别为为：别别为为：两两种种编编码码的的平平均均码码长长分分信信源源熵熵：%.LlogKH(X)(%.LlogKH(X)RH(X)(l)(bit/symbo.).().()Kp(xKl)(bit/symbo.).().()Kp(xKl)(bit/symbo.)p(xlog)p(x-H(X)iiiiiiiii68821195144994581319513311205005013020403120500502013040951 4343 三种最佳变长编码方法比较三种最佳变长编码方法比较n香农码香农码：有系统的、惟一的编码方法，但多数情况下编码：有系统的、惟一的编码方法，但多数情况下编码效率不是很高。效率不是很高。n费诺码费诺码：编