费诺编码 该信源的熵为H(X)=∑p(x)og2p(x)=2.35(比特/符号 i=1 平均码长为k=∑p(x)k=24(比特/符号) ■编码效率为 H(X) 2.352.35 m Klog, m Tlog2 2.4 =9792%这里L=1,m=2 ■本例中费诺编码有较高的编码效率。费诺码比较适合于 每次分组概率都很接近的信源。特别是对每次分组概率 都相等的信源进行编码时,可达到理想的编码效率
费诺编码 n 该信源的熵为 n 平均码长为 n 编码效率为 n 本例中费诺编码有较高的编码效率。费诺码比较适合于 每次分组概率都很接近的信源。特别是对每次分组概率 都相等的信源进行编码时，可达到理想的编码效率。 6 2 1 ( ) ( )log ( ) 2.35( / ) i i i H X p x p x 比特 符号 6 1 ( ) 2.4( / ) i i i K p x k 比特 符号 2.4 2 1 2 ( ) 2.35 2.35 97.92% 1, 2 log log 2 2.4 K L H X L m m 这里
费诺编码 题中码字还可用码树来表示,如图所示。 (01) 4(10 x.(110) s1110
费诺编码 n 题中码字还可用码树来表示，如图所示
霍夫曼编码 霍夫曼( Huffman)编码是一种效率比较高的变长 无失真信源编码方法。 编码步骤 ■二进制哈夫曼编码 ■m进制哈夫曼编码
霍夫曼编码 霍夫曼(Huf man)编码是一种效率比较高的变长 无失真信源编码方法。 n 编码步骤 n 二进制哈夫曼编码 n m进制哈夫曼编码
霍夫曼编码——编码步骤 ■将信源符号按概率从大到小的顺序排列,令 p(x1)p(x2)≥…p(xn) 给两个概率最小的信源符号p(xn1)和p(xn)各分配一个码位“0°和“1, 将这两个信源符号合并成一个新符号,并用这两个最小的概率之和 作为新符号的概率,结果得到一个只包含(n-1)个信源符号的新信源。 称为信源的第一次缩减信源,用S表示。 ■将缩减信源S1的符号仍按概率从大到小顺序排列,重复步骤2,得到 只含(mn-2)个符号的缩减信源S2 重复上述步骤,直至缩减信源只剩两个符号为止,此时所剩两个符 号的概率之和必为1。然后从最后一级缩减信源开始,依编码路径向 前返回,就得到各信源符号所对应的码字
霍夫曼编码——编码步骤 n 将信源符号按概率从大到小的顺序排列，令 p(x1)≥ p(x2)≥…≥ p(xn) n 给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1” ， 将这两个信源符号合并成一个新符号，并用这两个最小的概率之和 作为新符号的概率，结果得到一个只包含(n－1)个信源符号的新信源。 称为信源的第一次缩减信源，用S1表示。 n 将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到 只含(n－2)个符号的缩减信源S2。 n 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符 号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向 前返回，就得到各信源符号所对应的码字
霍夫曼编码——二进制哈夫曼编码 例设单符号离散无记忆信源如下,要求对信源编二进制 霍夫曼码。编码过程如下图(后页) P(X)104018010107006005004 在图中读取码字的时候,一定要从后向前读,此时编出 来的码字才是可分离的异前置码。若从前向后读取码字, 则码字不可分离
霍夫曼编码——二进制哈夫曼编码 例 设单符号离散无记忆信源如下，要求对信源编二进制 霍夫曼码。编码过程如下图（后页）。 1 2 3 4 5 6 7 8 , , , , , ( ) 0.4 0.18 0.1 0.1 0.07 0.06 0.05 0.04 X x x x x x x x x P X n 在图中读取码字的时候，一定要从后向前读，此时编出 来的码字才是可分离的异前置码。若从前向后读取码字， 则码字不可分离