信息论与编码8----限失真信源编码2.ppt
信息论与编码-限失真信源编码5.算术编码算术编码也是一种无失真信源编码方法。前面讨论的无失真信源编码方法，都是针对单个信源符号的编码，当信源符号之间有相关性时，这些编码方法由于没有考虑到符号之间的相关性，因此编码效率就不可能很高。解决的办法是对较长的信源序列进行编码，但会遇到与定长编码时同样的问题。而且，采用前面的序列编码需要完全知道联合概率和条件概率，这在信息论与编码-限失真信源编码场合下也是比较困难的。为了解决这个问题，需要跳出分组码的局限，研究非分组码。算术编码就是一种非分组编码方法。其基本思路是：从全序列出发，将不同的信源序列的累计概率映射到0，1区间上，使每个序列对应区间上的一点，也就是说，把区间0，1分成许多互不重叠的小区间，不同的信源序列对应不同的小区间，可以证明，只要这些小区间互不重叠，就可以编得即时码。信息论与编码-限失真信源编码这种编码方法无需计算出所有信源序列的概率分布及编出码表，可以直接对输入的信源符号序列进行编码输出。算术编码的主要编码方法就是计算信源符号序列所对应的小区间。下面我们讨论如何找出信源符号序列所对应的区间。设信源符号集 ，其相应的概率分布为 。定义信源符号的累积分布函数为信息论与编码-限失真信源编码则对二元序列有：现在，来计算信源序列 的累积分布函数。信息论与编码-限失真信源编码只讨论二元无记忆信源，结果可推广到一般情况。初始时，在0，1）区间内由F(1)划分成二个子区间0，F(1)）和F(1)，1），F(1)=p(0)。子区间0，F(1)的宽度为A(0)=p(0)，子区间F(1)，1）的宽度为A(1)=p(1)。子区间0，F(1)对应于信源符号“0”，子区间F(1)，1）对应于信源符号“1”。若输入符号序列的第一个符号为s=“0”，即落入相应的区间为0，F(1)），得F(s=“0”)=F(0)=0。即某序列累积概率分布函数为该序列所对应区间的下界值。信息论与编码-限失真信源编码当输入的第二个符号为“1”时，s=“01”，s=“01”所对应的区间是在0，F(1)）中进行分割。符号序列“00”对应的区间宽度为A(00)=A(0)p(0)=p(0)p(0)；符号序列“01”对应的区间宽度为A(01)=A(0)p(1)=p(0)p(1)=p(01)，也等于A(01)=A(0)-A(00)。”00”对应的区间为0，F(s=“01”)）；”01”对应的区间为F(s=“01”)，F(1)）。其中F(s=“01”)是符号序列“01”区间的下界值，可见，F(s=“01”)=p(0)p(0)正是符号序列s=“01”的累计分布函数。信息论与编码-限失真信源编码当输入符号序列中第三个符号为“1”时，因前面已输入序列为s=“01”，所以可记做输入序列为s1=“011”（若第三个符号输入为“0”，可记做s0=“010”）。现在，输入序列s1=“011”所对应的区间是对区间F(s)，F(1)）进行分割。序列s0=“010”对应的区间宽度为A(s0=“010”)=A(s=“01”)p(0)=A(s)p(0)，其对应的区间为F(s)，F(s)+A(s)p(0)），而序列s1=“011”对应的区间宽度为A(s1=“011”)=A(s)p(1)=A(s=“01”)-A(s0=“010)，信息论与编码-限失真信源编码即A(s1=“011”)=A(s)-A(s0)，其对应的区间为F(s)+A(s)p(0),F91)）。可的，符号序列s1=“011”的累计概率分布函数为F(s1)=F(s)+A(s)p(0)。若第三个符号输入为“0”，由上述分析可得，符号序列s0=“010”的区间下界值仍为F(s)，所以符号s0=“010”的累计分布函数为F(s0)=F(s)。现已输入三个符号串，将这符号序列标为s，接着输入第四个符号为“0”或“1”，又可计算出s0=“0110”或s1=“0111”对应的子区间及其累积信息论与编码-限失真信源编码分布函数。根据前面的分析，可归纳出：当已知前面输入符号序列s，若接着输入一个符号“0”，序列s0的累计分布函数为 F(s0)=F(s)对应区间宽度为 A(s0)=A(s)p(0)若接着输入的一个符号是“1”，序列s1的累计分布函数为信息论与编码-限失真信源编码 F(s1)=F(s)+A(s)p(0)对应的区间宽度为 A(s1)=A(s)p(1)=A(s)-A(s0)由前面的分析又知，符号序列对应的区间宽度为 A(s=“0”)=p(0);A(s=“1”)=1-A(s=“0”)=p(1);A(s=“00”)=A(0)p(0)=p(0)p(0)=p(00);A(s=“01”)=A(s=“0”)-A(s=“00”)=A(0)p(1)=p(0)p(1)=p(01);信息论与编码-限失真信源编码 A(s=“10”)=A(1)p(0)=p(1)p(0)=p(10);A(s=“11”)=A(s=“1”)-A(s=“10”)=A(1)p(1)=p(1)p(1)=p(11);A(s=“010”)=A(s=“01”)p(0)=p(01)p(0)=p(010);A(“011”)=A(s=“01”)-A(s=“010”)=A(s=“01”)p(1)=p(01)p(1)=p(011);由此可得，信源符号序列s对应的区间宽度等于符号序列s的概率p(s)。信息论与编码-限失真信源编码综合上述几个式子，可得二元信源符号序列的累计分布函数的递推公式为 F(sr)=F(s)+p(s)F(r)(r=0,1)其中sr表示已知前面信源符号序列为s，接着再输入符号为r。同样，可得信源符号序列所对应区间宽度的递推公式为 A(sr)=p(sr)=p(s)p(r)因此，当已输入的二元信源符号序列为s=“011”，若接着输入符号为“1”，得累积分布函数为信息论与编码-限失真信源编码F(s1)=F(0111)=F(s=“011”)+p(011)p(0)=F(s=“01”)+p(01)p(0)+p(011)p(0)=F(s=“0”)+p(0)p(0)+p(01)p(0)+p(011)p(0)=0+p(00)+p(010)+p(0110)其对应的区间宽度为A(s1)=A(s=“011”)p(1)=p(011)p(1)=p(0111)由于累积分布函数和子区间宽度都是递推公式，因此在实际应用中，只需要两个存储器，把p(s)和F(s)存下来，然后随着符号的输入，不断地信息论与编码-限失真信源编码 更新两个存储器中的数值。因为在编码过程中，没输入一个符号要进行乘法和加法运算，所以称这种编码方法为算术编码算术编码。很容易将其推广到多元信源序列。可以得到一般信元序列的累计分布函数和区间宽度的递推公式为 信息论与编码-限失真信源编码通过关于信元符号序列的累计分布函数计算，F(s)可以把区间0，1）分割成许多小区间，不同的信元符号序列对应于不同的区间为F(s),F(s)+p(s)）。可取小区间内的一点来代表这序列。如何选择这个点？将符号序列的累计分布函数写成二进制小数，取小数点后l位，若后面有尾数，则进位到第l位，这样得到的一个数C，并使l满足：信息论与编码-限失真信源编码设 ，取0或者1，得符号s的码字为 。这样选取的数值C，根据二进制小数截去位数的影响，得当F(s)在l位以后没有尾数时，C=F(s)。另外，由 可知，则信源符号序列信息论与编码-限失真信源编码S对应区间的上界可见，数值C在区间F(s)，F(s)+p(s)）内。不同的信源序列对应的不同区间（左封右开的区间）式不重叠的，所以编得的码是即时码。符号序列s的平均码长满足：信息论与编码-限失真信源编码平均每个信源符号的码长为对无记忆信源，有因此有信息论与编码-限失真信源编码可以看出，算术编码的编码效率是比较高的。当信源符号序列很长时，n很大，平均码长接近于信源的符号熵。例题：设二元无记忆信源s=0,1，其p(0)=1/4，p(1)=3/4。对二元序列s=11111100做算术编码。解：信息论与编码-限失真信源编码于是转换成二进制小数为：
