第四章：无失真源编码.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 分析：上述例子仅是一个特例，因为它没有考虑信源的统计特性，（它认为信源是遵从等概率分布的）所以编出的码字是等长码，而对应的算术运算则是简单的整数项相加。（即Ki为整数）。 §4.5实用的无失真信源编码方法举例－算术码编码－4 问题：对一般的具有统计特性的信源的算术编码问题。 方法：将上述算术编码方式进一步拓广，其中最关键的是要将算术编码与信源的符号概率及累积概率建立一一对应关系，进而将累计概率与 区间的一个数C联系起来。 新的问题：在引入统计特性后的算术编码中，每次移位的位数可以是非整数（精度有限的有理数），正是由于这种非整数的引入使算数编码变成了非分组码（当然，算术编码从全序列出发，考虑符号间的依赖关系来编码）。 算术码编码－5 信源符号序列的累积分布函数 设信源符号集 ： 其相应的概率分布为： 信源符号累积分布函数： 对二元信源 算术码编码－6 举例说明，二元无记忆信源为例。 区间由F(1)划分成两个子区间： 宽度A（0）=P（0） 宽度A（1）=P（1） 若输入第一个符号为S=“0”,即落入相应的区间 得 若输入第二个符号为1，S=“01”,相应的区间是在 进行分割，符号“00”对应的区间宽度为 符号“01”对应的区间宽度为 0 1 F(1) 算术码编码－7 符号S=“00”对应的区间为 符号S=“01”对应的区间为 是符号序列“01”对应区间的下界值（对应符号序列的累积分布函数） 0 1 F(1) 算术码编码－7 若输入第三个符号为1，S=“011”可以记作S+1=S1,相应的区间是在 进行分割， 符号S0=“010”对应的区间宽度为 对应的区间为 符号S1=“011”对应的区间宽度为 对应的区间为 符号序列s1=“011”的累积分布函数 若输入第三个符号为0，S=“010”下界仍为F(s),序列S0的累积分布函数为 算术码编码－8 信源符号序列的累积分布函数迭代公式 已知当前输入符号序列为S，若接着再输入一个0，序列S0累积分布函数： 区间宽度为 已知当前输入符号序列为S，若接着再输入一个1，序列S1累积分布函数： 区间宽度为 算术码编码－9 举例说明S=“011”,接着输入1 对应区间宽度为 * 算术码编码－10 信源符号序列的累积分布函数树图计算法 已知当前输入符号序列为S=(s1s2…sn)，另一二元序列串为Y=(y1y2…yn)对第一个i有si=1,yi=0,则SY。 把符号序列看成二进制小数0.S和0.Y，对第一个i有siyi,则0.S0.Y 将二元符号序列排成一棵n阶二元整树。可见所有小于S的序列都在同一阶S节点的左侧。 1 1 1 0 0 1 S=1101 0 1 C 0 P(S)=(3/4)3(1/4)? C=1000 (有尾数时进位） 1 1 0 1 00算术码编码举例－1 例14： P(S)=(3/4)3(1/4) 1 1 1 0 算术码编码举例－2 算术码编码过程： ：累积概率?码字 ：区间长度（符号所落区间） 例： 算术码编码举例－3 s F(s) A(s) k C 空 0 1 1 0.01 0.11 1 1 1 0.0111 0.1001 1 1 0 0.0111 0.001001 3 100 1 004 1000 F(1)=F( )+A( )F(1)=0+0.01=0.01 A(1)=A( )p1=1x0.11=0.11 F(11)=F(1)+A(1)F(1)=0.01+0.11x0.01=0.0111 A(11)=A(1)p1=0.11x0.11=0.1001 F(110)=F(11)+A(11)F(0)=0.0111+0.1001x0=0.0111 A(110)=A(11)p0=0.1