《信息论与编码》第三章 无失真信源编码（3-2）香农编码

香农编码 设离散无记忆信源 X P(X)1p(x),p(x2) P(x) ■二进制香农码的编码步骤如下: ■将信源符号按概率从大到小的顺序排列,为方便起见,令 p(x1)p(x2)…>p(xn) n令p(x)=0,用p(x),产计1表示第个码字的累加概率,则: P(x)=∑p(x),j=1,2 n确定满足下列不等式的整数k,并令k为第个码字的长度 log2 p(n)ski<- log2 p(xn)+ n将p(x)用二进制表示,并取小数点后k位作为符号x的编码

香农编码 n 设离散无记忆信源 n 二进制香农码的编码步骤如下： n 将信源符号按概率从大到小的顺序排列，为方便起见，令 p(x1)≥ p(x2)≥…≥ p(xn) n 令p(x0)=0，用pa(xj)，j=i+1表示第i个码字的累加概率，则： n 确定满足下列不等式的整数ki，并令ki为第i个码字的长度 n －log2 p(xn)≤ki<－ log2 p(xn)+1 n 将pa(xj) 用二进制表示，并取小数点后ki 位作为符号xi的编码。 1 0 ( ) ( ), 1, 2, , j a j i i p x p x j n       1 2 1 2 1 , , , , , , ( ) 1 ( ) ( ), ( ), , ( ), , ( ) n i n i i n i X x x x x p x P X p x p x p x p x                    

香农编码 例厂有一单符号离散无记忆信源 P(X)0.250.250.200.150.100.05 对该信源编二进制香农码。其编码过程如下表所示 二进制香农编码 xp(x)p(x)k码字 0.25 0.000 00(0.000)2 0.25 0.250 201(0.010)z 0.200.50031000)2 0.15 0.700 3101(0.10) 0.100.85041010.101 x60.050.950 51l1100.1

香农编码 例 有一单符号离散无记忆信源 对该信源编二进制香农码。其编码过程如下表所示。 二进制香农编码 xi p(xi) pa(xj) ki 码字 x1 0.25 0.000 2 00(0.000)2 x2 0.25 0.250 2 01(0.010)2 x3 0.20 0.500 3 100(0.100)2 x4 0.15 0.700 3 101(0.101)2 x5 0.10 0.850 4 1101(0.1101)2 x6 0.05 0.950 5 111110(0.11110)2 1 2 3 4 5 6 , , , , , ( ) 0.25 0.25 0.20 0.15 0.10 0.05 X x x x x x x P X             

香农编码 计算出给定信源香农码的平均码长 K=0.25×2×2+(0.2+0.15)×3+0.10×4+0.05×5=27(比特/符号) 若对上述信源采用等长编码,要做到无失真译码,每个符号至少要用3 个比特表示。相比较,香农编码对信源进行了压缩 由离散无记忆信源熵定义,可计算出: H(X)=∑p(x)log2p(x)=242(比特/符号) ■对上述信源采用香农编码的信息率为 R=02、21g22=2.7这里L=1,m=2 K L ■编码效率为信源熵和信息率之比。则η H(X)242 8963% R 7 可以看出,编码效率并不是很高

香农编码 n 计算出给定信源香农码的平均码长 n 若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用3 个比特表示。相比较，香农编码对信源进行了压缩。 n 由离散无记忆信源熵定义，可计算出： n 对上述信源采用香农编码的信息率为 n 编码效率为信源熵和信息率之比。则 n 可以看出，编码效率并不是很高。 K  0.25  2  2  (0.2  0.15)  3  0.10  4  0.05  5  2.7(比特 / 符号) 2 2 2.7 log log 2 2.7 1, 2 1 K R m L m L    这里   ( ) 2.42 89.63% 2.7 H X R     6 2 1 ( ) ( )log ( ) 2.42( / ) i i i H X p x p x     比特 符号

费诺编码 费诺编码也是一种常见的信源编码方法 编码步骤如下: ■将概率按从大到小的顺序排列,令 p(x1≥p(x2)≥…p(xn 按编码进制数将概率分组,使每组概率尽可能接近或相等。如 编二进制码就分成两组,编m进制码就分成m组。 给每一组分配一位码元 将每一分组再按同样原则划分,重复步骤2和3,直至概率不再 可分为止

费诺编码 费诺编码也是一种常见的信源编码方法。 编码步骤如下： n 将概率按从大到小的顺序排列，令 p(x1)≥ p(x2)≥…≥ p(xn) n 按编码进制数将概率分组，使每组概率尽可能接近或相等。如 编二进制码就分成两组，编m进制码就分成m组。 n 给每一组分配一位码元。 n 将每一分组再按同样原则划分，重复步骤2和3，直至概率不再 可分为止

费诺编码 例设有一单符号离散信源 P(X)0320220.18016008004 对该信源编二进制费诺码。编码过程如下表。 进制费诺编码 信源符号概率 编码 「码字码长 0.32 0 2 0 X2 0.22 01 0.18 0 10 2 0.16 0 0.08 0 1110 0.04

费诺编码 例 设有一单符号离散信源 n 对该信源编二进制费诺码。编码过程如下表。 二进制费诺编码 信源符号 概率 编码 码字 码长 x1 0.32 0 00 2 x2 0.22 0 1 01 2 x3 0.18 0 10 2 x4 0.16 0 110 3 x5 0.08 0 1110 4 x6 0.04 1 1 1 1 1111 4 1 2 3 4 5 6 , , , , , ( ) 0.32 0.22 0.18 0.16 0.08 0.04 X x x x x x x P X             

费诺编码 该信源的熵为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 在图中读取码字的时候，一定要从后向前读，此时编出 来的码字才是可分离的异前置码。若从前向后读取码字， 则码字不可分离