第2章信源编码技术PPT讲稿.ppt
《第2章信源编码技术PPT讲稿.ppt》由会员分享,可在线阅读,更多相关《第2章信源编码技术PPT讲稿.ppt(87页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第第2章信源编码技术章信源编码技术第1页,共87页,编辑于2022年,星期一信源编码信源编码原始的语音信号,如果不做任何处理,将含有很多的冗余信息,不利于在信道上进行传输。为了提高传输效率,需要对该信号进行压缩,这一步骤称为信源编码。与此类似,图像、视频等信号的压缩,都属于信源编码的范畴。最主要的目的:提高通信的有效性。第2页,共87页,编辑于2022年,星期一信源编码原理:冗余的存在是由于原有信息之间存在着一定的关联,以及不同信息之间出现的概率分布不均匀所致。例:语音的冗余,文字的不均匀性通过编码处理,使得信息之间成为完全独立的符号,且出现概率相同,可以大大压缩原有信息的长度,而保持信息量不
2、变。第3页,共87页,编辑于2022年,星期一2.1.4 信源的信息度量1.信息的基本概念我们在前面讨论了信源的分类与统计描述,主要利用了信源的客观概率分布(包括概率与概率密度)特性描述了信源。为了进一步深入定量地研究信源,仅限于上述一般化的描述是不够的。信源就其信息实质来说,具有不确定性,那么信息与不确定性是什么关系,而不确定性又如何利用客观概率来表达,这就是信源输出的消息(或符号)所包含信息的定量度量问题。第4页,共87页,编辑于2022年,星期一2.信源的信息度量信源输出的是消息,消息的内涵是信息,信息的最主要特征是具有不确定性。如何度量信息的不确定性?信源的统计特性可以采用概率及概率密
3、度来描述,那么度量信息的不确定性与信源的概率与概率密度是什么关系?信源输出的信息量,信息论创始人Shannon将其定义为 H(X)=HP(x1),P(xn)=EIP(xi)=E-logP(xi)=P(xi)logP(xi)第5页,共87页,编辑于2022年,星期一其中,“E”表示求概率统计平均值,即求数学期望值。Shannon称H(X)为信源的信息熵,简称为熵。从数学上看,熵是信源消息概率P(xi)的对数函数logP(xi)的统计平均值,故又称为P(xi)的泛函数,它是定量描述信源的一个重要物理量。熵是Shannon于1948年首先给出的一个从概率统计角度来描述信源不确定性的一个客观物理量,是
4、从信源整体角度上反映信源不确定性的度量。第6页,共87页,编辑于2022年,星期一4.信源编码的理论基础现在我们来讨论信源冗余度的概念,它是信源统计分析中一个非常重要的概念,是信源信息处理、信源编码的理论依据。由于实际信源几乎都是有记忆的,这也就是说信源输出的消息序列的各个消息之间存在着记忆,即统计关联。如果能首先定量地计算出这一统计关联引入的冗余度,就能充分地利用它。下面讨论冗余度及其计算。对于一个最简单二进制信源有下列基本不等式:0H(X/Y)H(X)lb2=1 (2-32)其中lb2为离散二进制信源消息等概率分布时的熵函数值(最大值、极值)。第7页,共87页,编辑于2022年,星期一例2
5、-3 关于英文文字信源冗余度的讨论。根据英文中各个字母(含空格)出现的概率,可列出表2-2。表2-2 英文字母出现概率统计表第8页,共87页,编辑于2022年,星期一 由表2-2,首先求得独立等概率情况下的H0(X)值:H0(X)=lb27=4.76 b再求独立不等概率情况下的H1(X)值:H1(X)=P(xi)lbP(xi)=4.03b还可进一步求得有一阶、二阶记忆下的H2(X)和H3(X)为 H2(X)=3.32 b H3(X)=3.1 b第9页,共87页,编辑于2022年,星期一 最后,利用统计推断方法求得H(X)的值。一般而言,由于采用不同的逼近方法和所取样本上的差异,所推算的结果也不
6、同,这里我们采用Shannon求得的推算值:H(X)1.4b 这 样,利 用 公 式(2-35)及(2-36)可 分 别 求 得=0.29,R=0.71。这一结论说明英文字母信源从理论上看,有71%是多余的,即可以认为一本100页的英文书,理论上看仅有29页是有效的,其余71页从统计角度看完全是多余的。也正是由于理论上存在着这一多余成分,引导了实际工作者对英文信源进行压缩编码的研究。英文信源的分析也带动了各国对自己国家语言文字信源的分析,现将类似结果列于表2-3。第10页,共87页,编辑于2022年,星期一表2-3 不同文字信源冗余度估算第11页,共87页,编辑于2022年,星期一例2-4 关
7、于语音信源冗余度的一个粗略估计。语音信源的编码大致可以分为波形编码、参量编码与混合编码三大类。这里,仅分析冗余度最大的参量编码,即声码器的最大潜力。以英语为例,其音素大约有2728个,若按人们通常讲话的速率,每秒钟大约平均发送10个音素,这时英语语音信源给出的信息率为 上限:I1=lb(256)10=80 b/s下限:I2=lb(128)10=70 b/s第12页,共87页,编辑于2022年,星期一 若按PCM常规数字化编码传送语音,其标准速率为64 kb/s,因此可求得 1=0.001 25 2=0.0011 R1=1-1=1-0.001 25=0.998 75 R2=1-2=1-0.001
8、1=0.9989 可见,语音参量编码潜力巨大。定义理论上最大压缩倍如下:K1=800(倍)K2=914(倍)第13页,共87页,编辑于2022年,星期一 2.2 无失真信源编码无失真信源编码 2.2.1 基本原理我们在前面讨论了无失真信源的信息度量:信源熵H(X)。在本节将进一步分析讨论实现通信系统优化的无失真信源编码定理。为了分析简化,这里仅讨论最简单情况组合下的信源无失真编码定理:离散、无记忆、平稳、遍历、二(多)进制等(变)长编码条件下的信源编码定理。下面,我们将从直观概念出发,直接推导出这类简化信源编码。首先研究等长码,参见图2-2,其中,x为输入,它共有L位(长度),每一位有n种取值
9、可能;s为输出,它共有K位(长度),每一位有m种取值可能。第14页,共87页,编辑于2022年,星期一图2-2 信源编码原理图第15页,共87页,编辑于2022年,星期一倘若不考虑信源的统计特性,为了实现无失真并有效的编码,应分别满足:无失真要求:nLmK(即每个信源组合必须有对应的编码)(2-37)有效性要求:nL mK(即编码组合总数要小于信源组合总数)(2-38)从式(2-37)可推出 (2-39)显然,上述两个条件是相互矛盾的。如何解决这一对矛盾呢?惟一的方法是引入信源的统计特性。这时,就无需对信源输出的全部nL种信息组合一一编码,而仅对其中少数大概率典型组合进行编码。第16页,共87
10、页,编辑于2022年,星期一下面,先分析公式(2-39)的含义,并在引入信源统计特性以后对它作适当的修改。公式(2-39)的右端,其分子部分表示等概率信源的熵,而分母部分则表示等概率码元的熵。当引入信源统计特性以后,信源不再满足等概率,这时分子可修改为不等概率实际信源熵H(X),则有 (2-40)再将上式稍作变化,即可求得典型Shannon第一等长编码定理形式,当 时,有效的无失真信源编译码存在,可构造;(2-41)第17页,共87页,编辑于2022年,星期一反之,当(2-42)时,有效的无失真信源编译码不存在,不可构造。再讨论变长码,这时仅需将公式(2-40)修改为 (2-43)式中将等长码
11、的码长K改成相对应变长码的平均码长 ,平均码长 由下式计算:(2-44)第18页,共87页,编辑于2022年,星期一 再将公式(2-43)稍加修改即可求得典型的Shannon第一变长编码定理形式:对于二进制(m=2),则有当对数取2为底时,有 (2-45)(2-46)(2-47)第19页,共87页,编辑于2022年,星期一式中,K/L表示平均每个码元的长度。可见它要求平均每个码元的长度应与信源熵相匹配,因此又称为熵编码。实现无失真信源编码的基本方法有两大类型:一类为改造信源方式,即将实际不理想的不等概率信源变换成理想的具有最大熵值的等概率信源,再采用等长编码进行匹配;另一类为适应信源方式,即对
12、实际的不等概率信源采用与之相匹配的变长编码方法,包括最佳变长哈夫曼(Haffman)编码、算术编码以及适合于有记忆信源的游程编码等。第20页,共87页,编辑于2022年,星期一2.2.2 哈夫曼(Huffman)编码哈夫曼编码是一种统计压缩的可变长编码,它将预编码的字符用另一套不定长的编码来表示,基本原理是:按照概率统计结果,出现概率高的字符用较短的编码来表示,出现概率低的字符用较长的编码来表示。编码压缩性能是由压缩率(compression ratio)来衡量的,它等于每个采样值压缩前的平均比特数与压缩后的平均比特数之比。由于编码的压缩性能与编码技术无关,而与字符集的大小有关,因此,通常可以
13、将字符集转化成一种扩展的字符集,这样采用相同的编码技术就可以获得更好的压缩性能。第21页,共87页,编辑于2022年,星期一哈夫曼编码过程可用于任意两个字符集。下面分析一个任意输入字符集到一个二进制输出字符集的转换过程。哈夫曼编码过程类似于树形生成过程。首先列出输入字符集及其概率(或相对频率),以降序排列,这些列表项相应于树枝末端,每个分支都标注了等于该分支概率的分支权值。现在开始生成包含这些分支的树:将最低概率的两个分支合并(在分支节点处),形成一个新分支,并标注上两个概率的相加值;每次合并后,将新的分支和剩下的分支重新排序(若需要),以保证减少的列表概率的递降性,将这种排列方法称为冒泡法。
14、在每次合并后的重排中,新的分支在列表中不断上升至不能上升为止。第22页,共87页,编辑于2022年,星期一因此,如果形成一个权值为0.2的分支,在冒泡过程中发现其他两个分支的权值也是0.2,那么,新的分支将被冒泡到权值为0.2的分支组的顶端,而不是简单地加入。冒泡到同权值组的顶端可以生成码长方差小的编码,以降低缓冲溢出的可能性。为了讨论方便、描述准确,我们定义n元素m字符集为:字符集中共有n个元素,每个元素都包含m个字符,即每个元素包含的字符数目相同。第23页,共87页,编辑于2022年,星期一例2-5 6元素单字符集的哈夫曼编码。设6元素单字符集中每个元素的出现概率如表2-4所示。表2-4
15、6元素单字符集哈夫曼编码的详细参数第24页,共87页,编辑于2022年,星期一图2-3 6元素单字符集的哈夫曼编码树第25页,共87页,编辑于2022年,星期一 将哈夫曼编码过程应用于表2-4所示的输入字符集。按照哈夫曼编码规则,生成哈夫曼编码树,如图2-3所示。然后在哈夫曼编码树的每个分支节点标上二进制数“0”或“1”,以区分两个分支。这种标记可以是任意的,但为了保持一致,将每个节点的上向分支标为“1”,下向分支标为“0”。标记好之后,沿着树径从树基(最右)到每个分支(最左)的路径包含了到达该分支的二进制序列,该二进制序列就是分支对应字符的哈夫曼编码,哈夫曼编码的详细参数如表2-4所示。第2
16、6页,共87页,编辑于2022年,星期一可计算出字符集的平均码长是2.4b。这好像意味着我们必须找到一个传输非整数比特的方法。实际上这个结果表明,当要传输100个输入码元时,通信信道中平均需要传输240 b。比较一下,若采用等长码来表示6元素单字符集,则码长K为3b。而输入字符集的熵(平均信 息 量)为 2.32b。因 此,哈 夫 曼 编 码 提 供 了1.25(3.0/2.4)的压缩率,该字符集编码效率达到了96.67(2.32/2.40)。为了说明代码扩展的应用,我们再举一个例子。第27页,共87页,编辑于2022年,星期一例2-6 3元素单字符集的哈夫曼编码(元素的概率分布不均匀)。该字
17、符集的哈夫曼编码树见图2-4,其详细参数见表2-5(i=1,2,3)。表2-5 3元素单字符集哈夫曼编码的详细参数第28页,共87页,编辑于2022年,星期一图2-4 3元素单字符集的哈夫曼编码树第29页,共87页,编辑于2022年,星期一 该哈夫曼编码的平均码长是1.27 b;采用等长码则码长 为 2b。这 里,哈 夫 曼 编 码 提 供 的 压 缩 率 是1.57(2/1.27),比6元素单字符集的1.25大。但是,应用式(2-21)计算字符集的熵(平均信息量)为0.9443b,该字符集编码效率为74.35(0.9443/1.27),却比6元素单字符集的96.67小。这是因为6元素单字符集
18、的信息熵(2.32b)与平均码长(2.4 b)的匹配比3元素单字符集的信息熵(0.9443 b)与平均码长(1.27 b)的匹配要好。第30页,共87页,编辑于2022年,星期一由此可见,由于有较多元素的字符集具有较大的信息熵(平均信息量),使得信息熵与平均码长的匹配更好些,所以具有更高的编码效率。为了提高编码效率或获得更大的压缩增益,必须重新定义信源字符集的元素,对字符集进行扩展。具体的方法是:每次从源字符集(3元素单字符集)中选择两个元素,排序形成扩展字符集(9元素双字符集)的新元素。如果假定元素是独立的,那么每个新元素的概率是各个元素独立概率之乘积。扩展字符集为XxiX,i=1,2,9,
19、每个元素xi的编码序列通过上述哈夫曼过程获得,扩展后的9元素双字符集的参数如表2-6所示。可以算出扩展后的9元素双字符集的 压 缩 率 是 2.07(2/0.9671),编 码 效 率 是 97.64(0.9443/0.9671),比扩展前的3元素单字符集的压缩率1.57、编码效率74.35有明显的提高。第31页,共87页,编辑于2022年,星期一表2-6 3元素单字符集扩展为9元素双字符集第32页,共87页,编辑于2022年,星期一扩展码提供了一种利用码元关联性的技术。例如,英文中的相邻字母有很强的关联性。特别常见的字母对有:th re insh he e_de ed s_ng at r_t
20、e es d_下划线代表一个空格。类似地,常见的3元组合有:the and foring ion ess因此,一般不对单个字母采用哈夫曼编码,而是将字符集扩展为包含所有单字母、常见2字母和3字母组合的扩展字符集,然后再对扩展字符集进行哈夫曼编码,这样可以得到更高的编码效率。第33页,共87页,编辑于2022年,星期一例2-7 概率分布均匀的3元素单字符集的哈夫曼编码。该字符集的哈夫曼编码树见图2-5,其详细参数见表2-7(i=1,2,3)。图2-5 概率分布均匀的3元素单字符集的哈夫曼编码树第34页,共87页,编辑于2022年,星期一表2-7 概率分布均匀的3元素单字符集哈夫曼编码的详细参数第
21、35页,共87页,编辑于2022年,星期一该哈夫曼编码的平均码长是1.667b,采用等长码时码 长 为 2b,则 哈 夫 曼 编 码 提 供 的 压 缩 率 是1.20(2/1.667)。应用式(2-21)计算字符集的熵(平均信息量)为1.585b,该字符集编码效率为95.08(1.585/1.667)。若把该3元素单字符集扩展为9元素双字符集,则扩展后的9元素双字符集的参数如表2-8所示。可算出扩展后的9元素双字符集的压缩率是1.24(2/1.611),编码效率是98.39(1.585/1.611),与扩展前的3元素单字符集的压缩率1.20、编码效率95.08相比较,有提高但提高的幅度不大。
22、第36页,共87页,编辑于2022年,星期一表2-8 概率分布均匀的3元素单字符集扩展为9元素双字符集第37页,共87页,编辑于2022年,星期一 通过例2-6与例2-7的比较,我们可以得出以下两点结论:字符集的哈夫曼编码的编码效率和压缩率与字符集的概率分布有关,概率分布不均匀,编码效率低,压缩率高;概率分布均匀,编码效率高,压缩率低。扩展后的字符集的编码效率和压缩率提高的幅度与原字符集的概率分布有关,概率分布不均匀,编码效率和压缩率提高的幅度大;概率分布均匀,编码效率和压缩率提高的幅度小。故哈夫曼编码适合用于概率分布不均匀的信源。第38页,共87页,编辑于2022年,星期一哈夫曼编码方法是一
23、种不等长最佳编码方法,此处的最佳是指:对于相同概率分布的信源而言,它的平均码长比其他任何一种有效编码方法的平均码长都短。第39页,共87页,编辑于2022年,星期一 2.3 限失真信源编码限失真信源编码2.3.1 基本原理若有一个离散、无记忆、平稳信源,其信息率失真函数为R(D),则当通信系统中实际信息率RR(D)时,只要信源序列L足够长(L),一定存在一种编码方式C使其译码以后的失真小于或等于D+,且为任意小的正数(0),反之,若RR(D),则无论用什么编码方式,其译码失真必大于D。第40页,共87页,编辑于2022年,星期一与实现无失真信源编码的方法类似,实现限失真信源编码的方法也分为两大
24、类型:一类为适应信源方式,即首先承认信源的实际客观概率统计特性,再寻找适应这类概率统计特性的编码方法。比如充分考虑并利用信源消息序列的各个消息变量(或各取样值)之间的统计关联(记忆特性)的矢量量化编码;另一类是改造信源方式,其着眼点首先是改造信源的客观统计特性,即解除实际信源消息序列的各个消息(或各取样值)之间的统计关联相关特性,将有记忆信源改造为无记忆信源,甚至还可以进一步将无记忆信源变换为理想最大熵等概率信源。第一类:矢量量化编码,第二类:预测编码与变换编码。第41页,共87页,编辑于2022年,星期一2.3.2 连续信源的限失真信源编码1.标量量化标量量化与连续信源的模拟信号数字化紧密相
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信源 编码 技术 PPT 讲稿
限制150内