信源编码定理

信源编码定理第1页，课件共99页，创作于2023年2月课程内容绪论信源的熵和互信息量信道和信道容量信息率失真函数信源编码定理和方法信道编码定理和方法密码学第2页，课件共99页，创作于2023年2月第五章信源编码定理和方法第3页，课件共99页，创作于2023年2月香农信息论的主要内容第4页，课件共99页，创作于2023年2月香农信息论的主要内容第5页，课件共99页，创作于2023年2月香农信息论的主要内容第6页，课件共99页，创作于2023年2月信源编码定理和方法编码的定义和类型无失真编码定理限失真编码定理最佳变长编码方法常用信源编码方法第7页，课件共99页，创作于2023年2月离散信源编码第8页，课件共99页，创作于2023年2月离散信源编码过程第9页，课件共99页，创作于2023年2月离散信源编码过程第10页，课件共99页，创作于2023年2月编码码字的码长第11页，课件共99页，创作于2023年2月平均码长第12页，课件共99页，创作于2023年2月码长偏差第13页，课件共99页，创作于2023年2月第14页，课件共99页，创作于2023年2月信源编码过程第15页，课件共99页，创作于2023年2月分组码／非分组码第16页，课件共99页，创作于2023年2月变长码／定长码第17页，课件共99页，创作于2023年2月变长码／定长码第18页，课件共99页，创作于2023年2月奇异码／非奇异码非奇异码：信源符号与码字一一对应；奇异码：信源符号与码字不是一一对应；码１码２a10.500a20.251110a30.1250000a40.1251101奇异码第19页，课件共99页，创作于2023年2月唯一可译码／非唯一可译码唯一可译码：任意有限长的码元序列，只能被唯一地分割成一个个的码字；非唯一可译码：奇异码，部分非奇异码码１码２码３码４a10.50011a20.2511101001a30.1250000100001a40.125110110000001唯一可译码第20页，课件共99页，创作于2023年2月唯一可译码／非唯一可译码码１码２码３码４a10.50011a20.2511101001a30.1250000100001a40.125110110000001唯一可译码例：{10000100}是由码2{10,0,0,01,00}产生的，但译码可以有多种分割方法，如{10,0,00,10,0}等，此时就产生歧义。第21页，课件共99页，创作于2023年2月即时码／非即时码非即时码：接收端收到一个完整的码字后，不能立即译码，还需要等待下一个码字开始接收后才能判断是否可以译码。即时码：任意一个码字都不是其他码字的前缀部分，又称为非延长码和异前缀码。第22页，课件共99页，创作于2023年2月即时码／非即时码码１码２码３码４a10.50011a20.2511101001a30.1250000100001a40.125110110000001即时码非即时码第23页，课件共99页，创作于2023年2月各类码的隶属关系第24页，课件共99页，创作于2023年2月码树编码的码树表示及码树定理第25页，课件共99页，创作于2023年2月码树定理编码的码树表示及码树定理定长码：满树变长码：非满树第26页，课件共99页，创作于2023年2月唯一可译码存在充要条件第27页，课件共99页，创作于2023年2月Ｋraft不等式Ｋraft不等式只是一个存在性证明，但不能作为唯一可译的判断依据．第28页，课件共99页，创作于2023年2月Ｋraft不等式Ｋraft不等式只是一个存在性证明，但不能作为唯一可译的判断依据．第29页，课件共99页，创作于2023年2月信源编码定理和方法编码的定义和类型无失真编码定理限失真编码定理最佳变长编码方法常用信源编码方法第30页，课件共99页，创作于2023年2月信源编码器第31页，课件共99页，创作于2023年2月无失真信源编码定理第32页，课件共99页，创作于2023年2月信源编码器第33页，课件共99页，创作于2023年2月无失真信源编码定理第34页，课件共99页，创作于2023年2月定长无失真信源编码定理第35页，课件共99页，创作于2023年2月定长无失真信源编码定理第36页，课件共99页，创作于2023年2月定长无失真信源编码定理第37页，课件共99页，创作于2023年2月例5-2说明误码来源及无失真要求第38页，课件共99页，创作于2023年2月例5-2说明误码来源及无失真要求第39页，课件共99页，创作于2023年2月例5-1说明误码来源及无失真要求第40页，课件共99页，创作于2023年2月信源序列长度Ｌ的界限第41页，课件共99页，创作于2023年2月信源序列长度Ｌ的界限第42页，课件共99页，创作于2023年2月编码效率第43页，课件共99页，创作于2023年2月编码过程第44页，课件共99页，创作于2023年2月例5-2计算保证高效时Ｌ的数量级第45页，课件共99页，创作于2023年2月例5-2计算保证高效时Ｌ的数量级第46页，课件共99页，创作于2023年2月变长无失真信源编码定理第47页，课件共99页，创作于2023年2月单符号变长编码定理第48页，课件共99页，创作于2023年2月离散平稳无记忆序列变长编码定理第49页，课件共99页，创作于2023年2月离散平稳无记忆序列变长编码定理第50页，课件共99页，创作于2023年2月变长无失真编码的编码效率第51页，课件共99页，创作于2023年2月例5-3变长编码的编码效率第52页，课件共99页，创作于2023年2月例5-3变长编码的编码效率第53页，课件共99页，创作于2023年2月例5-3变长编码的编码效率第54页，课件共99页，创作于2023年2月比较例5-2定长和变长编码的码长第55页，课件共99页，创作于2023年2月比较例5-3定长和变长编码的码长第56页，课件共99页，创作于2023年2月信源编码定理和方法编码的定义和类型无失真编码定理限失真编码定理最佳变长编码方法常用信源编码方法第57页，课件共99页，创作于2023年2月限失真信源编码定理第58页，课件共99页，创作于2023年2月限失真信源编码方法对于连续平稳无记忆信源，虽然无法进行无失真编码，在限失真情况下，有与上述定理一样的编码定理。上述定理只能说明最佳编码是存在的，而具体的构造方法却一无所知。因而就不能象无损编码那样从证明过程中引出概率匹配的编码方法，一般只能从优化的思路去实现最佳编码。第59页，课件共99页，创作于2023年2月信源编码定理和方法编码的定义和类型无失真编码定理限失真编码定理最佳变长编码方法常用信源编码方法第60页，课件共99页，创作于2023年2月最佳变长编码方法最佳变长码：能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。特点：概率大的信息符号编以短码；概率小的信息符号编以长码；第61页，课件共99页，创作于2023年2月香农(Shannon)编码方法第62页，课件共99页，创作于2023年2月例5-4演示Shannon编码过程例5-4对以下的信源进行单符号的二进制香农编码第63页，课件共99页，创作于2023年2月例5-4演示Shannon编码过程第64页，课件共99页，创作于2023年2月例5-4演示Shannon编码过程第65页，课件共99页，创作于2023年2月费诺(Fano)编码方法第66页，课件共99页，创作于2023年2月例5-5对以下的信源进行二进制费诺编码例5-5演示Fano编码过程第67页，课件共99页，创作于2023年2月例5-5演示Fano编码过程第68页，课件共99页，创作于2023年2月哈夫曼(Huffman)编码方法第69页，课件共99页，创作于2023年2月例5-6对以下的信源进行二进制Huffman编码例5-6演示Huffman编码过程第70页，课件共99页，创作于2023年2月例5-6演示Huffman编码过程第71页，课件共99页，创作于2023年2月二进制Huffman编码特点及注意事项1、码树上下的分支的分配码元应该固定，即上分支全为0，下分支全为1，或者上分支全为1，下分支全为0。不能有时上分支为0，下分支为1，有时上分支为1，下分支为0，反之亦然。2、如果合并后的概率与其它信源符号概率相同，则一般将合并后的概率放在信源符号概率之上，可以获得比较小的码长方差。3、即时码第72页，课件共99页，创作于2023年2月例5-７计算以下两种Huffman编码的码长方差第73页，课件共99页，创作于2023年2月例5-７计算以下两种Huffman编码的码长方差第74页，课件共99页，创作于2023年2月例5-8比较符号序列长度对编码效率的影响第75页，课件共99页，创作于2023年2月例5-8比较符号序列长度对编码效率的影响第76页，课件共99页，创作于2023年2月例5-8比较符号序列长度对编码效率的影响第77页，课件共99页，创作于2023年2月信源编码定理和方法编码的定义和类型无失真编码定理限失真编码定理最佳变长编码方法常用信源编码方法第78页，课件共99页，创作于2023年2月常用信源编码方法游程编码算术编码矢量量化（限失真压缩编码）预测编码变换编码第79页，课件共99页，创作于2023年2月游程编码第80页，课件共99页，创作于2023年2月游程编码第81页，课件共99页，创作于2023年2月游程编码第82页，课件共99页，创作于2023年2月常用信源编码方法游程编码算术编码矢量量化（限失真压缩编码）预测编码变换编码第83页，课件共99页，创作于2023年2月算术编码分组码的特点：直观。

(1)需要对各种信源各符号或者长为L的信源符号序列的概率进行精确的统计。

(2)当L较大时，需要的编译码存储设备开销大。

(3)长度L改变时，需要重新计算概率分布非分组码算术编码是一种非分组码,序贯编译码第84页，课件共99页，创作于2023年2月算术编码第85页，课件共99页，创作于2023年2月算术编码第86页，课件共99页，创作于2023年2月例5-9演示算术编码过程第87页，课件共99页，创作于2023年2月例5-9演示算术编码过程第88页，课件共99页，创作于2023年2月例5-9演示算术编码过程第89页，课件共99页，创作于2023年2月例5-9演示算术编码过程第90页，课件共99页，创作于2023年2月例5-9演示算术译码过程第91页，课件共99页，创作于2023年2月常用信源编码方法游程编码算术编码矢量量化（限失真压缩编码）预测编码变换编码第92页，课件共99页，创作于2023年2月矢量量化（限失真压缩编码）矢量量化用于压缩幅度连续,时间离散的数据矢量量化基于两个事实:(1)压缩符号序列比压缩单独符号在原理上可产生更好的效果;(2)相邻数据项(如图象、声音的样本)也很少会差别很大.第93页，课件共99页，创作于2023年2月矢量量化（限失真压缩编码）基本思想矢量量化时,一个数据流被分成许多包含N个字节的块(N>1),一个预先训练定义好的表包含了一系列的模式.对于每个块,表用来查询最为相似的模式(通过固定的标准),在表中的每个模式都有一个相关的索引,因此每个块都被分配一个索引.