常用信源编码方法简介.ppt

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