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

《信息论与编码第5章-3.ppt》由会员分享，可在线阅读，更多相关《信息论与编码第5章-3.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信源编码信源编码 第5章5.1 编码的定义5.2 无失真信源编码5.3 限失真信源编码5.4 常用信源编码方法简介内容25.3 限失真信源编码定理3限失真信源编码定理 在本章一开始我们就分析了在很多实际信源中,特别在模拟的连续信源中,无失真要求是完全没有必要的,而且也是达不到的。在实际中限失真信源是具有现实意义的4限失真信源编码定理 限失真信源编码定理：设离散无记忆信源X的信息率失真函数为R(D),当信息率 RR(D)时,只要信源序列长度 L 足够长,一定存在一种编码方法,其译码失真小于或等于 D+,为任意小的正数；反之,若RR(D),则无论采用什么样的编码方法,其译码失真必大于D。如是二元信

2、源,则对于任意小的0,每一个信源符号的平均码长满足如下公式：55.4 常用信源编码方法6常用信源编码 香农编码、费诺编码、哈夫曼编码主要是针对无记忆信源。当信源有记忆时上述编码效率不高；游程编码对相关信源编码更有效；香农编码、费诺编码、哈夫曼编码属于无失真信源编码；游程编码属于限失真信源编码。7游程编码 游程：数字序列中连续出现相同符号的一段。二元序列的游程：只有“0”和“1”两种符号。连“0”这一段称为“0”游程,它的长度称为游程长度L(0)；连“1”这一段称为“1”游程,它的游程长度用L(1)表示。8游程编码 二元独立序列游程长度概率 若规定二元序列总是从“0”开始,第一个游程是“0”游程

3、,则第二个游程必为“1”游程,第三个又是“0”游程。对于随机序列,游程长度是随机的其取值可为1,2,3,，直至无穷。游程长度序列/游程序列：用交替出现的“0”游程和“1”游程长度表示任意二元序列。游程变换：是一种一一对应的变换,也是可逆变换。例如：二元序列000101110010001 可变换成如下游程序列 311321319 游程变换减弱了原序列符号间的相关性。游程变换将二元序列变换成了多元序列；这样就适合于用其他方法,如哈夫曼编码,进一步压缩信源,提高通信效率。编码方法：首先测定“0”游程长度和“1”游程长度的概率分布,即以游程长度为元素,构造一个新的信源；对新的信源(游程序列)进行哈夫曼

4、编码。游程编码10传真编码 文件传真的基本特性 文字传真:黑、白两个灰度级 图像传真:有比较丰富的灰度的图片、图像 数字式文件传真把一页文件分为nm个像素 Xij表示第i行(i=l,2n)第j列(j=l,2m)的像素 由于文件传真是二值电平二值电平的,即只有两个灰度值,Xij0(白色)1(黑色)11传真编码 直接编码：每一个像素用一位二进码(0或1)代表 一页文件的码元数就等于该页二值图像的像素数 X3=1111 0010 0011 0001 1111分辨率分辨率：单位长度(lmm)包含的像素数。分辨率愈高,文件细节愈清晰,文件质量也就愈高。但是表示一页文件的比特数就愈多。12 例如一页A4文

5、件,分辨率为5点/mm。直接编码时需传送：21029752=1.5Mbit 用2400bit/s的数码率传送约需11分钟 如果希望达到CCITT的第3类文件传真机的标准,即用市话网作信道,1分钟内传输一页A4文件,那么我们就需要找到一种编码方法,把数码压缩到原来的1/11。某一种编码的压缩比为：13 CCITT建议使用两种分辨率：1728像素/行(8样点/mm),3.85行/mm(4行/mm)1728像素/行(8样点/mm),7.7行/mm(8行/mm)根据汉字的特点,对传真用的七种试用样张进行了统计,测得下列平均值：p(白)=pW=93.3 p(黑)=pB=6.7 测试结果表明：50%LW小

6、于18个像素 80%LW小于61个像素 50%LB小于4个像素 80%LB小于6个像素LW白游程长度LB 黑游程长度14游程编码 有了上述游程的概率分布,对不同的游程长度,按其不同的发生概率,可以分配不同的码字,这种编码方式称为游程编码。游程编码既可以将白、黑游程分别按其概率进行分别编码,也可以将白长与黑长混起来统一编码。15 黑、白分开编码时 白游程熵：其中LW为白游程长度,p(LW)为对应的白游程概率,L为游程最大长度,对文件传真L=1728，白游程平均编码长度应满足:令 为白游程长的平均像素数P84:5-2-9每像数的编码比特数 平均每像素的熵值 16 黑游程熵：黑游程平均编码长应满足

7、经过黑、白平均可得每个像素的熵值 每个像素的编码比特数 17 黑、白游程分别最佳编码后,由每个像素的熵hWB 即可得到最小比特率。极限压缩比游程编码18 对中文A4文件七种样张的平均值：分辨率88 分辨率84 pW=0.9326 0.933;pB=0.0674 0.0670 LW=85.99 86.44 像素(pel)LB=5.73 5.72 像素(pel)HW=5.89 5.87 b/run HB=3.14 3.14 b/run hWB=0.1003 0.0997 b/pel K0=9.97 10.03对中文A4文件,7种样张的统计极限压缩比 K0 10倍195.4.2 算术编码 算术编码是

8、近十多年来发展迅速的一种无失真信源编码,它与最佳的哈夫曼码相比,理论性能稍加逊色,而实际压缩率和编码效率却往往还优于哈夫曼码,且实现简单,故很受工程上的重视。算术编码不同于哈夫曼码,它是非分组(非块)码。它从全序列出发,考虑符号之间的关系来进行编码。算术编码利用了累积概率累积概率的概念。算术码主要的编码方法是计算输入信源符号序列所对应的区间。20算术码的主要概念 算术码的主要概念：把信源输出序列的概率和实数段0,1中的一个数C联系起来。设信源字母表为a1,a2,其概率p(a1)=0.6,p(a2)=0.4 将0,1分成与概率比例相应的区间,0,0.6 0.6,lp(a1)p(a2)0 0.6

9、1 设信源输出序列S=S1S2S3Sn 当信源输出的第一个符号S1=a1时,数C的值处在0,0.6 当信源输出的第一个符号S1=a2时,数C的值处在0.6,l 根据信源S1的情况,把C所在的段再次按概率比例划分0 0.36 0.6 0.84 1p(a1a1)p(a1a2)p(a2a1)p(a2a2)随着序列的长度不断增加,C所在区间的长度就越短,也就可以更加精确地确定C的位置 21累积概率 设信源符号集A=a1,a2,an,其相应概率分布为p(ai),p(ai)0(i=1,2,n)信源符号的累积概率累积概率为 显然 P1=0;P2=p1;P3=p1+p2;而且 pr=Pr+1 Pr22 累积概

10、率Pr+1和Pr都是小于1的正数,可用0,1区间内的两个点来表示;P1p1P2P3P41p2p30 pr就是这两点间的小区间的长度,如图:当A=0,1二元信源时：P(0)=0;P(1)=p(0)P(0)P(1)0 1p(0)p(1)23 计算二元无记忆信源序列的累积概率累积概率 初始时：在0,1)区间内由P(1)划分成二个子区间0,P1)和P1,1),P(1)=p(0)。子区间0,P1)的宽度为A(0)=p(0),对应于信源符号“0”；子区间P1,1)的宽度为A(1)=p(1),对应于信源符号“1”；若输入符号序列的第一个符号为S=“0”,落入0,P1)区间,得累积概率累积概率 P(S=“0”

11、)=P(0)=0；算术编码24 若输入第二个符号为“1”,S=“01”,S=“01”所对应的区间是在区间0,P(1)中进行分割；符号序列“00”对应的区间宽度为 A(00)=A(0)p(0)=p(0)p(0)=p(00)；对应的区间为0,P(S=“01”)。符号序列“01”对应的区间宽度为 A(01)=A(0)p(1)=p(0)p(1)=p(01)=A(0)A(00)；对应的区间为P(S=“01”),P(1)。累积概率累积概率:P(S=“01”)=p(00)=p(0)p(0)25P(0)0 P(1)1p(0)设输入符号序列S=011p(1)P(0)P(1)p(00)P(01)p(01)P(01

12、)P(1)P(011)p(010)p(011)p(0)=p(00)+p(01)p(01)=p(010)+p(011)归一律归一律 P(0)=0 P(01)=p(00)P(011)=P(01)+p(010)26 011S1,S=01 输入序列S1=“011”对应的区间是对区间P(S),P(1)进行分割 序列S0=“010”对应的区间宽度为 A(S=“010”)=A(S=“01”)p(0)=A(S)p(0)其对应的区间为P(S),P(S)+A(S)p(0)；序列S1=“011”对应的区间宽度为 A(S=“011”)=A(S)p(1)=A(S=“01”)A(S=“010”)=A(S)A(S0)其对应

13、的区间为P(S)+A(S)p(0),P(1)；27P(0)0 P(1)1p(0)p(1)P(0)P(1)p(00)P(S)S=01p(01)P(S)P(1)P(S1)p(010)p(011)当前面输入符号序列为S,若接着输入一个“0”,累积概率累积概率:P(S0)=P(S)对应区间宽度为：A(S0)=A(S)p(0)若接着输入的一个符号是“1”，累积概率累积概率:P(S1)=P(S)+A(S)p(0)对应区间宽度为：A(S1)=A(S)p(1)=A(S)A(S0)信源符号0的区间宽度A(0)=p(0)符号1的区间宽度A(1)=p(1)符号“00”区间宽度A(00)=p(00)信源符号“01”区

14、间宽度A(01)=p(01)=A(0)-A(00)28 符号序列对应的区间宽度A(S=“0”)=p(0)A(S=“1”)=1A(S=“0”)=p(1)A(S=“00”)=p(00)=A(0)p(0)=p(0)p(0)A(S=“01”)=A(S=“0”)A(S=“00”)=p(01)=A(0)p(1)=p(0)p(1)A(S=“10”)=p(10)=A(1)p(0)=p(1)p(0)A(S=“11”)=A(S=“1”)A(S=“10”)=p(11)=A(S=“1”)p(1)=p(1)p(1)A(S=“010”)=A(S=“01”)p(0)=p(01)p(0)p(010)A(S=“011”)=A(

15、S=“01”)A(S=“010”)=A(S=“01”)p(1)=p(01)p(1)=p(011)信源符号序列S所对应区间的宽度等于符号序列S的概率p(S)。算术编码29算术编码 二元信源符号序列的累积概率递推公式 Sr表示前面信源符号序列为S,接着再输入符号为r P(0)=0，P(1)=p(0)P(S0)=P(S)P(S1)=P(S)+p(S)p(0)信源符号序列所对应区间的宽度递推公式30 例：已输入二元符号序列为S=“011”,接着再输入符号为“1”,得序列累积概率为：P(S1)=P(0111)=P(S=“011”)+p(011)p(0)=P(S=“01”)+p(01)p(0)+p(011

16、)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)31算术编码 一般多元信源序列的累积概率递推公式 序列的概率公式32算术编码 实际应用中,采用累积概率P(S)表示码字C(S),符号概率p(S)表示状态区间A(S),则有：C(S,r)=C(S)+A(S)Pr A(S,r)=A(S)pr 实际编码时,只需两个存储器,起始时可令:A()=1,C()=0 每输入一个信源符号,存储器C和A 就按照上式更新一次,直至信源符号输

17、入完毕,就可将存储器C的内容作为该序列的码字输出。33算术编码 在编码过程中,每输入一个符号要进行乘法和加法运算,所以称为算术编码算术编码。通过关于信源符号序列的累积概率的计算,把区间分割成许多小区间,不同的信源符号序列对应不同的区间为P(S),P(S)+p(S)。可取小区间内的一点来代表这序列。34算术编码 编码方法：将符号序列的累积概率累积概率写成二进位的小数，取小数点后L位,若后面有尾数,就进位到第L位,这样得到的一个数C,并使L满足取整35例：设二元无记忆信源S=0,1,其p(0)=1/4,p(1)=3/4。对二元序列11111100做算术编码。P(S)=p(00000000)+p(0

18、0000001)+p(00000010)+p(11111011)=1 p(11111111)p(11111110)p(11111101)p(11111100)=1 p(111111)=1(3/4)6=0.110100100111得 C=0.1101010 S的码字为 1101010解：p(S=11111100)=p2(0)p6(1)=(1/4)2(3/4)636+=p(1)=3/4=(0.11)2p(11)=(3/4)2=(0.1001)2+=p(0)=(1/4)=2-2p(S)p(0)p(S)右移2位37信源编码总结 我们学习了几种信源编码：香农编码、费诺编码、哈夫曼编码、游程编码、算术编码。游程编码和算术编码是非分组编码；游程编码是限失真信源编码。本章介绍的都是离散信源变长编码。优点：提高编码效率；缺点：需要大量缓冲设备来存储这些变长码,然后再以恒定的码率进行传送；在传输的过程中如果出现了误码,容易引起错误扩散,所以要求有优质的信道。38 有时为了得到较高的编码效率，先采用某种正交变换，解除或减弱信源符号间的相关性，然后再进行信源编码；有时则利用信源符号间的相关性直接编码。39