信源编码第5章（第3讲）1p信息通过信道传输到信宿的过程即为通信。要做到既不失真又快速地通信，需要解决两个问题：n在不失真或允许一定失真条件下，如何提高信息传输速度-这是本章要讨论的信源编码问题.n在信道受到干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大-这是下章要讨论的信道编码问题.Date2p信源编码：n无失真信源编码第一极限定理可逆编码的基础，只适用于离散信源，主要用于文字、数据信源的压缩。n限失真信源编码第三极限定理只适用于连续信源，主要用于图像、语音信源的压缩p信道编码第二极限定理Date3p一般来说，抗干扰能与信息传输率二者相互矛盾。然而编码定理已从理论上证明，至少存在某种最佳的编码能够解决上述矛盾，做到既可靠又有效地传输信息。p信源虽然多种多样，但无论是哪种类型的信源，信源符号之间总存在相关性和分布的不均匀性，使得信源存在冗余度。信源编码的目的就是要减少冗余，提高编码效率。Date4p信源编码的基本途径有两个:n一是编码后使序列中的各个符号之间尽可能地互相独立，即解除相关性-方法包括预测编码和变换编码.n二是使编码后各个符号出现的概率尽可能相等，即均匀化分布-方法主要是统计编码.Date5p本章主要介绍信源编码的基本思路与主要方法，以无失真编码为主，期望通过本章学习能建立起信源压缩编码的基本概念。Date65.1编码的定义5.2无失真信源编码5.3限失真信源编码5.4常用信源编码方法简介主要内容Date75.2.3最佳变长编码p最佳码：n对于某一信源和某一码符号集来说若有一唯一可译码其平均码长小于所有其他唯一可译码的平均长度。p方法：将概率大的信源符号编以短的码字。概率小的符号编以长的码字，这样使得平均码字长度最短。p主要有：n香农（Shannon）n费诺（Fano）n哈夫曼（Huffma）Date8香农编码p香农第一定理指出了平均码长与信源之间的关系同时也指出了可以通过编码使平均码长达到极限值这是一个很重要的极限定理。p香农第一定理指出选择每个码字的长度Ki满足下式：或:log2p(xi)Ki1log2p(xi)p就可以得到这种码。p这种编码方法称为香农编码香农编码取整Date9p二进制香农码的编码步骤如下：将信源符号按概率从大到小的顺序排列p(a1)p(a2)p(an)确定满足下列不等式的整数Kilog2p(ai)Ki0(i=12n)p信源符号的累积概率累积概率为p显然P1=0P2=p1P3=p1+p2p而且pr=Pr+1PrDate38p累积概率Pr+1和Pr都是小于1的正数可用01区间内的两个点来表示P1p1P2P3P41p2p30ppr就是这两点间的小区间的长度如图:p当A=01二元信源时：P(0)=0P(1)=p(0)P(0)P(1)01p(0)p(1)Date39p计算二元无记忆信源序列的累积概率累积概率p初始时：在01)区间内由P(1)划分成二个子区间0P1)和P11)P(1)=p(0)。n子区间0P1)的宽度为A(0)=p(0)对应于信源符号“0”；n子区间P11)的宽度为A(1)=p(1)对应于信源符号“1”n若输入符号序列的第一个符号为S=“0”落入0P1)区间得累积概率累积概率P(S=“0”)=P(0)=0；算术编码Date40p若输入第二个符号为“1”S=“01”nS=“01”所对应的区间是在区间0P(1)中进行分割；p符号序列“00”对应的区间宽度为A(00)=A(0)p(0)=p(0)p(0)=p(00)；n对应的区间为0P(S=“01”)。p符号序列“01”对应的区间宽度为A(01)=A(0)p(1)=p(0)p(1)=p(01)=A(0)A(00)；n对应的区间为P(S=“01”)P(1)。pp累积概率累积概率:P(S=“01”)=p(00)=p(0)p(0)Date41P(0)0P(1)1p(0)p设输入符号序列S=011p(1)P(0)P(1)p(00)P(01)p(01)P(01)P(1)P(011)p(010)p(011)pp(0)=p(00)+p(01)pp(01)=p(010)+p(011)pp归一律归一律pP(0)=0pP(01)=p(00)pP(011)=P(01)+p(010)Date42p011S1S=01p输入序列S1=“011”对应的区间是对区间P(S)P(1)进行分割p序列S0=“010”对应的区间宽度为A(S=“010”)=A(S=“01”)p(0)=A(S)p(0)n其对应的区间为P(S)P(S)+A(S)p(0)；p序列S1=“011”对应的区间宽度为A(S=“011”)=A(S)p(1)=A(S=“01”)A(S=“010”)=A(S)A(S0)n其对应的区间为P(S)+A(S)p(0)P(1)；Date43P(0)0P(1)1p(0)p(1)P(0)P(1)p(00)P(S)S=01p(01)P(S)P(1)P(S1)p(010)p(011)p当前面输入符号序列为S若接着输入一个“0”nn累积概率累积概率:P(S0)=P(S)n对应区间宽度为：A(S0)=A(S)p(0)p若接着输入的一个符号是“1”，nn累积概率累积概率:P(S1)=P(S)+A(S)p(0)n对应区间宽度为：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)Date44p符号序列对应的区间宽度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)p信源符号序列S所对应区间的宽度等于符号序列S的概率p(S)。算术编码Date45算术编码p二元信源符号序列的累积概率递推公式nSr表示前面信源符号序列为S接着再输入符号为rP(0)=0，P(1)=p(0)P(S0)=P(S)P(S1)=P(S)+p(S)p(0)p信源符号序列所对应区间的宽度递推公式Date46p例：已输入二元符号序列为S=“011”接着再输入符号为“1”p得序列累积概率为：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)Date47算术编码p一般多元信源序列的累积概率递推公式p序列的概率公式Date48算术编码p实际应用中采用累积概率P(S)表示码字C(S)符号概率p(S)表示状态区间A(S)则有：C(Sr)=C(S)+A(S)PrA(Sr)=A(S)prp实际编码时只需两个存储器起始时可令:A()=1C()=0p每输入一个信源符号存储器C和A就按照上式更新一次直至信源符号输入完毕就可将存储器C的内容作为该序列的码字输出。Date49算术编码p在编码过程中每输入一个符号要进行乘法和加法运算所以称为算术编码算术编码。p通过关于信源符号序列的累积概率的计算把区间分割成许多小区间不同的信源符号序列对应不同的区间为P(S)P(S)+p(S)。可取小区间内的一点来代表这序列。Date50算术编码p编码方法：n将符号序列的累积概率累积概率写成二进位的小数，取小数点后L位若后面有尾数就进位到第L位这样得到的一个数C并使L满足取整Date51例：设二元无记忆信源S=01其p(0)=14p(1)=34。对二元序列11111100做算术编码。P(S)=p(00000000)+p(00000001)+p(00000010)+p(11111011)=1p(11111111)p(11111110)p(11111101)p(11111100)=1p(111111)=1(34)6=0.110100100111得C=0.1101010S的码字为1101010解：p(S=11111100)=p2(0)p6(1)=(14)2(34)6Date52+=p(1)=34=(0.11)2p(11)=(34)2=(0.1001)2+=p(0)=(14)=2-2p(S)p(0)p(S)右移2位Date535.4.3预测编码p预测编码是数据压缩三大经典技术（统计编码、预测编码、变换编码）之一，它是建立在信源数据相关性之上的。由信息理论可知，对于相关性很强的信源，条件熵可远小于无条件熵，因此人们常采用尽量解除相关性的办法，使信源输出转化为独立序列，以利于进一步压缩码率。p常用的解除相关性的措施是预测和变换，其实质都是进行序列的一种映射。一般来说，预测编码有可能完全解除序列的相关性，但必需确知序列的概率特性；变换编码一般只解除矢量内部的相关性，但它可有许多可供选择的变换方法，以适应不同的信源特性。下面介绍预测编码的一般理论与方法。Date54p预测编码的基本思想是通过提取与每个信源符号有关的新信息，并对这些新信息进行编码来消除信源符号之间的相关性。实际中常用的新信息为信源符号的当前值与预测值的差值，这里正是由于信源符号间存在相关性，所以才使预测成为可能，对于独立信源，预测就没有可能。p预测的理论基础主要是估计理论。所谓估计就是用实验数据组成一个统计量作为某一物理量的估值或预测值。若估值的数学期望等于原来的物理量，就称这种估计为无偏估计；若估值与原物理量之间的均方误差最小，就称之为最佳估计，基于这种方法进行预测，就称为最小均方误差预测，所以也就认为这种预测是最佳的。p要实现最佳预测就是要找到计算预测值的预测函数。Date55p设有信源序列，k阶预测就是由的前k个数据来预测。可令预测值为：式中是待定的预测函数。要使预测值具有最小均方误差，必须确知k个变量的联合概率密度函数，这在一般情况下较难得到，因而常用比较简单的线性预测方法。p线性预测是取预测函数为各已知信源符号的线性函数，即取的预测值为：其中为预测系数。Date56p最简单的预测是令称为前值预测，常用的差值预测就属于这类。p利用预测值来编码的方法可分为两类：p一类是对实际值与预测值之差进行编码，也叫差值预测编码。p另一类方法是根据差值的大小，决定是否需传送该信源符号。例如，可规定某一阈值T，当差值小于T时可不传送，对于相关性很强的信源序列，常有很长一串符号的差值可以不传送，此时只需传送这串符号的个数，这样能大量压缩码率。这类方法一般是按信宿要求来设计的，也就是压缩码率引起的失真应能满足信宿需求。Date57p下面简单介绍差值预测编码系统。如果信源的相关性很强，则采用差值编码可得较高的压缩率。由于相关性很强的信源可较精确地预测待编码的值，使得这个差值的方差将远小于原来的信源取值，所以在同样失真要求下，量化级数可大大减少，从而较显著地压缩码率。p差值预测编码系统的框图如下图所示，在编码端主要由一个符号编码器和一个预测器组成，在解码端主要由一个符号解码器和一个预测器组成。Date58编码器解码器Date59p当输入信源序列逐个进入编码器时，预测器根据若干个过去的输入产生对当前输入像素的估计值。预测器的输出