信息论.doc

第一章 概论1. 信息、消息、信号的定义及关系。定义信息：事物运动状态或存在方式的不确定性的描述。消息：指包含有信息的语言、文字和图像等。信号：表示消息的物理量，一般指随时间而变化的电压或电流称为电信号。关系信息和消息 信息不等于消息。消息中包含信息，是信息的载体。 同一信息可以用不同形式的消息来载荷。 同一个消息可以含有不同的信息量。信息和信号 信号是消息的载体，消息则是信号的具体内容。 信号携带信息，但不是信息本身。 同一信息可用不同的信号来表示，同一信号也可表示不同的信息。2. 通信系统模型，箭头上是什么？通信的目的及方法。通信的目的：是为了提高通信的可靠性和有效性。信源编码：提高信息传输的有效性。（减小冗余度）信道编码：提高信息传输的可靠性。（增大冗余度）第二章 信源及其信息量信源发出的是消息。信源分类1、信源按照发出的消息在时间上和幅度上的分布情况可将信源分成离散信源和连续信源。2、根据各维随机变量的概率分布是否随时间的推移而变化将信源分为平稳信源和非平稳信源。 单符号离散信源 离散无记忆信源 无记忆扩展信源离散平稳信源 离散有记忆信源 记忆长度无限 记忆长度有限（马尔可夫信源） 一、单符号离散信源单符号离散信源的数学模型为自信息量定义：一个随机事件发生某一结果后所带来的信息量为自信息量。定义为其发生概率对数的负值。以 奇才单位： 对数以2为底，单位为比特 (bit) （binary unit） 对数以e为底，单位为奈特 (nat) (nature unit) 对数以10为底，单位为笛特(det) (decimal unit) 或哈特 (hart) 物理含义： 在事件xi发生以前，等于事件xi发生的不确定性的大小； 在事件xi发生以后，表示事件xi所含有或所能提供的信息量。 性质:I(xi)是非负值.当p(xi)=1时，I(xi)=0.当p(xi)=0时，I(xi)=.I(xi) 是p(xi)的单调递减函数.联合自信息量 条件自信息量 自信息量、条件自信息量和联合自信息量之间有如下关系式： I(xi yj)= I(xi)+ I(yj / xi) = I(yj)+ I(xi / yj) 信息熵定义：各离散消息自信息量的数学期望，即信源的平均信息量.单位：比特/符号物理含义： 信源熵H(X)表示信源输出后，离散消息所提供的平均信息量. 信源熵H(X)表示信源输出前，信源的平均不确定度. 信源熵H(X)反映了变量X的随机性.信源符号的概率分布越均匀，则平均信息量越大; 确定事件，不含有信息量。 性质: 非负性 H(X) 0 对称性 当变量 p(x1),p(x2),p(xn) 的顺序任意互换时，熵函数的值不变. 最大离散熵定理:信源中包含n个不同离散消息时，信源熵H(X)有 确定性 可加性 (会证明) 证明： 香农辅助定理和极值性(会证明) 对于任意两个消息数相同的信源X和Y，i=1,2,n,有含义：任一概率分布对其他概率分布的自信息量取数学期望，必大于等于本身的熵。 由上式可证明条件熵小于等于无条件熵，即H(X/Y)H(X)证明：互信息量互信息为一个事件yj所给出关于另一个事件xi的信息，用I(xi; yj)表示，定义为xi的后验概率与先验概率比值的对数，即同理，可以定义xi对yj的互信息量为平均互信息量定义: Y对X的平均互信息量I(X;Y)单位: bit/符号物理意义: I(X;Y)=H(X)-H(X/Y) 平均互信息量是收到Y前后关于X的不确定度减少的量，即由Y获得的关于X的平均信息量。 I(Y;X)=H(Y)-H(Y/X)平均互信息量是发送X前后，关于Y的平均不确定度减少的量。 平均互信息量等于通信前后，整个系统不确定度减少的量。性质： 对称性 非负性 极值性 （会证明） 证明：由于根据H(X/Y)定义式，得H(X/Y)0，同理H(Y/X)0，而I(X;Y)，H(X)，H(Y)，是非负的，又I(X;Y)=H(X)-H(X/Y)=H(Y)-H(Y/X)，所以I(X;Y)H(X)，I(X;Y)H(Y)。当随机变量X和Y是确定的意义对应关系时，即平均互信息量取得最大值。 凸函数性 当条件概率分布p(yj/xi)给定（信道固定）时，I(X;Y)是输入信源概率分布p(xi)的严格上凸函数。 对于固定的输入分布p(xi)（信源固定），I(X;Y)是条件概率分布p(yj/xi)的严格下凸函数。 数据处理定理 （了解思想）模型X Y数据处理后会损失一部分信息，最多保持原来的信息各种熵之间的关系二、扩展信源无记忆扩展信源定义：每次发出一组含两个以上符号的符号序列代表一个消息，而且所发出的各个符号是相互独立的，各个符号的出现概率是它自身先验概率。序列中符号组的长度即为扩展次数。 例：单符号信源如下,求二次扩展信源熵 解：扩展信源：N次扩展信源的熵：H(XN)= NH(X)离散平稳信源 定义：各维联合概率均与时间起点无关的完全平稳信源。N维离散平稳有记忆信源的熵：平均符号熵： 极限熵：马尔可夫信源定义：在实际问题中，试图限制记忆长度，就是说任何时刻信源发出符号的概率只与前面已经发出的m个符号有关，而与更前面发出的符号无关，即马尔可夫信源。 在任何时刻l，符号发出的概率只与前面m个符号有关，把m个符号看做信源在l时刻的状态。因为原始信源符号集共有n个符号，则有记忆信源可以有nm个不同的状态，分别对应于nm个长度为m的序列。这时，信源输出依赖长度为m+1的随机序列就转化为对应的状态序列，而这种状态序列符合马尔可夫链的性质，称为m阶马尔可夫信源。n信源符号集 nm信源不同的状态数 m+1信源输出依赖长度；例：设一个二元一阶马尔可夫信源，信源符号集为X=0,1，信源输出符号的条件概率为p(0/0)=0.25，p(0/1)=0.50，p(1/0)=0.75，p(0/1)=0.50，求状态转移概率。 解：由于信源符号数n=2，因此二进制一阶信源仅有2个状态：s1=0，s2=1。由条件概率求得信源状态转移概率为p(s1/s1)=0.25，p(s1/s2)=0.50，p(s2/s1)=0.75，p(s2/s2)=0.50熵：例: 二阶马尔可夫信源00 01 10 11，求状态转移概率和极限熵。 p(e1/e1)= p(x1/e1)=p(0/00)=0.8 p(e2/e1)= p(x2/e1)=p(1/00)=0.2 p(e3/e2)= p(x1/e2)=p(0/01)=0.5 p(e4/e2)= p(x2/e2)=p(1/01)=0.5 p(e1/e3)= p(x1/e3)=p(0/10)=0.5 p(e2/e3)= p(x2/e3)=p(1/10)=0.5 p(e3/e4)= p(x1/e4)=p(0/11)=0.2 p(e4/e4)= p(x2/e4)=p(1/11)=0.8 求出稳定状态下的 p(ej),称为状态极限概率. 将一步转移概率代入上式得:p(e1)=0.8 p(e1)+0.5 p(e3) p(e3)=0.5 p(e2)+0.2 p(e4)p(e2)=0.2 p(e1)+0.5 p(e3) p(e4)=0.5 p(e2)+0.8 p(e4) 解方程组得：p(e1)= p(e4)=5/14p(e2)= p(e3)=2/14 计算极限熵：信源冗余度信息熵的相对率：信源的冗余度：三、连续信源数学模型： 并满足几种特殊连续信源的熵 均匀分布的连续信源的熵： h(X)=log(b-a) 高斯分布的连续信源的熵: m为均值，结论：高斯信源的熵仅与方差有关。 指数分布的连续信源的熵： 连续熵的性质 连续信源熵可为负值. 可加性 非负性 对称性三个最大熵定理1.幅度受限条件下的最大熵定理：当信源输出信号的概率密度分布是均匀分布时，信源具有最大熵，其值为h(X)=log(b-a)。 2.平均功率受限条件下的最大熵定理： 当信源输出信号的概率密度分布为高斯分布时，信息具有最大熵，其值为 h(X)3.均值受限条件下的最大熵定理：指数分布的连续信源具有最大熵：四、香农第一定理（无失真变长编码定理）对离散无记忆信源，消息长度为N，符号熵为H(X),对信源进行r元变长编码，一定存在无失真的信源编码方法，其码字平均长度满足：其码字平均信息率满足：第三章 信道及其容量 信道的输入输出都是信号 容量：平均互信息量的最大值。一、 信道模型信道的数学模型：X P(Y/X) YP(Y/X)XY二、 离散无记忆信道单符号离散信道的数学模型：p(yj/xi)XY信道转移概率矩阵：n行m列信道容量定义 ：最大的信息传输率，用C表示。C的单位：比特/信道符号单位时间的信道容量Ct为：Ct的单位：比特/秒几种特殊离散信道的容量1.一 一对应的无噪无损信道(一对一) CmaxI(X;Y)log n2.具有扩展性能的无损有噪信道(一对多) C = max H(X) = log n3.具有归并性能的无噪有损信道（多对一）C = max H(Y) = log m4.离散对称信道的信道容量矩阵中的每行都 是集合P = p1, p2, , pn中的诸元素的不同排列，称矩阵的行是可排列的。矩阵中的每行都 是集合P = p1, p2, , pn中的诸元素的不同排列，称矩阵的行是可排列的。如果矩阵的行和列都是可排列的，称矩阵是可排列的。如果一个信道矩阵具有可排列性，则它所表示的信道称为对称信道。练习：判断下列矩阵表示的信道是否是对称信道错误错误（p(xi)=1/n）5. 准对称信道若信道矩阵的行是可排列的，但列不可排列，如果把列分成若干个不相交的子集，且由n行和各子集的诸列构成的各个子矩阵都是可排列的，则称相应的信道为准对称信道。三、 离散无记忆扩展信道1YNYN次扩展信道的容量 CN=NC四、 连续信道香农公式(bit/s)例：在电话信道中常允许多路复用。一般电话信号的带宽为3.3kHz。若信噪功率比为20dB，求电话通信的信道容量。五、 信道编码定理香农第二定理：若一离散平稳无记忆信道，其容量为C，输入序列长度为L，只要待传送的信息率RC,任何编码的Pe必大于0，当。第四章 信息率失真函数 理论依据：平均互信息量是信道转移概率的下凸函数失真度定义：对任意，指定一个非负数 定义为单个符号的失真度或失真函数。失真矩阵：平均失真度定义：失真函数的数学期望称为平均失真度，记为 保真度准则 （D为允许平均失真度）信息率失真函数定义：平均失真由信源分布p(xi)、信道的转移概率p(yj/xi)和失真函数d(xi，yj)决定，若p(xi)和d(xi，yj)已定，则调整p(yj/xi) 使D失真许可的试验信道在上述允许信道PD中，可以寻找一种信道pij，使给定的信源p(xi)经过此信道传输后，互信息I(X；Y)达到最小。该最小的互信息就称为信息率失真函数R(D)，即 信息率失真函数的性质:定义域：最小值DH(X)R(D)当失真矩阵的每一行至少有一个零元素时，信源的平均失真度为零。时，R(0)=H(X)。最大值当R(D)=0时，对应的平均失真最大。下凸性连续和单调递减性信道容量与信息率失真函数的对偶关系：CR(D)I(X;Y)的上凸函数I(X;Y)的下凸函数 I(X;Y)的极大值 I(X;Y)的条件极小值 的函数 的函数仅与信道特性有关仅与信源特性有关解决可靠性问题解决有效性问题信息传输的基础信源压缩的基础保真度准则下的信源编码定理：对于任意允许平均失真度D0和任意小的R(D),只要信源序列长度L足够长，一定存在一种编码方式C，使译码后的平均失真度反之，若RR(D),则无论用什么编码方式，必有 第六章 信源编码1. 在通信系统模块中的位置，及输入输出是什么。（第一章）2. 信源编码的目的及方法。（第一章）3. 无失真信源编码定理。（第二章）4. 变长编码方法：香农编码、费诺编码、霍夫曼编码。（例题）第七章 信道编码的基本概念编码信道模型：信道译码 编码信道 信道编码 接收向量R码字通信系统的主要技术指标:1. 传输速率1) 码元传输速率rs ：每秒钟通过信道传输的码元数。单位：波特2) 比特传输速率rb ：每秒钟通过信道传输的信息量。 单位：比特/秒 对于M进制来说， rb=rslog2M 2. 差错率1) 码元差错率 ：指在传输的码元总数中发生差错的码元数所占的比例. 2) 比特差错率：指在传输的比特总数中发生差错的比特数所占的比例.3. 可靠性检错与纠错原理：检纠错的目的：要从信道的输出信号序列R来判断是否可能是发送的C或纠正导致R不等于C的错误。信道编码效率R R=k/n 其中k为消息m的长度， n为信号码字c的序列长度。定理：若纠错码的最小距离为dmin ，有如下三个结论：(1) 可以检测出任意小于等于l=dmin 1个差错。(2) 可以纠正任意小于等于t=(dmin 1)/2个差错。(3) 可以检测出任意小于等于l同时纠正小于等于t个差错，其中l和t满足 l+tdmin-1 tk），由2k个信息码组所编成的2k个码字集合称为线性分组码。2n：码组总数 2k：可用码组的数监督矩阵一致校验矩阵H r行n列矩阵 cHT=0 H的标准形式 生成矩阵k行n列矩阵对于二进制编码，G是二元矩阵, G的k个行矢量是线性无关的。系统形式编码 m为消息向量，即任意k维向量，生成矩阵为G，码字c为 c=mG 系统码：编码时，信息组m乘以系统形式的G所得的码字，这样生成的(n,k)码叫系统码。 生成矩阵G的每一行也是一个码字。译码1、伴随式(1) 定义：伴随式是一个r（n-k)维向量 s=rHT =(c+e) HT =cHT +eHT = eHT 如果收码无误，则s=0；如果信道中产生差错，则s不等于0。(2) 特性： 在HT固定的前提下，伴随式s仅与差错图案e有关，而与发送的具体码字无关。 伴随式是错误的判别式，即只能判别收码是否发生错误。汉明码(1) 纠错能力t=1，最小码距为dmin =3(2) 码长n和信息位k服从以下规律 当m=3时为(7,4)汉明码，当m=4时为(15,11)汉明码。(3) 汉明码是完备码。例：已知 (7,4) 码的生成矩阵为 写出所有许用码组，并求监督矩阵。若接收码组为1101101，计算伴随式。 例：设一分组码具有一致校验矩阵(1)求这分组码n=?k=?，共有多少个码字？ (2)此分组码的生成矩阵。 (3)矢量101010是否是码字。例：设一分组码具有一致校验矩阵试求生成矩阵。当输入序列为110101101010时，求编码器编出的码序列。 第九章 循环码循环码的生成多项式（1）定理：(n,k)循环码中存在唯一的一个非零的、首一的和最低次为r的码多项式g(x)=xr+gr-1xr-1+g1x+g0 其中r=n-k 使得所有码多项式都是g(x)的倍式即C(x)=m(x)g(x),且所有小于n次的g(x)的倍式都是码多项式。 （2）定义：g(x)称为(n,k)循环码的生成多项式。(3)定理：(n,k)循环码的生成多项式g(x)一定是(xn+1)的因子即(xn+1)=g(x)h(x)。相反，如果g(x)是(xn+1)的(n-k)次因子，则g(x)一定是(n,k)循环码的生成多项式。(4) 构造(n,k)循环码的步骤：对(xn+1)作因式分解，找出其(n-k)次因式。以该(n-k)次因式为生成多项式g(x)，与不高于(k-1)次的信息多项式m(x)相乘，即得码多项式c(x)=m(x)g(x)。例：构造一个长度n=7的循环码。 因式分解：x7+1=(x+1)(x3+x2+1)(x3+x+1) 现要得到(7,4)循环码。选x3+x2+1为例。 设信息多项式为m=(m3m2m1m0)=(0110)m(x)= m3x3+ m2x2+ m1x+ m0=x2+x码多项式是c(x)=m(x)g(x)= x5+x3+x2+x对应码字为 （0101110）生成矩阵G循环码的校验多项式h(x) h(x)= (xn+1)/g(x)校验矩阵系统循环码1、系统循环码的生成 将消息多项式m(x)乘以xn-k 将xn-km(x)除以g(x)得到余式p(x) 将p(x)加在x