信息理论编码课程PPT 第4章 信源无失真编码.ppt

第四章 离散无记忆信源无失真编码 信息理论与编码 第4章 离散无记忆信源无失真编码 4.1 信源编码概论 4.2 码的唯一可译性 4.3 定长编码定理和定长编码方法 4.4 变长编码定理 4.5 变长编码方法 4.6 几种实用的无失真信源编码 4.1 信源编码概论 传输之前的两次变换：信源编码、信道编码。 传输之后的两次反变换：信道译码、信源译码。 变换与反变换是成对出现的。 采取适当信道编码和译码措施后，可使信道传送的差错率降到允许的范围之内，因此，图中虚框部分可近似地视为一个等效的无损确定信道，简称为无噪信道，这一点是我们讨论信源编码的前提。 信源编码分类：无失真编码、有失真编码。 无失真编码：只对信源的冗余度进行压缩，不会改变信源的熵，又称冗余度压缩编码，它能保证码元序列经译码后能无失真地恢复成信源符号序列。 有失真编码：又称熵压缩编码，将在第6章讨论。 2、编码器模型 码长li ：码字wi 所含码元的个数。单位：码元/符号，r进制单位/符号。 定长码(FLC，Fixed Length code) ：码中所有码字均有相同的码长l ；否则称为变长码(VLC，Variable Length code)。 平均码长： 例：编码 3、编码器的输出 4、编码效率 4.2 码的唯一可译性 f 为一一对应的变换，只是无失真编码的必要条件，并不充分; 要保证将码元序列无失真地恢复成信源符号序列，还要求编出的码自身具有独特的结构。 有实用价值的码应该具有唯一可译性，即能从码字序列（也是码元序列）唯一地恢复成信源符号序列。 举例：下雨天留客天留我不留 1、唯一可译码（UDC，Uniquely Decodable Code） 唯一可译码（UDC）：该码的码字组成的任意有限长码字序列（也是码元序列）都能恢复成唯一的信源序列。否则称为非唯一可译码。 码是唯一可译码的充分必要条件是：由码中的码字组成的任意有限长的码字序列（也是码元序列），都能唯一划分成一个个的码字，且任一码字只与唯一一个信源符号对应。 奇异码：含相同码字的码。否则称为非奇异码。 非续长码：码中任一码字都不是另一码字的续长（延长）。否则为续长码。 非及时码：如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码。否则为及时码或立即码。 2、码树 码树从树根开始向上长出树枝，树枝代表码元，树枝与树枝的交点叫做节点 。 r 进制码树：码元个数为r ，各节点（含树根）向上长出的树枝数不大于r 。 l 阶节点：经过l 根树枝才能到达的节点。 终端节点或端点：向上不长出树枝的节点。 整树：r 进制码树各节点（包括树根）向上长出的树枝数均等于r 。 码字：与码树上的节点对应，组成该码字的码元就是从树根开始到该节点所经过的树枝（或码元）。 非续长码：所有码字均处于终端节点，即端点上。 3、Kraft不等式 不满足Kraft 不等式的码肯定不是非续长码； 满足Kraft 不等式的码也不一定是非续长码； 根据满足Kraft 不等式的码长集合可构造出一个非续长码； 上述定理对唯一可译码仍然成立。 Kraft 不等式是唯一可译码存在的充要条件； 如果码是唯一可译码，则必定满足该不等式； 如果满足Kraft 不等式，则这种码长的唯一可译码一定存在； 但不表示所有满足不等式的码一定是唯一可译码。 4.3 定长编码定理和定长编码方法 2、定长编码定理 3、定长编码方法（例） 4.4 变长编码定理(香农第一定理) 练习题 对U的二次扩展信源进行定长编码，码表如下表 ： 对U的二次扩展信源进行变长编码，码表如下表 ： 4.5 变长编码方法 变长编码采用非续长码； 力求平均码长最小，此时编码效率最高，信源的冗余得到最大程度的压缩； 对给定的信源，使平均码长达到最小的编码方法称为最佳编码，编出的码称为最佳码； 三种变长编码方法：霍夫曼编码、费诺编码以及香农编码； 霍夫曼编码是真正意义下的最佳编码。 4.5.1 霍夫曼编码 二进制霍夫曼编码过程如下： (1) 将信源符号按概率大小排序； (2) 对概率最小的两个符号求其概率之和，同时给两符号分别赋予码元“0”和“1”； (3) 将“概率之和”当作一个新符号的概率，与剩下符号的概率一起，形成一个缩减信源，再重复上述步骤，直到“概率之和”为1为止； (4) 按上述步骤实际上构造了一个码树，从树根到端点经过的树枝即为码字。 霍夫曼编码的基本特点 编出的码是非续长码：霍夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，直到树根结束，最后得到一个横放的码树，而且码字在终端节点上。 平均码长最小：霍夫曼编码采用概率匹配方法来决定各码字的码长，概率大的符号对应于短码，概率小的符号对应于长码。 码字不唯一：