第1章信息论基础

1、第第1章章 信息论基础信息论基础 第第1章章 信信息息论论基基础础 内容提要信息论是应用近代概率统计方法研究信息传输、交换、存储和处理的一门学科，也是源于通信实践发展起来的一门新兴应用科学。本章首先引出信息的概念，简述信息传输系统模型的各个组成部分，进而讨论离散信源和离散信道的数学模型，简单介绍几种常见的离散信源和离散信道。1.1 1.1 信息的概念信息的概念消息是能被人们感觉器官感知的客观物质和主观思维的运动状态或存在状态。物质、能量和信息是构成客观世界的三大要素。信息是物质和能量在空间和时间上分布的不均匀程度，或者说信息是关于事物运动的状态和规律。信息论信息论是研究信息的基本性质及度量方法

2、，研究信息的获取、传输、存储和处理的一般规律的科学。 通信系统中形式上传输的是消息，实质上传输的是信息，消息中包含信息，消息是信息的载体。对于信息论的研究，一般划分为三个不同的范畴： 广义信息论，包括信息论在自然和社会中的新的应用，如模式识别、机器翻译、自学习自组织系统、心理学、生物学、经济学、社会学等一切与信息问题有关的领域。 实用信息论，研究信息传输和处理问题，也就是狭义信息论方法在调制解调、编码译码以及检测理论等领域的应用。 狭义信息论，即通信的数学理论，主要研究狭义信息的度量方法，研究各种信源、信道的描述和信源、信道的编码定理。1.2 1.2 信息传输系统信息传输系统 通信的基本问题是

3、在彼时彼地精确地或近似地再现此时此地发出的消息。 各种通信系统，一般可概括为图1.1所示的统计模型： 干扰干扰源源 信道信道信道译码器信道译码器信道编码器信道编码器信源译码器信源译码器信源编码器信源编码器信宿信宿信源信源等效信源等效信宿等效无干扰信道图图1-1 信息传输系统模型信息传输系统模型 这个模型包括以下五个部分：3. 信道信道 信道是信息传输和存储的媒介。4. 译码器译码器 译码是编码的逆变换，分为信道译码和信源译码。5. 信宿信宿 信宿是消息的接收者。1.信源信源 信源是产生消息的源。2. 编码器编码器 编码器是将消息变成适合于信道传送的信号的设备。编码器信源编码器，提高传输效率信道

4、编码器，提高传输可靠性1.31.3 离散信源及其数学模型离散信源及其数学模型 信源是产生消息的源，根据x的不同情况，信源可分为以下类型： 根据信源的统计特性，离散信源又分为两种：离散信源离散信源 消息集x为离散集合。波形信源波形信源 时间和空间都连续的信源。连续信连续信源源 时间离散而空间连续的信源。无记忆信源无记忆信源 x的各时刻取值相互独立。有记忆信源有记忆信源 x的各时刻取值互相有关联。1.3.1 离散无记忆信源离散无记忆信源 离散无记忆信源离散无记忆信源(discrete memoryless source，简记为dms)输出的是单个符号的消息，不同时刻发出的符号之间彼此统计独立，而且

5、符号集中的符号数目是有限的或可数的。离散无记忆信源的数学模型为离散型的概率空间，即： )()()()(2211kkxqxxqxxqxxqxq(xi )：信源输出符号消息xi的先验概率； 满足：0 q(xi) 1，1 i k kiixq11)(1.3.2 离散无记忆的扩展信源离散无记忆的扩展信源 实际情况下，信源输出的消息往往不是单个符号，而是由许多不同时刻发出的符号所组成的符号序列。设序列由n个符号组成，若这n个符号取自同一符号集 a1 , a2 , , ak，并且先后发出的符号彼此间统计独立，我们将这样的信源称作离散无记忆的离散无记忆的n维扩展信源维扩展信源。其数学模型为n维概率空间： )(

6、)()()(2211mqqqqx xx xx xx xx xx xx xx xmx为各种长为n的符号序列，x = x1 x2 xn ，xi a1 , a2 , , ak ，1 i n，序列集x = a1a1 a1 , a1a1 a2 , , akak ak ，共有m=kn种序列，x x。 序列的概率q (x) = q (x1x2 xn) = niixq1)(1.3.3 离散平稳有记忆信源离散平稳有记忆信源 中、英文句子中前后出现的汉字、字母往往是有依赖的。这种依赖性我们称作有记忆。用联合概率空间x , q (x )来描述离散有记忆信源的输出。信源在i时刻发出什么符号与i时刻以前信源所发出的符号

7、有关，即由条件概率p (xixi-1 xi-2 )确定。如果该条件概率分布与时间起点无关，只与关联长度有关，则该信源为平稳信源平稳信源。对于离散平稳有记忆信源，有：p (x1 = a1) = p (x2 = a1) = p (x2 = a2x1 = a1) = p (x3 = a2x2 = a1) = p (x3x2 x1) = p (x4x3 x2) = p (xi+lxi+l-1 xi+l-2 xi) = p (xj+lxj+l-1 xj+l-2 xj) = 随机事件集xx1，x2，xi，xi，yy1，y2，yj，yj，1ii，1jj，将x，y中的随机事件xi，yj出现的概率记为p(xi)

8、，p(yj)称为先验概率先验概率/无条件概率无条件概率。在xy二维空间上，将两个事件xiyj同时出现的概率记为p(xiyj)称为联合概率联合概率。将x发生xi后，y又发生yj的概率记为p(yj|xi)，将y发生yj后，x又发生xi的概率记为p(xi |yj)称为条件概率条件概率。 复习概率论基础知识复习概率论基础知识无条件概率、条件概率和联合概率应满足的一些性质及关系无条件概率、条件概率和联合概率应满足的一些性质及关系1)()|()|()()(0jijiijjiyxpyxpxypypxpjjjijjjjiiiiijijiiijyxpypyxpxpxypxpyxpyp1111)()()()()(

9、)()()()()()()()(jijijijiyxpypxypxpyxp)()()()()()()(jijiijijijypxpyxpxpyxpypxypiijijijijjjijiijyxpyxpyxpyxpyxpxyp11)()()()()()(x与y相互独立时： iijjjiiijijjijjjjiiiyxpyxpxypypxp1111111)(1)|(1)|(1)(1)(【例】例】系里有教师100人，其中男教师占40%，女教师占60%，老、中、青年龄段的教师分别是10人、20人和70人。男教师中老、中、青分别占20%、30%和50%，女教师中老、中、青分别为2人(占1/30)、8人(

10、占4/30)和50人(占5/6)。老教师中80%是男性，20%是女性；中年教师中60%是男性，40%是女性；青年教师中2/7是男性，5/7是女性。 设：“教师性别”为x事件集，“教师年龄”为y事件集。则：事件集xx1，x2，事件x1表示男教师，x2表示女教师； 事件集yy1，y2，y3， 事件y1表示老年教师，y2表示中年教师，y3表示青年教师。 2) 条件概率： p(y1|x1)20%0.2 p(y2|x1)30%0.3 p(y3|x1)50%0.5p(y1|x2)1/30 p(y2|x2)4/30 p(y3|x2)5/6p(x1|y1)80%0.8 p(x2|y1)20%0.2p(x1|y

11、2)60%0.6 p(x2|y2)40%0.4p(x1|y3)2/7 p(x2|y3)5/7 根据题意根据题意1. 各事件的概率1) 先验概率/无条件概率： p(x1)40%0.4 p(x2)60%0.6p(y1)10/1000.1 p(y2)20/1000.2 p(y3)70/100.7“女性老年教师” p(x2y1)p(x2)p(y1|x2)0.61/300.02 p(y1)p(x2 |y1)0.10.20.02 “女性中年教师” p(x2y2)p(x2)p(y2|x2)0.64/300.08 p(y2)p(x2 |y2)0.20.40.08 “女性青年教师” p(x2y3)p(x2)p(

12、y3|x2)0.65/60.5 p(y3)p(x2 |y3)0.75/70.5 2. xy二维空间的联合概率 “男性老年教师” p(x1y1)p(x1)p(y1|x1)0.40.20.08 p(y1)p(x1 |y1)0.10.80.08 “男性中年教师” p(x1y2)p(x1)p(y2|x1)0.40.30.12 p(y2)p(x1 |y2)0.20.60.12 “男性青年教师” p(x1y3)p(x1)p(y3|x1)0.40.50.2 p(y3)p(x1 |y3)0.72/70.23. 验证概率的归一性(i=1, 2 j=1, 2, 3) 1)()()(2121ixpxpxpi1)()

13、()()(31321jjypypypyp1)|(jixypj3123222121312113111)|()|()|()|(1)|()|()|()|(jjjjxypxypxypxypxypxypxypxyp1)|(ijyxpi1)|()|()|(1)|()|()|(1)|()|()|(323121322212122112111yxpyxpyxpyxpyxpyxpyxpyxpyxpiiiiii1)()()()()()()(3222123121112131iyxpyxpyxpyxpyxpyxpyxpijjjjiyxpxp)()(i)()()()()()()()()()(322212312231312

14、11111yxpyxpyxpyxpxpyxpyxpyxpyxpxpjjjjijijyxpyp)()()()()()()()()()()()()()(323121332221212212112111yxpyxpyxpypyxpyxpyxpypyxpyxpyxpypiiiiii4. 无条件概率与联合概率的关系(i=1, 2 j=1, 2, 3) * 1.3.4 马尔可夫信源马尔可夫信源 离散有记忆信源，r时刻发出的符号xr与前m个时刻发出的符号xr-1 ，xr-2 ，xr-m （称做m 阶）有关，可用m阶状态描述。r时刻状态er=xr-1xr-2 xr-m=si，其中，xi a1 , a2 , ,

15、 ak , sis1, s2, skm 。信源发出符号xr后，(r1)时刻状态er+1= xr xr-1 xr-m+1=sj信源状态信源状态 er=si= xr-1 xr-2 xr-mx xr rx xr-mr-mx xr-2r-2x xr-1r-1信源信源当状态转移概率和已知状态下发符号的概率与时刻无关，即p(er1=sjer=si)=p(sjsi)和p(xr=aler=si)p(alsi )时，称为时齐的/齐次的。 状态转移概率和已知状态下发符号的概率为p(er1=sjer=si)和p(xr=aler=si)。齐次时（与时间无关）状态转移图：s1s2sisi1skm1skm马尔可夫信源输出

16、的消息序列与信源的状态满足下列条件： (1)某一时刻信源的输出只与当时的信源状态有关，而与以前的状态无关。p (xr = al er = si , er-1 = st , er-2 = sn , ) = p (xr = al er = si)，满足 。klirlrseaxp11)(2)某一时刻信源所处的状态只由当前的输出符号和前一时刻的状态唯一决定。当时齐马尔可夫信源达到平稳分布时，满足 10p (er+1 = sj xr = al , er = si) =iittitispsspspsp1)(0)()()(由于信源符号数为2，因此二进制一阶信源仅2个状态：s1=0，s2=1。由条件概率求得信

17、源状态转移概率和信源状态转移图：【例】设有一个二进制一阶马尔可夫信源，其信源符号集为 x0，1，条件概率为： p(00)0.25, p(01)0.50, p(10)0.75, p(11)0.50平稳后各状态的概率分布：p(s1)1/4p(s1)+1/2p(s2)p(s2)3/4p(s1)+1/2p(s2)p(s1)+p(s2)1p p( (s1)=2/5=0.4 )=2/5=0.4 p p( (s2)=3/5=0.6)=3/5=0.6 s1s200.510.7500.2510.5p(s1s1)0.25, p(s1s2)0.5, p(s2s1)0.75, p(s2s2)0.5【例】设有一个二进制

18、二阶马尔可夫信源，其信源符号集为0，1，条件概率为： p(000)p(111)0.8, p(100)p(011)0.2， p(001)p(010)p(101)p(110)0.50。这个信源的符号数为2，故共有224个可能状态： s1=00， s2=01， s3=10， s4=11。由条件概率求得信源状态转移概率和信源状态转移图： p(s1s1)p(s4s4)0.8,p(s2s1)p(s3s4)0.2, p(s3s2)p(s1s3)p(s4s2)p(s2s3)0.50 s2s310.510.200.800.5s4s110.800.510.500.21.4 1.4 离散信道及其数学模型离散信道及其

19、数学模型 信道是信息传输的通道，如图1-3，信道可看作一个变换器，它将输入消息x变换成输出消息y，以信道转移概率p (yx )来描述信道的统计特性。 信道信道p ( y y x x)xy图1-3 信道模型 无记忆信无记忆信道道 输出y只与当前时刻的输入x有关。 有记忆信有记忆信道道 输出y不仅与当前时刻的输入x有关，还与以前的输入有统计关系。 信道可以按不同的特性进行分类，根据输入和输出信号的特点可分为：波形信道波形信道 信道的输入和输出都是时间上连续，并且取值也连续的随机信号。 半连续信道半连续信道 输入序列和输出序列一个是离散的，而另一个是连续的。连续信道连续信道 信道的输入和输出都是时间

20、上离散、取值连续的随机序列，又称为模拟信道离散信道离散信道 信道的输入和输出都是时间上离散、取值离散的随机序列。离散信道有时也称为数字信道。根据统计特性，即转移概率p (yx )的不同，信道又可分类为： 输入符号集x xx1，x2，xi，xi ，输入符号xi a1 , a2 , , ak ，1ii；输出符号集y yy1，y2，yj，yj ，输出符号yj b1 , b2 , , bd ，1j j；输入符号xi的概率记为q(xi)称为先验概率先验概率，输出符号yj的概率记为w(yj)；输入符号为xi输出符号为yj时的概率记为p(yj|xi)称为信道转移概率信道转移概率，输出符号为yj估计输入符号是

21、xi的概率记为(xi|yj)称为后验概率后验概率；在输入输出xyxy二维联合空间上，xiyj的联合概率联合概率记为p(xiyj)q(xi)p(yj|xi)w(yj)(xi|yj)。 通信中常用的概率函数讨论通信中常用的概率函数讨论 先验概率、信道转移概率、后验概率和联合概率先验概率、信道转移概率、后验概率和联合概率应满足的一些性质及关系应满足的一些性质及关系 iijjjiiijijjijjjjiiiyxpyxxypywxq1111111)(1)|(1)|(1)(1)(jjjijjjjiiiiijijiiijyxywyxpxqxypxqyxpyw1111)()()()()()()()()()()

22、()()(jijijijiyxywxypxqyxp)()()()()()()(jijiijijijywxqyxpxqyxywxyp输入与输出相互独立时： 1)()|()|()()(0jijiijjiyxpyxxypywxq1.4.1 离散无记忆信道离散无记忆信道 离散无记忆信道的输入和输出消息都是离散无记忆的单个符号，输入符号xi a1 , a2 , , ak，1 i k，输出符号yj b1 , b2 , , bd ，1 j d，信道的特性可表示为转移概率矩阵：)()()()()()()()()(212222111211kdkkddxypxypxypxypxypxypxypxypxypp pp

23、 (yjxi )对应为已知输入符号为xi，当输出符号为yj时的信道转移概率，满足0 p (yjxi ) 1，且djijxyp11)(将信道特性表示成图1-4的形式： p (y1 x1 )x1x2y1y2xkydp (yd xk )图1-4 单符号离散无记忆信道1.二元对称信道二元对称信道(binary symmetric channel，简记为bsc)这是一种很重要的信道，它的输入符号x 0 , 1，输出符号y 0 , 1，转移概率p (yx )如图1-5所示，信道特性可表示为信道转移概率矩阵 ，其中p称作信道错误概率。pppp11p p下面列举几种常见的离散无记忆信道： 图1-5 二元对称信

24、道1-p0 p 1011-p p 图1-6 无干扰信道210011112 2. 无干扰信道无干扰信道 这是一种最理想的信道，也称作无噪信道，信道的输入和输出符号间有确定的一一对应关系，p (yx)= 如图1-6三元无干扰信道中，x , y 0 , 1 , 2 ，对应信道矩阵是单位矩阵 01yxyx100010001p p3. 二元删除信道二元删除信道 对于接收符号不能作出肯定或否定判决时，引入删除符号，表示对该符号存有疑问，作为有误或等待得到更多信息时再作判决。二元删除信道如图1-7所示，输入符号x 0 , 1，输出符号y 0 , e , 1，转移概率矩阵为pppp0110p pe图图1-7

25、二元删除信道二元删除信道 1-p0 p1011-p p 4.二元二元z信道信道 二元z信道如图1-8所示，信道输入符号x 0 , 1，输出符号y 0 , 1转移概率矩阵为 pp101p p101011-p p图图1-8 1-8 二元二元z z信道信道 1.4.2 离散无记忆的扩展信道离散无记忆的扩展信道 n维离散扩展信道的输入和输出都是长为n的消息序列，如图1-9 所示：图1-9 n维扩展信道y y = y1y2 ynx x = x1 x2 xnp ( y y x x) 信道信道若xi a1 , a2 , , ak ，yj b1 , b2 , , b d ，1 i , j n，则长为n的输入消息序列集为x = a1a1 a1 , a1a1 a2 , , akak ak ， x x，输出消息序列集为y = b1b1 b1 , b1b1 b2 , , bdbd bd ， y y。信道的特性用序列的转移概率p (yx) = p ( y1 y2yn x1 x2xn ) 描述。 当信道