常用信源编码方法简介

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,符号序列中某符号连续重复出现而形成符号串的长度，又称为游程长度或游长。,将这种符号序列映射成游程长度和对应符号序列的位置的标志序列。,如果知道了游程长度和对应符号序列的位置的标志序列，就可以完全恢复出原来的符号序列。,1,游程编码,二元序列的游程,连续出现“0”，称为“0”游程，表示为,L,(0)。连续出现“1”，称为“1”游程，表示为,L,(1)。,若规定二元序列总是从“0”开始，第一个游程是“0”游程，则第二个游程必为“1”游程，第三个又是“0”游程,对于随机序列，游程长度是随机的其取值可为1,2,3,，直至无穷。,用交替出现,的“0”游程和“1”游程,长度表示任意二元序列。,一种一一对应的变换，是可逆变换。,2,5.4 常用信源编码方法简介,游程编码,在二元序列中，连0段称为,0游程,连1段称为,1游程,0001,可变换成下列游程序列：3113213,3,5.4 常用信源编码方法简介,若已知,二元序列,以0起始，从游程序列很容易恢复成原来的二元序列,游程序列是多元序列，各长度可按,霍夫曼编码,或其它方法处理以达到压缩码率的目的。,4,5.4 常用信源编码方法简介,多元序列也存在相应的游程序列,多元序列变换成游程序列再进行压缩编码没有多大意义,游程编码只适用于二元序列，对于多元信源，一般不能直接利用游程编码,5,5.4 常用信源编码方法简介,冗余位编码,，游程编码在多元信源的应用,6,5.4 常用信源编码方法简介,如下多元序列,x,1,，,x,2,，,x,m1,，,y,，,y,，,y,，,x,m1+1,，,x,m1+2,，,x,m2,，,y,，,y,，,可以用下面序列表示,111，100，000111，111000,x,1,，,x,2,，,x,m1,，,x,m1+1,，,x,m1+2,x,2,，,1表示信息位，0表示冗余位,7,5.4 常用信源编码方法简介,算术编码,非分组码,的编码方法之一算术码,8,算术码的主要概念,把信源输出序列概率和实数段0,1中的一个数C联系起来。,设信源字母表为,a,1,a,2,，其概率,p,(,a,1,)=0.6,p,(,a,2,)=0.4,将0,1分成与概率比例相应的区间，0, 0.6 和0.6, l,设信源输出序列,S,=,S,1,S,2,S,3,S,n,当信源输出的第一个符号,S,1,=,a,1,时，数C的值处在0, 0.6,当信源输出的第一个符号,S,1,=,a,2,时，数C的值处在0.6, l,根据信源,S,1,的情况，把C所在的段再次按概率比例划分,算术编码,p,(,a,1,),p,(,a,2,),0 0.6 1,0 0.36 0.6 0.84 1,p,(,a,1,a,1,),p,(,a,1,a,2,),p,(,a,2,a,1,),p,(,a,2,a,2,),9,5.4 常用信源编码方法简介,符号概率与积累概率的递推关系,10,5.4 常用信源编码方法简介,采用累积概率P(S)表示码字C(S)，符号概率,p,(S)表示状态区间A(S),11,5.4 常用信源编码方法简介,P(S)把区间0，1)分割成许多小区间，每个小区间的长度等于各序列的概率,p,(S)，小区间内的任一点可用来代表这序列,0(P,1,) P,2,P,3,P,4,P,5, 1,p,1,p,2,p,3,p,4,12,5.4 常用信源编码方法简介,0(P,1,) P,2,P,3,P,4,P,5, 1,p,1,p,2,p,3,p,4,代表大于或等于的最小整数。,把积累概率P(S)写成二进位的小数，取其前L位;如果有尾数，就进位到第L位，这样得到一个数C,13,5.4 常用信源编码方法简介,例如,P(S)0.10110001，,p,(S)=1/17，则L5，得C0.10111,这个C就可作为S的码字,编码效率,很高，当序列很长时，可达到,概率匹配,。平均代码长度接近S的熵值。可以,唯一地译码,14,5.4 常用信源编码方法简介,符号,符号概率,p,i,符号累积概率,P,j,a,0.100(1/2),0.000,b,0.010(1/4),0.100,c,0.001(1/8),0.110,d,0.001(1/8),0.111,例,有四个符号,a，b，c，d,构成简单序列S,abda,，各符号及其对应概率如下表，算术编解码过程如下：,15,5.4 常用信源编码方法简介,设起始状态为空序列,，,则1，C(,)0。,16,5.4 常用信源编码方法简介,17,5.4 常用信源编码方法简介,C(,abda,)即为编码后的码字010111,18,5.4 常用信源编码方法简介,A(,),A(,a,),a b c d,A(,a,b,),a b c d,a b c d,A(,a,b,d,),C(,) 0(P,a,),p,a,P,b,p,b,P,c,p,c,P,d,p,d,1,C(,0,),C(,a,b,d,),C(,a,b,),算术编码过程,19,5.4 常用信源编码方法简介,译码,C(,abda,)=0.0101110.1,0,0.1,第一个符号为,a,放大至0,1(,p,a,-1,)：,C(,abda,)2,1,0.10111,0.1,0.110,第二个符号为,b,去掉累积概率P,b,： 0.10111-0.1=0.00111,20,5.4 常用信源编码方法简介,放大至0,1(,p,b,-1,)：,0.001112,2,=0.111,0.111,1,第三个符号为,d,去掉累积概率P,d,： 0.111-0.111=0,放大至0,1(p,d,-1,)：02,4,0,0,0.1 第四个符号为,a,21,5.4 常用信源编码方法简介,算术编码从性能上看具有许多优点，特别是由于所需的参数很少，不象哈夫曼编码那样需要一个很大的码表，常设计成自适应算术编码来针对一些信源概率未知或非平稳情况。,22,5.4 常用信源编码方法简介,但是在实际实现时还有一些问题，如计算复杂性、计算的精度以及存储量等，随着这些问题的逐渐解决，算术编码正在进入实用阶段，但要扩大应用范围或进一步提高性能，降低造价，还需进一步改进。,23,矢量量化,连续信源进行编码的主要方法是量化。,量化分为两大类：一类是标量量化，另一类是矢量量化。,标量量化：用若干个离散的数字值来表示每一个幅度具有连续取值（模拟值）的离散时域信号（抽样信号）。,矢量量化：是将若干个取样信号分成一组，即构成一个矢量，然后对比矢量一次进行量化。将某一个范围内的矢量归为一类，即矢量量化。,24,