信息论第八章节课件
25页1、第八章 无失真的信源编码,8.1 霍夫曼(Huffman)码,8.2 费诺(Fano)码,8.3 香农费诺埃利斯码,8.1 霍夫曼(Huffman)码,8.1.1 二元霍夫曼码,8.1.2 r元霍夫曼码,8.1.3 Huffman码的最佳性,香农编码:,1、码长,2、按照算出的码长、用树图法编出相应的即时码。,一般香农编码的 不是最短的,即不是最佳码。,例8.1 用香农编码方法编成二元惟一可译码.,编码,8.1.1 二元霍夫曼码,1、二元Huffman码的编码步骤,将q个信源符号按概率分布由大到小的 顺序排列起来:,(2)将码符号0,1分配给两个最小概率的信 源符号,并将其概率值合并,成为一个 信源符号,q个符号的 信源缩减成q-1 个 信源。,(3)排序 ,分配0,1, 重复步骤(2), 得缩减 信源,(4)直至最后信源只含两个符号,分配码 符号0,1.,(5) 从最后一级信源开始,向前返回,码 符号顺序列出,得相应码字。,例8.1,构造出码树,原因:(1) 最小概率分配0,1时可任意。各 码长 不变, 不变, 码形式不同.,(2) 缩减合并后的符号概率与其它符号概 率相同时, 概率
2、大小次序当上下移动 时, 不违反规定。编码后 不同, 码不 同, 但 相同。,Huffman编码方法得到的码并不唯一。,2、例8.1 新合并概率放上面,问题:码长相同,哪种编码好?,码长度方差小的码序列长度变化较小,从实现的角度更好。,编码方法补充:,在霍夫曼编码过程中,在缩减信源时,使合并得来的概率尽量处于最高的位置。,3、霍夫曼码具有的三个特点,(1) 短码得到充分利用 则,(2) 各次缩减信源中最小概率的两个符号 有相同的码长。,(3) 各次缩减信源中最小概率的两个符号 的码字只有最后一位码元不同。,8.1.2 r元霍夫曼码,注意三点,(2) 每次合并r个最小概率成为新信源,减 少 个符号。,(1) 将最小概率的r个符号分配码元,例8.2 四元Huffman码,补二项,8.1.3 Huffman码的最佳性,1、定理8.1,(1) 若,对于给定分布的任何信源,存在一个最佳即时码,此码满足以下性质,(2) 两个最小概率的信源符号所对应的 码字具有相同的码长。,(3) 两个最小概率的信源符号对应的码 字,除最后一位码元不同外,前面 各位码元都相同。,2、定理 8.2,C是 Huffma
3、n 码。,可以证明 r 元霍夫曼码一定是最佳码。而且信源的N次扩展也可以采用Huffman 编码方法,当N增大时,快速,二元 Huffman 码一定是最佳即时码。即,(1) 无失真编码效率高, , 常用于文件传 真, 语音处理和图象处理的数据压缩.,(2) 解决速率匹配问题,设备较复杂, 信源与信 道间需增加缓冲寄存器, 变速入, 恒速出。,Huffman 码的优点和缺点,(3) 克服误差扩散:限制霍夫曼码仅能应用于 优质信道(=10-6)以限制扩散的可能性。,(4) 要求了解信源的统计分布。,(5) 算法复杂度随着信源符号串长度的增加而 迅速增长。,Fano 码的编码步骤:,(1) 将信源符号以概率递减的次序排列.,(2) 划分成两大组,使每组的概率和近似 相等,并分别赋予码符号“0”和“1”.,(3) 将每大组的信源符号再分成两大组, 重复(2), 直至每小组只剩一个信源符号.,(4) 信源符号所对应的码符号序列则为 编得的码字。,8.2 费诺(Fano)码,例8.4,例8.1,费诺码的编码方法实际上是构造码树的一种方法,是即时码,当概率和相差较远时,会使平均码长增加.一般不是最佳码.,它是采用信源符号的累积分布函数来分配码字.,1、设信源符号集 且所有 定义累积分布函数,定义修正的累积分布函数,8.3 香农-费诺-埃利斯码,(1) 是每台阶的上界值,(2) 处于对应 台阶的中点,(3) 每台阶的高度是该符号的概率,(4) 当,可采用 的数值作为符号 的码字.,码字,取多长?,选取,用 替代 所带来的误差小于 , 其值仍在同台阶以内不同的 对应不同的台阶,即区域,没有重叠,是即时码。,书中证明,例8.5 求香农费诺埃利斯码,Shannon-Fano-Elias 码虽然不是最佳码,但它发展成为算术码,其编码和译码可由计算获得,效率很高。,
《信息论第八章节课件》由会员E****分享,可在线阅读,更多相关《信息论第八章节课件》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-03-21 39页
2024-03-21 41页
2024-03-21 40页
2024-03-21 34页
2024-03-21 33页
2024-03-21 35页
2024-03-21 21页
2024-03-21 45页
2024-03-21 33页
2024-02-20 85页