信息论与编码_第4章无失真信源编码

《信息论与编码_第4章无失真信源编码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章无失真信源编码信息论与编码InformationandCodingTheory王永容机械与电气工程学院wangyr416@126.com1信源编码信源编码是以提高通信的有效性为目的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。同样多的信息用较少的码率来传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。2信源编码的基本途径有两个：使序列中的各个符号尽可能地互相独立，即解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。3信源编码的基础是信息论中的两个编码定理：无失真信源编码定理限失真信源编码定理无失真信源编码只

2、适用于离散信源对于连续信源，只能在失真受限制的情况下进行限失真编码下面介绍几种典型的离散信源编码方法。4第4章无失真信源编码4.1无失真信源编码的概念4.2等长编码4.3变长编码4.4常用的变长编码算法54.1无失真信源编码的概念信源符号(字母)集：S＝{s1,s2,…,sq}.码符号(字母、元)集：A＝{a1,a2,…,am}.编码函数f:将有限个信源符号变换成有限个码符号的函数用AN表示全体长度为N的信源符号序列构成的集合码字：wi=f(si)码字wi的长度(码长)：li=l(wi)码:C={wi=f(si)

3、siSN}.64.1无失真信源编码的概念N=1时f：无失真信源编码器7如何

4、分离码字？如果0，01都是码字，译码时如何分离？？84.1无失真信源编码的概念例4-1几个二元码信源符号概率分布码1:C1码2:C2码3:C3码4:C4码5:C5s10.5000011s20.250111101001s30.125100000100001s40.12511110110000001码的扩展码C1的扩展:s1s3001094.1无失真信源编码的概念m元码:码符号集A＝{a1,a2,…,am}.二元码:m=2,A＝{0,1}等长码（定长码）:所有码字的码长相等.例:中文电报码是码长为4的等长的10元码中0022;国0948;北0554;京0079.变长码（非定长码）:码

5、字的码长不相等.非奇异码:s1,s2A,s1s2f(s1)f(s2)否则，称为奇异码104.1无失真信源编码的概念唯一可译码:任意有限长的码元序列,只能被唯一地分割成一个一个的码字,则称为唯一可译码,或单义可译码.否则，就称为非唯一可译码,或非单义可译码.例：码4是唯一可译码:10001001000,100码3是非唯一可译码:100010010,00,10,0或10,0,01,00信源符号概率分布码1:C1码2:C2码3:C3码4:C4码5:C5s10.5000011s20.250111101001s30.125100000100001s40.12511110110000001

6、备注等长码非唯一可译非唯一可译唯一可译及时码114.1无失真信源编码的概念即时码:如果收到一个码字后,就能及时译出，则称为即时码,也称为非延长码，或异前缀码.即没有任何完整的码字是其它码字的前缀。否则，就称为非即时码.例：码5是即时码,码4是非即时码.信源符号概率分布码1:C1码2:C2码3:C3码4:C4码5:C5s10.5000011s20.250111101001s30.125100000100001s40.12511110110000001备注等长码非唯一可译非唯一可译唯一可译及时码12关系即时码一定是唯一可译码唯一可译码一定是非奇异码定长的非奇异码一定是唯一可译码非定长的非奇异码

7、不一定是唯一可译码4.1无失真信源编码的概念13第4章无失真信源编码4.1无失真信源编码的概念4.2等长编码4.3变长编码4.4常用的变长编码算法144.2等长编码离散信源X的熵：H(X)字母集:S＝{s1,s2,…,sq}.对信源输出的N个符号进行编码:共有qN个消息码元集A＝{a1,a2,…,am}.长度为L的等长码：共有mL个可能码字能正确译码的必要条件：(非奇异码)154.2等长编码编码速率（编码信息率）:编码后每个信源符号所能承载的的最大信息量编码效率平均码长：平均每个信源符号所需要的码符号个数编码效率:164.2等长编码例4-2设一个离散信源的输出字母表有q=10个符号，将其编

8、为无失真二元码，即m=2，求平均码长。174.2等长编码无失真编码假设信道无干扰译码错误概率:Pe=P{MM’}无失真编码:译码错误概率Pe可以任意小.MWM’信源信源编码信道信宿信源解码W184.2等长编码等长信源编码定理定理4-1(Shannon信源编码定理)设离散无记忆信源X的熵为H(X),若对长为N的信源符号序列进行等长编码,码长为L,码元符号个数为m.则对任意的>0,>0,只要时,则译码差错概率一定是有限