信息论与编码-第一章

信息论与编码

主讲老师：姚志强

yaozhiqiang@

(Informationtheoryandcoding)学习的意义信息论与编码理论是信息科学的基础理论，对信息进行定量的分析，对信息处理给出理论的指导，是20世纪后半叶数字化革命的主要理论和技术支柱．信息论与编码的许多思想和方法已广泛渗透到许多领域：[计算机]，[通信技术]，[统计学],[物理学]，[生物学]，[系统科学],

[经济学],[社会学],……组成客观世界的三大基本要素：物质、能量和信息，材料科学、能源科学、和信息科学一起被称为当代文明的“三大支柱”。Withoutmaterials,thereisnothing.没有物质的世界是虚无的世界；Withoutenergy,nothinghappens.没有能源的世界是死寂的世界；Withoutinformation,nothingmakessense没有信息的世界是混乱的世界。几十年来许多优秀的学者，工程师共同努力推动了该理论和实践的发展．美国科学家ClaudeElwoodShannon，1916年4月30日—2001年2月26日，以60多年前Shannon的不朽论文《通信的数学理论》为里程碑．信息论的奠基人：信息论的学习有助于对其他学科的研究,同时其他相关学科的研究也会促进信息论的发展.这些理论是属于21世纪的工程科学理论，将对21世纪新科技产生巨大的作用．国外的一流学校在20世纪50年代末就开始设立信息论与编码课程．目前国内各高校的信息类专业研究生都已把信息论与编码作为一门重要的专业基础理论课．信息论对于不同学科的重要性通讯工程师说：当受信者对一个事件出现的先验概率估计越小时，他获得的信息量就越大；计算机科学家则说：微处理器时钟频率的大小，决定着它处理信息的速度高低；生物学家则高呼：脱氧核糖核酸上的信息是控制子代和亲代相象的唯一源泉。……

不同学科的信息有着不同的内涵，有着不同的研究目的主要参考文献《信息理论与编码》姜丹、钱玉美编著中国科技大学出版社（第一版，第二版，第三版）；《信息论—基础理论与应用》傅祖芸编著电子工业出版社2001年版；《信息论与编码方法》西南交通大学勒蕃教授著；《信息论与编码》陈运、周亮、陈新编著电子工业出版社；《信息论与编码》仇佩亮编著高等教育出版社；需具备的相关数学知识：概率与统计理论矩阵论需了解的相关专业方面知识：通信原理高等数学最优化理论本课程的主要教学目标：信息论基本原理与应用第一章、绪论第一节、信息论起源和发展第二节、信息的概念第三节、信息论的研究内容和核心第一节、信息论的起源及发展1、起源

1924年，奈奎斯特（Nyquist）：信号带宽和信息速率间的关系。

1928年，哈特利（Hartley）：通讯系统传递信息的能力，并给出了信息度量的方法。1948年，香农（Shannon）：通讯中的数学理论。并由此创立了信息论学科，因此称他为信息论的创始人。1956年，布里渊（Brillouin

）：《科学与信息论》，信息就是负熵。信息定义的概念1928年，哈特利在《BellSystemTechnicalJournal》上发表了一篇题为“信息传输”的论文。在这篇论文中，他把信息理解为选择通信符号的方式，并用选择的自由度来计量这种信息的大小。他认为，发信者所发出的信息，就是他在通信符号表中选择符号的具体方式。哈特利信息定义的局限性哈特利的这种理解能够在一定程度上解释通信工程中的一些信息问题，但是它也存在着一些严重时局限性：所定义的信息不涉及内容和价值，只考虑选择的方式，没有考虑到信源的统计性质；把信息理解为选择的方式，就必须有一个选择的主体作为限制条件。这些缺点使它的运用范围受到很大的限制。美国数学家香农在《BellSystemTechnicalJournal》发表了一篇题为“AMathematicalTheoryofCommunication”的长文（1948）。这篇论文以概率论为工具，深刻阐述了通信工程的一系列基本理论问题，给出了计算信源信息量和信道容量的方法和一般公式，得到了一组表征信息传递重要关系的编码定理。香农在进行信息的定量计算的时候明确地把信息量定义为随机不定性程度的减少。这就表明了他对信息的理解：信息是用来减少随机不确定性的东西。随机不确定性是指由于随机因素所造成的不能肯定的情形，在数值上可以用概率熵来计量。香农简介

1916-2001，信息论及数字通信时代的奠基人。美国科学院院士、工程院院士，英国皇家学会会员，美国哲学学会会员。

1936年获得密西根大学数学与电气工程学士学位。

1938年获MIT（麻省理工学院）电气工程硕士学位，《继电器与开关电路的符号分析》。

1940年获MIT数学博士学位，《理论遗传学的代数论》。二战期间：著名的密码破译者，在BELL实验室，主要跟踪德国的飞机和火箭。

1948年发表《通信中的数学理论》。1949年，另一著名论文《噪声下的通信》根据这一思想，法裔美国科学家布里渊（Brillouin，1956）在他的名著《科学与信息论》中直接了当地指出：信息就是负熵。并且他还创造了Negentropy这一词来表示负熵的概念。美国数学家、控制论的主要奠基人维纳在1950年出版的《控制论与社会》一书中对信息的理解是：“人通过感觉器官感知周围世界”，“我们支配环境的命令就是给环境的一种信息”，因此，“信息就是我们在适应外部世界，并把这种适应反作用于外部世界的过程中，同外部世界进行交换的内容的名称”。“接收信息和使用信息的过程，就是我们适应外界环境的偶然性的过程，也是我们在这个环境中有效地生活的过程”。维纳信息定义的缺陷维纳把人与外部环境交换信息的过程当作是一种广义的通信的过程。这当然是没有问题的；因为，广义的通信本来就可以泛指人与人、机器与机器、机器与自然物、人与自然物之间的信息传递与交换。不过，这里所理解的信息仍然不够确切。这是因为：人与环境之间互相交换的内容中不仅有信息，也有物质与能量，把它们统统起一个名字信息，岂不是把信息与物质及能量混为一谈。信息定义的总结信息是人与外界交互的内容，是有序程度的度量和负熵，是用以减少不定性的东西，这些都是Wiener、Brillouin、Shannon等人的理解。这些认识比仅仅把信息看作消息或通信内容要更深刻。在数学上很容易证明，Hartley的信息概念仅是Shannon信息概念的一种特殊情形。总起来说，在现有的各种理解中，Shannon的定义比较深刻，而且这种定义还导出了相应的算法。香农信息定义的概念信息是事物运动状态或存在形式的不确定性的描述，所谓不确定性就是千变万化、不规则、随机性，用概率模型来描述并对其进行定量的计算。通信系统中接受消息的过程就是消除不确定性的过程。不确定的消除就获得了信息。信息量与不确定性消除的程度有关。香农信息定义的缺陷（1）Shannon《通信的数学理论》明确地指出：

通信的任务是在收端复制发端所发出的波形，至于它的内容含义，因与通信工程无关，所以可以舍去。

可见Shannon理论中的不定性纯粹是波形形式上的不定性，与此相应的信息概念也是纯粹的形式化的概念（称为语法信息）。

这样的信息概念排除了信息的含义因素，（即语义信息）和价值因素（即语用信息），不考虑收信者的主观特性。因此，其适用范围受到严重的限制。香农信息定义的缺陷（2）只考虑了随机型的不定性，不能解释与其他型式的不定性（如模糊不定性）有关的信息问题。这种信息定义只从功能角度上来表述，还是没有从根本上回答“信息是什么”的问题。Ⅰ．信源编码与数据压缩Ⅱ．信道编码与差错控制技术Ⅲ．多用户信息论与网络通信Ⅳ．多媒体与信息论Ⅴ．信息论与密码学和数据安全Ⅵ．信息论与概率统计Ⅶ．信息论与经济学Ⅷ．信息论与计算复杂性Ⅸ．信息论与系统、控制、信号检测和处理Ⅹ．量子信息论Ⅺ．Shannon的其它重要贡献2、发展信息论主要几个方面的进展2、发展⑴、信道编码定理，1948，C.E.Shannon。⑵、发现Hamming码，1950，H.W.Hamming。⑶、发现Golay码，1954，M.J.E.Golay。⑷、发现Reed-Muller码，1954，I.S.ReedandD.E.Muller。⑸、发现卷积码，1955,P.Elias。⑹、线性码、群码的系统描述，1956，D.Slepian。⑺、发现循环码，1957,E.Prange。⑻、卷积码的序列译码算法，1957,J.M.Wozencraft;1964,R.M.Fano。⑼、发现BCH码，1960,R.C.BoseandD.K.Ray-Chaudhuri,1959,A.Hocquenghem。⑽、发现Reed-Solomon码，1960,I.S.ReedandG.Solomon。⑾、纠错码作为信息论的分支出现，第一本书Error-CorrectingCodes,W.W.Peterson,MITPress,1961。编码技术的发展编码技术的进展情况2、发展(12)Berlekamp-Massey译码算法─分组码实用代数译码算法，1966,E.R.Berlecamp,1969,J.L.Massey。(13)发现级连码，1966,G.D.Forney。(14)卷积码的Viterbi译码算法，1967,A.J.Viterbi。(15)发现Goppa码和代数几何码，1970,V.C.Goppa。1982,M.A.Tsfasman,S.G.Vladut,andTh.Zink(16)发现欧氏几何码，TCM,1976,G.Ungerboeck；BCM,1977,H.ImaiandS.Hirakawa。(17)发现格码，1989，R.deBuda。格(lattice)码可趋近频带受限高斯信道容量。Loeligerz在1992年已证明，这是Zp上的欧氏空间群码。(18)发现Turbo码，迭代自适应译码算法，1993,C.BerrouandA.Glavieux.(19)LDPC码，近来又重新被发现。信息论发展中的悲情人物诺贝尔经济学获得者：

JOHNNASH于1951年发表《非合作博弈论》成就著名的“纳什均衡”理论1958年（30岁）开始痴迷于信息编码技术，出现精神失常。直到80年代末，方从癫疯中苏醒，继续从事经济学博弈论研究，1994年获得诺贝尔经济学奖

奥斯卡影片《美丽心灵》第二节、信息的概念消息(message)是信息的载体，相对具体的概念，如语言，文字，数字，图像;信号(signal)表示消息的物理量，电信号的幅度，频率，相位等等;信息(information)一个抽象的概念，可以定量的描述。信息、物质和能量是构成一切系统的三大要素;第二节、信息的概念狭义信息论（经典信息论）研究信息测度，信道容量以及信源和信道编码理论一般信息论研究信息传输和处理问题，除经典信息论外还包括噪声理论，信号滤波和预测，统计检测和估值理论，调制理论，信息处理理论和保密理论广义信息论除上述内容外，还包括自然和社会领域有关信息的内容，如模式识别，计算机翻译，心理学，遗传学，神经生理学第三节、信息论的研究内容和核心1、研究内容：通信系统模型信源编码器信道译码器信宿干扰源通信系统的基本任务要求：可靠性、有效性。可靠:要使信源发出的消息经过传输后，尽可能准确地、不失真或限定失真地再现在接收端。有效:用尽可能短的时间和尽可能少的设备来传输最大的消息通信系统模型进一步细分信源信源编码器信道编码器调制器信道干扰源解调器信道译码器信源译码器信宿等效离散信道等效离散信源等效信宿信道编码器信道译码器第三节、信息论的研究内容和核心2、研究核心信息的测度、传输与处理课程作业1信息论的最新研究成果综述要求：

（1）结合自己将来的研究方向（-2）；

（2）不容许拷贝文献，必须综合多篇文

献，以自己的语言书写完成（-5）；

（3）采用2009年以后的文献（-1）；

（4）可以是全面的综述（难），也可以

是个别成果。第一章单符号离散信源本章介绍信源的统计特性和数学模型各类信源的信息测度----熵及其性质引入信息理论的一些基本概念和重要结论第一章的几个推论通信系统模型：对信息论的学习可从信源开始消息是信息的载荷者。信息是抽象的，消息是具体的。要研究信息，还得从研究消息入手。由于信源发送什么消息预先是不可知的，只能用概率空间来描述信源1.1信源的数学模型及分类单符号信源：

输出是单个符号（代码）的消息离散信源连续信源平稳随机序列信源：

信源输出的消息由一系列符号序列所组成，可用N维随机矢量

X＝(X1,X2,…,XN)描述，且随机矢量X的各维概率分布都与时间起点无关----平稳！离散平稳信源连续平稳信源平稳随机序列信源（续）：无记忆（独立）离散平稳信源有记忆信源m阶马尔可夫信源随机波形信源实际某些信源的输出常常是时间和取值都是连续的消息.例如语音信号,电视信号.这样的信源成为随机波形信源；离散信源(单符号)特点：输出是单个符号（代码）的消息，符号集的取值A:{a1,a2,…,aq}是有限的或可数的，可用一维离散型随机变量X来描述。例：投硬币、书信、电报符号等等。数学模型：设每个信源符号ai出现的(先验)概率p(ai)(i=1,2,…,q)

满足：概率空间能表征离散信源的统计特性，因此也称概率空间为信源空间。有记忆信源信源在不同时刻发出的符号之间是相互依赖的，即信源输出的平稳随机序列X中，各随机变量Xi之间相互依赖。需在N维随机矢量的联合概率分布中，引入条件概率分布来说明它们之间的关联。

例：汉字组成的中文序列中，只有根据中文的语法、习惯用语、修辞制约和表达实际意义的制约所构成的中文序列才是有意义的中文句子或文章。所以，在汉字序列中前后文字的出现是有依赖的，不能认为是彼此不相关的。其他如英文，德文等自然语言都是如此m阶马尔可夫信源不同时刻发出的符号间的依赖关系记忆信源的记忆长度为m+1时，称这种有记忆信源为m阶马尔可夫信源若上述条件概率与时间起点

i无关，信源输出的符号序列可看成为时齐马尔可夫链，则此信源称为时齐（平稳）马尔可夫信源1.2离散信源的信息熵其性质

讨论基本的离散信源(即输出为单个符号的消息，且这些消息间两两互不相容)基本的离散信源可用一维随机变量X来描述信源的输出，信源的数学模型可抽象为:问题：这样的信源能输出多少信息?

每个消息的出现携带多少信息量?

（书P1的例子）信息的度量考虑：信息的度量（信息量）和不确定性消除的程度有关，消除的不确定性＝获得的信息量；不确定性就是随机性，可以用概率论和随机过程来测度，概率小－>不确定性大；推论：概率小－>信息量大，即信息量是概率的单调递减函数；信息量应该具有可加性；信息量的计算公式为（香农（自）信息量的度量）：一.自信息设离散信源X的概率空间为：I(ai)代表两种含义：（1）当事件ai发生以前，表示事件ai发生的不确定性（2）当事件ai发生以后，表示事件ai所提供的信息量称事件ai发生所含有的信息量为ai的自信息量。定义为：一点说明计算自信息量时要注意有关事件发生概率的计算；自信息量的单位取决于对数的底；底为2，单位为“比特（bit,binaryunit）”；底为e，单位为“奈特（nat,natureunit）”；底为10，单位为“哈特（hat,Hartley）”；根据换底公式得：一般计算都采用以“2”为底的对数，为了书写简洁，常把底数“2”略去不写1nat=1.44bit,1hat=3.32bit；例子[例]8个串联的灯泡x1，x2，…，x8，其损坏的可能性是等概率的，现假设其中有一个灯泡已损坏，问每进行一次测量可获得多少信息量？总共需要多少次测量才能获知和确定哪个灯泡已损坏。解：收到某消息获得的信息量(即收到某消息后获得关于某事件发生的信息量)

＝不确定性减少的量＝(收到此消息前关于某事件发生的不确定性)-(收到此消息后关于某事件发生的不确定性)已知8个灯泡等概率损坏，所以先验概率P(x1)＝1/8

，即第二次测量获得的信息量=

I[P(x2)]-I[P(x3)]=1(bit)第三次测量获得的信息量=

I[P(x3)]=1(bit)至少要获得3个比特的信息量就可确切知道哪个灯泡已坏了。

第一次测量获得的信息量=

I[P(x1)]-I[P(x2)]=1(bit)经过二次测量后，剩2个灯泡，等概率损坏，P(x3)＝1/2一次测量后，剩4个灯泡，等概率损坏，P(x2)＝1/4自信息的推导某事件发生所含有的信息量应该是该事件发生的先验概率的函数。即：

I(ai)

＝f[p(ai)]根据客观事实和人们的习惯概念，函数f[p(ai)]应满足以下条件：（1）它应是先验概率p(ai)的单调递减函数，即当

p

(a1)>p

(a2)

时，有f

[

p

(a1)]

<f

[

p

(a2)

]

；（2）当p

(ai)=1时，f

[

p

(ai)]=0

（3）当p

(ai)=0时，f

[

p

(ai)]=（4）两个独立事件的联合信息量应等于它们分别的信息量之和。即统计独立信源的信息量等于它们分别的信息量之和。可以证明对数函数满足上述条件：二.信息熵对一个信源发出不同的消息所含有的信息量也不同。所以自信息I(ai)是一个随机变量，不能用它来作为整个信源的信息测度定义自信息的数学期望为平均自信息量Hr(X)，称为信息熵：由于这个表达式和统计物理学中热熵的表达式相似，且在概念上也有相似之处，因此借用“熵”这个词，把H(X)称为信息“熵”；信息熵的单位由自信息量的单位决定，即取决于对数的底。H(X)的单位：r进制单位／符号（r>1）熵的计算例：

有一布袋内放l00个球，其中80个球是红色的，20个球是白色的。随便摸出一个球，猜测是什么颜色，那么其概率空间为：

如果被告知摸出的是红球，那么获得的信息量是：

I(a1)

＝－logp(a1)

＝－log0.8=0.32

（比特）如被告知摸出来的是白球，所获得的信息量应为：

I(a2)

＝

－logp(a2)

＝－log0.2

=2.32

（比特）平均摸取一次所能获得的信息量为：

H(X)=

p(a1)

I(a1)+p(a2)I(a2)

=0.72（比特/符号）熵的含义熵是从整个集合的统计特性来考虑的，它从平均意义上来表征信源的总体特征。在信源输出后，信息熵H(X)表示每个消息提供的平均信息量；在信源输出前，信息熵H(X)

表示信源的平均不确定性；信息熵H(X)表征了变量X的随机性。例如，有两信源X、Y，其概率空间分别计算其熵，得：H(X)=0.08（bit/符号）

H(Y)=1（bit/符号）H(Y)＞H(X)，因此信源Y比信源X的平均不确定性要大。

[例]

设甲地的天气预报为：晴(占4／8)、阴(占2／8)、大雨(占1／8)、小雨(占1／8)。又设乙地的天气预报为：晴(占7／8)，小雨(占1／8)。试求两地天气预报各自提供的平均信息量。若甲地天气预报为两极端情况，一种是晴出现概率为1而其余为0。另一种是晴、阴、小雨、大雨出现的概率都相等为1／4。试求这两极端情况所提供的平均信息量。又试求乙地出现这两极端情况所提供的平均信息量。两个信源解：甲地天气预报构成的信源空间为:则其提供的平均信息量即信源的信息熵:乙地天气预报的信源空间为:结论：甲地天气预报提供的平均信息量大于乙地，因为乙地比甲地的平均不确定性小。甲地极端情况极端情况1：晴天概率＝1

结论：等概率分布时信源的不确定性最大，所以信息熵（平均信息量）最大。极端情况2：各种天气等概率分布乙地极端情况极端情况1：晴天概率＝1

结论：在极端情况2下，甲地比乙地提供更多的信息量。因为，甲地可能出现的消息数比乙地可能出现的消息数多。极端情况2：各种天气等概率分布二元信源信息熵与概率空间信息熵是信源概率空间的一种特殊矩函数。这个矩函数的大小，与信源的符号数及其概率分布有关。我们用概率矢量P来表示概率分布P(x)：三、信息熵的基本性质这样，信息熵H(X)是概率矢量P或它的分量p1，p2，…，pq的q-1元函数(因各分量满足上述条件限制，所以独立变量只有q-1元)。一般H(X)可写成：熵函数H(P)是概率矢量P的函数，称为熵函数。我们用下述表示方法：用H(x)

表示以离散随机变量x描述的信源的信息熵；用H(P)

或H(p1,p2,…,pq

)表示概率矢量为

P=(p1,p2,…,pq

)的q个符号信源的信息熵。若当q=2时，因为p1+p2=1,所以将两个符号的熵函数写成H(p1)或H(p2)。熵函数H(P)是一种特殊函数，具有以下性质。性质：1、对称性：H(P)的取值与分量p1,p2

,

···

,pq的顺序无关。说明：

从数学角度：H(P)=pi·logpi中的和式满足交换率；从随机变量的角度：熵只与随机变量的总体统计特性有关。一个例子：2、确定性：H(1,0)=H(1,0,0)=H(1,0,0…,0)=0性质说明：从总体来看，信源虽然有不同的输出符号，但它只有一个符号几乎必然出现，而其它符号则是几乎不可能出现，那么，这个信源是一个确知信源，其熵等于零。

3、非负性：H(P)0说明：随机变量X的概率分布满足0＜pi＜1，当取对数的底大于1时，log(pi)

＜0，-pilog(pi)

＞0，即得到的熵为正值。只有当随机变量是一确知量时熵才等于零。这种非负性合适于离散信源的熵，对连续信源来说这一性质并不存在。以后可看到在相对熵的概念下，可能出现负值。

非负性体现信息是非负的。4、扩展性性质说明：信源的取值数增多时，若这些取值对应的概率很小(接近于零)，则信源的熵不变。所以，上式成立因为5、可加性

统计独立信源X和Y的联合信源的熵等于信源X和Y各自的熵之和。

H(XY)=H(X)+H(Y)

可加性是熵函数的一个重要特性，正因具有可加性，才使熵函数的形式是唯一的。证明：例如，甲信源为它们的联合信源是可计算得联合信源的联合熵：H(Z)=H(XY)=log(nm)=logm+logn=H(X)+H(Y)乙信源为6、强可加性两个互相关联的信源X和Y的联合信源的熵等于信源X的熵加上在X已知条件下信源Y的条件熵。

H（XY）=H（X）+H（Y/X）H（Y/X）表示信源X

输出一符号的条件下，信源Y再输出一符号所能提供的平均信息量，称为条件熵。H（XY）=H（X）+H（Y/X）的证明：H（XY）=H（X）+H（Y/X）7、递增性

若原信源X中有一个符号分割成了m个元素(符号)，这m个元素的概率之和等于原元素的概率，而其他符号的概率不变，则新信源的熵增加。熵的增加量等于由分割而产生的不确定性量。证明:递增性的推广它表示n个元素的信源熵可以递推成(n-1)个二元信源的熵函数的加权和。这样，可使多元信源的熵函数的计算简化成计算若干个二元信源的熵函数。