香农编码 设离散无记忆信源 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