信息论与编码.ppt

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