《2.10常用信源编码》由会员分享，可在线阅读，更多相关《2.10常用信源编码（33页珍藏版）》请在金锄头文库上搜索。
1、2.10 常用信源编码信源编码也称为有效性编码，通过编码的方式，压缩信源的冗余度，从而提高了了通信的有效性。2.10.1 山农费诺编码山农费诺编码是一种常见的信源编码，其编码的步骤如下：(1)将信源的符号按其概率从大到小排列。(2)将这一列符号分成尽可能概率接近或相同的两组。(3)上面一组符号编为 0，下面一组符号编为 1，或反之。(4)已分的组再按（ 2） 、 （3）步骤重复做，直至不能再分组。(5)自左至右写出各码字。例 2.10.1有一单符号离散无记忆信源 X 如下，要求进行山农费诺编码因为信源有 8 个符号，其理论最大熵为 lb8=3 比特/符号，而实际熵为 2.55 比特/符号，如采
2、用三位二进制等长编码，则效率 =2.55/3 = 85%，或者说采用定长编码效率较低。如采用山农费诺编码，则效率会提高不少。2.10.2 哈夫曼编码哈夫曼编码是效率比较高的又一种无失真信源编码，二进制哈夫曼编码步骤如下：(1) 把信源符号按概率从大到小排成一列；(2) 把概率最小的两个分成一组，上面一个编为 0，下面一个编为 1，并将这两个符号的概率加起来，其结果再和尚未处理过的符号重新按大小排序；(3) 重复步骤 2，直到所有信源符号都处理完。(4) 从右向左依据编码路径返回，就得到各码字。例 2.10.2同前例 ,编码过程见下 图 2.10.2：（PPT 001 第四章）第 五 节 香 农
3、 编 码 设 离 散 无 记 忆 信 源 二 进 制 香 农 码 的 编 码 步 骤 如 下 ： 将 信 源 符 号 按 概 率 从 大 到 小 的 顺 序 排 列 ， 为 方 便 起 见 ， 令p(x1) p(x2) p(xn) 令 p(x0)=0， 用 pa(xj)， j=i+1表 示 第 i个 码 字 的 累 加 概 率 ， 则 ： 确 定 满 足 下 列 不 等 式 的 整 数 ki， 并 令 ki为 第 i个 码 字 的 长 度 log2 p(xn) ki log2 p(xn)+1 将 pa(xj) 用 二 进 制 表 示 ， 并 取 小 数 点 后 ki 位 作 为 符 号 xi的
4、 编 码 。0,2,ijn12 1,()()()()() niniixxxX pxP 2.10.3 冗余位编码冗余的信息完全可以不全部传送（压缩掉） ，从而提高了传输效率。1LD 编码现在来讨论一种由林绪（Lynch）和达维生（Davission）分别独立提出的冗余位编码法，称为 LD 编码。例如有一二元序列，其中的一串000100000001000 共二进制 15 位，其余的也可分割成 15 位一串，称为一帧。现在研究压缩冗余的方法。显然对该帧可确切描述为：（1） 帧长为 15。（2） 共有两个 1。（3） 第一个 1 在第 4 位。（4） 第二个 1 在第 12 位。可简写为：N=15,Q
5、=2,n1=4,n2=12其中 N 为帧长，Q 表示帧中 1 的个数，n1,n2 表示 1 的位置.再来分析包括这些信息至少要二进制多少位，显然 1 的个数可能为 015 个共16 种情况，需要的二进制符号数为 4，而1 的位置的可能性应为 N 中取 Q 的组合数。需要用二进制的位数为 6.7，取最小整数 7 位。于是共需 4+7=11 位二进制，可见有1511=4 位冗余可压缩掉。 Q 很好处理，直接用 4 位二进制数表示即可。难点是n1,n2，如何把它们综合起来，成为一个 7位的二进制数，而在译码时又能从这一个7 位的二进制数中唯一地求出 n1,n2 来。解题步骤 P110-P111根据上
6、例可归纳出 LD 码编码方法：(1) 将冗余序列截成 N 位二进制的一帧。(2) 根据 1 的数目写出 Q，根据 1 的位置写出 n1。(3) 根据公式求出 T。(4) 根据公式 A 求压缩后的二进制位数，前一项表示 1 的数目，后一项表示所有 1的位置。(5) 用二进制表示 QT。 LD 译码方法(1)用尝试的方法从 K=N-1 起，根据下式求出 K，进而求出 nQ;(2)再令 ，从 L=K-1 起求适合下式KCT1的 L，进而求出 nQ-1; (3)重复（2）直至 nQ-1= n1。 (4)根据 Q ,n 恢复出原冗余位序列。例 1 ： =piu8/14/2143u消息 U 概率 pi 编
7、码 CU1 1/2 0 01 0U2 1/4 0 10 1/2 1U3 1/8 0 1101/4 1U4 1/8 1 111编码规则：1)将信源消息 U 按概率大小排序（由大至小）。2) 从最小两个概率开始编码，并赋予一定规则，如下支路小概率为“1”，上支路大概率为“0” 。若两支路概率相等，仍为下支为“1”上支为“0” 。3) 将已编码两支路概率合并，重新排 队，编码。4) 重复步骤 3）直至合并概率归一 时为止。5) 从概率归一端沿树图路线逆行至对应消息编码，如 U3为“110”。例 2. U1U234U567U= 0.20 , 0.19 , 0.18 , 0.17 , 0.15 , 0.
8、10 , iP0.01编码UiP0.20 0.26 0.35 0.39 0.61 110 1.0 0.19 0.20 0.26 0.35 0 0.39 2U110.18 0.19 0.20 0 0.26 1 30000.390.17 0.18 0 0.19 1 4U0010.350.15 0 0.17 1 01050.10 0 0.26 01106U0.11 10.01 1 70111例 3. U1U23U45U= 0.4 , 0.1 , 0.2 , 0.2 , 0.1iP 编码UiP C0.4 0.4 0.6 0 1 11.0 0.2 0.4 0 0.4 1 0130.60.2 0 0.2
9、1 0004U0.40.1 0 0010 20.2 10.1 1 00115U编码iP C0.4 0.4 0.4 0.6 00 11.0 0.2 0.2 0.4 0.4 103U0.60.2 0.2 0 0.2 1140.40.1 0 0.2 1 010 2U0.2 0.1 1 0115可见，编成的码 C 和 C不一样，这说明哈夫曼编码并不唯一，这是由于哈夫曼编码是与信源统计特性相匹配的编码，而不是某个信源固定特性相匹配，不唯一性是明显的，但是只要在编码和译码过程中遵守同一规则，译码是唯一的。虽然 C 和 C不一样，但是两者都是哈夫曼编码，并且码长相等。Kc=0.41+0.22+0.23+20
10、.14=2.2Kc =0.42+0.222+0.132=2.2 但是，若从二阶矩来看，即方差来看，C 的方差大，C的方差小，所以 C 优于 C下面讨论哈夫曼编码应用中的一些问题：1)首先讨论误差扩散：哈夫曼编码 是一种无失真信源最佳编码，但是在实际信道中是有失真的。噪声的引入必然要破坏长码结构，而且是变长码，错误不但影响受干扰位，还要进一步扩散。目前对扩散还没有很有效的方法，工程上克服方法有两种：一是限制哈夫曼码仅能应用于优质信道（=10 -6）以限制扩散的可能性；二是采用定期清洗，防止扩散区域增大。但是它是靠牺牲有效性换取的。2)其次是速率匹配问题：由于绝大多数信源是不等概率的，由它编成的码
11、长度与速率是可变的。然而实际信道则要求其输入端速率是固定的。所以信源与信道之间还存在一个速率匹配问题。在工程上解决这一问题的方法是在两者之间加一个类似与水库的缓存器，它变速入，恒速出，以解决两者速率的匹配。3)第三是与信源统计特性匹配的问题 。其中：1）、小消息（符号）集信源不易匹配可采用信源消息集不断扩展的方法来解决，但是太复杂。2）、信源统计特性未知时，怎么办？可采用所谓通用编码的方法来解决。2游程编码例如 01000111101100000,其中连在一起的 0 段称为 0 游程，同样连在一起的 1段称为 1 游程， 由 1000111101100000 可编码成一个游程序列 1134125，一般游程越长，压缩越有效。接下来可以用其它方法例如多元哈夫曼编码进一步消除冗余，提高效率。思考题 已知 12 个球中有一个球的重量与其它球不同，其它球均等重。问用无砝码的天平至少须几次才能找出此球？解：天平有 3 种状态，即平衡，左重，左轻，所以每称一次消除的不确定性为log3，12 个球中的不等重球（可较轻，也可较重）的不确定性为： 24log12log
