[工学]第8章 无失真的信源编码

《[工学]第8章 无失真的信源编码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章无失真的信源编码8.1霍夫曼（Huffman）码8.2费诺(Fano)码8.3香农-费诺-埃得斯码8.4游程编码和MH编码8.6字典码8.5算术编码8.1霍夫曼（Huffman）码设离散无记忆信源二进制香农码的编码步骤如下：将信源符号按概率从大到小的顺序排列，为方便起见，令p(x1)≥p(x2)≥…≥p(xn)令p(x0)=0，用pa(xj)，j=i+1表示第i个码字的累加概率，则：确定满足下列不等式的整数ki，并令ki为第i个码字的长度－log2p(xn)≤ki<－log2p(xn)+1将pa(xj)用二进制表示，并取小数点后ki

2、位作为符号xi的编码。例有一单符号离散无记忆信源对该信源编二进制香农码。其编码过程如下表所示。8.1霍夫曼（Huffman）码计算出给定信源香农码的平均码长若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用3个比特表示。相比较，香农编码对信源进行了压缩。由离散无记忆信源熵定义，可计算出：对上述信源采用香农编码的信息率为编码效率为信源熵和信息率之比。则可以看出，编码效率并不是很高。8.1霍夫曼（Huffman）码第六节费诺编码费诺编码也是一种常见的信源编码方法。编码步骤如下：将概率按从大到小的顺序排列，令p(x1)≥p(x2)≥…

3、≥p(xn)按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编m进制码就分成m组。给每一组分配一位码元。将每一分组再按同样原则划分，重复步骤2和3，直至概率不再可分为止。第六节费诺编码例设有一单符号离散信源对该信源编二进制费诺码。编码过程如下表。第六节费诺编码该信源的熵为平均码长为编码效率为本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。第六节费诺编码题中码字还可用码树来表示，如图所示。第七节霍夫曼编码霍夫曼(Huff

4、man)编码是一种效率比较高的变长无失真信源编码方法。编码步骤二进制哈夫曼编码m进制哈夫曼编码第七节霍夫曼编码——编码步骤将信源符号按概率从大到小的顺序排列，令p(x1)≥p(x2)≥…≥p(xn)给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n－1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n－2)个符号的缩减信源S2。重复上

5、述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。第七节霍夫曼编码——二进制哈夫曼编码例设单符号离散无记忆信源如下，要求对信源编二进制霍夫曼码。编码过程如下图（后页）。在图中读取码字的时候，一定要从后向前读，此时编出来的码字才是可分离的异前置码。若从前向后读取码字，则码字不可分离。第七节霍夫曼编码——二进制哈夫曼编码第七节霍夫曼编码——二进制哈夫曼编码将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树。信源熵为：平均码长为编码效率为若

6、采用定长编码，码长K=3，则编码效率可见哈夫曼的编码效率提高了12.7%。第七节霍夫曼编码——二进制哈夫曼编码第七节霍夫曼编码——二进制哈夫曼编码注意：哈夫曼的编法并不惟一。每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。不同的码元分配，得到的具体码字不同，但码长ki不变，平均码长也不变，所以没有本质区别；缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同

7、。不同的编法得到的码字长度ki也不尽相同。例：单符号离散无记忆信源，用两种不同的方法对其编二进制哈夫曼码。siliWi概率s1s2s3s4s512344101000001000110.40.20.20.10.10.40.20.20.20.40.40.20.60.4010101方法一：合并后的新符号排在其它相同概率符号的后面。第七节霍夫曼编码——二进制哈夫曼编码siliWi概率s1s2s3s4s512344101000001000110.40.20.20.10.10.40.20.20.20.40.40.20.60.4010101这两种编码哪

8、一种更好呢，我们来计算一下二者的码长。方法二：合并后的新符号排在其它相同概率符号的前面。第七节霍夫曼编码——二进制哈夫曼编码两种编码的平均码长是一样的，都是2.2，那一种更好呢，我们可以计算一