信息论与编码第5章.ppt

《信息论与编码第5章.ppt》由会员分享，可在线阅读，更多相关《信息论与编码第5章.ppt（39页珍藏版）》请在三一办公上搜索。

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

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

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

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

5、辨率为5点/mm。直接编码时需传送：21029752=1.5Mbit用2400bit/s的数码率传送约需11分钟如果希望达到CCITT的第3类文件传真机的标准,即用市话网作信道,1分钟内传输一页A4文件,那么我们就需要找到一种编码方法,把数码压缩到原来的1/11。某一种编码的压缩比为：,14,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小于18个像

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

7、足,经过黑、白平均可得每个像素的熵值,每个像素的编码比特数,18,黑、白游程分别最佳编码后,由每个像素的熵hWB 即可得到最小比特率。极限压缩比,游程编码,19,对中文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倍,20,5.4.2 算术编

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

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

10、 Pr,23,累积概率Pr+1和Pr都是小于1的正数,可用0,1区间内的两个点来表示;,P1,p1,P2,P3,P4,1,p2,p3,0,pr就是这两点间的小区间的长度,如图:,当A=0,1二元信源时：P(0)=0;P(1)=p(0),P(0),P(1),0,1,p(0),p(1),24,计算二元无记忆信源序列的累积概率初始时：在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

11、)区间,得累积概率 P(S=“0”)=P(0)=0；,算术编码,25,若输入第二个符号为“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),26,P(0),0,P(1),1,p(0),设输入符号序列S=011,p(1),P(0)

12、,P(1),p(00),P(01),p(01),P(01),P(1),P(011),p(010),p(011),p(0)=p(00)+p(01)p(01)=p(010)+p(011)归一律,P(0)=0P(01)=p(00)P(011)=P(01)+p(010),27,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

13、=“01”)A(S=“010”)=A(S)A(S0)其对应的区间为P(S)+A(S)p(0),P(1)；,28,P(0),0,P(1),1,p(0),p(1),P(0),P(1),p(00),P(S)S=01,p(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的区间

14、宽度A(1)=p(1),符号“00”区间宽度A(00)=p(00),信源符号“01”区间宽度A(01)=p(01)=A(0)-A(00),29,符号序列对应的区间宽度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”

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

16、)=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),32,算术编码,一般多元信源序列的累积概率递推公式,序列的概率公式,33,算术编码,实际应用中,采用累积概率P(S)表示码字C(S),符号概率p(S)表示状态区间A(S),则有：C(S,r)=C(S)+A(S)Pr A(S,r)=A(S)pr,实际编码时,只需两个存储器

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

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