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

信源编码,第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。 如是二元信源,则对于任意小的0,每一个信源符号的平均码长满足如下公式：,6,5.4 常用信源编码方法,7,常用信源编码,香农编码、费诺编码、哈夫曼编码主要是针对无记忆信源。 当信源有记忆时上述编码效率不高； 游程编码对相关信源编码更有效； 香农编码、费诺编码、哈夫曼编码属于无失真信源编码； 游程编码属于限失真信源编码。,8,游程编码,游程： 数字序列中连续出现相同符号的一段。 二元序列的游程：只有“0”和“1”两种符号。 连“0”这一段称为“0”游程,它的长度称为游程长度L(0)； 连“1”这一段称为“1”游程,它的游程长度用L(1)表示。,9,游程编码,二元独立序列游程长度概率 若规定二元序列总是从“0”开始,第一个游程是“0”游程,则第二个游程必为“1”游程,第三个又是“0”游程。 对于随机序列,游程长度是随机的其取值可为1,2,3,，直至无穷。 游程长度序列/游程序列：用交替出现的“0”游程和“1”游程长度表示任意二元序列。 游程变换： 是一种一一对应的变换,也是可逆变换。 例如：二元序列000101110010001 可变换成如下游程序列 31132131,10,游程变换减弱了原序列符号间的相关性。 游程变换将二元序列变换成了多元序列； 这样就适合于用其他方法,如哈夫曼编码,进一步压缩信源,提高通信效率。 编码方法： 首先测定“0”游程长度和“1”游程长度的概率分布,即以游程长度为元素,构造一个新的信源； 对新的信源(游程序列)进行哈夫曼编码。,游程编码,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点/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个像素 80% LW小于61个像素 50% LB小于4个像素 80% LB小于6个像素,LW白游程长度 LB 黑游程长度,15,游程编码,有了上述游程的概率分布,对不同的游程长度,按其不同的发生概率,可以分配不同的码字,这种编码方式称为游程编码。 游程编码既可以将白、黑游程分别按其概率进行分别编码,也可以将白长与黑长混起来统一编码。,16,黑、白分开编码时 白游程熵：,其中LW为白游程长度,p(LW)为对应的白游程概率,L为游程最大长度,对文件传真L=1728， 白游程平均编码长度应满足:,令 为白游程长的平均像素数,P84:5-2-9,每像数的编码比特数,平均每像素的熵值,17,黑游程熵：,黑游程平均编码长应满足,经过黑、白平均可得每个像素的熵值,每个像素的编码比特数,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 算术编码,算术编码是近十多年来发展迅速的一种无失真信源编码,它与最佳的哈夫曼码相比,理论性能稍加逊色,而实际压缩率和编码效率却往往还优于哈夫曼码,且实现简单,故很受工程上的重视。 算术编码不同于哈夫曼码,它是非分组(非块)码。它从全序列出发,考虑符号之间的关系来进行编码。 算术编码利用了累积概率的概念。 算术码主要的编码方法是计算输入信源符号序列所对应的区间。,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),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 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 )区间,得累积概率 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),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)= 0 P(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 =“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的区间宽度 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”) = 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)=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,实际编码时,只需两个存储器,起始时可令: A() =1, C() = 0 每输入一个信源符号,存储器C和A 就按照上式更新一次,直至信源符号输入完毕,就可将存储器C的内容作为该序列的码字输出。,34,算术编码,在编码过程中,每输入一个符号要进行乘法和加法运算,所以称为算术编码。 通过关于信源符号序列的累积概率的计算,把区间分割成许多小区间,不同的信源符号序列对应不同的区间为P(S), P(S) + p(S) 。可取小区间内的一点来代表这序列。,35,算术编码,编码方法： 将符号序列的累积概率写成二进位的小数，取小数点后L位,若后面有尾数,就进位到第L位,这样得到的一个数C,并使L满足,取整,36,例：设二元无记忆信源S=0,1,其