信息论与编码技术无失真信源编码定理

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

1、信息论与编码技术第4章无失真信源编码定理苗付友mfy@ustc.edu.cn2016年9月本章介绍对离散信源进行无失真信源编码的要求、方法及理论极限，并引出香农第一定理。进一步加深对熵的物理意义的理解信源编码码符号集：X=｛x1，x2…xq｝信源符号集：S=｛s1,…,sq｝码字集：C=｛W1,…,Wq｝信道编码信道译码信源译码信源信宿信道干扰5.1编码器5.2几个概念5.3等长码5.4渐进等分割性和?典型序列5.5等长信源编码定理5.6变长码5.7变长信源编码定理主要内容编码的实质是对信源的原始符号按一定的数学规则进行的一种变换，以码字代替原始信

2、源符号，使变换后得到的码符号接近等概率分布，从而提高信息的传输有效性5.1编码器编码器码源符号集：X=｛x1，x2…xq｝信源符号集：S=｛s1…sq｝码字集：C=｛W1…Wq｝信源信宿5.1编码器信源编码：从信源符号到码符号的一种映射。信源编码器：编码器X=｛x1，x2…xq｝S=｛s1…sq｝C=｛W1…Wq｝定义：信源编码器的输入信源符号集,是输入消息单元也可以是未编码的信号单元.S的元素si，i=1，2…q叫做信号单元或消息（共有q个信源符号）。编码器输出的码,W的元素Wi,i=1,2,…q叫做码字。构成码字的符号集,其元素xi一般是适合信

3、道传输的,称为码元.信源信宿5.1编码器编码器X=｛x1，x2…xq｝S=｛s1…sq｝C=｛W1…Wq｝将信源符号集中的符号sj，i=1，2…q（或者长为N的信源符号序列）变换成由基本符号xj,j=1,2…r组成的长度为Li的一一对应的输出符号序列,即C=｛W1,W2，…，Wq｝，Wi称为码字，li称为码字长度或简称码长,所有这些码字的集合C称为码.可见编码就是从信源符号到码符号的一种映射,若要实现无失真编码,这种映射必须是一一对应的,可逆的。信源信宿5.1编码器例：二元信道基本符号集为{0,1},将信源符号s变换成由0和1符号组成的码符号序列(

4、码元),即编码。编码器X=｛x1=0，x2=1｝S=｛s1…sq｝C=｛W1…Wq｝5.1编码器例：下表为信源编码所使用的码表，信源输出序列的长度为L=1，信源共有4个符号，对应的概率空间为信源符号si信源符号出现概率p(si)码表码1码2s1p(s1)001s2p(s2)0110s3p(s3)10101s4p(s4)111115.1编码器以码1为例，将信源输出的符号按照固定的规则进行变换，即信源编码器输出共有4个码字，分别为00，01，10和11，码字的长度都为2，即li=2，（i=1，2，3，4）每个码字都是由取值于码符号集合{0，1}的两位二

5、元码组成。也就是说，该码表将信源输出的每个符号映射成二元码。信源符号si信源符号出现概率p(si)码表码1码2s1p(s1)001s2p(s2)0110s3p(s3)10101s4p(s4)11111各种码的定义5.1编码器1.二元(代)码:码符号集为X={0,1},所得码字都是一些二元序列,则为二元码.它是数字通信和计算机系统中最常用的一种码。2.同价(代)码:若码符号集X:{x1,x2,…,xr}中每个码符号x所占的传输时间相同,则所得的码C为同价码.一般二元码是同价码.电报中常用的摩尔斯码是非同价码，其码符号(·)和划(－)所占的传输时间不同

6、.3.等长码(固定长度码或定长码):若一组码中所有(码字的)码长都相等,(即Li=L(i=1,2,…,q)),则称为等长码。如下表中的码1。4.变长码:码中的码字长短不一，如上图中的码2。信源符号si信源符号出现概率p(si)码表码1码2s1p(s1)001s2p(s2)0110s3p(s3)10101s4p(s4)111115.非奇异码：一组码中所有的码字都不相同。即6.奇异码：一组码中有相同的码字，即码1奇异，码2非奇异。信源符号si符号出现的概率p(si)码1码2码3码4s11/20011s21/411101001s31/8000010000

7、1s41/81101100000017.码的N次扩展码码C把信源S中的符号si一一变换成码C中的码字Wi,则码C的N次扩展码是所有N个码字组成的码字序列的集合。若码其中则N次扩展码为每个码字Bi与N此扩展信源SN中每个信源符号序列一一对应。例子：信源S的概率空间为，二元信道传输，si0或1信源符号si信源符号出现概率p(si)码表码1码2s1p(s1)001s2p(s2)0110s3p(s3)10101s4p(s4)11111可以求得信源S的任意N次扩展码。码1的二次扩展码:1)信源S的二次扩展信源S2={?1=s1s1,?2=s1s2,?3=s

8、1s3,…?16=s4s4}，共qN=42=16个符号2）S的二次扩展码信源符号?i码字Bi信源符号?i码字Bi?1000