《信息论与编码ppt优秀课件.ppt》由会员分享，可在线阅读，更多相关《信息论与编码ppt优秀课件.ppt（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息论与编码ppt第1页，本讲稿共16页引言引言n人类很早就学会利用语言文字来表示信息，而随着时间的流逝，这些语言文字逐渐发展成更简练的形式，即现代人表达和传递信息的文字形式。n无论是古文字还是现代文字，都有相同之处，即基本组成要素的个数都是有限的。这个事实在信息论中依然有效，在此基础上可建立相应的数学模型，也即编码理论。第2页，本讲稿共16页编码的目的n编码理论更关心如何高效地表示信息，这是古代语言所不具备的特性。第3页，本讲稿共16页语言与编码 n形式语言(Formal Language)n语言由符号(Symbol)组成，它是语言的基本元素且总数有限，其全体则组成了字母表(Alphabet
2、)。n编码(Coding)n码字(Codeword)，所有码字形成集合即码簿(Codebook)。n译码(Decoding)第4页，本讲稿共16页编码:正确 vs 性能n采用标点符号进行断句的方案 n如何衡量编码性能 q数学期望形式描述每个随机变量所需码字长度 q编码的期望长度(Expected Length)n传输终止符号(EOT)的重要性n压缩是要寻找随机变量的最小描述长度(Minimum Description Length,MDL)。第5页，本讲稿共16页唯一可译码 n编码的扩展是非奇异的，称此情况下的编码是唯一可译码(Uniquely Decodable Code)。nSardina
3、s和Patterson判断唯一可译码方法q编码的拼接 q悬挂后缀(Dangling Suffix)。q利用遍历算法不但可判断编码的唯一可译性，还可根据路径构造出存在二义性的序列。q悬挂前缀也可第6页，本讲稿共16页即时码与前缀码 n读入当前字符后立即得到译码结果的编码称之为即时码(Instantaneous Code)。即时码必须是唯一可译码，反之则不然。n前缀码(Prefix Code)n后缀码(Suffix Code)n前缀码和后缀码都是唯一可译码，但如果采用了不合适的译码方式则它们则不为即时码。第7页，本讲稿共16页译码二叉树 第8页，本讲稿共16页前缀码的码长约束 nKraft不等式(
4、Krafts Inequality)n可考察其码字形成译码树q由于前缀码的码字必须放置于叶子结点q码字长度恰为根到叶子结点的路径长度q可使用上述结论证明Kraft不等式第9页，本讲稿共16页唯一可译码的码长约束 n唯一可译码也满足Kraft不等式的特性 n取前缀码即可nKarush的简化证明q生成函数 q字母表中元素的不同排列形式 q任意次扩展情况下均成立，可取极限证之第10页，本讲稿共16页最佳码 n下界nShannon编码第11页，本讲稿共16页Huffman编码 n贪婪算法 nHuffman编码是最佳码 n典范码(Canonical Code)q满足的性质q归纳证明Huffman编码的最
5、佳性n一般情况下的Huffman编码第12页，本讲稿共16页Fano编码 nHuffman编码使用了较为复杂的堆nFano编码可给出较简单的实现方式，不但可降低编码实现难度，且拥有较好的性能n近似等分nFano编码的期望长度满足 第13页，本讲稿共16页Shannon-Fano-Elias编码 n区间二叉树(Interval Binary Tree)n修正累积分布函数n从区间相互不相交特性证明唯一可译n将累积分布函数进一步减少可得到Shannon编码，更为紧致n更为一般的算术编码 第14页，本讲稿共16页总结 通过对作者论文的学习，得知最好的压缩工具将概率模型预测结果用于算术编码。算术编码由 Jorma Rissanen 发明，并且由 Witten、Neal 以及 Cleary 将它转变成一个实用的方法。优点：提高编码效率；缺点：需要大量缓冲设备来存储这些变长码,然后再以恒定的码率进行传送；在传输的过程中如果出现了误码,容易引起错误扩散,所以要求有优质的信道。有时为了得到较高的编码效率，先采用某种正交变换，解除或减弱信源符号间的相关性，然后再进行信源编码；有时则利用信源符号间的相关性直接编码。第15页，本讲稿共16页THANKS!第16页，本讲稿共16页