信息论、编码与密码学

《信息论、编码与密码学》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一部分信息论和信源编码第1章信源编码并不是我们注意到的每一件事都重要，也不是每一件重要的事我们都注意到了。爱因斯坦（1879—1955）1.1信息论简介今天，我们生活在信息时代。因特网（Internet）已经成为我们生活中不可缺少的一部分，这使得太阳系第三大行星成为一个地球村。人们通过手机交谈已经是一件很平常的事。电影可以以DVD碟片的形式租回家欣赏。名片上印上电子邮箱和网址也很正常。许多人宁愿给朋友发送电子邮件和电子贺卡而不去发普通信件。股票行情也可以通过手机来查看。信息已成为成功的关键（它一直是成功的关键之

2、一，但在今天的世界上它是最关键的）。在所有这些信息的背后，信息的交换却依靠小小的1和0（即无所不在的比特），通过它们一个接一个地排在一起来表达信息。我们今天所生活的信息时代的存在主要归功于发表于1948年的一篇精辟的论文，这篇论文为奇妙的信息论奠定了基础。信息论的创始人是美国电子工程师ClaudeE.Shannon，他在发表于BellSystemTechnicalJournal（1948）的论文“TheMathematicalTheoryofCommunication”（通信的数学理论）中阐述了自己的思想。广义地

3、说，信息包括一切标准通信媒体的内容，如电报、电话、无线电、电视以及来自电子计算机、伺服机械装置系统和其他数据处理器件的信号。该理论甚至可应用于人体和其他动物神经网络的信号。信息论最关注的是发现能描述为通信和处理信息而设计的控制系统的数学定律。它建立量化指标来度量信息以及不同系统在传输、储存和处理信息时的容量。有些要解决的问题与发现最好的使用各种已有通信系统的方法相关，也和最好的将有用的信息或信号同无用的信息或噪声分开的方法有关。另一个问题就是对给定的信息载体（通常称为信道）给出容量上界。尽管主要是通信工程师对那些

4、结果感兴趣，但有些概念已被诸如心理学和语言学等领域采用并发现它们很有用。信息论的界限非常模糊。这种理论与通信理论有很大的重叠部分，但它主要面向信息处理和通信方面的基本限制，而较少涉及所用元器件的详细运作情况。本章，我们将首先阐述对信息的直观理解。然后用数学模型来描述信息源以及对信息源所发出的信息的量化度量。然后我们将陈述并证明信源编码定理。有了基本的数学框架之后，我们将介绍四种信源编码技术，即Huffman编码、Shannon-Fano-Elias编码、算术（Arithmetic）编码和Lempel-Ziv编码。

5、本章还将讨论游程编码（RunLengthEncoding）、率失真函数（RateDistortionFunction）和优化量化器（OptimumQuantizer）。为了说明相关的随机变量，我们将学习随机过程的熵率。本章后面介绍图像压缩，它是信源编码的一个重要应用领域。特别是，我们将简单讨论JPEG（JointPhotographicExpertsGroup）标准。2第一部分　信息论和信源编码1.2不确定性和信息任何信源，不管是模拟的还是数字的，都产生本质上随机的输出。假若不是随机，即我们能准确地知道其输出，那

6、么就没必要传输它！信源存在模拟信源和离散信源两种。我们生活在一个模拟世界里，多数信源都是模拟信源，例如语音、温度波动等。离散信源都是人造的信源，例如从有限字母集中产生一连串字母（如，写电子邮件）的信源（如，人）。在进一步介绍信息的数学度量之前，让我们先找一下直观感觉。请阅读下面的句子：（1）明天太阳将从东边升起。（2）在一小时后电话会响。（3）今年冬天德里将下雪。这三个句子带有不同量的信息。事实上，第一个句子几乎带不来任何信息，因为每个人都知道太阳从东边升起，也就是说这件事再次发生的概率几乎为1（N.Bohr说道

7、：“作预言是有风险的，特别是在涉及将来的时候。”）。第二个句子看来比第一个句子带来更多的信息，因为电话可能响，也可能不响。电话在一小时后响的概率是有限的（除非维修人员又在工作！）。最后一个句子你可能要读两遍，因为德里从来没下过雪，因此德里下雪的概率非常低。有趣的是，上述句子所携带的信息量与句子中所陈述的事件发生的概率有关，而且我们也观察到相反的关系。第一个句子讲的是发生概率几乎为1的事件，它几乎没带什么信息。第三个句子发生的概率很低，看来带来了不少的信息。（我们应读上两遍以确定没看错！）另外可以注意到句子的长度与

8、所携带的信息量无关。事实上，第一个句子最长但所携带的信息量最少。现在我们将建立信息的数学度量。定义1.1考虑可能输出为xi，i＝1,2,⋯,n的离散随机变量X。则事件X＝xi的自信息（self-information）定义为1Ix()i=log=−log()Pxi(1-1)Px()i我们注意到高概率事件没有低概率事件所携带的信息多。对于P(xi)＝1的事件，有