后3章复习.ppt

第六章 限失真信源编码 信息理论与编码 1、信源编码 信源编码分类： 无失真编码：只对信源的冗余度进行压缩，不会改变信源的熵，又称冗余度压缩编码，它能保证码元序列经译码后能无失真地恢复成信源符号序列。 有失真编码：会改变信源的熵，不可逆压缩，又称熵压缩编码。 无失真信源编码的作用： 符号变换：使信源的输出符号与信道的输入符号相匹配； 冗余度压缩：使编码之后的新信源概率分布均匀化，信息含量效率等于或接近于100%。 2、单符号信源无失真编码器模型 3、定长编码定理 3、香农第一定理 4、变长编码方法 变长编码采用非续长码； 力求平均码长最小，此时编码效率最高，信源的冗余得到最大程度的压缩； 对给定的信源，使平均码长达到最小的编码方法称为最佳编码，编出的码称为最佳码； 三种变长编码方法：霍夫曼编码、费诺编码以及香农编码； 霍夫曼编码是真正意义下的最佳编码。 霍夫曼编码 二进制霍夫曼编码过程如下： （1）将信源符号按概率大小排序； （2）对概率最小的两个符号求其概率之和，同时给两符号分别赋予码元“0”和“1”； （3）将“概率之和”当作一个新符号的概率，与剩下符号的概率一起，形成一个缩减信源，再重复上述步骤，直到“概率之和”为1为止； （4）按上述步骤实际上构造了一个码树，从树根到端点经过的树技即为码字。 r进制霍夫曼编码 每次求缩减信源时，求r个最小概率之和，即将个概率最小的r符号缩减为一个新符号，直到概率之和为1终止。 新问题：缩减到最后时剩下不到r个符号了。 为保证平均码长最小，希望缩减到最后刚好还剩下r个符号。为达到此目的，可给信源添加几个无用的符号（概率为0的符号），使得信源符号数q满足: q+i=(r-1)θ+r 费诺（Fano）编码 费诺（Fano）编码也是构造一个码树，因此，编出的码是非续长码，但不一定是最佳码。 费诺编码步骤(以二进制编码为例)： （1）将信源符号按概率从大到小的排序； （2）将信源符号分成2组，使2组信源符号的概率之和近似相等，并给2组信源符号分别赋码元“0”和“1”； （3）接下来再把各小组的信源符号细分为2组并赋码元，方法与第一次分组相同； （4）如此一直进行下去，直到每一小组只含一个信源符号为止； （5）由此即可构造一个码树，所有终端节点上的码字组成费诺码。 香农编码 香农（Shannon）编码步骤(以二进制编码为例)： （1）将信源符号按概率从大到小的排序； （2）按下式求i个信源符号对应的码长li，并取整； （3）按下式求i个信源符号的累加概率Pi； （4）将累加概率Pi转换成二进制数； （5）取Pi二进制数小数点后li个二进制数字作为第i个信源符号的码字。 信道编码 信息传输系统的基本功能：在系统输出端准确地再现系统输入端发送的消息。 衡量信息传输速度的指标是信息（传输）率R 衡量信息传输可靠性的指标是平均差错率Pe。 为了降低平均差错率，可先对消息进行编码再送入信道传送，这种为了降低平均差错率而进行的编码称为信道编码。 1、译码规则与平均差错率 2、最佳译码规则与极大似然译码规则 3、汉明距离 4、香农第二定理 5、线性分组码 限失真信源编码 失真矩阵: 香农第三定理 复习题 习题 习题 编码器 f 信源 f 是一一对应的映射 bit/码字或bit/符号 bit/码元 新信源X ： 编码后的信息率R ：平均一个码元携带的信息量。 bit/码元 平均码长越小，每个码元携带的信息量就越多，传输一个码元就传输了较多的信息。 码元/符号 编码效率：编码后的实际信息率与编码后的最大信息率之比。 新信源的冗余度也是码的冗余度： 码 奇异码 非奇异码 非唯一可译码 唯一可译码 定长非奇异码 变长非续长码 （部分）变长续长码 非分组码 分组码 唯一可译码（UDC）：该码的码字组成的任意有限长码字序列都能恢复成唯一的信源序列。否则称为非唯一可译码。 定长码：所有的码字都具有相同的长度，否则为变长码。 奇异码：含相同码字的码。否则称为非奇异码。 非续长码：码中任一码字都不是另一码字的续长（延长）。否则为续长码。 非即时码：如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码。否则为即时码。 定长无失真编码定理：用r元符号表对离散无记忆信源U的N长符号序列进行定长编码，N长符号序列对应的码长为lN，若对于任意小的正数 ，有不等式 就几乎能做到无失真编码，且随着序列长度N的增大，译码差错率趋于0。反过来，若 就不可能做到无失真编码，且随着N的增大，译码差错率趋于1。 无