信息论与编码zjh201209zjh第五章.ppt

信源编码 第5章 信源编码： 无失真信源编码—第一极限定理 离散信源 限失真信源编码—第三极限定理 连续信源 信道编码 第二极限定理 信源编码 在不失真或允许一定失真条件下,如何用尽可能少的符号来传送信源信息,以便提高信息传输率 信道编码 在信道受干扰的情况下如何增加信号的抗干扰能力,同时又使得信息传输率最大。 信源编码: 将信源输出符号,经信源编码器后变换成另外的压缩符号,然后将压缩后信息经信道传送给信宿 信源符号之间存在分布不均匀和相关性,使得信源存在冗余度,信源编码的主要任务就是减少冗余,提高编码效率。 针对信源输出符号序列的统计特性,寻找一定的方法把信源输出符号序列变换为最短的码字序列。 编码定理证明: 必存在一种编码方法,使代码的平均长度可任意接近但不能低于符号熵; 达到这目标的途径就是使概率与码长匹配。 统计匹配编码： 根据信源的不同概率分布而选用与之匹配的编码,以达到在系统中传信速率最小。 5.1 编码的定义 用树的概念可导出唯一可译码存在的充分和必要条件，各码字的长度Ki 应符合克劳夫特（ Kraft ）不等式： 例5-1：设二进制码树中X=(a1 , a2 , a3 , a4), K1=1,K2=2,K3=2,K4=3,应用Kraft不等式,得： 当编码器容许的输出信息率,也就是当每个信源符号所必须输出的码长是 当信源序列长度L满足 在连续信源的情况下，由于信源的信息量趋于无限，显然不能用离散符号序列Y来完成无失真编码，而只能进行限失真编码。 例 设离散无记忆信源概率空间为 比特/符号 5.2.2 变长编码定理 例5-3 将信源序列的长度增加,L＝3或L=4,对这些信源序列X进行编码,并求出其编码效率为 5.2.3最佳变长码 凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。 香农第一定理指出了平均码长与信源之间的关系,同时也指出了可以通过编码使平均码长达到极限值,这是一个很重要的极限定理。 香农第一定理指出,选择每个码字的长度Ki满足下式： 二进制香农码的编码步骤如下： （1）将信源符号按概率从大到小的顺序排列, 　　　　p(a1)≥ p(a2)≥…≥ p(an) （2）确定满足下列不等式的整数Ki , －log2 p(ai)≤ Ki 1－log2 p(ai) （3）令p(a1)=0,用Pi表示第i个码字的累加概率， 2.费诺编码 费诺编码属于概率匹配编码 。编码步骤如下： （1）将概率按从大到小的顺序排列,令 p(x1)≥ p(x2)≥…≥ p(xn) （2）将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。 （3）将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。 （4）如此重复，直至每个组只剩下一个信源符号为止。 （5）信源符号所对应的码字即为费诺码。 例 对以下信源进行费诺编码。 例有一单符号离散无记忆信源 对该信源编二进制费诺码,编码过程如表: 信源熵为 H(X)=2.75(比特/符号) 平均码长为 3.哈夫曼编码的步骤如下： ⑴ 将信源消息符号按其出现的概率大小依次排列 p(x1)≥p(x2)≥…≥ p(xn) ⑵取两个概率最小的字母分别配以0和1两码元,并将这两个概率相加作为一个新字母的概率,与未分配的二进符号的字母重新排队。 ⑶ 对重排后的两个概率最小符号重复步骤⑵的过程。 ⑷不断继续上述过程,直到最后两个符号配以0和1为止。 ⑸ 从最后一级开始,向前返回得到各个信源符号所对应的码元序列,即相应的码字。 例5-7 设单符号离散无记忆信源如下,要求对信源编二进制哈夫曼码。编码过程如下表 平均码长为 哈夫曼的编法并不惟一。 每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的,所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性,即能得到可分离码字。 不同的码元分配,得到的具体码字不同,但码长Ki不变,平均码长也不变,所以没有本质区别； 缩减信源时,若合并后的新符号概率与其他符号概率相等,从编码方法上来说,这几个符号的次序可任意排列,编出的码都是正确的,但得到的码字不相同。 不同的编法得到的码字长度Ki也不尽相同。 例5-8 单符号离散无记忆信源 单符号信源编二