香农编码 ·例：有一单符号离散无记忆信源 X X2 X3 X4 X5 0.40.30.20.050.05 。X1(00) X1(00) X2(01) x2(01) X3(101) X3(10) 。X4(11100) ·X4(110) X5(11101) X5(111) H(X)1.95 7= =78% H(X)1.95 2.5 7= =92.9% 2.1
11 • 例: 有一单符号离散无记忆信源 1 2 3 4 5 ( ) 0.4 0.3 0.2 0.05 0.05 X x x x x x p x 香农编码 x1 (00) x2 (01) x3 (101) x4 (11100) x5 (11101) ( ) 1.95 78% 2.5 H X K ( ) 1.95 92.9% 2.1 H X K x1 (00) x2 (01) x5 (111) x3 (10) x4 (110)
费诺(Fano)编码 冬费诺编码属于概率匹配编码。编码步骤如下： 1.将概率按从大到小的顺序排列，令 p(X1)≥p(X2)≥..≥p(Xn) 2.按编码进制数将概率分组，使每组概率尽可能接近或 相等。如编二进制码就分成两组，编m进制码就分成m 组。 3.给每一组分配一位码元。 4,将每一分组再按同样原则划分，重复步骤2和3，直至概 率不再可分为止。 12
12 费诺( Fano )编码 v费诺编码属于概率匹配编码 。编码步骤如下： 1.将概率按从大到小的顺序排列,令 p(x1)≥ p(x2)≥…≥ p(xn) 2.按编码进制数将概率分组,使每组概率尽可能接近或 相等。如编二进制码就分成两组,编m进制码就分成m 组。 3.给每一组分配一位码元。 4.将每一分组再按同样原则划分,重复步骤2和3,直至概 率不再可分为止
费诺编码 例：设有一单符号离散信源 平均码长：K2.1 [ 编码效率 7=93% 0.40.30.20.050.05 平均码长：K=2.0 对该信源编二进制费诺码 编码效率：7 =97.5% 倍源 符号 信源 符号 符号 概率 第1次第2次第3次 码 码 特号 码 概率 第1第2 第3第4 码 分组今组分组 字 p(x;) 台组分组分组分组 字 p(x) X1 0.4 0 00 2 0.4 0 0 1 XA 0.05 0 0 010 3 X2 0.3 0 10 2 1 X5 0.05 011 3 X3 0.2 0 110 3 X2 0.3 0 10 2 X4 0.05 1 0 1110 4 X3 0.2 1 11 2 X5 0.05 4 13
13 信源 符号 xi 符号 概率 p(xi) 第1次 分组 第2次 分组 第3次 分组 码 字 码 长 x1 0.4 0 0 00 2 x4 0.05 1 0 010 3 x5 0.05 1 011 3 x2 0.3 1 0 10 2 x3 0.2 1 11 2 • 例：设有一单符号离散信源 • 对该信源编二进制费诺码 1 2 3 4 5 ( ) 0.4 0.3 0.2 0.05 0.05 X x x x x x p x 信源 符号 xi 符号 概率 p(xi) 第1 分组 第2 分组 第3 分组 第4 分组 码 字 码 长 x1 0.4 0 0 1 x2 0.3 1 0 10 2 x3 0.2 1 0 110 3 x4 0.05 1 0 1110 4 x5 0.05 1 1111 4 平均码长：K= 2.1 编码效率: η=93% 平均码长：K= 2.0 编码效率: η =97.5% 费诺编码
费诺编码 。例：设有一单符号离散无记忆信源 [H[& X7 7 1/41/81/81/161/161/16 1/16 。对该信源编二进制费诺码，其过程如表： 信源符号 概率 编码 码字 码长 X1 0.25 0 00 2 0 X2 0.25 1 01 2 X3 0.125 0 100 3 0 4 0.125 1 101 3 X5 0.0625 0 1 0.0625 0 1100 4 X6 1 1101 4 X7 0.0625 0 1110 4 X8 0.0625 1 1111 4 14
14 • 例：设有一单符号离散无记忆信源 信源符号 概率 编码 码字 码长 x1 0.25 0 0 00 2 x2 0.25 1 01 2 x3 0.125 1 0 0 100 3 x4 0.125 1 101 3 x5 0.0625 1 0 0 1100 4 x6 0.0625 1 1101 4 x7 0.0625 1 0 1110 4 x8 0.0625 1 1111 4 1 2 3 4 5 6 7 8 , , , , , ( ) 1/ 4 1/ 4 1/ 8 1/ 8 1/16 1/16 1/16 1/16 X x x x x x x x x P X 费诺编码 • 对该信源编二进制费诺码，其过程如表:
费诺编码 平均码长：F=(0.25+0.25)×2+0.12×2×3+0.0625×4×4=2.75bit/符号 。信源熵： H(X)=2.75bit/符号 x(00) 编码效率：刀=1 之所以如此，因 x,(01) ,(100 为每次所分两 组的概率恰好 ,(101) x(1100) 相等。 x(1101) x1110) x(1111) 15
15 v 信源熵： H X 2.75 bit / 符号 v 平均码长：K (0.25 0.25) 2 0.12 2 3 0.0625 4 4 2.75 bit / 符号 v 编码效率： 1 费诺编码 v 之所以如此,因 为每次所分两 组的概率恰好 相等