信息论与编码-第六章.ppt

得霍夫曼码其平均码长信源符号sis1s2s3s4s5另一种霍夫曼编码方式最终，得霍夫曼码信源符号相应的码字为其平均码长两种霍夫曼编码的不同之处仅仅在于码长相同的两种码字的码符号序列形式不同。由此可见，同一信源的霍夫曼码的形式不是唯一的。在遵循“缩减信源中的符号按其概率大小，以递减次序，由大到小，自上至下排列”这个原则的前提下，各次缩减所得的虚拟符号可能有多于1个合适的位置。合适位置的不同选择，也会导致构成结构相同、有效性相同，而形式不同的多种霍夫曼码。验证可知，本题不满足上述的关系，所以需要增加概率为零的虚拟符号，因为，所以，当时，，需增加的符号数为：编码过程如下表码长码字信源符号概率第一次缩减第二次缩减0.5411s10.240.240.24200s20.200.220.22201s30.180.20202s40.160.18220s50.140.16221s60.08222s10由霍夫曼编码得出的码长求得平均码长：若不设置一个概率为零的虚拟信号，直接对含有6个信源符号的原信源进行霍夫曼编码，如下表:码长码字信源符号概率第一次缩减第二次缩减2100.240.380.382100.200.242120.180.202200.160.182210.142220.08根据上述表中求出的码长得出平均码长：0.62从以上两个表中可以看出：直接对含有6个信源符号的原信源进行霍夫曼编码，在最后一次缩减信源赋于的码符号“0”构成的码长为1的最短码字就不可能代表概率最大的信源符号，码长为1的最短码字没有得到合理而充分的利用。相反，把码长为最长的码字不合理地给了信源符号，所以导致平均码长增大，其有效性下降。霍夫曼码是非延长码以[例6.1]为例，以霍夫曼编码缩减过程的终点作为“树根”，以码符号集码符号数r=2作为“分枝”数，经过四次分枝可得具有四阶节点的“码树”，可知，赋于各信源符号的码字都是“码树”的“端点”。所以，表6.3所得霍夫曼码在结构上是非延长码。对于表6.4，同样可得相应的“码树”如图6.7所示。表6.4中的霍夫曼码的码字同样也是图6.7所示“码树”的“端点”。所以，霍夫曼码在结构上也是非延长码。由以上的实例分析可知：霍夫曼编码方法中的逐次缩减过程，实际上是“码树”构码方法中逐级分枝过程的逆过程；霍夫曼编码方法对码字的构成原则，确保霍夫曼码各码字是“码树”的“端点”。因此，霍夫曼码在结构上是非延长码，是单义可译码。霍夫曼码是有效码霍夫曼码的两个特点：保证概率大的信源符号对应短码；概率小的信源符号对应长码。而且，所有短码都得到充分利用；每次缩减信源中概率最小的r个符号对应的码符号序列中，总是最后一个码符号不同，前面各位码符号均相同。这两个特点保证了霍夫曼码的平均码长是用其它编码方法编出的结构相同的单义可译码的平均码长中最小的平均码长。即，霍夫曼码是有效码。两种霍夫曼码的比较信源符号sis1s2s3s4s5平均码长：表6.3信源符号sis1s2s3s4s5平均码长：表6.7两种霍夫曼码的平均码长是相等的，由二者的“码树”图可以看出，两种霍夫曼码的码字在“码树”上的“端点”的位置不同，这体现了两种霍夫曼码的码字长度结构的区别。所以，两种霍夫曼码都是非延长码，且都是有效码。表一的“码树”图表二的“码树”图为了区分两种方法，我们引入码长方差的概念：设码中各码字的长度分别为