问题假设已给定信源概率Pi和失真函数dij在约束条件下课件.ppt
2023/3/28,1,问题:假设已给定信源概率Pi和失真函数dij，在约束条件下，求信源的R（D）函数的极小值问题?,第二节 离散信源和连续信源的R(D)计算,2023/3/28,2,R（D）三种特殊表示(1)当d(x,y)=(x-y)2,p(x)=时，R（D）=(2)当d(x,y)=p(x)=时，R（D）=,2023/3/28,3,(3)当D(x,y)=时，R（D）=H（p）-H（D）R（D）曲线见图4-2-1,2023/3/28,4,这些R（D）可画成三条曲线,图4-2-1 信息率失真函数R(D),2023/3/28,5,分析：,(1)它们都有一最大失真值 Dmax对应 R（D）0。当允许的平均失真D大于这最大值时，R（D）当然也是零，也就是不用传送信息已能达到要求。上述三种情况的 Dmax分别为 和p（若p1/2，不然就是1-p）,2023/3/28,6,(2)当DDmax时，R（D）就已不是零，随着D的减小，R（D）单调地增加；(3)当D=0，前两种情况下R（D）趋于无限，这就是说，大于信息量无限大的连续信源符号，无法进行无损编码，除非信息率R趋向无限大。对于离散信源就不同，在第三种情况下，D=0时，R（0）=H（p），这就是无损编码时，所需的信息率不能小于信源的符号熵。,2023/3/28,7,例421,设输人输出符号表为XY=0,1，输入概率分布P（x）P,l一p，0p，失真矩阵为,求信息率失真函数R（D）。,2023/3/28,8,解：,(1)按下式解方程,简记,写成矩阵形式,2023/3/28,9,(2)按下式解方程,由此解得,2023/3/28,10,写成矩阵形式,解得,2023/3/28,11,(3)按下式得转移概率分布Pij,写成矩阵形式,2023/3/28,12,(4)求,2023/3/28,13,（5）计算R（D），将上面各式代入，则有,2023/3/28,14,结果得到如图4-2-2所示的曲线：,2023/3/28,15,2023/3/28,16,限失真信源编码定理：设离散无记忆信源X的信息率失真函数为R（D），则当信息率RR（D），只要信源序列长度 L足够长，一定存在一种编码方法，其译码失真小于或等于D，为任意小的正数；反之，若RR（D），则无论采用什么样的编码方法,其译码失真必大于D。,第三节 限失真信源编码定理,2023/3/28,17,说明:(1)如果是二元信源，对于任意小的 0，每一个信源符号的平均码长满足如下公式,则 在失真限度内使信息率任意接近R（D）的编码方法存在。,(2)该定理只能说明最佳编码是存在的，而具体构造编码方法却一无所知，因而就不能像无损编码那样从证明过程中引出概率匹配的编码方法。一般只能从优化的思路去求最佳编码。实际上，迄今尚无合适的可实现的编码方法来接近R（D）这个界。,2023/3/28,18,4.4.1 游程编码 游程编码基本思想:将任何(二元)序列变换成一一对应的游程长度序列，按哈夫曼编码或其他方法处理以达到压缩码率的目的.,第四节 常用信源编码方法简介,2023/3/28,19,什么叫二元序列游程和游程长度?在二元序列中，只有两种符号，即“0”和“1”，这些符号可连续出现，连“0”这一段称为“0”游程，连“1”这一段称为“1”游程。它们的长度分别称为游程长度L（0）和L（l）。“0”游程和“l”游程总是交替出现的。如果规定二元序列是以“0”开始，第一个游程是“0”游程，第二个必为“1”游程，第三个又是“0”游程等等。对于随机的二元序列，各游程长度将是随机变量，其取值可为1，2，3，直到无限。,2023/3/28,20,说明:(1)例 如有一个二元序列：000101110010001 可变换成游程序列：3113213(2)对二元序列进行哈夫曼编码时，应先测定“0”游程长度和“l”游程长度的概率分布，或由二元序列的概率特性去计算各种游程长度的概率。,2023/3/28,21,什么叫多元序列游程和游程长度?对于多元序列也存在相应的游程序列。例如m元序列中，可有m种游程。连着出现符号ar的游程，其长度L（r）就是“r”游程长度。这也是一个随机变量。用L（r）也可构成游程序列。但是这种变换必须再加一些符号，才能成为一一对应或可逆的.,2023/3/28,22,说明:(1)与二元序列变换所得的游程序列不同，这里每个“r”游程的前面和后面出现什么符号是不确定的，除r外的任何符号都是可能的，因此这一游程之后是何种符号的游程就无法确定，除非插人一个标志说明后一游程的类别。上述的附加标志可能抵销压缩编码所得的好处，对原来的多元序列直接编码，或许会更有效一些,所以把多元序列变换成游程序列再进行压缩编码是没有多大意义的.,2023/3/28,23,(2)一般情况下，游程长度越大，其概率越小；这在以前的计算中也可看到，而且将随长度的增大渐趋向零。对于小概率的码字，其长度未达到概率匹配或较长，损失不会太大，也就是对平均码字长度影响较小。这样就可对长游程不严格按哈夫曼码步骤进行；在实际应用时，常采用截断处理的方法。,2023/3/28,24,(3)游程编码只适用于二元序列，对于多元信源，一般不能直接利用游程编码；但在下面介绍的冗余位编码，也可认为是游程编码在多元信源的一种应用。,2023/3/28,25,冗余位编码思想?,设有多元信源序列（4-4-1）其中x是含有信息的代码，取值于m元符号集A，可称为信息位；y是冗余位，它们可为全零，即使未曾传送在收端也能恢复。这样的序列可用下列两个序列来代替：111，100，000111，111000和（4-4-2）,2023/3/28,26,前一个序列中，用“1”表示信息位，用“0”表示冗余位；后一个序列是取消冗余位后留下的所有信息位。显然，从（4-4-1）式变换成（4-4-2）式中的两个序列是一一对应的，也就是可逆的。如果把（4-4-2）式中的两个序列传送出去，只要没有差错，在收端就可恢复（4-4-1）式中的多元信源序列。这样就把一个多元序列分解为一个二元序列和一个缩短了的多元序列。它们可用不同的方法来编码以利于更有效地压缩码率。,2023/3/28,27,例(1)在电话通信中，讲话时常有间隙，如字句间的停顿，听对方讲话而静默.(2)图象信源中，背景基本上不变，并在图象中占相当大一部分，而其值为常量相当于平均亮度，一般也可以不传送.(3)在数据信源序列中，信息包间的间歇或某种固定模式，也属于冗余性质。这些符号可称为冗余位，若能删除它们，可得较大的压缩比。,2023/3/28,28,4.4.2 算术编码,算术编码的基本思路：从全序列出发，将各信源序列的概率映射到0,1区间上，使每个序列对应这区间内的一点，也就是一个二进制的小数。这些点把0,1区间分成许多小段，每段的长度等于某一序列的概率。再在段内取一个二进制小数，其长度可与该序列的概率匹配，达到高效率编码的目的。,2023/3/28,29,信源符号 概率和累积概率的关系信源符号 概率 如果信源符号集为A 信源序列X=（），A，共有mL种可能序列。由于考虑的是全序列，也许是整页纸上的信息作为一个序列，因而序列长度L很大。实用中很难得到对应序列的概率，只能从已知的信源符号概率 P=中递推得到。,2023/3/28,30,累积概率定义各符号的积累概率为（4-4-3）显然，由上式可得P0=0，P1=p0,P2=p0+p1等，而且 pr=Pr+1-Pr（4-4-4）由于Pr+1和Pr都是小于1的正数，可用0,1区间内的两个点来表示，则pr就是这两点间的小区间的长度，如图4-4-l。不同的符号有不同的小区间，它们互不重叠所以可将这种小区间内的任一个点作为该符号的代码。以后将计算这代码所需的长度，使之能与其概率匹配。,2023/3/28,31,如何分析多元序列累积概率递推公式 P(Sar)P(S)p(s)Pr?分析:有一序列S011，这种三个二元符号的序列可按自然二进数排列，000，001，010，则S的累积概率为 P（S）=p（000）p（001）十p（010）,2023/3/28,32,如果S后面接一个“0”，累积概率就成为P（S0）=p（0000）十p（0001）p（0010）p（0011）p（0100）p（0101）=p（000）p（001）p（010）=P（S）因为两个四元符号的最后一位是“0”和“1”时，根据归一律，它们的概率和应等于前3位的概率，即p（0000）十p（0001）=p（000）等。,2023/3/28,33,如果S后面接一个“1”，则其累积概率是P（S1）=p（0000）p（0001）p（0010）+p（0011）P（0100）+p（0101）P（0110）P（S）十p（0110）=P(S)+p(S)p0,2023/3/28,34,由于单符号序列的积累概率为P00,P1=p0，所以上面两式可统一写作 P（Sr）=P（S）十p（S）Pr，r0，1 序列的概率的公式 P（Sar）p（S）pr,2023/3/28,35,如何选择小区间内的点?,P(S)把区间0,1分割成许多小区间、每个小区间的长度等于各序列的概率p（S），而这小区间内的任一点可用来代表这序列，现在来讨论如何选择这个点。令,2023/3/28,36,式中 表示大于或等于的最小整数。把积累概率P（S）写成二进位的小数，取其前L位，以后如果有尾数，就进位到第L位，这样得到一个数C。例如P（S）=0.10110001，p（S）117，则L5，得C=0.10111这个C就可作为S的码字。,2023/3/28,37,C不小于P（S），至少等于P（S）。又由（4-4-7）式可知p（S）。令（S1）为按顺序正好在 S后面的一个序列，则 P（S1）P（S）p（S）C 当P（S）在第L位以后没有尾数时，P（S）就是C，上式成立；如果有尾数时，这尾数就是上式的左右两侧之差，所以上式也成立。,2023/3/28,38,由此可见C必在P（S1）和P（S）之间，也就是在长度为p（S）的小区间（左闭右开的区间）内，因而是可以唯一地译码的。这样构成的码字，编码效率是很高的，因为已可达到概率匹配.,2023/3/28,39,采用累积概率P(S)表示码字C(S)，符号概率p(S）表示状态区间A(S），则有(4-4-8)对于二进制符号组成的序列，r0，l。,2023/3/28,40,实际编码大致过程:先置两个存储器C和A，起始时可令 A（）1，C（）0 其中 代表空集。每输入一个信源符号，存储器C和A就按照（4-4-8）式更新一次，直至程序结束，就可将存储器C的内容作为码字输出。由于A（S）是递增的，而这增量随着序列的增长而减小，因为这增量是序列的概率与信源符号序列的积累概率的乘积；所以C的前面几位一般已固定，在以后计算中不会被更新，因而可以输出。只需保留后面几位用作更新。译码也可逐位进行，与编码过程相似。,2023/3/28,41,例,有简单的四个符号a,b,c,d构成序列Sabda，各符号及其对应概率如表4-4-1，算术编/解码过程书：P65,2023/3/28,42,4.4.3 矢量量化,什么叫标量量化?连续信源进行编码的主要方法是量化，即将连续的样值x离散化成为yi，il，2，3，n。n是量化级数，yi是某些实数。这样就把连续值转化为n个实数，可用0,1,2,n-1等n个数字来表示。离散信源也会涉及量化的问题，比如当提供的量化级数少于原来的量化级数时，也需要对该信源信号进行再次量化。在上述的这些量化中，由于x是一个标量，因此称为标量量化。,2023/3/28,43,什么叫量化噪声?当一个样值x经量化后所产生的误差为 zi=x-yi 或 yi=x-zi也就是在信号值x上叠加了一个样值为-zi，的噪声信号。这种噪声通常称为量化噪声。,2023/3/28,44,什么叫做矢量量化?,连续信源也是如此，当把多个信源符号联合起来形成多维矢量，再对矢量进行标量量化时，自由度将更大，同样的失真下，量化级数可进一步减少，码率可进一步压缩。这种量化叫做矢量量化。,2023/3/28,45,4.4.4 预测编码,常用信源编码方法评述(1)哈夫曼码对于独立多值信源符号很有效；(2)二元序列的游程编码实际上是为了把二值序列转化成多值序列以适应哈夫曼编码；(3)多个二元符号合并成一个符号的方法也有类似的情况。算术码对于独立二元信源序列是很有效的，对于相关信源虽然可采用条件概率来编码而达到高效率，但这样做所引起的复杂度，往往使之难以实现。,2023/3/28,46,常用的解除相关性的两种措施,常用的解除相关性的两种措施是预测和变换。它们既适应于离散信源，也可用于连续信源。其实两者都是序列的变换。一般来说，预测有可能完全解除序列的相关性，但必需确知序列的概率特性；变换编码一般只解除矢量内部的相关性，但它可有许多可供选择的变换矩阵，以适应不同信源特性。这在信源概率特性未确知或非平稳时可能有利。,2023/3/28,47,什么叫预测?,预测就是从已收到的符号来提取关于未收到的符号的信息，从而预测其最可能的值作为预测值；并对它与实际值之差进行编码，达到进一步压缩码率的目的。由此可见，预测编码是利用信源的相关性来压缩码率的，对于独立信源，预测就不适用。,2023/3/28,48,什么叫估计?,估计就是用实验数据组成一个统计量作为某一物理量的估值或预测值。最常见的估计是利用某一物理量在被干扰下所测定的实验值，这些值是随机变量的样值，可根据随机量的概率分布得到一个统计量作为估值。若估值的数学期望等于原来的物理量，就称这种估计为无偏估计；若估值与原物理量之间的均方误差最小，就称之为最佳估计。用来预测时，这种估计就成为最小均方误差的预测，所以也就认为这种预测是最佳的。,2023/3/28,49,利用预测值编码的方法可分两类,一类是差值编码:用实际值与预测值之差进行编码。常用于相关性强的连续信源，也可用于离散信源。在连续信源的情况下，就是对此差值量化。由于相关性很强的信源可较精确地预测待编码的值，这差值的方差将远小于原来的值，所以在同样失真要求下，量化级数可明显地减少，从而较显著地压缩码率。对于离散信源也有类似的情况。,2023/3/28,50,另一类方法是根据差值的大小，决定是否需传送该信源符号。例如，可规定某一可容许值，当差值小于它时可不传送。对于连续函数或相关性很强的信源序列，常有很长一串符号可以不送而只需传送这串符号的个数，这样能大量压缩码率。这类方法一般是按信宿要求设计的，也就是失真应能满足信宿需求。,2023/3/28,51,4.4.5 变换编码,什么叫变换编码?变换编码就是经变换后的信号的样值能更有效地编码，也就是通过变换来解除或减弱信源符号间的相关性，再将变换后的样值进行标量量化，或采用对于独立信源符号的编码方法，以达到压缩码率的目的。,
