信息论与编码第五章PPT

第5章信源编码5.1数据压缩概述5.2无失真信源编码的基本原理5.3无失真信源编码方法主要内容本次课内容:5.1数据压缩概述5.2无失真信源编码的基本概念5.2.1信源编码器5.2.2码的类型对于信源来说，有三个重要问题需要解决：1、如何构建描述信源的模型；2、信源输出信息量的计算，即信源熵的问题；3、如何更有效的表示信源输出问题，即信源压缩编码问题。信源编码的主要任务就是：减少冗余，提高编码效率。第5章信源编码信源编码的基本途径有两个：一是使序列中各个符号尽可能地相互独立，即解除相关性；二是使编码中各个符号出现的概率尽可能地相等，即概率均匀化。具体来说，就是针对信源输出符号序列的统计特性，寻找一定的办法把信源输出符号序列变换为最短的码字序列。但在许多情况下，并不要求在信宿精确重现信源的输出，只要满足一定的重建质量要求即可，既允许信息传输中出现一定失真，这就是限失真信源编码问题。例如，在电话通信中，只要能将通话内容送达对方就可以了，对音质并无太高要求。实际通信时，信道往往存在干扰，要完全精确地重现信源输出几乎是做不到的。这就允许接收信号有一定限度的失真。这就是限失真编码问题,我们不做重点介绍。5.1数据压缩概述数据压缩:就是用尽可能少的比特数来表示源信号（采样和量化后数字信号），并能将其还原。压缩的任务就是保持信源信号在一个可以接受的状况前提下,把需要的比特数减到最少程度，以达到减少存储、处理和传输成本的目的。4.1数据压缩概述信息理论认为：若信源编码的熵大于信源的实际熵，则该信源中一定存在冗余度，去掉冗余不会减少信息量，仍可原样恢复数据；但若减少了熵，数据则不能完全恢复。但在允许的范围内损失一定的熵，数据可以近似地恢复。4.1数据压缩概述常用的压缩编码方法可以分为两大类：1、无损压缩编码法，也称冗余压缩法或熵编码法及无失真编码；2、有损压缩编码法，也称为熵压缩法或限失真编码。4.1数据压缩概述5.2无失真信源编码的基本概念5.2.1信源编码器编码的实质：是对信源的原始符号按一定的数学规则进行的一种变换，以码字代替原始信源符号，使变换后得到的码符号接近等概率分布，从而提高信息的传输有效性。4.2无失真信源编码的基本概念4.2无失真信源编码的基本概念信源编码：从信源符号到码符号的一种映射。信源编码器：编码器X=｛x1，x2…xq｝S=｛s1…sq｝C=｛W1…Wq｝定义：信源编码器的输入信源符号集,是输入消息单元也可以是未编码的信号单元.S的元素si，i=1，2…q叫做信号单元或消息（共有q个信源符号）。编码器输出的码,W的元素Wi,i=1,2,…q叫做码字。构成码字的符号集,其元素xi一般是适合信道传输的,称为码元.编码器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｝，si(i=1,2…q),Wi=(xi1,xi2,…xiL),xik∈X,(k=1,…L)L称为码字长度或简称码长,所有这些码字的集合C称为码.可见编码就是从信源符号到码符号的一种映射,若要实现无失真编码,必须这种映射是一一对应的,可逆的。4.2无失真信源编码的基本概念如：二元信道基本符号集为{0,1},将信源符号s变换成由0和1符号组成的码符号序列(码元),即编码。编码器X=｛x1=0，x2=1｝S=｛s1…sq｝C=｛W1…Wq｝4.2无失真信源编码的基本概念例如，下表为信源编码所使用的码表，信源输出序列的长度为L=1，信源共有4个符号，对应的概率空间为信源符号xi信源符号出现概率p(xi)码表码1码2x1p(x1)001x2p(x2)0110x3p(x3)10101x4p(x4)11111XP(x)éëêêùûúú=x1x2x3x4p(x1)p(x2)p(x3)p(x4)éëêêùûúú4.2无失真信源编码的基本概念以码1为例，将信源输出的符号按照固定的规则进行变换，即信源编码器输出共有4个码字，分别为00，01，10和11，码字的长度都为2，即li=2，（i=1，2，3，4）每个码字都是由取值于码符号集合{0，1}的两位二元码组成。也就是说，该码表将信源输出的每个符号映射成二元码。11,10,01,004321xxxx4.2无失真信源编码的基本概念信源符号xi信源符号出现概率p(xi)码表码1码2x1p(x1)001x2p(x2)0110x3p(x3)10101x4p(x4)111115.2.2码的类型1.二元(代)码:码符号集为X={0,1},所得码字都是一些二元序列,则为二元码.它是数字通信和计算机系统中最常用的一种码。2.同价(代)码:若符号集X:{x1,x2,…,xr}中每个码符号x所占的传输时间相同,则所得的码C为同价码.一般二元码是同价码.电报中常用的摩尔斯密码是非同价码，其码符号(·)和划(－)所占的传输时间不同.4.2.2码的类型3.定长码(固定长度码或等长码):若一组码中所有(码字的)码长都相等,(即Li=L(i=1,2,…,q)),则称为定长码。见书表5-1码一。4.变长码:码中的码字长短不一.见书表5-1码二。5.非奇异码：一组码中所有的码字都不相同。即xi≠xj，wi≠wj4.2.2码的类型信源符号xi信源符号出现概率p(xi)码表码1码2x1p(x1)001x2p(x2)0110x3p(x3)10101x4p(x4)111116.奇异码：一组码中有相同的码字，即xi≠xj，但wi=wj。见表码1奇异，码2非奇异。4.2.2码的类型信源符号xi符号出现的概率p(xi)码1码2码3码4x11/20011x21/411101001x31/80000100001x41/81101100000017.唯一可译码：若码的任意一串有限长的码符号序列,只能被唯一的译成所对应的信源符号序列,则称为唯一可译码。4.2.2码的类型码1:如码符号序列为码符号序列为0010s1s3唯一可译码si码1码2s1000s20101s310001s411111s1s2s1s3s1是非唯一可译码码2.0010可能译为4.2.2码的类型注:奇异码不是唯一可译码;非奇异码有唯一可译码,又有非唯一可译码。唯一可译码又分为非即时译码和即时码.非即时译码:接收端收到一个完整的码字后,不能立即译码,而等下一码字开始接收后才判断是否可以码.4.2.2码的类型表中码3是非即时码,码4是即时码.只要收到1就表示码意完整。4.2.2码的类型信源符号Xi符号出现的概率P(Xi)码1码2码3码4X11/20011X21/411101001X31/80000100001X41/8110110000001即时码(非延长码或非续长码):任意一个码子都不是其它码字的前缀部分.在延长码中有的是唯一可译,有的不是.如码3是唯一可译码。综上所述，码的分类有：非分组码奇异码非唯一可译码码分组码非奇异码非即时码唯一可译码即时码（非延时码）4.2.2码的类型信源符号Xi符号出现概率P(Xi)码1码2码3码4X11/20011X21/411101001X31/80000100001X41/8110110000001表5-2不同的码字1是奇异码，码2是非奇异码。码3是唯一可译码，码2不是唯一可译码码3是非即时码。码4中只要收到符号1就表示该码字已完整，可以立即译码，所以码4是即时码,又称为非延长码，任意一个码字都不是其他码字的前缀部分构.上次课的内容:第5章信源编码5.1数据压缩概述5.2无失真信源编码的基本原理5.2.1信源编码器5.2.2码的类型一、常用的压缩编码方法可以分为两大类：1、无损压缩编码法，也称冗余压缩法或熵编码法及无失真编码；2、有损压缩编码法，也称为熵压缩法或有失真编码。非分组码奇异码非唯一可译码码分组码非奇异码非即时码唯一可译码即时码二、码的分类本次课的内容5.2.3几个基本概念5.2.4等长编码定理5.2.5变长编码定理5.3无失真信源编码方法1、码树：通常情况下可以用码树来表示各个码字的构成，如果码字序列符号为m进制的，可以用m个符号的码树来构造码字，每个码树有一个树根A,树根有m个树枝，树枝的尽头称为节点,每个节点生出是树枝的数量等于码符号的数量m，从而形成m进制的码树。5.2.3几个基本概念4.2.3几个基本概念A021012120021120A10100101101001图4-3（a）二进制码树图4-3（b）图是三进制码树A为根分为两个支，有n=3级节点，其终端结点为23=8个表示信源符号，a图为满树.b图为非满树，是一个三进码树，有三个支，码是不定长的。码树一定是即时码，反之，任何即时码都是用码树来表示。即时码的码树可以用来译码4.2.3几个基本概念【例5.2-1】某地二月份天气的概率分布统计如下：雨天的概率是1/8，雪天的概率也是1/8，阴天的概率是1/4，晴天的概率是1/2。设x1表示雨天，x2表示雪天，x3表示阴天，x4表示晴天，则其离散无记忆信源的概率空间为2/14/18/11/8)(4321xxxxXPX4.2.3几个基本概念表5-3两种信源编码方案信源符号概率方案1的码字方案2的码字X11/800000X21/801001X31/41001X41/21114.2.3几个基本概念采用两种信源编码方案编成的码字如表下所示。绘出方案一和方案二的码树，试比较方案1和方案2的码字哪个有效性更好一些？表5-3两种信源编码方案信源符号概率方案1的码字方案2的码字X11/800000X21/801001X31/41001X41/21114.2.3几个基本概念编码后的每个信源符号平均所需的码元（码符号）个数。单位为“码元/信源符号”。对单个信源符号进行编码，设信源为2、平均码长)()()()(2121qqxPxPxPxxxxPX4.2.3几个基本概念4.2.3几个基本概念每个码字对应的码长为Ki（i＝1，2……q）该码的平均码长为iqiiKxPK1)(（码元/信源符号）方案1的平均码长方案2的平均码长2)(1iqiiKxPK75.112124138181)(1iqiiKxPK（码元/信源符号）（码元/信源符号）信源符号概率方案1的码字方案2的码字X11/800000X21/801001X31/41001X41/21113、信息传输率编码后信息传输率R又称为码率，是指编码后每个码元载荷的信息量。单位为“比特/码元”或“比特/码符号”。KxHR)(（比特/码元）码率K--平均码长H(x)—信源熵4.2.3几个基本概念【例4.2-1】中信源熵H(x)＝1.75比特/符号，方案1编码后每个码元载荷的平均信息量：方案2编码后每个码元载荷的平均信息量：875.0275.1)(KxHR（比特/码元）175.175.1)(KxHR（比特/码元）由于每个二进制码元所能携带的最大信息量为1比特，所以方案2是一种最佳编码。4.2.3几个基本概念信源符号概率方案1的码字方案2的码字X11/800000X21/801001X31/41001X41/21114、编码效率编码效率：表示编码后实际信息量和能载荷最大信息量的比值。假设码元为m进制，即可取m种可能值，则每个码元所能载荷的最大信息量为logm比特/码元。mKxHRRlog)(max二元编码效率KxH)(4.2.3几个基本概念方案2编码后每个码元载荷的平均信息量：875.0275.1)(KxHR（比特/码元）175.175.1)(KxHR（比特/码元）方案1编码后每个码元载荷的平均信息量：从编码效率看，方案1的编码效率为0.875，方案2的编码效率为1。所以方案2比方案1的有效性要更好一些。5、克劳夫特