第三章无失真源信编码.pptVIP

第三章 无失真信源编码; 引言 编码的定义 定长编码定理 变长编码定理 变长编码方法;引言;什么是编码;什么是编码;香农信息论三大定理;编码的分类;信源编码目的与方法;信源编码的基本途径;编码定理表明：（1）必存在一种编码方法，使代码的平均长度可任意接近但不能低于符号熵。（2）达到这目标的途径，就是使概率与码长匹配。 ;编码器;编码器的数学模型;一些基本概念;1.二元码 若码符号集为X={0,1}，所有码字都是二元符号序列，则称为二元码。 2.定长码 若一组码中所有码字的码长都相同，即 li=l（i=1,2…,n）,则称为定长码。 ;3.变长码若一组码中所有码字的码长各不相同，即任意码字由不同长度li的码符号序列组成，则称为变长码。;;5.奇异码若一组码中有相同的码字，则称码为奇异码。;6.同价码若码符号集中每个码符号所占的传输时间都相同，则所得的码为同价码。 7.分组码 将信源符号集中的每个信源符号映射成一个固定的码字，这样的码称为分组码。;8.唯一可译码 若码的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列，则此码称为唯一可译码。也称单义可译码。 注意：定长码是非奇异的就是唯一可译码，因为它能固定长度分组。 变长码则不一定，主要是不能固定长度分组。 唯一可译码还有判定准则，后面将介绍。 ;唯一可译码(续);9.即时码无需考虑后续的码符号即可从码符号序列中译出码字，这样的唯一可译码称为即时码或瞬时码或逗点码或非延长码或异前缀码。;10.码的前缀 定理:唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。;码树图;唯一可译码定理;唯一可译码;唯一可译码;无失真信源编码定理研究内容; 由于Yk可取m种可能值，即平均每个符号输出的最大信息量为logm，KL长码字的最大信息量为KLlogm。用该码字表示L长的信源序列,则送出一个信源符号所需要的信息率平均为:;第二节 定长编码定理;说明;(2)将定理的条件改写成 其中：左边：KL长码字所能携带的最大信息量， 右边：L长信源序列携带的信息量。 上述定理表明，只要码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，当然条件是L足够大。 反之，当 时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。 时，则为临界状态，可能无失真，也可能有失真。 ;第三节 变长编码定理;离散平稳无记忆序列变长编码定理;证明:设用m进制码元作变长编码，序列长度为L个信源符号，则由（3－3－1）式可以得到平均码字长度 满足下列不等式 ;说明: (1) 用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小得多。可得编码效率的下界： ;(2) 例 用二进制，m＝2，log2m=l，H（X）＝2.55比特／符号，若要求 ，则 ;(3) 码的冗余度为;例3－3－1;(1)定长编码 若用二元定长编码（0,1）来构造一个 即时码： 这时平均码长为 =1 二元码符号/信源符号 编码效率为(对于无记忆信源而言,有HL(X)=H(X) ) 输出的信息率为 R＝0.811比特／二元码符号 ;(2)变长编码 假定信源序列的长度为L=2,其即时码如表3-3所示。 ;这个码的码字平均长度 单个符号的平均码长 编码效率 输出的信息率为 R2＝0．961 比特／二元码符号 ;将信源序列的长度增加，L＝3或L=4，对这些 信源序列X进行编码，并求出其编码效率为 ;变长码相关结论;第四节 变长码的编码方法;3.4.1 香农编码方法; (3)为了编成唯一可译码，计算第i个消息 的累加概率 (4)将累加概率Pi 变换成二进制数。 (5)取Pi二进数的小数点后Ki位即为该消 息符号的二进制码字。 ;例3-4-1; 累加概率P4=0.57，变换成二进制为0.1001…，由于＝3，所以第4个消息的编码码字为100。其他消息的码字可用同样方法求得，7个消息符号对应的码字依次为： 00