西安电子科技大学信息论与编码理论讲义
更新时间:2023-09-30 17:27:01 阅读量: 综合文库 文档下载
《信 息 论》
讲 义
204教研室 2005年11月
主要内容: 第一章 绪论
第二章 离散信源及其信息测度 第三章 离散信道及其信道容量 第四章 无失真信源编码 第五章 有噪信道编码
1
第一章 绪论
信息论——人们在长期通信工程的实践中,由通信技术与概率论、随机过程和数理统计相结合而逐步发展起来的一门学科。
奠基人——香农
1948年发表了著名的论文——《通信的数学理论》,为信息论奠定了理论基础。
1.1 信息的概念
人类离不开信息,信息的接收、传递、处理和利用时时刻刻都在发生。 如:“结绳记事”、“烽火告警”,信息的重要性是不言而喻的。 什么是信息?——信息论中最基本、最重要的概念。
信息与“消息”、“情报”、“知识”、“情况”等的区别:
“情报”——人们对于某个特定对象所见、所闻、所理解而产生的知识。是一类特定的信息。 “知识”——人们根据某种目的,从自然界收集得来的数据中,整理、概括、提取得到的有价值的、人们所需的信息。是一种具有普遍和概括性质的高层次的信息。
“消息”——以文字、符号、数据、语言、音符、图片、图像等能够被人们感觉器官所感知的形式,表达客观物质运动和主观思维活动的状态。
消息包含信息,是信息的载体。二者既有区别又有联系。 “信号”——消息的运载工具。
香农从研究通信系统传输的实质出发,对信息作了科学的定义,并进行了定性和定量的描述。 信宿 信源 信道 (发送者) (收信者) 干扰或噪声 图1.1 通信系统框图 收信者:
收到消息前,发送者发送的消息——1、描述的是何种事物运动状态的具体消息;2、描述的是这种消息还是那种消息;3、若存在干扰,所得消息是否正确与可靠。
存在“不知”、“不确定”或“疑问”
收到消息后,知道消息的具体内容,原先的“不知”、“不确定”或“疑问”消除或部分消除了。 消息传递过程——从不知到知的过程;从知之甚少到知之甚多的过程;从不确定到部分确定或全部确定的过程。
通信过程——消除不确定性的过程。 不确定性的消除,就获得了信息。
若原先不确定性全部消除了,就获得了全部的消息;若消除了部分不确定性,就获得了部分信息;若原先不确定性没有任何消除,就没有获得任何消息。
信息——事物运动状态或存在方式的不确定性的描述。
通信的结果——消除或部分消除不确定性而获得信息。 信息如何测度?
信息量与不确定性消除的程度有关。消除了多少不确定性,就获得了多少信息量。 不确定性——随机性——概率论与随机过程。 样本空间——所有可能选择的消息的集合。 概率空间——样本空间和它的概率测度。[X,P]
2
,?,aq??X??a1,a2,?P(x)???P(a),P(a),?,P(a)?
????12q?P(ai)——先验概率,选择符号ai作为消息的概率。
定义:自信息——I(ai)?log1 P(ai)若信道存在干扰,假设接收到的消息是bj,bj可能与ai相同,也可能与ai有差异。
P(ai|bj)——后验概率
定义:互信息——I(ai;bj)?log11?log P(ai)P(ai|bj)1.2 信息论研究对象、目的和内容
1、 研究对象
编码器 译码器 信宿 信源 信道
消息 信号 信号+干扰 消息
干扰
噪声源
图1.2 通信系统模型
(1) 信源——产生消息和消息序列的源 (2) 编码器——消息变换成信号
信源编码——对信源输出的消息进行适当的变换和处理,目的为了提高信息传输的效率。 信道编码——为了提高信息传输的可靠性而对消息进行的变换和处理。 还包括换能、调制、发射等。
(3) 信道——载荷消息的信号的传输媒介。
(4) 译码器——信道输出的编码信号(迭加有干扰)进行反变换。信源译码器和信道译码器 (5) 信宿——消息传送的对象。
将上述模型中编(译)码器分成信源编(译)码、信道编(译)码和加密(解密)编(译)码三个子部分。 Y S C′ V X S U C 信信源信道信信道信源信
源 编码 编码 道 译码 译码 宿
n
解密加密噪声源
译码 编码 图1.3 信息传输系统模型 2、 研究目的
要找到信息传输过程的共同规律,以提高信息传输的可靠性、有效性、保密性和认证性,使达到信息传输系统最优化。
3
可靠性高——要使信源发出的消息经过信道传输以后,尽可能准确地、不失真地再现在接收端。 有效性高——经济效益好,即用尽可能短的时间的尽可能少的设备来传送一定数量的信息。 保密性——隐蔽和保护通信系统中传送的消息,使它只能被受权接收者获取,而不能被未受权者接收和理解。
认证性——接收者能正确判断所接收的消息的正确性,验证消息的完整性,而不是伪造的和被窜改的。 3、研究内容
三种理解: (1)狭义信息论(经典信息论)
研究信息的测度、信道容量以及信源和信道编码理论等问题。
香农基本理论
(2)一般信息论
香农理论、噪声理论、信号滤波和预测、统计检测与估计理论、调制理论、信息
处理理论以及保密理论等。
(3)广义信息论
4
证明:Hnm????ppii?1j?1nmnmijlogpipij
nm????pipijlogpi???pipijlogpij
i?1j?1i?1j?1???(?pij)pilogpi??pi?pijlogpij
i?1nj?1i?1mj?1nmnm ???plogp??p(??piiii?1i?1j?1nijlogpij)
?Hn(p1,p2,?,pn)??piHm(pi1,pi2,?,pim)
i?1nHm(pi1,pi2,?,pim)???pijlogpij?H(Y|X?xi)
j?1m?pHii?1nm(pi1,pi2,?,pim)??piH(Y|X?xi)?H(Y|X)
i?1n7、递增性
Hn?m?1(p1,p2,?,pn?1,q1,q2,?qm)
mnqmq1q2?Hn(p1,p2,?,pn?1,pn)?pnHm(,,?,) (?pi?1,?qj?pn)
pnpnpnj?1i?1证明:Hn?m?1(p1,p2,?,pn?1,q1,q2,?qm) ???plogp??qiii?1nj?1n?1mjlogqj
m ???plogpii?1i?pnlogpn??qjlogqj
j?1 ?Hn(p1,p2,?,pn?1,pn)?logpn?m?q??qjj?1j?1mmjlogqj
?Hn(p1,p2,?,pn?1,pn)??qj?1jlogqjnqjpnlog
?Hn(p1,p2,?,pn?1,pn)?pn?pj?1mqjpn
10
qqq?H1n(p1,p2,?,pn?1,pn)?pnHm(p,2p,?,m) nnpn进一步分析,见P32 例2.4(P33) 8、极值性
H(pp1111,2,?,pn)?H(n,n,?,n)?logn
——最大离散熵定理
补充:
1、上凸函数的基本知识
设f(x)是实变量x的实值连续函数,如对定义域中的任何x1和x2,f(x1?x2f(x1)?2)?f(x2)2 f(x2) 则称f(x)是上凸函数
f(x1) (上凸函数的任何弦均位于函数图形之下) x1 x2 设?x?[x1,x2],则?0???1 使得x??xx1?(1??)x2 (??2?xxx)不同的?值表示[x1,x2]间不同的值
2?1f(x)?f(?xf(x1?(1??)x2) 2) f(x) h(x)?f(xh(x) 1)??x
f(x1) ?x x?f(x?(x?xf(x2)?f(x1)1 x x2 1)1)x
2?x1??f(x1)?(1??)f(x2)
f(x)?h(x)
f(?x1?(1??)x2)??f(x1)?(1??)f(x2)
n推广到统计平均值的范畴,令m1,m2,?,mn为任意整数,且?mi?n
i?1有f(m1x1?m2x2???mnxnn)?1n{m1f(x1)?m2f(x2)???mnf(xn)}
令pmnii?n,?pi?1
i?1 11
满足不等式
则f{?px}??pf(x) 即f[E(X)]?E[f(x)]
iiiii?1i?1nn2、最大离散熵定理 约束条件
?pi?1ni?1,H(P)?H(p1,p2,?,pq)的最大值。
作辅助函数
F(p1,p2,?,pq)?H(p1,p2,?,pq)??[?pi?1]???pilogpi??[?pi?1]
i?1i?1i?1nnn则:
?F??(1?logp1)???0 ?p1?F??(1?logp2)???0 ?p2?
?F??(1?logpn)???0 ?pnn?F??pi?1?0 ??i?1即
??(1?logpi)???0?n (i?1,2,?,n) ?p?1?0??i?i?1?pi?2??1?所以,???11
?2?n?1时,H(P)取极大值。 n111即Hmax(p1,p2,?,pq)?H(,,?,)?logn
nnn故:p1?p2???pn?
补充:信源X的概率空间P?(p1,p2,?,pn) 0?pi?1,(i?1,2,?,n),
nn?pi?1ni?1
另xi?0,(i?1,2,?,n),有log{?px}??plogxiiii?1i?1i(logx为上凸函数。)
12
设另一概率分量数同样也等于n的概率空间S?(s1,s2,?,sn)
其中0?si?1,(i?1,2,?,n),
?si?1ni?1
令xi?nsi,(i?1,2,?,n),则有xi?0,(i?1,2,?,n) pinsislog{?pi}??pilogi
pipii?1i?1log{?si}??pilogsi??pilogpi
i?1i?1i?1nnn??pilogpi???pilogsi
i?1i?1nnH(X)?H(p1,p2,?,pn)???pilogsi
i?1n
补充:lnx?x?1
f(x)?x?1?lnx lnx? f?(x)?1? f??(x)?logxloge logx?lnx?loge
1?0 x?1 x1?0 x2 f(x)在x?1处取极小值。f(x)极小值为0。
nnsisie?(?1)?loge??(si?pi)?0 ?pilog??pi?logppi?1i?1i?1iin??pilogpi???pilogsi
i?1i?1nnH(X)?H(p1,p2,?,pn)???pilogsi
i?1n9、上凸性
熵函数H(P)是概率矢量P?(p1,p2,?,pq)是上凸函数。即
??? 对任意概率矢量P1?(p1,p2,?,pq)和P2?(p1,p2,?,pq),及任意0???1,则有
13
H[?P1?(1??)P2]??H(P1)?(1??)H(P2)
证明:H[?P1?(1??)P2] ???[?pi?1qqi?(1??)pi?]log?[pi?(1??)pi?]
q ????plog?[pii?1i?(1??)pi?]?(1??)?pi?log?[pi?(1??)pi?]
i?1qpip?????pilog[?pi?(1??)pi?]?(1??)?pi?logi[?pi?(1??)pi?]
pipi?i?1i?1qqq???H(P1)?(1??)H(P2)???pilog[?pi?(1??)pi]???pilogi?1i?11pi
?(1??)?pi?log[?pi?(1??)pi?]?(1??)?pi?logi?1i?1qq1i pi?令?i??pi?(1??)pi?,(i?1,2,?,q),
qq??i?1qi?1
???pilog[?pi?(1??)pi?]???pilogi?1qi?11 piq???pilog?i???pilogpi????pilogpi???pilogpi?0
i?1i?1i?1i?1qq同理:?(1??)?pi?log[?pi?(1??)pi?]?(1??)?pi?logi?1i?1qq1i?0 ?pi所以,H[?P1?(1??)P2]??H(P1)?(1??)H(P2)
2.4 信息熵的唯一性定理
定理2.1 设Hn(p1,p2,?,pn)是概率矢量P?(p1,p2,?,pq)的非负函数,对于任意n,概率矢量满足pi?0,
?pi?1ni?1。若Hn(P)满足下述公理:
(A1)对?n,函数Hn(p1,p2,?,pn)是pi(i?1,2,?,n)的连续和对称函数; (A2)扩展性。对?n,有
Hn?1(p1,p2,?,pn,0)?Hn(p1,p2,?,pn);
14
(A3)极值性。对?n,有
Hn(p1,p2,?,pn)?Hn(1,1,?,1);
nnn(A4)强可加性。若
pipij?0,??pipij?1,?pij?1 (i?1,2,?,n)(j?1,2,?,m)
i?1j?1j?1nmm有 Hnm(p1p11,p1p12,?,p1p1m,p2p21,?p2p2m,pnpn1,?pnpnm) ?Hn(p1,p2,?,pn)?则得
?pHii?1nnm(pi1,pi2,?,pim);
Hn(p1,p2,?,pn)????pilogpi
i?1其中?为一正常数。
定理中,?为一常数,它由对数的底来决定,只影响所取的单位。
2.5 离散无记忆的扩展信源
设一个离散无记忆信源的概率空间
,?,aq??X??a1,a2,?P(x)???P(a),P(a),?,P(a)? ???12q??则信源X的N次扩展信源XN?pi?1Nqi?1
是具有q个符号的离散信源,其N重概率空间为
,?,?q??XN???1,?2,????P(?),P(?),?,P(?)?
21?P(?i)??qN???i——某一个由N个ai组成的序列。
P(ai)——N个aik组成的序列的概率。?p(?i)?1
i?1qNN次扩展信源的熵
H(X)?H(XN)???P(X)logP(X)???P(?i)logP(?i)
XNXNH(XN)?NH(X)
证明:?i?(ai1,ai2,?,aiN)
P(?i)?pi1?pi2???piN (i1,i2,?,iN?1,2,?,q)
15
H(XN)???P(?i)logP(?i)
XNH(XN)??P(?i)logXN1
pi1?pi2???piN111 ??P(?i)log????P(?i)logNpi1XNpi2pXiN ??P(?i)logXNqq111qP(?i)log??pi1?pi2???piNlog??pi1log??pi2????piN ?NNpppi1?1iN?1XXi1i1i1i2?1q??pi1logi1?1N1?H(X) pi1所以,H(X)?H(X)?H(X)?H(X)???H(X)?NH(X) 例2.5 (P40)
2.6 离散平稳信源
2.6.1 离散平稳信源的数学定义
一维平稳信源
P(xi)?P(xj)?P(x) (i,j为任意大于1的任意整数)
二维平稳信源
P(xi)?P(xj)?P(x)
P(xixi?1)?P(xjxj?1) (i,j为任意整数,i?j)
离散平稳信源
P(xi)?P(xj) P(xixi?1)?P(xjxj?1)
????
P(xixi?1?xi?N)?P(xjxj?1?xi?N) (i,j为任意整数,i?j)
由联合概率与条件概率的关系:
P(xixi?1)?P(xi)P(xi?1|xi)
P(xixi?1xi?2)?P(xi)P(xi?1|xi)P(xi?2|xixi?1)
????
16
P(xixi?1?xi?N)?P(xi)P(xi?1|xi)??P(xi?N|xixi?1?xi?N?1)
可得:
P(xi?1|xi)?P(xj?1|xj) P(xi?2|xixi?1)?P(xj?2|xjxj?1)
????
P(xi?N|xixi?1?xi?N?1)?P(xj?N|xjxj?1?xj?N?1)
条件概率均与时间起点无关,只与关联长度N有关。(平稳信源发出的平稳随机序列前后的依赖关系与时间起点无关。)
2.6.2 二维平稳信源及其信息熵
q,?,aq??X??a1,a2,?? ?? 且?P(ai)?1 ?i?1??P(x)??P(a1),P(a2),?,P(aq)?连续两个信源符号出现的联合概率分布P(aiaj)(i,j?1,2,?,q),并有
??P(aa)?1
iji?1j?1qqP(aj|ai)?P(aiaj)P(ai) (i,j?1,2,?,q)
?P(aj?1qj|ai)?1
信源发出的符号序列中相邻两个符号是有关联的。
如何进行信息测度?——信息熵的近似值计算 分析一:
将二维信源输出的随机序列分成每二个符号一组,每组代表新信源X?X1X2中的一个符号。 假设组与组之间是统计独立的,互不相关的。(实际上,不是统计独立的。)
?X1X2??a1a1,a1a2,?,aq?1aq,aqaq??P(xx)???P(aa)?P(a)P(a|a)?
ij?iji?12???qq??P(aa)?1
iji?1j?1qqH(X1X2)????P(aiaj)logP(aiaj) —— X1X2的联合熵
i?1j?1表示原来信源X输出任意一对消息的共熵,即描述信源X输出长度为2的序列的平均不确定性,或
所含有的信息量。 可用
1H(X1X2)作为二维平稳信源X的信息熵的近似值。 217
分析二:
H(X2|X1?ai)???P(aj|ai)logP(aj|ai)
j?1qH(X2|X1)???P(ai)H(X2|X1?ai)????P(ai)P(aj|ai)logP(aj|ai)i?1i?1j?1qqq
????P(aiaj)logP(aj|ai)
i?1j?1qq——条件熵
H(X1X2)????P(aiaj)logP(aiaj)????P(aiaj)logP(ai)P(aj|ai)
i?1j?1i?1j?1qqqq????P(aiaj)logP(ai)???P(aiaj)logP(aj|ai)
i?1j?1qqi?1j?1qqqq????P(aiaj)logP(ai)?H(X2|X1)
i?1j?1q???P(ai)?P(aj|ai)logP(ai)?H(X2|X1)???P(ai)logP(ai)?H(X2|X1)
i?1j?1i?1qq?H(X1)?H(X2|X1)
H(X1X2)?H(X1)?H(X2|X1)——熵的强可加性
条件熵与无条件熵的关系:H(X2|X1)?H(X2)
证明:在区域[0,1]中,设f(x)??xlogx(上凸函数)。并设xi?P(aj|ai)?pij,而P(ai)?pi,
有
?pi?1qqi?1
q由詹森不等式
?pf(x)?f{?px}可得:
iiiii?1i?1qqqq??pipijlogpij???pipijlog(?pipij)??pjlogpj(?pipij??p(aiaj)?P(aj)?pj)
i?1i?1i?1i?1i?1q上式对j求和:
???pipijlogpij???pjlogpj ? H(X2|X1)?H(X2)
i?1j?1j?1qqq 18
等式成立条件:只有当P(aj|ai)?P(aj)。
当X1和X2取自同一概率空间X,则有H(X2)?H(X1)?H(X)
H(X1X2)?H(X1)?H(X2)?2H(X)
例2.6 (P44)
1H(X1X2)与H(X2|X1)选取哪个值更能接近实际二维平稳信源的熵? 22.6.3 离散平稳信源的极限熵
设离散平稳有记忆信源
q?X??a1,a2,?,aq??P(x)???p,p,?,p? 且?pi?1
i?1???12q??信源符号之间依赖长度为N,已知各维概率分布。
离散平稳信源的一系列联合熵
H(X1X2?XN)?????P(ai1ai2?aiN)logP(ai1ai2?aiN) (N?2,3,?,N)
i1?1iN?1qq定义N长的信源符号序列中平均每个信源符号所携带的信息量为
HN(X)?H(X1X2?XN)——平均符号熵
条件熵:
H(XN|X1X2?XN?1)?????P(ai1ai2?aiN)logP(aiN|ai1ai2?aiN?1)i1?1iN?1qq
(N?2,3,?,N)
对于离散平稳信源,当H1(X)??时,则具有以下性质: (1) 条件熵H(XN|X1X2?XN?1)随N的增加是非递增的;
(2) N给定时,平均符号熵?条件熵,即HN(X)?H(XN|X1X2?XN?1); (3) 平均符号熵HN(X)随N增加而非递增的; (4) H??limHN(X)?limH(XN|X1X2?XN?1)
N??N??称H?为平稳信源的极限熵或极限信息量(平稳信源的熵率)。 证明:
(1) 由H(X2|X1)?H(X2)可得:H(X3|X1X2)?H(X3|X2)
19
?log?P(?h)?log1?0
Y证得:I(X;Y)??I(X;Y)。当信道是无记忆时,等号成立!
iii?1N当信源和信道都是无记忆时,I(X;Y)??I(X;Y)。
iii?1N若信道输入序列X?(X1X2?XN)中Xi取自于同一信源符号集,并具有同一概率分布,且通过相同的信道传送到输出端(即输出序列Y?(Y1Y2?YN)中Yi也取自于同一符号集),因此有:
I(X1,Y1)?I(X2,Y2)???I(XN,YN)?I(X;Y) ?
?I(X;Y)?NI(X;Y)
iii?1N对于离散无记忆信道的N次扩展信道,若信源也是无记忆的,则:I(X;Y)?NI(X;Y)。 (当信源无记忆时,无记忆的N次扩展信道的平均互信息等于原来信道的平均互信息的N倍。) 对于一般的离散无记忆信道的N次扩展信道,有I(X;Y)?NN?I(X;Y)。
iii?1NN其信道容量:CN?maxI(X;Y)?max?I(Xi;Yi)??maxI(Xi;Yi)??Ci。
P(x)P(x)i?1i?1P(xi)i?1CN?NC
离散无记忆的N次扩展信源的信道容量等于原来原单符号离散信道的信道容量的N倍。 一般情况下,消息序列在离散无记忆的N次扩展信道中传输的信息量为:I(X;Y)?NC。
3.7 独立并联信道及其信道容量
设有N个信道,它们的输入分别是X1,X2,?,XN,它们的输出分别是Y1,Y2,?,YN,它们的传递概率分别是P(y1|x1),P(y2|x2),?,P(yN|xN)。在N个独立并联信道中,每一个信道的输出Yi只与本信道的输入Xi有关,与其他信道的输入、输出都无关。则:
P(y1y2?yN|x1x2?xN)?P(y1|x1)P(y2|x2)?P(yN|xN)
I(X1X2?XN;Y1Y2?YN)??I(Xi;Yi)
i?1NC1,2,?,N?maxI(X1X2?XN;Y1Y2?YN)?独立并联信道的信道容量:
P(x1?xN)?Ci?1Ni Ci?maxI(Xi;Yi)
P(xi) 45
当输入符号Xi相互独立,且输入符号Xi的概率分布达到各信道容量的最佳输入分布时,独立并联信道的信道容量才等于各信道容量之和。C1,2,?,N??C。
ii?1N3.8 串联信道的互信息和数据处理定理
信道输出端对接收到的信号或数据进行适当的处理——数据处理。一般地,数据处理系统可看成是一种信道。它与传输数据的信道是串联关系。
信道II 信道 信道I Z Z X Y X
P(y|x) I(Z;X) P(z|x) ((zz||xy))?1 xy?P(y|x)?1 ?PPYZ?P(z|x)?1
Z串接信道 等价总信道
X:{a1,a2,?,ar} Y:{b1,b2,?,bs} Z:{c1,c2,?,ct}
P(z|x)??P(y|x)?P(z|xy)
Y若信道II的传递概率使其输出Z只与输入Y有关,与前面的输入X无关,即满足
P(z|xy)?P(z|y),称X、Y、Z构成马尔可夫链。
[P(z|x)]?[P(y|x)]?[P(z|xy)] [P(z|x)]?[P(y|x)]?[P(z|y)](X、Y、Z满足马尔可夫链)
r?tr?ss?tr?tr?ss?t讨论I(X;Y)、I(X;Z)、I(Y;Z)之间的关系。
Th3.7 I(XY;Z)?I(Y;Z),当且仅当P(z|xy)?P(z|y)时,等式成立。 证明:I(XY;Z)?X,Y,Z?P(xyz)logP(z|xy)P(z|xy)?E[log]
P(z)P(z) I(Y;Z)??P(yz)logY,ZP(z|y)P(z|y)P(z|y)??P(xyz)log?E[log]
P(z)P(z)P(z)X,Y,Z I(Y;Z)?I(XY;Z)?E[logP(z|y)P(z|xy)P(z|y)?log]?E[log] P(z)P(z)P(z|xy) ?logE[ ?logP(z|y)P(z|y)]?log?P(xyz)?log?P(xy)P(z|y)
P(z|xy)P(z|xy)X,Y,ZX,Y,ZZ?P(xy)?P(z|y)?log1?0
X,Y同理可得:I(XY;Z)?I(X;Z)
46
Th3.8 (数据处理定理)
若X、Y、Z组成一个马尔可夫链,则有I(X;Z)?I(X;Y)、I(X;Z)?I(Y;Z)。
证明:因为X、Y、Z是马尔可夫链,可得:I(XY;Z)?I(Y;Z),而I(XY;Z)?I(X;Z), 所以:I(X;Z)?I(Y;Z)
因为X、Y、Z是马尔可夫链,可证得:Z、Y、X也是马尔可夫链,所以有:
I(YZ;X)?I(Y;X),又可得:I(YZ;X)?I(Z;X) I(X;Y)?I(Y;X)?I(Z;X)?I(X;Z)
在串联信道中一般有H(X|Z)?H(X|Y),当满足P(x|y)?P(x|z)时,等式成立。 例3.12 (P120)
对于一系列不涉及原始信源的数据处理,即对一系列串接信道,有:
H(X)?I(X;Y)?I(X;Z)?I(X;W)??
Z W X Y … 信道II 信道III 信道I
一系列串接信道
——信息不增性原理。 例3.13 (P124) 一般的通信系统模型: Y X S 信源 编码 信道 译码 (YY…Y) (XX…X) (S1S2…SN) 12N12N 一般的通信系统 Z 信宿 (Z1Z2…ZN) (S,X,Y,Z)——随机矢量序列,对于实际通信系统,它们形成一个马尔可夫链。
对(X,Y,Z),有I(X;Z)?I(X;Y);对(S,Y,Z),有I(S;Z)?I(S;Y);对(S,X,Z),有
I(S;Z)?I(X;Z),可得:I(S;Z)?I(X;Y)——一般的数据处理定理。
3.9 信源与信道匹配
当信源与信道连接时,若信息传输率达到了信道容量,称此信源与信道达到匹配。否则认为信道有剩余。
定义:信道剩余度=C?I(X;Y) 信道相对剩余度=
无损信道中,C?logr,I(X;Y)?H(X)。
C?I(X;Y)I(X;Y)?1?
CC无损信道的相对剩余度=1?
H(X)——信源剩余度。 logr47
例 (P127)
是否存在一种信源编码,使信道的信息传输率R接近或等于信道容量?即存在一种编码,使每个信源符号所需的二元符号最少?——香农无失真信源编码理论(无失真数据压缩理论)。
将信源输出的消息变换成适合信道传输的新信源的消息,使信源和信道达到匹配。
第四章 无失真信源编码
问题:1、在不失真或允许一定失真条件下,如何用尽可能少的符号来传送信源信息,以便提高信息
传输率? ——信源编码 2、在信道受干扰的情况下,如何增加信号的抗干扰能力,同时又使得信息传输率最大?
——信道编码
4.1 编码器
码符号(码元):xj
s: {s1,s2,?,sq} 编码器 X: C: {W1,W2,?,Wq} {x1,x2,?,xr} 无失真信源编码器 si(i?1,?,q)?Wi?(xi1xi2?xil) xik?X (k?1,?,li)
isi?(si1si2?siN)?Wi?(xi1xi2?xil) sik?S (k?1,?,N) xik?X (k?1,?,li)
i码字——Wi 码字长度(码长)——li 码——C(所有码字的集合) 编码:信源符号映射到码符号。 无失真编码:映射一一对应,可逆。 码的定义: 1、二元码
码符号集X?{0,1} 2、等长码(固定长度码) li?l (i?1,?,q) 3、变长码
所有码字的码长各不相同。 4、非奇异码
si?sj? Wi?Wj si,sj?S Wi,Wj?C
5、奇异码
si?sj? Wi?Wj si,sj?S Wi,Wj?C
6、同价码
码符号集X中每个码符号xi所占的传输时间都相同。
48
7、码的N次扩展码
码C?{W1,W2,?,Wq},si?S?Wi?(xi1xi2?xil) xik?X
iN则N次扩展码B?{Bi?(Wi1Wi2?WiN)} (i1,i2,?iN?1,?,q) (i?1,?,q)
举例 (P136)
8、惟一可译码(单义可译码)
若码的任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列。 码的任意有限长N次扩展码都是非奇异码。
4.2 等长码
若等长码是非奇异码,则它的任意有限长N次扩展码一定也是非奇异码。 表4.2 (P137)
若对信源S进行等长编码,则必须满足q?r。q——信源符号个数;l——码长;r——码元数。 要使编得的等长码是惟一可译码,则必满足q?r。
Nllllogq? Nlogr4.3 渐近等分割性和ε典型序列
渐近等分割性(AEP)——弱大数定律的推论。
1n对于独立、等同分布的随机变量X1X2?Xn,只要n足够大时,?Xi是接近其数学期望值E[X]。
ni?1设离散无记忆信源
q?S??s1,s2,?,sq??P(s)???P,P,?,P? (?Pi?1)
i?1???12q??它的N次扩展信源,SN?(S1S2?SN)
?SN???1,?2,?,?qN?N????P(?),P(?),?,P(?)? ?i?(si1si2?siN) (i?1,?,q,i1,i2,?iN?1,?,q)
12?P(?)??qN??P(?i)??P(sik)??Pik (i?1,?,qN,i1,i2,?iN?1,?,q)
k?1k?1NNI(?i)??logP(?i)???logPik??I(sik) E[I(?i)]?H(S)??E[I(sik)]?NH(S)
Nk?1k?1k?1NNND[I(?i)]?ND[I(sik)]?N{E[I(sik)]?[H(S)]}?N{?pi(logpi)?[??pilogpi]2}
222i?1i?1qqTh4.1 渐近等分割性(AEP):若S1S2?SN随机序列中Si(i?1,?,N)相互统计独立并且服从同一
49
??P(sL?Ei|s1?Ej)[??P(xL|sL?Ei)logP(xL|sL?Ei)]
i?1JJxL??P(sL?Ei|s1?Ej)H(XL|sL?Ei)
i?1状态的马尔可夫链是时齐的,可得:
H(XL|X1X2?XL?1s1?Ej)??P(sL?Ei|s1?Ej)H(X|s?Ei)
i?1J将上式对初始状态空间求统计平均,得:
H(XL|X1X2?XL?1S)=?P(s1?Ej)H(XL|X1X2?XL?1s1?Ej)
j?1J???P(s1?Ej)P(sL?Ei|s1?Ej)H(X|s?Ei)??P(sL?Ei)H(X|s?Ei)
j?1i?1JJJi?1P(sL?Ei)是信源的状态马尔可夫链的绝对概率。它表示L时刻信源处于状态Ei的概率。
一般情况,它与马氏链的初始概率分布和状态一步转移概率有关。
11H(X1X2?XN|S)?NN1qN(Ei)?N??P(sL?1i?1NJL?Ei)H(X|s?Ei)??qN(Ei)H(X|s?Ei)
i?1J?P(sL?1NL?Ei)——表示在L?1到L?N时间内,状态Ei出现概率的平均值。
H??H?(X)?lim?lim1H(X1?XN|S)
N??NJN???qi?1JN(Ei)H(X|s?Ei)??q?(Ei)H(X|Ei)
i?1q?(Ei)?limN???P(sL?1NL?Ei)——与初始状态概率分布有关。
对于时齐的、遍历的马尔可夫链,其极限概率Q(Ei)存在,即
N??limP(sN?Ei|s1?Ej)?limPj(iN)?Q(Ei) Ei?E
N??并有P(sL?Ei)??P(sj?1J1?Ej)P(sL?Ei|s1?Ej) limP(sN?Ei)?Q(Ei) Ei?E
L??因此得时齐、遍历的马尔可夫信源
1q?(Ei)?limN??N
?P(sL?1NL?Ei)?Q(Ei) (i?1,?,J)
25
可见L足够长后,状态绝对概率与初始概率分布无关。而且Q(Ei)满足
Ej?E?Q(E)P(E|E)?Q(E)
jijiEi?E?Q(E)?1
iJJq时齐、遍历的马尔可夫信源的熵:
H???Q(Ei)H(X|Ei)????Q(Ei)P(ak|Ei)logP(ak|Ei)
i?1i?1k?1时齐、遍历的m阶马尔可夫信源:
H(X|Ei)???P(ak|Ei)logP(ak|Ei)??k?1Jqkm?1?1?P(aqkm?1|ak1ak2?akm)logP(akm?1|ak1ak2?akm) H??Hm?1??Q(E)H(X|E) Eiii?1i?(ak1ak2?akm) (km?1,2,?,qi?1,2,?,J?qm)
一阶马尔可夫信源:
给定的条件概率为P(ak|ak?1),状态集就是符号集,状态极限概率Q(Ei)等于信源达到平稳以后信源符号的概率分布P(ak)。
概率空间:
?a1,a2,?,aq?X:??
?P(ak|ak?1)k,k?1?1,2,?,q?E?[a1,a2,?,aq]
?P(ak?1qk|ak?1)?1(k?1?1,2,?,q)
得:P(ak|Ei)?P(ak|ak?1) (k?1,2,?,q;i?k?1?1,2,?,q)
Q(Ei)?P(ak?1)(i?k?1?1,2,?,q)
H??H2??Q(Ei)H(X|Ei)???i?1Jqk?1k?1?1?P(aqk?1)P(ak|ak?1)logP(ak|ak?1)
一阶马尔可夫信源的熵等于条件熵。极限概率分布P(ak?1)为信源达到平稳以后的分布。 若P(ak?1)等于起始的符号概率分布,P(ak|ak?1)已给定并与时间平移无关,因此一阶马尔可夫信源变成了二维平稳信源。
例2.9 (P57) 例2.10 (P57)
26
2.8 信源剩余度与自然语言的熵
实际离散信源可能是非平稳的,H?不一定存在。?假设它平稳的,用H?来近似。但是计算H?极其困难。?假设它是m阶马尔可夫信源,用Hm?1来近似。(m=1时,Hm?1?H2?H(X2|X1))
?假设信源为无记忆信源,可用信源的平均自信息量H1?H(X)来近似。?等概率分布时,可用
H0?logq来近似。
对于一般的离散信源都可以近似用不同记忆长度的马尔可夫信源来逼近。
logq?H0?H1?H2???Hm?1???H?
由于信源符号间的依赖关系使信源的熵减小。若前后依赖关系越长,则信源的熵越小。 信源符号之间依赖关系越强,每个符号提供的平均信息量越小。
每个符号提供的平均自信息量随着符号间的依赖关系长度的增加而减小。 引入 信源的剩余度来衡量信源的相关性程度。
熵的相对率 —— 一个信源实际的信息熵与具有同样符号集的最大熵的比值称为相对率。 信源剩余度 —— 1减去熵的相对率。 相对率:??H? H?——信源的实际熵;H0?logq——最大熵,q——信源的符号数。 H0H? H0信源剩余度:??1???1?信源剩余度的大小——反映离散信源输出的符号序列中符号之间依赖关系的强弱。
剩余度?越大,表示信源的实际熵H?越小。——信源符号之间依赖关系越强。(记忆长度越长。)
英文字母(26个字母+空格=27个符号)组成的信源:H??1.4(比特/符号) H0?log27?4.76 熵的相对率 ??
27
H??0.29 剩余度 ??1???0.71 H0
第三章 离散信道及其信道容量 3.1 信道的数学模型及分类
3.1.1 信道的分类
1、根据用户的多少,分为:两端(单用户)信道、多端(多用户)信道。 2、根据输入端和输出端的关联,分为:无反馈信道、反馈信道。 3、根据信道的参数与时间的关系,分为:固定参数信道、时变参数信道。
4、根据输入和输出信号的特点,分为:离散信道、连续信道、半离散或半连续信道、波形信道。
3.1.2 离散信道的数学模型
无反馈、固定参数、单用户离散信道 Y X 信道
X?(X1,?,Xi,?,XN) P(y|x) Y?(Y1,?,Yi,?,YN)
X:[a1,?,ar] Y:[b1,?,bs]
P(y|x)?1
y
图3.1 离散信道模型
?条件概率P(y|x)描述了输入信号和输出信号之间统计依赖关系,反映了信道的统计特性。 根据信道的统计特性即条件概率P(y|x)的不同,离散信道可分为: 1、无干扰(无噪)信道——输出与输入之间有确定的一一对应的关系。 y?f(x) 且P(y|x)???1y?f(x)
?0y?f(x)2、有干扰无记忆信道——任意时刻输出符号只与对应时刻的输入符号有关,而与以前时刻的输入符
号、输出符号无关,也与以后的输入符号无关。
3、有干扰有记忆信道
离散无记忆信道的充要条件?P(y|x)?P(y1y2?yN|x1x2?xN)?证明:充分性(?):
P(y|x)?P(y1y2?yN|x1x2?xN)
?P(yi?1Ni|xi)
28
?P(y1|x1x2?xN)P(y2?yN|x1x2?xNy1)
?P(y1|x1x2?xN)P(y2?yN|x1x2?xNy1)P(y3?yN|x1x2?xNy1y2) ??
?P(y1|x1x2?xN)P(y2|x1x2?xNy1)P(y3|x1x2?xNy1y2)
?P(yN?1|x1x2?xNy1?yN?2)P(yN|x1x2?xNy1?yN?1)
P(y1y2?yN|x1x2?xN)P(yN|x1x2?xNy1?yN?1)??P(y1y2?yN?1|x1x2?xN)?P(y|x)iiN?P(y1y2?yN?1yN|x1x2?xN)yNi?1
??P(y|x)iiN?P(yyNi?11|x1)P(y2|x2)?P(yN?1|xN?1)P(yN|xN)12N
?P(y|x)?????P(yy?yYy1y2yN|x1x2?xN)?1
????P(y|x)P(y11y1y2yN2|x2)?P(yN?1|xN?1)P(yN|xN)?1
2所以:
?P(y|x)?1 ?P(y11y1y2N|x2)?1 ?
|xi)?P(yyNN|xN)?1
P(yN|x1x2?xNy1?yN?1)??P(y?P(yi?1i?1N?1i?P(yN|xN) |xi)iP(y1y2?yN?2yN?1|x1x2?xN)同理:P(yN?1|x1x2?xNy1?yN?2)??P(y1y2?yN?2|x1x2?xN)??P(y|x)iiyNN???P(y|x)iiyNyN?1i?1i?1N
??P(y|x)iiN?1?P(y|x)iii?1i?1N?2?P(yN?1|xN?1)
P(yN?2|x1x2?xNy1?yN?3)?P(yN?2|xN?2) ? P(y2|x1x2?xNy1)?P(y2|x2) P(y1|x1x2?xN)?P(y1|x1)
必要性(?):
P(y1|x1x2?xN)?P(y1|x1) P(y2|x1x2?xNy1)?P(y2|x2) ?
29
证明:固定信道:即P(y|x)固定。
选取输入信源X的两种概率分布:P1(x)、P2(x)
对应的联合概率分布:P1(xy)?P1(x)P(y|x) P2(xy)?P2(x)P(y|x) 平均互信息:I[P1(x)]、I[P2(x)]
选择另外一种概率分布:P(x),令0???1、????1,P(x)??P1(x)??P2(x) 平均互信息:I[P(x)]
?I[P1(x)]??I[P2(x)]?I[P(x)]
=
??P1(xy)logX,YP(y|x)P(y|x)P(y|x)???P2(xy)log??P(xy)log
P(y)P(y)P(y)X,YX,Y12P(y|x)P(y|x)P(y|x)???P2(xy)log??[?P(xy)??P(xy)]log 12PP2(y)P(y)X,YX,Y1(y)P(y)P(y)???P2(xy)log
P(y)P(y)X,Y21P(y)P(y)??log?P2(xy) PP2(y)X,Y1(y)=
??P1(xy)logX,Y=??P1(xy)logX,Y??log?P1(xy)X,Y=?logP(y)P(y)P(xy)??logP2(xy) ????1P(y)P(y)YXYX12P(y)P(y)P(y)??logP2(y) ??1P(y)P(y)YY12=?log=?log?P(y)??log?P(y)=0
YY?I[P1(x)]??I[P2(x)]?I[P(x)]?0 即 I[?P1(x)??P2(x)]??I[P1(x)]??I[P2(x)]
故:平均互信息I(X;Y)是输入信源的概率分布P(x)的∩型凸函数。 例3.4 (P88)
Th 3.2 平均互信息I(X;Y)是信道传输概率P(y|x)的∪型凸函数。 证明:固定信源:即P(x)固定。
选择两种信道,传递概率分别为:P1(y|x)、P2(y|x)
35
平均互信息分别为:I[P1(y|x)]、I[P2(y|x)]
选择第三种信道,传递概率为:P(y|x)??P1(y|x)??P2(y|x) 平均互信息为:I[P(y|x)]
I[P(y|x)]??I[P2(y|x)] 1(y|x)]??I[P=
?[?P1(xy)??P2(xy)]logX,YPP2(x|y)P(x|y)1(x|y)???P(xy)log??P(xy)log ?12P(x)P(x)P(x)X,YX,Y=??P1(xy)logX,YP(x|y)P(x|y)???P2(xy)log
PP2(x|y)X,Y1(x|y)P(x|y)P(x|y)??log?P2(xy)
P(x|y)P(x|y)X,Y12X,Y??log?P1(xy)X,Y??log?P1(y)P(x|y)??log?P2(y)P(x|y)
X,Y??log?P1(y)?P(x|y)??log?P2(y)?P(x|y)
YXYX=?log?P(y)??log?P(y)=0
12YYI[P(y|x)]??I[P2(y|x)]?0 1(y|x)]??I[P即I[?P1(y|x)??P2(y|x)]??I[P2(y|x)] 1(y|x)]??I[P故:平均互信息I(X;Y)是信道传输概率P(y|x)的∪型凸函数。 #
3.4 信道容量及其一般计算方法
研究信道的目的——讨论信道中平均每个符号所能传送的信息量,即信道的信息传输率R
R?I(X;Y)?H(X)?H(X|Y) (比特/符号)
111Rt?I(X;Y)?H(X)?H(X|Y) (比特/秒) —— 信息传输速率
tttI(X;Y)是输入信源的概率分布P(x)的∩型凸函数。对于一个固定的信道,总存在一种信源(某种
概率分布P(x)),使传输每个符号平均获得的信息量最大。即每个固定信道都有一个最大的信息传输率。定义这个最大的信息传输率为信道容量C,即C?max{I(X;Y)} (比特/符号)
P(x)相应的输入概率分布称为最佳输入分布。
36
1Ct?max{I(X;Y)} (比特/秒)
tP(x)信道容量C是信道传输概率函数。只与信道的统计特性有关。 ——完全描述信道特性的参量,是信道能够传输的最大信息量。 续 例3.4 (P91)
3.4.1 离散无噪信道的信道容量
X Y 1
a1 b1
1 a2 b2
1 a3 b3 无噪无损信道
1、无噪无损信道(一一对应)
X 1/2 a1 1/2 3/5 Y b1 b2 b3 b4 b5 b6 a1 a2 a3 a4 a5 a6 X 1 1 1 1 Y b1 a2 3/10 1/10 b2
1 a3 1 1 b3
有噪无损信道 无噪有损信道
?0i?j P(bj|ai)?P(ai|bj)??
1i?j? 前向概率和后向概率均是等于0或1。损失熵H(X|Y)?0;噪声熵H(Y|X)?0。 I(X;Y)?H(X)?H(Y)——信道中无信息损失。
2、有噪无损信道(一对多)(信道的传递矩阵中每一列有一个且仅有一个非零元素。)
前向概率不等于0或1;后向概率均是等于0或1。损失熵H(X|Y)?0;噪声熵H(Y|X)?0。 I(X;Y)?H(X)?H(Y)——平均互信息等于信源熵。 3、无噪有损信道(多对一)
前向概率等于0或1;后向概率不等于0或1。损失熵H(X|Y)?0;噪声熵H(Y|X)?0。 I(X;Y)?H(Y)?H(X)
无损信道——信息传输率R为输入信源X输出每个符号携带的信息量(H(X)) 信道容量:C??maxH(X)?logr (比特/符号)
P(x)无噪信道——信道容量:C???maxH(Y)?logs (比特/符号)
P(x)图3.15 (P93)
3.4.2 对称离散信道的信道容量
37
?,p2?,?,p?对称性——信道矩阵P中每一行都是由同一个?p1s?集的诸元素不同排列组成,且每一列
?,q2?,?,qr??集的诸元素不同排列组成。也都由?q1(行与行置换;列与列置换)
一般r?s,当r?s时,?pi??集与?qi??集相同;若r?s,?qi??集是?pi??的子集。(例 P93) 强对称信道(均匀信道):
??p??pP??r?1????p??r?1pr?1p?pr?1pr?1pr?1?pr?1????p?r?1??p?r?1? p?p?1 ????p??总的错误概率为p,对称地平均分配给r?1个输出符号。各列之和等于1。
I(X;Y)?H(Y)?H(Y|X) H(Y|X)??P(x)?P(y|x)logXY1??P(x)H(Y|X?x)
P(y|x)XH(Y|X?x)——对信道矩阵的行求和。根据信道对称性,H(Y|X?x)与x无关,为一常数。 ?,p2?,?,p?即:H(Y|X?x)?H(p1s)
?,p2?,?,p?信道容量:C?max[H(Y)?H(p1s)]
P(x)对于对称信道,当输入符号达到等概率分布时,输出符号一定也达到等概率分布。
?,p2?,?,p????C?logs?H(p1s) ?p1,p2,?,ps?——信道矩阵行矢量。
例3.5 (P95) 例3.6 (P95)
3.4.3 准对称信道的信道容量
若信道矩阵Q的列可以划分成若干个互不相交的子集Bk,即B1?B2???Bn??,
B1?B2???Bn?Y,由Bk为列组成的矩阵Qk是对称矩阵,则称信道矩阵Q所对应的信道为准
对称信道。 例 (P96)
最佳输入分布——等概分布。
?,p2?,?,p?信道容量:C?logr?H(p1s)??Nk?1nklogMk
?,p2?,?,p?r——输入符号集的个数;?p1s?——准对称信道矩阵中的行元素;
38
设矩阵可划分成n个互不相交的子集。
Nk——第k子矩阵Qk中行元素之和;Mk——第k子矩阵Qk中列元素之和。
即Nk?y?Yk?P(y|x) Mik??P(y|xi)
Xy?Yk (k?1,2,?,n)
例3.7 (P97)
3.4.4 一般离散信道的信道容量
信道容量——在固定信道的条件下,对所有可能的输入概率分布P(x)求平均互信息的极大值。
I(X;Y)是r个变量{P(a1),P(a2),?,P(ar)}的多元函数,并满足?P(ai)?1。
i?1r求极大值。——拉格朗日乘子法。 构造新函数??I(X;Y)??解方程组:
。 ?P(a) ?——拉格朗日乘子(待定常数)
iX??[I(X;Y)???P(ai)]???X??0??P(a)?P(a) ?ii?P(a)?1?i??XI(X;Y)???P(ai)P(bj|ai)logi?1j?1rsP(bj|ai)P(bj) P(bj)??P(a)P(bii?1rj|ai)
P(bj|ai)??logP(bj)?[lnP(bj)]loge?loge
?P(ai)?P(ai)P(bj)?P(bj|ai)logj?1sP(bj|ai)P(bj)???P(ak)P(bj|ak)logk?1j?1rrsP(bj|ai)P(bj)sloge???0
(对i?1,2,?,r均成立)(
?P(ak?1k)P(bj|ak)?P(bj)
?P(bj?1j|ai)?1 i?1,2,?,r)
P(bj|ai)?sP(b|a)log???logeji??P(bj)?j?1 ?r?P(a)?1?i??i?1假设解得使平均互信息I(X;Y)达到极值的输入概率分布为{p1,p2,?,ps}({pi}或P)
??P(bj|ai)logi?1j?1rsP(bj|ai)P(bj)e ???loge C???log39
令I(xi;Y)??P(bj|ai)logj?1sP(bj|ai)P(bj)
——输出端接收到Y后获得关于x?ai的信息量,即信源符号x?ai对输出端Y平均提供的互信息。
I(xi;Y)?C (i?1,2,?,r)
Th 3.3 一般离散信道的平均互信息I(X;Y)达到极大值(即等于信道容量)的充要条件是输入概率分布{pi}满足??(a)I(xi;Y)?C对所有xi其pi?0?(b)I(xi;Y)?C对所有xi其pi?0
?I(X;Y)?(a)??对所有xi其pi?0??pi?或? (*)(I(X;Y)简写成I(P) ?(b)?I(X;Y)??对所有x其p?0ii??pi?证明:(充分性?)
假设有一输入概率分布{pi}?P满足(*)式,证明分布{pi}一定使平均互信息I(P)达到极大值,即证明对于任何其它输入概率分布Q?{qi},有I(Q)?I(P) 设0???1,?I(Q)?(1??)I(P)?I[?Q?(1??)P]
I(Q)?I(P)?{I[?Q?(1??)P]?I(P)}?ri?1
??0时,I(Q)?I(P)??(qi?pi)因为P满足(*)式,即当pi?0时,
r?I(P) ?pi?I(P)?I(P)??;而当pi?0,(qi?pi)?qi?0时,??。 ?pi?pirr所以得:I(Q)?I(P)???(qi?1i?pi)??[?qi??pi]?0?I(Q)?I(P)
i?1i?1(必要性?)假设有一输入概率分布P使I(X;Y)达到极大值I(P),证明概率分布P满足条件式(*)。
设任一其他概率分布Q?{qi},有:I[?Q?(1??)P]?I(P)?0,0???1 上式除以?,并取??0的极限,得:
?(qi?pi)i?1r?I(P)?0 ?pi 40
对于{pi},因为
?pi?1i?1,所以至少有一分量pi?0,令pl?0。选择另一种概率分布
?ql?pl???Q?{qi}满足?qi?pi (i?l,j) ?为任意数,满足?pj???pl。
?q?p??j?j于是,
?(qi?pi)i?1r?I?I?I??I???0 令??? I(P)?0变为:???? 得:??pl?pj?pj?pi?pl?I??。 ?pj?I?I??;若取负数,得?? ?pj?pj因为pl?0,所以当pj?0,?总取正数,得
若pj?0,?可取正数,也可取负数。若取正数,得
故当pj?0,
?I?? 满足(*)式条件。 ?pj结论:当信道平均互信息达到信道容量时,输入信源符号集中每一个信源符号x对输出端Y提供相同的互信息,只是概率为零的符号除外。 例3.8 (P100) P3.9 (P101)
对于一般的离散信道,很难利用Th3.3来寻求信道容量和对应的输入概率分布。因此仍只能采用求解方程组的方法。
P(bj|ai)?s??P(bj|ai)logP(b)???loge?j?1j ?r?P(a)?1?i??i?1?P(bj?1ssj|ai)logP(bj|ai)??P(bj|ai)logP(bj)?C (i?1,2,?,r)
j?1s?P(bj?1j|ai)[C?logP(bj)]??P(bj|ai)logP(bj|ai) (i?1,2,?,r)
j?1s令?j?C?logP(bj),得:
?P(bj?1sj|ai)?j??P(bj|ai)logP(bj|ai)
j?1s设r?s,信道传递矩阵P是非奇异矩阵,则此方程组有解。可求出?j的数值。
C?log?2j?j?C (比特/符号)
P(bj)?2?j?C (j?1,2,?,s) ? {pi}
例3.10 (P102)
41
3.6 离散无记忆扩展信道及其信道容量
离散无记忆信道的输入符号集A?{a1,?,ar},输出符号集B?{b1,?,bs},信道矩阵为:
?p11?pP??21????pr1p12p22?pr2p13???p23?pr3?p1s?sp2s?? 且?pij?1 (i?1,2,?,r) ??j?1?prs?则此无记忆信道的N次扩展信道的数学模型:
NN输入随机序列X?(X1,X2,?,XN),Xi可能取值:r个;输出随机序列Y的可能取值有s个。
XN?1?(b1b1?b1)??(a1a1?a1)??1??(aa?a)????(bb?b)?11?211222NP(?|?) ??Y hk?????(arar?ar)??N?sN?(bsbs?bs)?r????11?12??1sN???????N2122N2s? ?kh?P(?h|?k) (k?1,2,?,r????????????rN1?rN2??rNsN??h?1,2,?,s)
N??h?1sNhk?1
?k?(akak?ak) ak?{a1,a2,?,ar} (i?1,2,?,N)
12Ni?h?(bhbh?bh) bh?{b1,b2,?,bs} (i?1,2,?,N)
12Ni?kh?P(?h|?k)?P(bhbh?bh|akak?ak)??P(bh|ak)
12N12NNi?1ii例3.11 (P112)
无记忆信道的N次扩展信道的平均互信息:
I(X;Y)?I(XN;YN)?H(XN)?H(XN|YN)?H(YN)?H(YN|XN)
?XN,YN?P(??kh)logP(?k|?h)P(?h|?k)??P(?k?h)log
P(?k)P(?h)XN,YNTh3.5 若信道的输入随机序列为X?(X1X2?XN),通过信道传输,接收到的随机序列为
Y?(Y1Y2?YN)。假若信道是无记忆的,即信道传递概率满足P(?h|?k)??P(bhi|aki)
i?1N 42
(k?1,2,?,rNh?1,2,?,s),则存在I(X;Y)??I(Xi;Yi)。
NNi?1证明:设信道输入和输出随机序列X和Y的一个取值为:
?k?(akak?ak) ak?{a1,a2,?,ar} (i?1,2,?,N)
12Ni?h?(bhbh?bh) bh?{b1,b2,?,bs} (i?1,2,?,N)
12NiI(X;Y)??P(?k?h)logX;YP(?h|?k)P(?h|?k)?E[log]
P(?h)P(?h)P(?h1|?k1)P(?h2|?k2)?P(?hN|?kN) I(X;Y)?E[log]
P(?h)P(bhi|aki) ?I(Xi;Yi)???P(akibhi)log
P(b)i?1i?1Xi,YihiNN ?X1,Y1?P(a?k1h1b)logP(bh1|ak1)P(bh1)?X2,Y2?P(a
k2h2b)logP(bh2|ak2)P(bh2)???
XN,YNP(akNbhN)logP(bhN|akN)P(bhN) ?X1,Y1??????XN,YNP(ak1?akNbh1?bhN)logP(bh1|ak1)?P(bh2|ak2)?P(bhN|akN)P(bh1)?P(bh2)?P(bhN)
?E?logNP(bh1|ak1)?P(bh2|ak2)?P(bhN|akN)??
P(bh1)?P(bh2)?P(bhN)??I(X;Y)??I(Xi;Yi)
i?1?P(bh1|ak1)?P(bh2|ak2)?P(bhN|akN)P(bh1|ak1)?P(bh2|ak2)?P(bhN|akN)??E?log?log?
P(?)P(b)?P(b)?P(b)??hh1h2hN??P(bh1)?P(bh2)?P(bhN)???E?log?
P(?h)??P(bh1)?P(bh2)?P(bhN)?P(bh1)?P(bh2)?P(bhN)??logE? ??log?P(?k?h)P(?)P(?)X,Yhh???log?P(?k|?h)P(bh1)?P(bh2)?P(bhN)?log?P(bh1)?P(bh2)?P(bhN)?log1?0
X,YY 43
即得:I(X;Y)??I(X;Y)。当信源无记忆时,等号成立!
iii?1NTh3.6 若信道的输入随机序列为X?(X1X2?XN),通过信道传输,接收到的随机序列为
Y?(Y1Y2?YN),而信道的传递概率为P(y|x),假若信源是无记忆的,则存在
I(X;Y)??I(Xi;Yi)。
i?1N证明:
I(X;Y)??P(?k?h)logX;YP(?k|?h)P(?k|?h)?E[log]
P(?k)P(?k)?k?(akak?ak) ak?{a1,a2,?,ar} (i?1,2,?,N)
12Ni?h?(bhbh?bh) bh?{b1,b2,?,bs} (i?1,2,?,N)
12Ni P(?k)?P(ak)P(ak2)?P(akN)
?1 I(X;Y)?E[logP(?k|?h)]
P(ak?1)P(ak2)?P(akN)
P(aki|bhi) I(Xi;Yi)???P(akibhi)log?P(aki)i?1i?1Xi,YiNN ?X1,Y1??XN,YN?P(ak1?akNbh1?bhN)logP(ak1|bh1)?P(ak2|bh2)?P(akN|bhN)P(ak1)?P(ak2)?P(akN)
?P(ak1|bh1)?P(ak2|bh2)?P(akN|bhN)? ?E?log?
P(a)?P(a)?P(a)??k1k2kN??P(ak1|bh1)?P(ak2|bh2)?P(akN|bhN)??I(Xi;Yi)?I(X;Y)?E?log??
P(?|?)i?1kh??N?P(ak1|bh1)?P(ak2|bh2)?P(akN|bhN)??logE??P(?|?)kh??
?log?P(?k?h)X,YP(ak1|bh1)?P(ak2|bh2)?P(akN|bhN)P(?k|?h)?log?P(?h)P(ak1|bh1)?P(ak2|bh2)?P(akN|bhN)X,Y 44
正在阅读:
西安电子科技大学信息论与编码理论讲义09-30
档案分类方案及编号标准03-23
应对新常态下的新挑战07-19
加强纪律作风建设 促进公正廉洁执法04-06
汽轮机AST遮断详解07-10
2022年山西高考392分能报什么大学 392分能上哪些院校03-29
新点子02-18
把握新常态下湖南林业新业态04-24
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 西安电子科技大学
- 信息论
- 讲义
- 编码
- 理论
- 2009-2016年税务执法资格考试真题-地税卷(含答案) - 图文
- 特殊教育学校汇报材料
- 吉林省人民政府办公厅关于切实提高省级专项资金精准性和有效性的意见
- 风区附加线肩架安装及架设技术交底04
- 2009年11月心理咨询师三级技能真题
- 五年级品德与社会上册一二单元复习1
- 散打教学设计 - 图文
- 数与代数整理与复习
- 2018咨询工程师继续教育-PPP政策解析及制度建设试卷答案-3套
- 老年大学开学典礼致辞(精选多篇)
- 蒂森负载称重装置LMS1调试说明
- 第七章国民收入决定理论:简单凯恩斯模型,浙大远程金融学作业
- 增大无效腔对家兔呼吸运动的影响 - 图文
- 玄武岩纤维复合筋工程案例及反馈情况 - 图文
- 题组一漫画类图文转换
- 大工14春《楼宇自动化》辅导资料四
- 轿车公司全新车型开发流程
- 数据库上机实验报告
- 教育行政执法的原则
- 移相全桥变换电路尖峰产生及抑制机理研究