信息论与编码第三版

信息论与编码计算器2简介是一门应用概率论、随机过程、数理统计和近代代数的方法，来研究信息传输、提取和处理中一般规律的学科。奠基人：美国数学家香农（C.E.Shannon）1948年“通信的数学理论”3简介信息论的基本问题—信息的度量无失真信源编码定理—香农第一定理信道编码定理—香农第二定理信源编码、信道编码绪论第1章51.1信息的概念6情报：是人们对于某个特定对象所见、所闻、所理解而产生的知识。知识：一种具有普遍和概括性质的高层次的信息，以实践为基础，通过抽象思维，对客观事物规律性的概括。消息：用文字、符号、语音、图像等能够被人们感觉器官所感知的形式，把客观物质运动和主观思维活动的状态表达出来。几个常见概念7香农信息的度量（1）样本空间某事物各种可能出现的不同状态。（2）概率测度对每一个可能选择的消息指定一个概率。（3）概率空间先验概率p(xi)：选择符号xi作为消息的概率。)()()()(2121nnapapapaaaxPX样本空间概率测度8例：气象预报甲乙1/41/4,1/4,1/4,小雨大雨阴晴p(y)Y8/1,8/1,4/1,2/1)(小雨大雨阴晴xpX“甲地晴”比“乙地晴”的不确定性小。某一事物状态出现的概率越小，其不确定性越大。某一事物状态出现的概率接近于1,即预料中肯定会出现的事件，那它的不确定性就接近于零。9对xi的不确定性可表示为先验概率p(xi)的倒数的某一函数。（4）自信息（5）互信息先验的不确定性减去尚存的不确定性。后验概率p(ai|bj)：接收端收到消息bj后而发送端发的是ai的概率。)(1log)(iiaPaI)(1log)(1log);(jiijibapaPbaI10信息的特征•信息是物质存在的普遍属性，信息和能量、物质规定了事物的功能和性能；•接收者在收到信息之前，对它的内容是不知道的，所以，信息是新知识、新内容；它使认识主体对某一事物的未知性或不确定性减少的有用知识；•信息的存在具有普遍性、无限性、动态性、时效性和相对独立性；•信息可以产生，也可以消失，同时信息可以被传递、转换、扩散、复制、贮存、分割，具有可共享性；•信息是可以量度的，信息量有多少的差别。111.2信息论研究的对象、目的和内容12研究对象：通信系统模型信道信源信源编码加密信道编码干扰源信宿信源解码解密信道解码加密密钥解密密钥13信源：发送消息的源离散信源模拟信源信源是信息论的主要研究对象之一.我们不探讨信源的内部结构和机理，而关注信源的输出。重点讨论其描述方法及性质。信宿：信息归宿之意，亦即收信者或用户，是信息传送的终点或目的地。信道：传输信息的物理媒介。信源、信道、信宿14信源编码器通过信源编码可以压缩信源的冗余度,以提高通信系统传输消息的效率。信源编码器分为两类无失真信源编码：适用于离散信源或数字信号；限失真信源编码：用于连续信源或模拟信号,如语音、图像等信号的数字处理。信源编码器与译码器信源编码器的主要指标是它的编码效率。一般来说，效率越高，编译码器的代价也将越大。信源译码器把信道译码器的输出变换成信宿所需的消息形式，相当于信源编码器的逆过程。15信道编码器与译码器信道编码主要作用是提高信息传送的可靠性。信道编码器的作用在信源编码器输出的代码组上有目的地增加一些监督码元,使之具有检错或纠错的能力。信道编码的主要方法增大码率或频带,即增大所需的信道容量。这恰与信源编码相反。信道译码器的作用具有检错或纠错的功能,它能将落在其检错或纠错范围内的错传码元检出或纠正,以提高传输消息的可靠性。161.3信息论的形成和发展17信息论是在长期的通信工程实践和理论研究的基础上发展起来的。简史现代信息论是从20世纪20年代奈奎斯特和哈特莱的工作开始的：1924年奈奎斯特(Nyquist)的“影响电报速率因素的确定”。1928年哈特莱(Hartley)的“信息传输”一文研究了通信系统传输信息的能力，并给出了信息度量方法。信息论的形成181946年柯切尔尼柯夫的学位论文“起伏噪声下的潜在抗干扰理论”，根据最小错误概率准则和最小均方误差准则研究了离散和连续信道的最佳接收问题。1948年香农的权威性长文“通信的数学理论”，讨论了信源和信道特性，1949年香农“噪声中的通信”，两论文奠定了现代信息论的理论基础。此后，在基本理论和实际应用方面，信息论都得到了巨大的发展。第2章离散信源及其信息测度2.1信源的数学模型及分类2.2离散信源的信息熵2.3信息熵的基本性质2.5离散无记忆的扩展信源2.6离散平稳信源2.7马尔可夫信源2.8信源剩余度与自然语言的熵20信源产生消息或消息序列的源。消息携带信息，是信息的具体形式。描述方法通信过程中，信源发出何种消息是不确定的、是随机的。因此，信源可用随机变量、随机矢量或随机过程（或样本空间及其概率测度）来描述。不同的信源根据其输出消息的不同的随机性质进行分类。2.1信源的数学模型及分类211、随机变量描述的信源（单符号）特点：输出单符号消息。符号集的取值A:{a1,a2,…,aq}是有限的或可数的,可用离散型随机变量X描述。数学模型：设每个信源符号ai出现的(先验)概率p(ai)(i=1,2,…,q)满足：)(......)()()(......)(则321321qqaPaPaPaPaaaaxPX：1)(1qiiap概率空间能表征离散信源的统计特性，因此也称概率空间为信源空间。1）离散信源221）平稳信源特点:信源输出的消息由一符号序列所组成。可用N维随机矢量X＝(X1,X2,…,XN)描述，且随机矢量X的各维概率分布都与时间起点无关。离散平稳信源：每个随机变量Xi(i＝1,2,…,N)是取值离散的随机变量。连续平稳信源：每个随机变量Xi(i＝1,2,…,N)是取值连续的随机变量。2、随机矢量描述的信源232）离散无记忆平稳信源离散平稳信源的特例，信源发出的符号都相互统计独立，即各随机变量Xi(i＝1,2,…,N)之间统计独立。性质：独立－P(X)=P(X1,X2,…,XN)=P1(X1)·P2(X2)···PN(XN)平稳－P1(Xi)=P2(Xi)=···=PN(Xi)=P(Xi)（下标1-N为时间标志）NiiNXPXXXPP121)()()(X),...,2,1(,)(),...,()(121qiaPaaaPPkNkikiNiiixN维随机矢量的一个取值，i＝(ai1ai2…aiN)P(aik)是符号集A的一维概率分布若各随机变量Xi取值同样符号集A:{a1,a2,…,aq}，则24信源X的各输出Xi间统计独立、且取值同一符号集A。该信源输出的N维随机矢量X为离散无记忆信源X的N次扩展信源。此扩展信源取值为符号集i＝(ai1ai2…aiN),其中(i1,i2,…,iN=1,2,…,q)，其数学模型是X信源空间的N重空间：)(...)()(...)(2121NNqqiNPPPPX)(......)()()(......)(321321qqaPaPaPaPaaaaxPX),...,2,1(,)()(其中1qiaPPkNkiik，3）离散无记忆信源的N次扩展信源若X为离散无记忆信源：254）有记忆信源信源在不同时刻发出的符号之间是相互依赖的，即信源输出的随机序列X中，各随机变量Xi之间相互依赖。须使用随机矢量的联合概率分布和条件概率分布来说明它们之间的关联关系。例：汉字组成的中文序列中，只有根据中文的语法、习惯用语、修辞制约和表达实际意义的制约所构成的中文序列才是有意义的中文句子或文章。所以，在汉字序列中前后文字的出现是有依赖的，是彼此相关的。265）m阶马尔可夫信源（非平稳信源）不同时刻发出的符号间的依赖关系),,2,1()|()|(2112112NixxxxPxxxxxxxPmiiiimiiiiii记忆信源的记忆长度为m+1时，称这种有记忆信源为m阶马尔可夫信源。若上述条件概率与时间起点i无关，信源输出的符号序列可看成为时齐马尔可夫链，则此信源称为时齐马尔可夫信源。272.2离散信源的信息熵基本的离散信源：输出单符号消息，且这些消息间两两互不相容。用一维随机变量X来描述信源的输出，其数学模型可抽象为:)(......)()()(......)(321321qqaPaPaPaPaaaaxPX1)(1qiiaP问题：这样的信源能输出多少信息?每个消息的出现携带多少信息量?28信息的度量要点：信息的度量（信息量）和不确定性消除的程度有关，消除的不确定性＝获得的信息量；不确定性就是随机性，可以用概率论和随机过程来测度；推论：概率小－信息量大，即信息量是概率的单调递减函数；信息量应该具有可加性；信息量的计算公式为（香农（自）信息量的度量）：)(log)(1log)(krkrkaPaPaI292.1.1自信息设离散信源X的概率空间为：)(log)(1log)]([)(iririiaPaPaPfaII(ai)代表两种含义：（1）当事件ai发生以前，表示事件ai发生的不确定性（2）当事件ai发生以后，表示事件ai所提供的信息量)(......)()()(......)(321321qqaPaPaPaPaaaaxPX1)(1qiiaP自信息量：事件ai发生所含有的信息量30度量单位计算自信息量时要注意有关事件发生概率的计算；自信息量的单位取决于对数的底；底为2，单位为“比特（bit,binaryunit）”；底为e，单位为“奈特（nat,natureunit）”；底为10，单位为“哈特（hat,Hartley）”；根据换底公式得：aXXbbalogloglog一般计算都采用以“2”为底的对数，为了书写简洁，常把底数“2”略去不写1nat=1.44bit,1hat=3.32bit；31收信者收到某消息获得的信息量＝不确定性减少的量＝(收到此消息前关于某事件的不确定性)-(收到此消息后关于某事件的不确定性)通信的实质？即：传递信息，消除不确定性。322.2.2信息熵对一个信源发出不同消息所含有的信息量也不同。所以自信息I(ai)是一个随机变量，不能用它来作为整个信源的信息测度。信息熵：自信息的数学期望，平均自信息量Hr(X)：qiiriirrapapapEXH1)(log)()(1log)(qiiiiapapapEXH1)(log)()(1log)(当r＝2时：rXHXHrlog/)()(r进制单位/符号33熵的含义熵是从整个集合的统计特性来考虑的，它从平均意义上来表征信源的总体特征。信源输出前，熵H(X)表示信源的平均不确定性；信源输出后，熵H(X)表示每个消息的平均信息量；信息熵H(X)表征了变量X的随机性。34信息熵是信源概率空间的一种特殊函数。这个函数的取值大小，与信源的符号数及其概率分布有关。用概率矢量P来表示概率分布P(x)：3.3信息熵的基本性质则信息熵H(X)是概率矢量P或它的分量p1，p2，…，pq的q-1元函数(独立变量只有q-1元)。则H(X)可写成：),,,())(,),(),((2121qqpppaPaPaPP),,2,1(0,11qippiqiiiqiiiqiippaPaPXH11log)(log)()()(),,,(21PHpppHq35熵函数的向量形式H(P)是概率矢量P的函数，称为熵函数。我们用下述表示方法：用H(x)表示以离散随机变量x描述的信源的信息熵；用H(P)或H(p1