变长编码定理pptx

发布者:admin 发布时间:2019-10-30 04:08 浏览次数:

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  离散平稳无记忆序列变长编码定理 对于平均符号熵为HL(X)的离散平稳无记忆信源,必存在一种无失真编码方法,使平均信息率 满足不等式 其中 为任意小正数。 证明: 设用m进制码元作变长编码,序列长度为L个信源符号,则由(3-3-1)式可以得到平均码字长度 满足下列不等式 当L足够大时,可使 ,这就得到了 所需结论说明: (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比特/二元码符号 序列序列概率即时码 0 x1x1 9/16 x1x2 3/16 10 x2x1 3/16 110 x2x2 1/16 111(2)变长编码 假定信源序列的长度为L=2,其即时码如表3-3所示。 这个码的码字平均长度 单个符号的平均码长 编码效率 输出的信息率为 R2=0.961比特/二元码符号将信源序列的长度增加,L=3或L=4,对这些信源序列X进行编码,并求出其编码效率为 信息传输率分别为: R3=0.985比特/二元码符号 R4=0.991比特/二元码符号如果对这一信源采用定长二元码编码,要求编码效率达到96%时,允许译码错误概率 。则根据(3-2-6)式,自信息的方差 所需要的信源序列长度 第四节 最佳编码(1)最佳码定义是什么? 凡是能载荷一定的信息量,且码字的平均长度最短,可分离的变长码的码字集合都可称为最佳码。 (2)最佳编码思想是什么? 将概率大的信息符号编以短的码字,概率小的符号编以长的码字,使得平均码字长度最短。 (3)最佳码的编码主要方法有哪些? 香农(Shannon)、费诺(Fano)、哈夫曼(Huffman)编码等。 3.4.1 香农编码方法 编码方法如下: (1)将信源消息符号按其出现的概率大小依次排列 (2) 确定满足下列不等式的整数码长Ki: (3)为了编成唯一可译码,计算第i个消息 的累加概率 (4)将累加概率Pi 变换成二进制数。 (5)取Pi二进数的小数点后Ki位即为该消 息符号的二进制码字。 例3-4-1 设信源共7个符号消息,其概率和累加概率如表3-4-1所示。以i=4为例, 累加概率P4=0.57,变换成二进制为0.1001…,由于=3,所以第4个消息的编码码字为100。其他消息的码字可用同样方法求得,如表3-4-1所示。 xiP(xi)Pi-logp2(xi)Ki码字x10.2002.343000x20.190.22.413001x30.180.392.483011x40.170.572.563100x50.150.742.743101x60.100.893.3441110x70.010.996.6671111110说明: (1)该信源共有5个三位的码字,各码字之间至少有一位数字不相同,故是唯一可译码。同时可以看出,这7个码字都不是延长码,它们都属于即时码。这里L=1,m=2. (2)信源符号的平均码长 码元/符号 (3) 平均信息传输率 3.4.2 费诺编码方法 编码步骤:(1)将信源消息符号按其出现的概率大小依次排列:p(x1) ≥p(x2) ≥ … ≥ p(xn)。(2)将依次排列的信源符号按概率值分为两大组,使两个组的概率之和近于相同,并对各组赋予一个二进制码元“0”和“1”。(3)将每一大组的信源符号进一步再分成两组,使划分后的两个组的概率之和近于相同,并又赋予两个组一个二进制符号“0’和“1”。(4)如此重复,直至每个组只剩下一个信源符号为止。(5)信源符号所对应的码字即为费诺码。 如何求出费诺码 编码过程参见P44 ,表3-4-2。 费诺码的平均码长 ? 信息传输速率 3.4.3 哈夫曼编码方法 哈夫曼编码 步骤:(1)将n个信源消息符号按其出现的概率大小依 次排列, p(x1)≥p(x2)≥…≥p(xn)(2)取两个概率最小的字母分别配以0和1两码元,并将这两个概率相加作为一个新字母的概率,与未分配的二进符号的字母重新排队。 (3)对重排后的两个概率最小符号重复步骤(2)的过程。(4)不断继续上述过程,直到最后两个符号配以0和1为止。(5)从最后一级开始,向前返回得到各个信源符号所对应的码元序列,即相应的码字。 哈夫曼编码过程,见P44表3-4-3所示 说明:哈夫曼码的平均码长为 ?信息传输速率 问题:为何哈夫曼编码方法得到的码并非是唯一的? (1)每次对信源缩减时,赋予信源最后两个概率最小的符号,用0和1是可以任意的,所以可以得到不同的哈夫曼码,但不会影响码字的长度。(2)对信源进行缩减时,两个概率最小的符号合并后的概率与其它信源符号的概率相同时,这两者在缩减信源中进行概率排序,其位置放置次序是可以任意的,故会得到不同的哈夫曼码。此时将影响码字的长度,一般将合并的概率放在上面,这样可获得较小的码方差。例3-4-2 设有离散无记忆信源 哈夫曼编码如下(见书P45):

  请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。用户名:验证码:匿名?发表评论


上一篇:采用FPGA器件实现并行侦测多路可变长编码    下一篇:没有了