信息论与编码课件第5章-3.ppt

信源编码 第5章 5.1 编码的定义 5.2 无失真信源编码 5.3 限失真信源编码 5.4 常用信源编码方法简介 限失真信源编码定理 在本章一开始我们就分析了在很多实际信源中,特别在模拟的连续信源中,无失真要求是完全没有必要的,而且也是达不到的。 在实际中限失真信源是具有现实意义的 限失真信源编码定理 限失真信源编码定理： 设离散无记忆信源X的信息率失真函数为R(D) , 当信息率 ＞R(D)时,只要信源序列长度 L 足够长,一定存在一种编码方法,其译码失真小于或等于 D+ε,ε为任意小的正数； 反之,若 ＜R(D) ,则无论采用什么样的编码方法,其译码失真必大于D。 如是二元信源,则对于任意小的ε＞0,每一个信源符号的平均码长满足如下公式： 5.4.2 算术编码 算术编码是近十多年来发展迅速的一种无失真信源编码,它与最佳的哈夫曼码相比,理论性能稍加逊色,而实际压缩率和编码效率却往往还优于哈夫曼码,且实现简单,故很受工程上的重视。 算术编码不同于哈夫曼码,它是非分组(非块)码。。 算术编码利用了累积概率的概念。 算术码主要的编码方法是计算输入信源符号序列所对应的区间。 累积概率 设信源符号集A={a1,a2,…,an},其相应概率分布为p(ai), p(ai) 0(i=1,2, …,n) 信源符号的累积概率为 累积概率Pr+1和Pr都是小于1的正数,可用[0,1]区间内的两个点来表示; 算术编码 二元信源符号序列的累积概率递推公式 例：已输入二元符号序列为S=“011”,接着再输入符号为“1”, 得序列累积概率为： P(S1)=P(0111)=P(S=“011”)+p(011)p(0) =P(S=“01”)+p(01)p(0)+p(011)p(0) =P(S=“0”)+p(0)p(0)+p(01)p(0)+p(011)p(0) =0 +p(00)+p(010)+p(0110) 对应的区间宽度为 A(S1)=p(S=“011”) p(1)= p(011) p(1)= p(0111) 算术编码 实际应用中,采用累积概率P(S)表示码字C(S),符号概率p(S)表示状态区间A(S),则有： C(S,r) = C(S)+A(S)Pr A(S,r) = A(S) pr 算术编码 编码方法： 将符号序列的累积概率写成二进位的小数，取小数点后L位,若后面有尾数,就进位到第L位,这样得到的一个数C,并使L满足 算术编码 例如 P(S)＝0p(S)=1/17，则L＝5， 得C＝0.10111 这个C就可作为S的码字 编码效率很高，当序列很长时，可达到概率匹配。平均代码长度接近S的熵值。可以唯一地译码 算术编码 算术编码 设起始状态为空序列?， 则A(?) ＝1，C(?)＝0。 算术编码 算术编码 算术编码 算术编码 译码 C(abda)=0.0101110.1?[0,0.1] 第一个符号为a 放大至[0,1](×pa-1)： C(abda)×21＝0.10111?[0.1,0.110] 第二个符号为b 去掉累积概率Pb： 0.10111-0.1=0.00111 算术编码 放大至[0,1](×p b-1)： 0.00111×22=0.111 ?[0.111,1] 第三个符号为d 去掉累积概率Pd： 0.111-0.111=0 放大至[0,1](×p d-1)：0×24＝0 ?[0,0.1] 第四个符号为a 信源编码总结 我们学习了几种信源编码：香农编码、费诺编码、哈夫曼编码、算术编码。 --香农编码、费诺编码、哈夫曼编码是分组 编码； 算术编码是非分组编码； 本章介绍的都是离散信源变长编码。 优点：提高编码效率； 缺点：需要大量缓冲设备来存储这些变长码,然后再以恒定的码率进行传送；在传输的过程中如果出现了误码,容易引起错误扩散,所以要求有优质的信道。 * * 内容 5.3 限失真信源编码定理 5.4 常用信源编码方法 显然 P1= 0; P2= p1 ; P3= p1+p2 ; … 而且 pr = Pr+1 － Pr P1 p1 P2 P3