2.1离散信源熵

2.1离散信源熵在通信系统设计中如何实现有效性、可靠性上节回顾信息论的研究对象研究的主要问题Shannon通信系统模型•学习信息论的意义一、为工程实践提供理论指导二、为从事相关理论工作奠定基础1信息论2编码理论3密码学与网络安全上节回顾•通信过程是一种消除不确定性的过程。•Shannon信息的定义信息是事物运动状态或存在方式的不确定性的描述。2.0概率基础一维离散随机变量二维离散随机向量123123...~...KKxxxxXpppp⎛⎞⎜⎟⎝⎠{}(),,ijijPXxYypxy===121111212212221112\(,)~,1JJKJJkjkjKKKKJXYyyyxpppXYxppppxppp==⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦∑∑###其中输入输出均为离散的情况。X和Y分别表示输入与输出离散事件集。•输入空间X={xk,k=1,2,…,K},概率记为q(xk)=qk.称为先验概率•输出空间Y={yj,j=1,2,…,J},概率记为ω(yj)=ωj称为输出概率2.0概率基础2.0概率基础•联合空间XY={xkyj;k=1,2,…,K;j=1,2,…,J},概率为p(xk，yj)=pkj()11,1KJkjkjPxy===∑∑XY()()1,...,Jyyωω()()1,...,Kqxqx()|jkpyx121111212212221112\(,)~,1JJKJJkjkjKKKKJXYyyyxpppXYxppppxppp==⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦∑∑###其中2.0概率基础•边际分布•X和Y独立()()1,JkkkjjqqxPxy===∑()()1,KjjkjkyPxyωω===∑()()(),kjkjkjkjPxyqxypqωω=={k=1,2,…,K;j=1,2,…,J}概率基础•p(xk，yj)=p(xk|yj)ω(yj)=p(yj|xk)q(xk)p(xk|yj)=p(xk,yj)/ω(yj).事件xk在yj出现条件下的后验概率p(yj|xk)=p(xk,yj)/q(xk).转移概率或条件概率数学期望（均值）：∑==KkkkqxEX11JjjjEYyω==∑概率基础•全概率公式•Bayes公式()()()()11,/KKjkjjkkkkyPxyPyxqxω====∑∑()()()|,/kjkjjPxypxyyω=()()()1|/,Kjkkijipyxqxpxy==∑()()()()1|/|Kjkkjiiipyxqxpyxqx==∑2.1信源的数学模型及分类信源的分类信号取值的集合信号取值时刻的集合信源的种类离散离散数字信源（或离散信源）连续连续模拟信源（或波形信源）连续离散连续信源离散连续•不同的信源输出的消息的随机性质不同，可以根据消息的不同的随机性质来对信源进行分类：•按照某时刻信源输出消息的取值集合的离散性和连续性,信源可分为离散信源和连续信源。•按照信源输出消息的所对应的随机序列中随机变量前后之间有无依赖关系,信源可分为无记忆信源和有记忆信源。•按照信源输出消息的所对应的随机序列的平稳性,信源可分为平稳信源和非平稳信源。信源的分类•离散信源⎥⎥⎦⎤⎢⎢⎣⎡=⎥⎦⎤⎢⎣⎡)(,),(),(,,,)(2121qqaPaPaPaaaxPX1)(1)(0:1=≤≤∑=qiiiaPaP且满足•连续信源1)()(),()(=⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡∫badxxpxpbaxpX并满足注：X代表随机变量，指的是信源整体；ai代表随机事件的某一结果或信源的某个元素。注：这里的p(x)代表概率密度函数。简单信源离散信源在不同时刻发出的符号之间是无依赖的彼此统计独立的。⎥⎥⎦⎤⎢⎢⎣⎡=⎥⎦⎤⎢⎣⎡)(,),(),(,,)(qqPPPxPXαααααα2121其中，{}qiαααα,,,21∈且∑==qiiP11)(α离散无记忆信源•有记忆信源：输出的随机序列X中各随机变量之间有依赖关系，但记忆长度有限。•m阶马尔可夫信源：信源每次发出的符号只与前m个符号有关，与更前面的符号无关。•随机波形信源：信源输出的消息在时间上和取值上都是连续的。其它几种常见信源设单符号离散信源的信源空间为⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡)(,),(),(,,,)(2121nnxpxpxpxxxxPX1)(,1)(0:1=≤≤∑=niiixpxp且满足自信息量定义如果知道事件xi已发生，则该事件所含有的信息量称为自信息，定义为:)(log)(1log)(iiixpxpxI−==(1)I(xi)是非负值(2)当p(xi)=1时，I(xi)=0(3)当p(xi)=0时，I(xi)=∞(4)I(xi)是先验概率p(xi)的单调递减函数，即当p(x1)＞p(x2)时，I(x1)＜I(x2)(5)两个独立事件的联合信息量等于它们分别的信息量之和，即统计独立信源的信息量等于它们分别的信息量之和。自信息的性质I(xi)代表两种含义：（1）当事件xi发生以前，表示事件xi发生的不确定性（2）当事件xi发生以后，表示事件xi所提供的信息量一点说明•自信息量的单位取决于对数的底；–底为2，单位为“比特（bit,binaryunit）”–底为e，单位为“奈特（nat,natureunit）”–底为10，单位为“哈特（hat,Hartley）”–换底公式：aXXbbalogloglog=1nat=1.44bit,1hat=3.32bit；•二进制码元0,1,当符号概率为p(0)=1/4,p(1)=3/4,则这两个符号的自信息量为：I(0)=-log2(1/4)=log24=2bitI(1)=-log2(3/4)=0.4151bit•一个以等概率出现的二进制码元(0,1)所包含的自信息量为：自信息量例题I(0)=I(1)=-log2(1/2)=log22=1bit信源模型(涉及两个随机事件)联合自信息量111212111121,,,,,,,,()(),(),(),,()mmnnmmnmxyxyxyxyxyxyXYPXYpxypxypxypxy⎧⎫⎡⎤=⎨⎬⎢⎥⎣⎦⎩⎭)(log)(jijiyxpyxI−=•联合自信息量•在特定条件下(已定)随机事件发生所带来的信息量•定义式注：–联合自信息量和条件自信息量也满足非负和单调递减性。–关系•当X和Y独立时，jyix)/(log)/(2jijiyxpyxI−=)/()()/()(log)/()()/()(log)(22jijjijijiijijiyxIyIyxpypxyIxIxypxpyxI+=−=+=−=)()()(log)(log)(22jijijiyIxIypxpyxI+=−−=条件自信息量复习随机事件的自信息量意义：不确定性(提供的信息量)性质：非负单调减可加1()[()]loglog()()iirriiIxfPxPxPx===−复习条件自信息量联合自信量I(x)是概率空间(X,P)上的一个随机变量)/(log)/(2jijiyxpyxI−=)(log)(jijiyxpyxI−=)/()()/()(log)/()()/()(log)(22jijjijijiijijiyxIyIyxpypxyIxIxypxpyxI+=−=+=−=()()()()()123123......()()()......()()KKIxIxIxIxIxPxPxPxPxPx⎡⎤⎡⎤=⎢⎥⎢⎥⎣⎦⎣⎦二.信息熵•定义自信息的数学期望为平均自信息量Hr(X)，称为信息熵：()()K11()log()log()()rririiiHXEIxEpxpxpx=⎛⎞===−⎜⎟⎝⎠∑K11r=2()log()log()()iiiiHXEpxpxpx=⎛⎞==−⎜⎟⎝⎠∑当时：–由于这个表达式和统计物理学中热熵的表达式相似，且在概念上也有相似之处，因此借用“熵”这个词，把H(X)称为信息“熵”；–信息熵的单位由自信息量的单位决定，即取决于对数的底。HH((XX))的单位的单位：：rr进制单位／符号进制单位／符号（（r1r1））熵的计算例：有一布袋内放l00个球，其中80个球是红色的，20个球是白色的。随便摸出一个球，猜测是什么颜色，那么其概率空间为：如果被告知摸出的是红球，那么获得的信息量是如果被告知摸出的是红球，那么获得的信息量是：：I(a1)＝＝－logp(a1)＝－log0.8=0.32（（比特比特））如被告知摸出来的是白球，所获得的信息量应为如被告知摸出来的是白球，所获得的信息量应为：：I(a2)＝－logp(a2)＝－log0.2=2.32（（比特比特））⎥⎦⎤⎢⎣⎡=⎟⎟⎠⎞⎜⎜⎝⎛2.08.0)(21aaXPX平均摸取一次所能获得的信息量为平均摸取一次所能获得的信息量为：：H(X)=p(a1)I(a1)++p(a2)I(a2)=0.72（（比特比特//符号符号））熵的含义•熵是从整个集合的统计特性来考虑的，它从平均意义上来表征信源的总体特征。•在信源输出后，信息熵H(X)表示每个消息提供的平均信息量；•在信源输出前，信息熵H(X)表示信源的平均不确定性；•信息熵H(X)表征了变量X的随机性。熵的含义••例如例如，有两信源有两信源XX、、YY，，其概率空间分别其概率空间分别⎥⎦⎤⎢⎣⎡=⎟⎟⎠⎞⎜⎜⎝⎛01.099.0)(21aaxPX⎥⎦⎤⎢⎣⎡=⎟⎟⎠⎞⎜⎜⎝⎛5.05.0)(21aayPY计算其熵，得得：：H(Y)=1H(Y)=1（（bitbit））H(Y)＞H(X)，因此信源Y比信源X的平均不确定性要大。()()0.99log0.990.01log0.010.08HXbit=−−=电视屏上约有500×600=3×105个格点，按每格点有10个不同的灰度等级考虑，则共能组成个不同的画面。按等概率计算，平均每个画面可提供的信息量为5310221()()log()log1/10niiiHXpxpx×==−=−∑=9.97×105bit510310×信源熵例题有一篇千字文章，假定每字可从万字表中任选，则共有不同的千字文N=100001000=104000篇仍按等概率1/100001000计算，平均每篇千字文可提供的信息量为H(X)＝log2N≈1.3×104bit“一个电视画面”平均提供的信息量远远超过“一篇千字文”提供的信息量。信源熵例题三条件熵I(x/y)是概率空间(XY,P(xy))的一个随机变量是给定yj∈Y条件下集X的熵。11(/)(/)(/)(/)log(/)mjijijimijijiHXypxyIxypxypxy====−∑∑(/)jHXy也称为半条件熵()(/0),(/1)0101/41/811/21/8HXyHXypxyyyxx======例题计算()/0101/31/212/31/2pxyyyxx====三条件熵11111(/)[(/)]()(/)()(/)log(/)()log(/)mjjjjmnjijijjimnijijjiHXYEHXypyHXypypxypxypxypxy========−=−∑∑∑∑∑定义条件熵(相对熵)H(X|Y)是概率空间(Y,P(y))的随机变量(/)jHXy()0101/41/811/21/8pxyyyxx====()/0101/31/212/31/2pxyyyxx====条件熵定义为：11(/)[(/)]()log(/)mnijijijjiHXYEIxypxypxy====−∑∑条件熵条件熵是一个确定值，表示信宿在收到Y后，信源X仍然存在的不确定度。这是传输失真所造成的。有时称H(X/Y)为信道疑义度，也称损失熵。称条件熵H(Y/X)为噪声熵。XY()()1,...,Jyyωω()()1,...,Kqxqx()|jkpyx•联合离散符号集合XY上的每个元素对的联合自信息量的数学期望。•公式：)(log)()()()(jinimjjijinimjjiyxpyxpyxIyxpXYH21111∑∑∑∑====−==)/(log)()/()()/(kjiijkkjikjiijkkjizyxpzyxpzyxIzyxpZXYH2∑∑∑∑∑∑−==联合熵)(jiyxH(XY)•一个二