信息论与编码ppt

1、信息论与编码ppt第1页，共16页，2022年，5月20日，1点13分，星期一引言人类很早就学会利用语言文字来表示信息，而随着时间的流逝，这些语言文字逐渐发展成更简练的形式，即现代人表达和传递信息的文字形式。 无论是古文字还是现代文字，都有相同之处，即基本组成要素的个数都是有限的。这个事实在信息论中依然有效，在此基础上可建立相应的数学模型，也即编码理论。 第2页，共16页，2022年，5月20日，1点13分，星期一编码的目的编码理论更关心如何高效地表示信息，这是古代语言所不具备的特性。 第3页，共16页，2022年，5月20日，1点13分，星期一语言与编码 形式语言(Formal Langua

2、ge)语言由符号(Symbol)组成，它是语言的基本元素且总数有限，其全体则组成了字母表(Alphabet)。编码(Coding)码字(Codeword)，所有码字形成集合即码簿(Codebook)。译码(Decoding)第4页，共16页，2022年，5月20日，1点13分，星期一编码: 正确 vs 性能采用标点符号进行断句的方案 如何衡量编码性能 数学期望形式描述每个随机变量所需码字长度 编码的期望长度(Expected Length)传输终止符号(EOT)的重要性压缩是要寻找随机变量的最小描述长度(Minimum Description Length, MDL)。第5页，共16页，202

3、2年，5月20日，1点13分，星期一唯一可译码 编码的扩展是非奇异的，称此情况下的编码是唯一可译码(Uniquely Decodable Code)。Sardinas和Patterson判断唯一可译码方法编码的拼接 悬挂后缀(Dangling Suffix)。利用遍历算法不但可判断编码的唯一可译性，还可根据路径构造出存在二义性的序列。悬挂前缀也可第6页，共16页，2022年，5月20日，1点13分，星期一即时码与前缀码 读入当前字符后立即得到译码结果的编码称之为即时码(Instantaneous Code)。即时码必须是唯一可译码，反之则不然。前缀码(Prefix Code)后缀码(Suffi

4、x Code)前缀码和后缀码都是唯一可译码，但如果采用了不合适的译码方式则它们则不为即时码。第7页，共16页，2022年，5月20日，1点13分，星期一译码二叉树 第8页，共16页，2022年，5月20日，1点13分，星期一前缀码的码长约束 Kraft不等式(Krafts Inequality)可考察其码字形成译码树由于前缀码的码字必须放置于叶子结点码字长度恰为根到叶子结点的路径长度可使用上述结论证明Kraft不等式第9页，共16页，2022年，5月20日，1点13分，星期一唯一可译码的码长约束 唯一可译码也满足Kraft不等式的特性 取前缀码即可Karush的简化证明生成函数 字母表中元素的

5、不同排列形式 任意次扩展情况下均成立，可取极限证之第10页，共16页，2022年，5月20日，1点13分，星期一最佳码 下界Shannon编码第11页，共16页，2022年，5月20日，1点13分，星期一Huffman编码 贪婪算法 Huffman编码是最佳码 典范码(Canonical Code)满足的性质归纳证明Huffman编码的最佳性一般情况下的Huffman编码第12页，共16页，2022年，5月20日，1点13分，星期一Fano编码 Huffman编码使用了较为复杂的堆Fano编码可给出较简单的实现方式，不但可降低编码实现难度，且拥有较好的性能近似等分Fano编码的期望长度满足 第

6、13页，共16页，2022年，5月20日，1点13分，星期一Shannon-Fano-Elias编码 区间二叉树(Interval Binary Tree)修正累积分布函数从区间相互不相交特性证明唯一可译将累积分布函数进一步减少可得到Shannon编码， 更为紧致更为一般的算术编码 第14页，共16页，2022年，5月20日，1点13分，星期一总结 通过对作者论文的学习，得知最好的压缩工具将概率模型预测结果用于算术编码。算术编码由 Jorma Rissanen 发明，并且由 Witten、Neal 以及 Cleary 将它转变成一个实用的方法。 优点：提高编码效率； 缺点：需要大量缓冲设备来存储这些变长码,然后再以恒定的码率进行传送；在传输的过程中如果出现了误码,容易引起错误扩散,所以要求有优质的信道。有时为了得到较高的编码效率，先采用某种正交变换，解除或减弱信源符号间的相关性