信息论第5章.

《信息论第5章.》由会员分享，可在线阅读，更多相关《信息论第5章.（59页珍藏版）》请在金锄头文库上搜索。

1、 第5章 无失真信源编码 5.1 编码器 5.2 分组码 5.3 定长码 5.4 变长码 5.1 编码器 图5.1 信源编码器 信源编码就是从信源符号到输出码符号的一种映射。要实现 无失真编码，这种映射必须是一一对应的、可逆的。 信源符号 si 信源符号出现现概率 p(si) 码码1码码2 s1p(s1)000 s2p(s2)0101 s3p(s3)10001 s4p(s4)11111 5.1 编码器 表5.1 5.1 编码器 码的分类 固定长度码：代码组C中所有码字的长度相同。 可变长度码：代码组C中码字的长度不相同。 码的奇异性 非奇异码：代码组C中所有码字都不相同。 奇异码：代码组C中有

2、相同的码字。 信源符号si信源符号出现现概率 p(si) 码码1码码2 s1p(s1)00 s2p(s2)1110 s3p(s3)0000 s4p(s4)1110 5.1 编码器 表5.2 5.1 编码器 N次扩展码 信源S的N次扩展信源为 ，其中，N次扩 展信源符号为 ，且 。经信源 编码后，相应的有CN=(Wj, j1，2，qN。其中，码字Wj 是和N次扩展信源SN中信源符号 一一对应的。 5.1 编码器 二次扩扩展信 源符号 j，j=1，2 ，16 码码字 Wj，j=1，2 ，16 1=s1s1 2=s1s2 3=s1s3 16=s4s4 00 001 0001 111111 表5.3

3、（表5.1中码2的二次扩展码） 注：同价码，即每个码符号所占的传输时间都相同的码。 5.2 分组码 定义5.2.1 将信源符号集S中的每个符号si，i1，2，q映 射成一个固定的码字Wi，i1，2，q，这样的码称为分 组码。 5.2 分组码 性质1 奇异性 定义5.2.2 若一种分组码中的所有码字都互不相同，则称此分 组码为非奇异码，否则称为奇异码。 分组码是非奇异的，这是分组码正确译码的必要条件。 信源符号siC1C2 s100 s21110 s30000 s41101 表5.2 5.2 分组码 性质2 唯一可译性 定义5.2.3 设信源符号si，i1，2，q映射成一个固定的 码字Wi，i1

4、，2，q，则码 映射为 的分组码称为原分组码的N次扩展。 定义5.2.4 如果一个分组码对于任意有限的整数N，其N次扩展 码均为非奇异码，则此码为唯一可译码。 5.2 分组码 信源符号si码码C1码码C2 s111 s21001 s3100001 s410000001 表5.5 5.2 分组码 性质3 即时码 定义5.2.5 无须考虑后续的码符号即可以从码符号序列中译出 码字，这样的唯一可译码称为即时码。 命题5.2.1 唯一可译码成为即时码的充要条件是其中任意一个 码字不是其他码字的前缀。 5.2 分组码 可采用树图构造法来构造即时码。 5.3 定长码 要实现无失真的信源编码，不但要求信源符

5、号与码字是一一 对应的，而且还要求码符号序列的逆变换也是唯一的。也就 是说，一个码的任意一串有限长的码符号序列（码字）只能 被唯一的译成所对应的信源符号序列。 5.3 定长码 (1) 简单信源S 对信源S进行定长编码，得到唯一可译码的条件为qrl，其 中，q是信源S的符号个数，r是基本码符号数，l是定长码的 码长。 信源存在唯一可译码的条件是什么？ 信源符号si信源符号出现现概率 p(si) 码码1码码2 s1p(s1)0000 s2p(s2)0111 s3p(s3)1010 s4p(s4)1111 表5.6 (2) N次扩展信源 对N次扩展信源S进行等长编码，得到唯一可译码的条件为 qNrl

6、，其中，qN是扩展信源符号个数，l是扩展信源定长码 长度。 5.3 定长码 例如：英文电报有32个符号，即q=32，若采用二元码时，则 r=2。对信源S的逐个符号si进行二元编码，则llogrq=5，这 就是说，每个英文电报符号至少要用5位二元符号进行编码 才能得到唯一可译码。 5.3 定长码 定长编码定理：编码的有关参数对译码差错的限制关系。 5.3 定长码 定理5.3.1 设离散无记忆信源S=s1,s2,sq的熵为H(S)，其N 次扩展信源为SN，采用码符号集X=x1,x2,xr对N次扩展信 源SN进行长度为l的定长编码，则对于任意 ， 只要满足 则N当足够大时，必可使译码差错小于。反之，

7、若 则当N足够大时，译码错误概率趋于（必定出错）。 5.3 定长码 定理5.3.2 一个熵为H(S)的离散无记忆信源，若对信源长为 N的符号序列进行定长编码，设码字是从r个字母的码符号 集中选取l个字母组成，对于任意，只要满足 则当N，几乎可实现无失真编码，即译码错误能为任意 小，即pE，反之，若满足 则不可能实现无失真编码，而当N足够大时，译码错误概率 近似等于，即pE。 以英文电报符号为例，不难求得英文电报信源的极限熵 H(S)1.4bit，所以 l/N1.4 二元符号/信源符号 这表明，平均每个英文信源符号只需近似用1.4个二元符号来 编码。 5.3 定长码 5.3 定长码 定义5.3.

8、1 设熵为H(S)的离散无记忆信源，若对信源的长为N 的符号序列进行定长编码，设码字是从r个码符号集中选取l 个码元组成，定义 （bit/符号） 为编码速率。当R H(S)+时，可以实现无失真传输。 5.3 定长码 定义5.3.2 称 为编码效率。 5.3 定长码 最佳编码效率 当错误概率pE时，N应满足 将代入得 例5.3.1 设有离散无记忆信源 5.3 定长码 其信息熵H(S)=2.55bit，自信息的方差DI(si)=7.82(bit)2，如 果对信源符号采用定长二元编码，要求编码效率=90%， 允许错误概率10-6，由 求得=0.28。由 得 1）应用变长码往往在N不很大时，就可编出效

9、率很高而且 无失真的码； 2）变长码必须是唯一可译码，才能实现无失真编码； 3）变长码要满足唯一可译码必须是非奇异码，而且任意有 限长N次扩展码也都必须是非奇异的； 4）为了能够即时进行译码，变长码还必须是即时码。 5.4 变长码 5.4 变长码 5.4.1 码的分类和主要编码方法 5.4.2 克拉夫特不等式和麦克米伦不等式 5.4.3 唯一可译码判别准则 5.4.4 变长编码定理 5.4.5 变长码的编码方法 5.4.1 码的分类和主要编码方法 若编码规则仅局限在本码组之内，即本码组的监督元仅与本 码组的信息元相关，则称这类码为分组码。 如果本码组的监督元不仅和本码组的信息元有关，而且还和

10、本码组相邻的前N-1个码组的信息元相关，这类码称为卷积码。 5.4.1 码的分类和主要编码方法 5.4.1 码的分类和主要编码方法 信源编码方法主要有三种： 1）匹配编码 根据编码对象的概率分布，分别给与不同长度的代码。 概率大的信源符号，代码长度短，反之代码长度长； 2）变换编码 先对信号进行变换，从一种空间变换成另一种空间，然 后针对变换后的信号进行编码； 3）识别编码 对有标准形状的文字、符号和数据进行编码。 定理5.4.1 设信源符号集S=s1,s2,sq，码符号集为X=x1,x2,xr，对 信源进行编码，相应的码字为W=W1,W2,Wq，其对应的 码长分别为l1,l2,lq，则存在即

11、时码的充要条件是 5.4.2 克拉夫特不等式和麦克米伦不等式 该不等式称为克拉夫特（Kraft）不等式。 该不等式也是存在唯一可译码的充要条件，此时它被称为麦 克米伦（McMillan）不等式. 定理指出了即时码（唯一可译码）中r，q，lq之间的关系，如 果它们满足克拉夫特（麦克米伦）不等式，则一定能够构成 至少一种即时码（唯一可译码），否则无法构成即时码（唯 一可译码）。 但是该定理并不能作为判别一种码是否为即时码的判据。例 如，在码字中有两个码字长度相同，则这两个码字无论是否 相同，都有可能使不等式成立。然而，当两个码字相同时， 显然，它们不可能时唯一可译码。 5.4.2 克拉夫特不等式和

12、麦克米伦不等式 由原始码集合S0，构造集合S1,S2，。 第一步：S1的构造：设WiS0，WjS0，若WiWjA，则 后缀A列入S1的元素，S1是具有这样性质的A的集合； 第二步：Sn(n1)的构造：将S0与Sn-1进行比较。若WS0， USn-1，且UWA，则A列为Sn的元素；若WSn， U Sn-1，且WUA，则A列为Sn的元素。Sn是由所有的 A和A组成的集合。 5.4.3 唯一可译码判别准则 5.4.3 唯一可译码判别准则 例5.4.1 设消息集合共有6个元素x1,x2,x3,x4,x5,x6,它们分别被 编码为a,c,abb,bad,deb,bbcde。判断该编码是否为唯一可译 码。

13、 S0S1S2S3S4S5S6S7 adebaddeb cbbcdebcde abb bad deb bbcde 定义5.4.1 设信源为 5.4.4 变长信源编码定理 编码后的码字为C=W1,W2,Wq，各码字Wi的长度分别为 l1,l2,lq。因是唯一可译码，信源符号si与码字Wi一一对应， 则这个码的平均长度是 1）码平均长度 单位：码符号/信源符号 定义5.4.2 对于某一信源和某一码符号集，若有一个唯一可 译码，其平均长度小于所有其他唯一可译码的平均长度，则 称该码为紧致码或最佳码。 5.4.4 变长信源编码定理 定理5.4.3 对于熵为H(S)的离散无记忆信源 5.4.4 变长信源

14、编码定理 若用具有r个码符号的集X=（x1,x2,xr）对该信源进行编码， 则一定存在一种编码方式构成唯一可译码，其平均码长满足 定理5.4.4 香农第一定理 5.4.4 变长信源编码定理 2）变长无失真信源编码定理 若离散无记忆信源的信源熵为H(S)。它的N次扩展信源的熵 为H(SN)，码符号集X=x1,x2,xr，对信源SN进行编码，总可 找到一种编码方法，构成唯一可译码，使信源S中的每一个信 源符号所需的码字平均长度满足 当N时，则得 5.4.4 变长信源编码定理 编码速率：变长编码的编码速率为 表示信源编码后，平均每个码元所能携带的最大信息量；若 H(S)RH(S)，则存在唯一可译码；

15、若RH(S)，则无 法进行唯一可译编码。 定理5.4.4 编码效率定义为 5.4.4 变长信源编码定理 定义5.4.3 对于变长码，定义码的剩余度为 5.4.5 变长码的编码方法 1）香农编码方法 香农第一定理指出了平均码长与信源之间的关系： 同时也指出了可以通过编码使平均码长达到极限值： 如何构造这种码，香农第一定理指出，选择每个码字的长度li 使之满足 将信源发出的q个消息按其概率的递减顺序依次加以排列， p1p2pq； 按下式计算第i个消息的二进制代码组的码长li，并取正整数； 5.4.5 变长码的编码方法 1）香农编码方法 为了编成唯一可译码，首先计算第i个消息的累加概率； 将累加概率Pi变换成二进制数； 去除小数点，并根据码长li，取小数点后li位数作为第i个消 息的代码组。li由下式确定。 5.4.5 变长码的编码方法 1）香农编码方法 例5.4.3 对信源进行香农编码。 5.4.5 变长码的编码方法