《信息论与编码技术》课程教学课件（讲稿）第五章 无失真信源编码

信息论与编码技术第5章无失真信源编码2024

2024

无失真信源编码算法5.1香农编码5.2费诺编码5.3哈夫曼编码5.4常用的变长编码算法2/信息论与编码技术-无失真信源编码定理

信息论与编码技术-无失真信源编码定理 2/  5.1 香农编码  5.2 费诺编码  5.3 哈夫曼编码  5.4 常用的变长编码算法

5.1香农编码设有离散无记忆信源XiX2xZp(x)=1p(x)p(x2)i=11i= 1,2....ql;logp(s;)L< H,(S)+1r--码元符号数()时(a;为整数)只有当信源符号概率筛呈现L才能达到极限值,(S)33/信息论与编码技术-无失真信源编码定理

信息论与编码技术-无失真信源编码定理 3/ 3 =  =      n i i n n p x p x p x p x x x x 1 2 1 1 2 , ( ) 1 ( ) ( ) . ( ) . 设有离散无记忆信源 L H S 1 i 1 2 q p s 1 l r i i  + =       = ( ) , ,., ( ) log ( ). ( ), L H S a r 1 r i ai 才能达到极限值 只有当信源符号概率分布呈现（ ） 时 为整数 r-码元符号数

香农编码方法的步骤按信源符号的概率从大到小的顺序排队不妨设 p(x)≥ p(x)≥ ......≥ p(x,)令p(xo)=0，用pa(x,),j=i+l表示第i个码字的累加概率(x;)=乞p(x;)i=1-log2p(xi) ≤ ki < 1 - log2p(xi)把pa(xi)用二进制数表示，用小数点后的k位作为x;的码字

4 1 2 3 4 香农编码方法的步骤 按信源符号的概率从大到小的顺序排队 ( ) ( ) . ( ) 1 2 n 不妨设 p x  p x   p x 表示第 个码字的累加概率 令 ，用 i p x p x j i ( 0 ) = 0 a ( j ), = +1 =  − = j 1 i 1 pa x j p xi ( ) ( ) 把𝑝𝑎 𝑥𝑖 用二进制数表示，用小数点后的𝑘𝑖 位作为𝑥𝑖的码字 −log2𝑝 𝑥𝑖 ≤ 𝑘𝑖 < 1 − log2𝑝 𝑥𝑖

例设有一单符号离散无记忆信源Xx1X2XsX3X40.20.10.250.150.050.25P(X)试对该信源编二进制香农码

5 例       =      ( ) 0.25 0.25 0.2 0.15 0.1 0.05 2 3 4 5 6 x1 x x x x x P X X 设有一单符号离散无记忆信源 试对该信源编二进制香农码

(1) pa(x,)=Zp(x,)编码过程i=0码字kiPa(x;)20000.25x12010.250.25X230.20.5100X331010.150.7x440.10.851101X550.050.9511110X6- log2 p(x,)≤k, ≤1 - log2 p(x,)6

6 x 0 05 0 95 5 11110 x 0 1 0 85 4 1101 x 0 15 0 7 3 101 x 0 2 0 5 3 100 x 0 25 0 25 2 01 x 0 25 0 2 00 p x k 6 5 4 3 2 1 a j i . . . . . . . . . . . ( ) 码 字 编码过程  − = = 1 0 ( ) ( ) j i a j i （1） p x p x log ( ) 1 log ( ) 2 i i 2 i − p x  k  − p x

评价指标H(X)=2.42比特/信源符号6平均码长：L=p(x,)l,=2.7码元/信源符号i=1Llog, m = L比特/信源符号编码信息率：R=N编码信息率：是指编码后平均分配给每个信源符号的信息量最大信息量，或每个信源符号平均占用的最大信息量H(x)2.42编码效率：n89.63%二=R2.71

7 6 1 ( ) 2.7 / i i i L p x l = 平均码长： = =  码元 信源符号 H X( ) 2.42 = 比特/信源符号 ( ) 2.42 89.63% 2.7 H x R 编码效率： = = = 2 log / L R m L N 编码信息率： = = 比特 信源符号 评价指标 编码信息率：是指编码后平均分配给每个信源符号的信息 量最大信息量，或每个信源符号平均占用的最大信息量

5.2弄费诺编码-按信源符号的概率从大到小的顺序排队 p(x) ≥ p(x) ≥.....≥ p(xn)不妨设对概率按m(码符号数)进行分组，使每组概率尽可能相等给每个分组分配一个码元对每个分组重复2、3步，直到不可分为止8/信息论与编码技术一无失真信源编码定理

信息论与编码技术-无失真信源编码定理 8/ 对概率按m(码符号数)进行分组，使每 组概率尽可能相等 给每个分组分配一个码元 对每个分组重复2、3步，直到不可分 为止 按信源符号的概率从大到小的顺序排队 ( ) ( ) . ( ) 1 2 n 不妨设 p x  p x   p x 1 2 3 4

美例设有一单符号离散无记忆信源Xx1X2X3X4Xs460.220.180.160.080.0410.32P(X) I试对该信源编二进制费诺码。9/信息论与编码技术-无失真信源编码定理

信息论与编码技术-无失真信源编码定理 9/       =      ( ) 0.32 0.22 0.18 0.16 0.08 0.04 2 3 4 5 6 x1 x x x x x P X X 设有一单符号离散无记忆信源 试对该信源编二进制费诺码。 例

编码过程0000.32Xi001X20.22110x0.180x401100.1610Xs0.081110111111t0.041

1 x 2 x 3 x 4 x 5 x 6 x 0.32 0.22 0.18 0.16 0.08 0.04 0 0 1 0 1 0 0 1 1 000110110 1110 1111 1 编码过程