信息论与编码ppt

信息论与编码ppt第一页，共十六页，编辑于2023年，星期六引言人类很早就学会利用语言文字来表示信息，而随着时间的流逝，这些语言文字逐渐发展成更简练的形式，即现代人表达和传递信息的文字形式。无论是古文字还是现代文字，都有相同之处，即基本组成要素的个数都是有限的。这个事实在信息论中依然有效，在此基础上可建立相应的数学模型，也即编码理论。第二页，共十六页，编辑于2023年，星期六编码的目的编码理论更关心如何高效地表示信息，这是古代语言所不具备的特性。第三页，共十六页，编辑于2023年，星期六语言与编码形式语言(FormalLanguage)语言由符号(Symbol)组成，它是语言的基本元素且总数有限，其全体则组成了字母表(Alphabet)。编码(Coding)码字(Codeword)，所有码字形成集合即码簿(Codebook)。译码(Decoding)第四页，共十六页，编辑于2023年，星期六编码:正确vs性能采用标点符号进行断句的方案如何衡量编码性能数学期望形式描述每个随机变量所需码字长度编码的期望长度(ExpectedLength)传输终止符号(EOT)的重要性压缩是要寻找随机变量的最小描述长度(MinimumDescriptionLength,MDL)。第五页，共十六页，编辑于2023年，星期六唯一可译码编码的扩展是非奇异的，称此情况下的编码是唯一可译码(UniquelyDecodableCode)。Sardinas和Patterson判断唯一可译码方法编码的拼接悬挂后缀(DanglingSuffix)。利用遍历算法不但可判断编码的唯一可译性，还可根据路径构造出存在二义性的序列。悬挂前缀也可第六页，共十六页，编辑于2023年，星期六即时码与前缀码读入当前字符后立即得到译码结果的编码称之为即时码(InstantaneousCode)。即时码必须是唯一可译码，反之则不然。前缀码(PrefixCode)后缀码(SuffixCode)前缀码和后缀码都是唯一可译码，但如果采用了不合适的译码方式则它们则不为即时码。第七页，共十六页，编辑于2023年，星期六译码二叉树第八页，共十六页，编辑于2023年，星期六前缀码的码长约束Kraft不等式(Kraft'sInequality)可考察其码字形成译码树由于前缀码的码字必须放置于叶子结点码字长度恰为根到叶子结点的路径长度可使用上述结论证明Kraft不等式第九页，共十六页，编辑于2023年，星期六唯一可译码的码长约束唯一可译码也满足Kraft不等式的特性取前缀码即可Karush的简化证明生成函数字母表中元素的不同排列形式任意次扩展情况下均成立，可取极限证之第十页，共十六页，编辑于2023年，星期六最佳码下界Shannon编码第十一页，共十六页，编辑于2023年，星期六Huffman编码贪婪算法Huffman编码是最佳码典范码(CanonicalCode)满足的性质归纳证明Huffman编码的最佳性一般情况下的Huffman编码第十二页，共十六页，编辑于2023年，星期六Fano编码Huffman编码使用了较为复杂的堆Fano编码可给出较简单的实现方式，不但可降低编码实现难度，且拥有较好的性能近似等分Fano编码的期望长度满足第十三页，共十六页，编辑于2023年，星期六Shannon-Fano-Elias编码区间二叉树(IntervalBinaryTree)修正累积分布函数从区间相互不相交特性证明唯一可译将累积分布函数进一步减少可得到Shannon编码，更为紧致更为一般的算术编码第十四页，共十六页，编辑于2023年，星期六总结通过对作者论文的学习，得知最好的压缩工具将概率模型预测结果用于算术编码。算术编码由JormaRissanen发明，并且由Witten、Neal以及Cleary将它转变成一个实用的方法。优点：提高编码效率；缺点：需要大量缓冲设备来存储这些变长码,然后再以恒定的码率进行传送；在传输的过程中如果出现了误码,容易引起错误扩散,所以要求有优质的信道。有时为了得到较高的编码效率，先采用某种正交变