信息论基础 总复习.ppt

,信息论基础总复习,信息论基础,内容提要信息论是应用近代概率统计方法研究信息传输、交换、存储和处理的一门学科，也是源于通信实践发展起来的一门新兴应用科学。本章首先引出信息的概念，简述信息传输系统模型的各个组成部分，进而讨论离散信源和离散信道的数学模型，简单介绍几种常见的离散信源和离散信道。,物质、能量和信息是构成客观世界的三大要素。信息是物质和能量在空间和时间上分布的不均匀程度，或者说信息是关于事物运动的状态和规律。,通信系统中形式上传输的是消息，实质上传输的是信息，消息中包含信息，消息是信息的载体。,信息论是研究信息的基本性质及度量方法，研究信息的获取、传输、存储和处理的一般规律的科学。,对于信息论的研究，一般划分为三个不同的范畴：,广义信息论，包括信息论在自然和社会中的新的应用，如模式识别、机器翻译、自学习自组织系统、心理学、生物学、经济学、社会学等一切与信息问题有关的领域。,实用信息论，研究信息传输和处理问题，也就是狭义信息论方法在调制解调、编码译码以及检测理论等领域的应用。,狭义信息论，即通信的数学理论，主要研究狭义信息的度量方法，研究各种信源、信道的描述和信源、信道的编码定理。,通信的基本问题是在彼时彼地精确地或近似地再现此时此地发出的消息。,各种通信系统，一般可概括为图1.1所示的统计模型：,这个模型包括以下五个部分：,3.信道信道是信息传输和存储的媒介。,4.译码器译码是编码的逆变换，分为信道译码和信源译码。,5.信宿信宿是消息的接收者。,2.编码器编码器是将消息变成适合于信道传送的信号的设备。,1.信源信源是产生消息的源。,信源是产生消息的源，根据X的不同情况，信源可分为以下类型：,根据信源的统计特性，离散信源又分为两种：,无记忆信源X的各时刻取值相互独立。,有记忆信源X的各时刻取值互相有关联。,信道是信息传输的通道，如图1-3，信道可看作一个变换器，它将输入消息x变换成输出消息y，以信道转移概率p(yx)来描述信道的统计特性。,图1-3信道模型,无记忆信道信道的输出y只与当前时刻的输入x有关。,有记忆信道信道的输出y不仅与当前时刻的输入有关，还与以前的输入有统计关系。,信道可以按不同的特性进行分类，根据输入和输出信号的特点可分为：,波形信道信道的输入和输出都是时间上连续，并且取值也连续的随机信号。,半连续信道输入序列和输出序列一个是离散的，而另一个是连续的。,连续信道信道的输入和输出都是时间上离散、取值连续的随机序列，又称为模拟信道,离散信道信道的输入和输出都是时间上离散、取值离散的随机序列。离散信道有时也称为数字信道。,根据统计特性，即转移概率p(yx)的不同，信道又可分类为：,1.4.1离散无记忆信道,离散无记忆信道的输入和输出消息都是离散无记忆的单个符号，输入符号xia1,a2,ak，1iI，输出符号yjb1,b2,bD，1jJ，信道的特性可表示为转移概率矩阵：,p(yjxi)对应为已知输入符号为xi，当输出符号为yj时的信道转移概率，满足0p(yjxi)1，且。,离散集的平均自信息量熵,熵,条件熵和联合熵,XY独立时有H(X|Y)=H(X),熵的凸性,H(P)是P的上凸函数,平均互信息量,非负性对称性,条件互信息,连续随机变量的互信息,随机变量的相对熵(微分熵),凸函数,凸集R：a，b属于R，qa+(1-q)b也属于R，其中0q1概率矢量矢量a的所有分量和为1上凸函数,凸函数的性质,f(a)是上凸的，f(a)是下凸的f1(a),fL(a)是R上的上凸函数，c1,cL是正数，c1f1(a)+cLfL(a)也是上凸函数f(a)是上凸函数，Ef(a)fE(a),E为求数学期望,香农信息论三大定理,第一极限定理:无失真信源编码定理。第二极限定理:信道编码定理(包括离散和连续信道)。第三极限定理:限失真信源编码定理。,一些基本概念,二元码定长码变长码非奇异码奇异码同价码分组码唯一可译码即时码码的前缀码树,唯一可译码定理,设原始信源符号集为S:S1,S2,Sq，码元符号集为x:x1,x2,xr，码字集合为W:W1,W2,Wq，其码长分别为L1,L2,Lq；则唯一可译码存在的充要条件为码长组合满足Kraft不等式，即式中，r是进制数，q是信源符号数，l为码字长度。,Huffman编码,例(0.20,0.19,0.18,0.17,0.15,0.10,0.01),平均码长,Shannon-Fano-Elias编码,算术码,基本概念,失真信道编码定理欲无失真，必RC，必失真失真必要性连续信源R趋向于无穷大，必有失真压缩亦有失真失真可能性终端性能有限，如人眼,人耳研究：信息率允许失真信息率失真理论,失真矩阵将所有的失真函数d(xi,yj)，i=1,2,n；j1,2,m排列起来，用矩阵表示为,说明:R（D）也称率失真函数。对于离散无记忆信源，R（D）函数可写成,图5-1-2信道模型,5.1.2信道容量,1如何刻画DMC信道的容量?考虑一个DMC信道，其输入字符集是X=x0，x1，xq-1，输出字符集是Y=y0,y1，yQ-1，转移概率P（yjxi）.若给定信道的转移概率和对应于输入符号的概率分布p（xi）,则DMC信道容量C为,如何计算信道容量?,（1）对称DMC信道的容量什么叫对称DMC信道?如果转移概率矩阵P的每一行都是第一行的置换（包含同样元素），称该矩阵是输入对称的；如果转移概率矩阵P的每一列都是第一列的置换（包含同样元素），称该矩阵是输出对称的；如果输入、输出都对称，则称该DMC为对称的DMC信道。,例如：,第六章有噪信道编码,6.1译码准则与译码错误概率,有噪声信道编码的主要目的是提高传输可靠性，增加抗干扰能力，因此也称为纠错编码或抗干扰编码。信源编码之后的码字序列抗干扰能力很脆弱，在信道噪声的影响下容易产生差错，为了提高通信系统的有效性和可靠性，要在信源编码器和信道之间加上一个信道编码器，,译码准则的含义,一个例子影响通信系统可靠性的一个重要问题是译码方式，可以通过一个例子看一下；有一个BSC信道，如图所示。,对于这样一个信道，如果采用自然的译码准则，即收0判0，收1判1；这时可以明显看到，当信源先验概率的等概时p(0)=p(1)=1/2；这时收到Y判X的后验概率等于信道转移概率，系统正确的译码概率为1/4，错误译码概率为3/4。但如果采用另一种译码准则，收0判1，收1判0；则系统正确的译码概率为3/4，错误译码概率为1/4，通信的可靠性提高了。译码准则,这时定义一个收到yj后判定为xi的单值函数，即：F(yj)=xi(i=1,2,n;j=1,2,m)；这个函数称为译码函数。它构成一个译码函数组，这些函数的值组成了译码准则。对于有n个输入，m个输出的信道来说，可以有nm个不同的译码准则。例如上面例子中有4中译码准则分别为：A:F(0)=0;F(1)=0B:F(0)=0;F(1)=1C:F(0)=1;F(1)=0D:F(0)=1;F(1)=1,译码错误概率,6.1.3最大后验概率准则,由平均错误译码概率的表达式可以看出，错误译码概率与信道输出端随机变量Y的概率分布p(yj)有关，也与译码准则有关。当信道信道转移概率p(yj/xi)确定后，而且信源统计特性p(xi)确定之后，信道输出端的p(yj)也就确定了。因为：p(xi,yj)=p(xi)p(yj/xi);而p(yj)可以由p(xi,yj)的(i=1,2,n)求和得到。因此，在这种情况下，平均错误译码概率只与译码准则有关了。通过选择译码准则可以使平均译码概率达到最小值。当式中的每一项的PF(yj)=xi/yj达到最大值时，平均错误译码概率就可以为最小值。设信源X的信源空间为：,收到每一个yj(j=1,2,m)后，推测发送为xi(i=1,2,n)的后验概率共有n个，为：p(x1/yj),p(x2/yj),p(xn/yj)。这其中必有一个为最大的，设其为：p(x*/yj)，即有：p(x*/yj)p(xi/yj)(对一切的i)这表明：收到符号yj后就译为输入符号x*，即译码函数选为：F(yj)=a*(j=1,2,m)这种译码准则称为“最大后验概率准则”。,这个表达式平均错误译码概率的最小值，是把每一个yj对应的后验概率排除后再连续求和。从表达式中可以看到，这