实验复习信息论和编码

目第1 信息的定性描 对信息的初步认 信息社 信息的普遍 信息论的发 信息的本 信息论与信息科 第1章小 第1章习 附录1A香农——信息论之 第2 信息的定量描 信息的传 2. 信息的度 两个关 两条公 信息量定义式的导 2. 信源的 离散信源的 连续信源的 2. 信道容 离散信道的信道容 连续信道的信道容 . 香农定 第2章小 第2章习 附录2 运算中用到的........................................................................................附录2 熵函数计算用 附录2 线性可加的连续函数是可微 附录2 信息熵与热 附录2 互熵的凸凹 附录2 转移概率矩阵可逆时信道容量的计 附表2 信道容量计算程 附录2 复合信道的信道容 附录 反相对称法原 第3 信源编 1基本概念53. 二态检验与最佳编 二态检 费诺（Fano）编码 哈夫曼（Huffman）编码 香农（Shannon）编码 单义代 信源编码定 匹配编码和匹配定 信源编码基本定 利用关联压缩码 联合 条件 实用编码方法介 变换编 识别编 第3章小 第3章习 附录 几种文字符号的频率统 附录 信源编和译.....................................................................................附录 信源编码程 附录 编码容量及其计算方 附录 高次方程的数值解法程 第4 抽象代数基 代数结构——群、环、 集 代数结 环和 模p运 向量空间和矩 向量空 子空 基底和维 线性变 对偶空间（正交补空间 多项式及多项式 多项式的基本概 多项式的性 多项式的模p(x)运 第4章小 第4章习 第5 信道编 信道编码的基本概 有扰信 信道编码的基本思 信道编码的分 514常用的差错控制方法.........................................................................12分组码和信道编码定 521分组码的概念......................................................................................12522几种简单的分组码.............................................................................13523分组码的纠检错能力.........................................................................13524完备码与汉明界..................................................................................13525信道编码定理（香农第二编码定理）........................................13线性分组 531线性分组的定义和性质....................................................................14532线性分组码的构造原理和生成矩阵.............................................14533线性分组码的监督矩阵和伴随式..................................................14534生成矩阵与监督矩阵的关系...........................................................14535线性分组码的译码.............................................................................15循环 541循环码原理...........................................................................................15542循环码编、译码的实现....................................................................16543循环码的性质......................................................................................16544实际的循环码......................................................................................16卷积 551卷积码的编、译码过程....................................................................16552卷积码的构造原理.............................................................................17第5章小 第5章习 第6 信息率失真理 基本概 失真函 信息率失真函 631信息率失真函数的定义....................................................................18632率失真函数的性质.............................................................................18率失真函数R(δ)的计 连续信源的信息率失真函 651失真函数................................................................................................20652信息率失真函数..................................................................................20第6章小 第6章习 参考文 上过的，但还有待讨论，因此也将其放在了附录中编著2015111对信息的初步认近年来，移动、个人电脑和因特网正以高于摩尔定律①的速度迅猛增长，我国联网进行社会活动就需要有信息交流。例如，除了书信、、电报之外，天天都要同许多人交境活动，是保证机体的重要因一。每当一个婴儿来到上，他就时时刻刻与种本领也就越高超。鸽子利用地磁来辨别方位；通味来分辨地域；鸟、不同的Wiener础。香农于1948年了一篇著名的 重新回到那些与信息论的本源密切联系的领域。2050年代至60人们在调制解60、等，高没有香农信息论，就不会有今天覆盖全球的移动系统，没有香农信息论就不会有连接全信息的本⑴首先哈特莱(R.V.Hartley)在1928年的《信息的传输》(TransmissionofInformation)奥运会开幕式早已结束，而它的却可以随时随地。这就是信息的独立性。物质、能量和信息事物的三个基本方面，。例如：一个人具有、体信息论与信息息和更好地利用信息，并为信息科学和提供必要的理论依据和正确的方向。数学称“老三论”（SCI。它们都是从整体上把握事物的规律的。人们在长期实践的基础上研究基于内容的信息理论，以适应网络智能化和的要求。突破香农信息论1小一二.信息的特征三.四.消息、信号与信息的区别五.物质、能量与信息的关系六.信息论与信息科学.1习1A香农——信息论之克劳德·艾尔伍德·香农(ClaudeElwoodShannon，1916-2001)，1916年4月30日生于密西根州的盖洛尔夫·香农(MabelWolfShannon)是镇里的中学校长。香1936年香农在密西根大学获得数学与电气工程学士，然后进入麻省理工学院攻读。1938年香农在麻省理工学院获得电气工程学位，题目是《继电器与开关电路的符号分析》(ASymbolicysisofRelayandSwitchingCircuits)，把布可能是本世纪最重要、最著名的一篇。”

ClaudeElwoodShannon (AnAlgebraforTheoreticalGenetics)。后来他在不同的学科方面过许多有影响的文章。 《微分分析器的数学理论》(Mathematicaltheoryofthedifferential 1941年香农以数学研究员的进入新泽西州的电报公司(AT&T)的贝尔实验室(BellLab)197231年。香农与约翰·瑞尔丹(JohnRiordan)一起工作，1942年了一篇关于串并联网络的双终端数的。这篇扩展了麦克马洪(PercyAMaccMahon1854-19291892年在《电工》(Electrician)上的的理论。1948年香农在《贝尔系统技术》(BellSystemTechnicalJournal)上了长达55页 《通信的数学理论》(AMathematicalTheoryofCommunication)， 同署名(注：该 Weaver，1894-1978)当时是洛克菲勒自然科学部的，他为文章写了序言，后来，研究信息论的哲学问题。1949年，香农又在该上了另一篇著名 (CommunicationinPresenceofNoise)。在这两 中，香农阐明了通信的基本问题，给编码、信道编码等一系列基本问题。这两篇是信息论的奠基性著作。国进行闪电战的消息。1949年，香农发还表了另外一篇重要《系统的通信理论》(CommunicationTheoryofSecrecySystems)，它使通信由艺术变成科学。驱动3个一起玩11个环、7个球和5个棍子。香农的平衡技巧是十分有名的，他经常和贝尔度过。香农曾获得过许多和荣誉，例如1949年Morris奖，1955年Ball 奖，1962年年基础科学奖。他曾是、工程院、英国学会会员、哲学学表的讣告都尊崇香农为信息论之父和数字通信时代的奠基人。香农的塑像与的发明人贝尔的塑像一起耸立在贝尔大厅处。他的事迹已经载入贝尔的展览厅中。2信息量I，并建议，当这m个符号等概出现时，用I=nlgm作为信息量的计算。莱的扩展到概率pi不相等的情况，得到了著名的计算平均信息量（熵）的：H=－pilog2 是，给出信息传输基本数学模型的人物是香农。他的这篇创立了信息论这门学科。功，并且一直指导着的发展。信息的传信息传输的方式是多种多样的。例如，日常生活中最常见的有打、写书信、带口信等等。在这些场合，通信的双方都是人，不过信息传输的途径各不相同。在打的场合，传输途径是系统；在写书信的场合，传输途径是邮递系统；而在带口信的场合，传输途噪信信信噪信信信

（电线、光纤、电磁场者把噪声与干扰区分开来，而国内则不加区分，对噪声的进一步讨论详见第55.1.1。往往需要进行编码和译码。于是我们给出一个完整的信息系统模型，如图2-2所示。 2-2 信息的度我们在发或在网上聊天时，总是设法用较少的字数来表达一件事情，这属于信源编码的 巨大的难题。要对信息进行定量描述，将会遇到极大的。息量的定义式，继而构筑整个香农信息论这座。I(x)=f[p(x)]为连续减函数，p(x)∈[01⑴A.一辆汽车停在大树旁 ⑵A.早上从东方升起 A.八月份的天气预报：明天有雨；B.⑷A.班上的优等生张三考了95分 象非常罕见，它为“夏商周工程”提供了宝贵的资料，为《夏商表》的完成起合消息x所含的信息量等于各所含信息量的和。用数学式子来表达就是： x=x1x2…xm，且p(x)=p(x1)·p(x2)·… I(x)=I(x1)＋I(x2)＋…＋I(xm) =+ I(x)=－loga f(p)=f(p1)＋f(p (2-不妨设p2=1，代入上式得 f(p1)=f(p1)＋f(1 (2-上式两边消去f(p1)后得 f(1)=0 ⑴当p1≠0时，可得：f＇(p1)=C0/p1 此时令p1=1，再利用式(2-5)得：f(1)=C1=0 f(p1)=C0ln 由公1f(p1)为减函数，∴必有C0＜0，不妨C0－k，代入上式f(p1)=－klnp1=－ln(p1令a=e1/k，利用换底可得f(p1)=－logap1；p1∈(0,1]（半开区间p1

f(p1)limlnp1p1因此补充定义：p(x)=0时，信息量I(x为无穷大。I(x)=f[p(x)]=－logap(x bit；nat；（Hart0、1p0p1)05，则每个消息所含的信I=log20.5=1比特。可见这早在1928年就以a=10来计算信息量，因此以名的单位“Hart”的首字母要大写。xp(x)，则此消息所含的信息量为：Ix)=logpx)I（汉字）=logp=log10000)13.3比特。每一份电报报文均10个汉字构成，它们的信息量为I（1）=I（2）=10I（汉字）=133比特。甲I甲=－logp甲=－log1/646I乙=－logp乙=－log1/42丙I丙=－logp丙=－log1/16)4 I甲=I乙＋I丙=6比特IB=－logpB=－log(1/2)=1比特。IC=－logpC=－log1/21pA=pB·pC=(1/2)×(1/2)=1/ IA=－logpA=－log142比特。显然A所提供的信息量为B、C所提供的信息量之和，即：IAIB＋IC信源的中各个消息所含信息量的以概率为权的平均值，用H表示。mH(X)pilog

比特/消 其中：X={x1x2…,xm}为信源消息的集合，m信源消息的概率场可记为：P(Xp1p2…,pm}，piixi学的平均。再求平均：Y=627/30=20.7(岁/人p1=3/30=0.1p2=15/30=0.5，p3=12/30=0.4；再求平均：Y=0.1×22＋0.5×21＋0.4×20=20.7(岁/人) H(X)=0.25log0.250.25log0.25－0.5log0.5=1.5比特/颜色9 H(X)pilogpi3.055（比特 数字 HX) pilogpi4.065（比特/英文字母iH(X)≤logm（比特/消息 mp1p2=pm=1mpi1i此时，任取一球猜测其颜色的程度为H(X)=－(1/3)log(1/3)－(1/3)log(1/3)－(1/3)log(1/3)=log3=1.585＞1.5（比特/颜色⑵当10个数字等概出现时，H(X)=log10=3.322＞3.055（比特/数字27个英文字母（1个空格）等概出现时，H(Xlog274.755＞4.065（比 [引理1] pi1，qi1；且pi0,qi0;i1,2,, pilogpipilog i ipi=qii=12,,m)证：p1个q1p1)p2个(q2p2)pm个qmpm)，取它们的几何平均值及pi(q/p)p1(q/p p(q/p)p(q/p1 m i i

(2-piqi∵=1m)∑pi=1，∑qi(q1/p1)p1…(qm/pm)pm≤∑pilogqi－∑pilogpi≤—∑pi=pilogpipilog1/m)=log当且仅当pi=qi(i=1,2,…,m)时，上式才取等号。 特别当m=2时，有：H(X)=－p1logp1－p2logp2log21（比特/消息p1p2=1p1=pp2=1pHXp的一元函数，上式化为：H(p)=－plogp－(1－p)log(1－p)≤ lim(plnplimlnplim1plimp0可以证明，当p→０时，p p0 p01 p因此可H0)=0。同理可得H10。而p=0.5时，H(0.5)=1比特/消息，为最大熵。H(p)的图像如2-3所示。附录2B中给出了H(p)的数值表。相传古埃及在执行前会让犯人抓阄。抓到那个阄了。

H(H(2-3Hp)的图

x1(x1(tx2(txm(t),),x2(t),…由于发送的消息是随机的且可以表示为 … X(t)={x1(t),x2(t),…,xm(t),…例如：X(t1)={x1(t1),x2(t1),…,xm(t1),…}X(t2)={x1(t2),x2(t2),…,xm(t2), X(tn)={x1(tn),x2(tn),…,xm(tn),

2-4即：Xt)={Xt1),Xt2…,Xtn),…}=xqk用圆圈“”表示。当xk落入某个量化{Nk{Dk}={010101111101011010100用8位二进制数来表示，而不是3位。值落在Δxi范围内的的概率为：

x(tx(t)3

Dp(xi)=px∈Δxi}f(xi)·Δxi。mH(X)f(xi)Δxilogf(xi)Δxi

比特/样 然后再令Δxi→0，m→∞，取极限，即可得到连续信源的 H(X)limf(xi)Δxilogf(xi)Δxif(x)dxlogf(x)Δ

i f(x)logf(x)dxf(x)log(Δ 比特/样 我们定义上式中第一项为连续信源的相对熵，用H1X)来表示，H1(X)f(x)logf(x)dx比特/样 而将上式中第二项称为连续信源的绝对熵，记作HΔ(X)，HΔ(X)f(x)log(Δx)dx比特/样 当Δxi→0时，HΔ(X)→∞。这个无穷大的量给我们的计算带来了不便。但在大多数实熵来代表连续信源的熵。为便于积分，可取对数的底为e，这时熵的单位为奈特/样值。H1X)fx)lnfx)dx/样需要注意，H1X)是一个相对量，它与离散信源的熵有区别。在离散信源情况下，当概率确H1X)=1（bit/样值。而当把它用一个线性放大器2倍之后，所得f(x)=1/(ba)

H1(X)=ln(b－a)奈特/样 当信号平均功率受限为σ2f(x) exp(x2/2σ2H1(X)

2e

奈特/样 此时最佳概率密度函数f(x)为：f(x)=1/(b-a)，[a<x<b] H1max=ln(b－a)(nat/样值 h(x)f(x)f

(x)h(x)λϕ(ϕ(x)1

f(x)dx

(x)0f( f(x)lnf(x)λf(x)dxf(x)

G(x)dxG(x)dx f(x) f(

G(x)f

f(x)lnf(x)λff1lnf(x)λ f(x)=beλ1dxeλ1(ba) f(x)=eλ－1 H1maxmax dxln(bb b 此时最佳概率密度函数f(x)为： 1 f(x) exp(x2/2σ2

H1

ln(2πeσ)1/

h(x)f(x)lnf ϕ(x)f(x)x2dxσ

(平均功率σ2 ϕ2(x)f(x)dx (等周条件 Φ(x)= Φ(x)f f(x)lnf(x)λf(x)x2λf(x)dx f(x) 设被积函数G(x)，则

G(x)dxG(x)dxf(x) f(f

f(x)lnf(x)λf(x)x2λff 1lnf(x)λ1x2λ2 f(x)=eλ2－1·eλ1x2 eλ1eλ1xdx易知λ1<0，故令

1λx2z ，dx 1ez2dz eλxdx ezdz∴

eλ21eλ1xdx

πeλ21 eλ21

π

x2eλ1eλx2dxσλ1x2eλx2dxσ λ x2eλ1x2dx xeλ1x2dλ

x2

1xd(eλ1x22λ1 1xeλ1x

eλ1x2dx2λ1 0 1

x2eλ1x2dx σ λ 2σ f(x)eλ21eλ1x2

exp(x

2σ2再代如熵函数得：H1maxmaxh(x)ln(2πeσ2)1 信源的熵。人们可能会担心用这种近似来计算连续信源的熵是否可行。下面我们就来讨离散消息的方法来分析连续消息了。这实际上就是我们所熟悉的A/D转换过程。虽然抽样不会产生误差，但是量化必然会带来误差。量化间隔Δx越大，用式(2-14)x p(y1/x1)x p(y/x)

2

2p(ym/xm)

信息速率和信道容离散信道可分为无扰离散信

无扰离散信p(y1/p(yn/p(yn/p(yn/p(yn/

2-5离散信道模型R收。它们满足下面的关系式：R传=R收=R发－R C=max｛R传｝=max｛R发－R误 p(yj/xj)=1p(yj/xi)=0(i≠j)R发=rH(X)比特/ CmaxrH(X)2BlogP(X

比特/ r=2fH= p1p41/8，p2=p3=3/84 H(X)pilogpi

比特符 R发=rH(X)=8000×1.8=14.4千比特/此时信道所允许的最大符号速率为rmax=2B=8000符号/秒。p1p2p3p41/4 Hmax(X)=log4=2比特/符号 C=Rmax=rmaxHmax(X)=16千比特/秒在有扰信道中，噪声的存在会使信息传输受到损R误＞0R发＞R传=R收，传信率小于发RR收，二者是同一个概念。R=R发R误，所以要想提高传信率，不能只考虑提高R发，同时还要考虑降低R误，最终目的是使二者的差值最大。具有一定的统计关联，并且反映在信道的转移p(y/x)上。我们用信道的转移概率来描述信p(xj/yj)1p(xi/yj)0（i=1,2,,mj=1,2,,n;i I(xi)=－logp(xi)比特。我们称I(xi)为自信息量，简称信息量，称概率p(xi)为先验概率 仍存在着不定它的大小I(xi/yj)由 I(xi/yj)=－logp(xi/yj)比特我们称I(xi/yj)为条件(自)信息量，称条件概率p(xiyj)为后验概率Ixi)与条件自Ixi/yj)之差定义为互信息量，记Ixiyj)。简I(x;y)I(x)I(x/y)logp(xi/yj 比 i p(xi它表示收到的yj为我们提供的关于xi的信息量，即信宿所获得的信息量，也就是此时信对所有发送xi而收yj的互信息量I(xi；yj)取统计平得到平均互信息互熵 p(xi/yjI(X;Y)p(xiyj) p(x 比特/符 i1j I(X;Y)=H(X)－H(X/Y)比特/符 )= H(X/Y)p(xiyj)logp(xi/yj)比特/符 i1jH(X/Y)是一种条件熵，也就是当信宿收y后，对信源x仍不确定的程度，故又称为疑义度。它表示信道每传输一个符号所损失的平均信息量，H(X/YR误。若要信宿收到某一个符号yj后，对信源符号x仍不确定的程度，则用下面的条件熵

mH(X/yj)i

p(xi/yj)logp(xi/yj

比特/符

(2-H(X/Y)称为整体条件熵，而H(X/yj)称为局部条件熵。可以证明nH(X/Y)p(yj)H(X/yj

由式(2-26)可知，I(X;Y)就是信道每传送一个符号所传输的平均信息量，即I(X;Y)=R传R传=I(X;Y)=H(X)－H(X/Y)比特/符 (2-r(符号/秒)R传=rI(X;Y)=r[H(X)－H(X/Y)]比特/ 可使R传达到最大值。因此，有扰信道的信道容量可由下式给出：CmaxRmaxrHXHX/Y

P(X) P(X当噪声很大时，H(X/Y)H(X)R传→0。当无噪声时，H(X/Y0R传=rH(X)。和信道的转移概率PYX)I(X;Y)=H(YH(Y/X来计算互信息量会更方便：I(X;Y)=H(X)H(X/Y)=H(Y)H(Y/X)

2-6

散布度=噪声的熵，后面将有详细论述) C1＋qlogq＋(1－q)log(1－q)比特/符号其中q为错误概率。

2-8 为了简便，设p(x1)=t，p(x2)=1－ p(x1y1)=t(1－s)，p(x1y2)=ts，p(x2y1)=0，p(x2y2)=1－p(y1)=t(1－s)，p(y2)=1－t(1－ H(Y)=－p(y1)logp(y1)－p(y2)log=－t(1－s)logt(1－s)－[1－t(1－s)]log[1－t(1－H(Y/X)p(xy)logp(y/x)t(1s)log(1s)tslogX R=H(Y)－H(Y/X)=－t(1－s)logt－[1－t(1－s)]log[1－t(1－s)]＋tslog=－t(1－s)logt－[1－t(1－s)]log[1－t(1－s)]＋tslogR＇(t)=(1－s)ln{[1－t(1－s)]/t}＋sln然后令R＇(t)=0，可解得：p(x1)=t=α/[1＋α(1－s)]，其中α=ss/(1- CP(x

Rlog1(1s)比特/符 p(x1)未必等于0.5，它随s而变。

2-1Cp(x1)s变化的过s0.0.1/0p(.CCmaxRmaxH(X)H(X/Y)P(x P(x)maxH(Y)H(Y/XP(x)RI(X；Y)H(Y)H(Y/X

(2- p(yj)lnp(yj)p(xiyj)lnp(yj/xijm p(xi)i

i1j；p(xi)0，i=1,2,…,m p(x)ΦP(x)I(X；Y)i

1

λ p(

,λ。再把所得到的最佳概率分布代入式(2-35A)，便可得信道容量C I(X；Y)=H(Y)－H(Y/XH(Y/x1)=H(Y/x2)=…=HH(Y/X)=p(x1)H(Y/x1)p(xm)H(Y/xm)=H(Y/x1)，p(x)无关。因此求I(X；Y)的最大值就变成了求H(Y)的最大值。根据最大熵定理：H(Y)=logn（n为信宿的消息个数）CmaxI(X；Y)lognH(Y/P(

(2-R=H1(X)－H1(X/Y)=H1(Y)－H1(Y/X 比特/符 (2-H1表示相对熵y(t)=x(t)＋n(tf(n/x)=f(nf(y/x)=f(n/x)=f H1(Y/x)=H1( XYf(xy)logf(y/x)dxdyXNf(xn)logf(n)dxd H1(Y/X)=H1( R=H1(Y)－H1(N)比特/样 CmaxRmaxH(Y)H(N) f(x f(x

比特/符 H1(X)ln2πeσ2 (设σ2S,为信号的平均功率 H1(N)2πeσ2(设σ2N,为噪声的平均功率(2-nn若要R最大，则要求H1Y最大，因此Y服从正态分布。可以证明，两个正态分正态分布。并且Y的平均功率等于信号功率与噪声功率之和，它的最大相对熵为：H1(Y)

2πe(SN

(奈特/样值 ))C SCln1

(奈特/样值 (2- N CCBloS(比特秒 NCCBloS(bite/秒n0为噪声的单边功率谱密度，即单位带宽内的噪声功率，单位为：W/Hz（瓦/赫兹。出第三个来。香农给出了信道传输能力的理论上界，并为工程计算带来了方便。每一像素所含的信息量为：I0=log83比特/符号 由香农求得最小带宽为： =I/log(1＋S/N)=2.25香农定加以修正（见本章末附录2H。尽管如此，香农和香农定理仍然不失其重要性。立。如果在信噪比S/N较小时，上述关系将不会太突出。（So/No）B输入fSi/输入fSi/B噪声理想解调或译码理想调制或编码f2-92-9给出了理想系统框图。设输入的信号带宽为fH(Hz)Ri(bps)。此信号Ri=Blog(1＋Si/Ni)(bit/秒 Ro=fHlog(1＋So/No)(bit/秒 Ro= Blog(1＋Si/Ni)=fHlog(1＋ (2-(1＋Si/N)B=(1＋So/N) SBoi Ni

(2-SoNo(B/fH2；在数字通信中，PCM系统信噪比的改善的确 I=T·C=TBlog(1＋S/N)bit C一定时，增加时间T可以I增加。例如，用话路传输图像信号，就可以把传输速而增强了性。由于信号加快，其带宽必然会增加，所以，这也是一种扩频的方法。它们互相转化，互相制约。在香农定理和香农中，它们得到了完整的表述。2小要在形式上原消息和解除信息的不定性。机过程的概率特性有关。当某消息发生的概率为p(x)时，这个消息所含的信息量为I(x)=logap(x)对数的底可取2、e10，相应的单位为比特bit)、奈特nat)和哈特(Hart)个消息所含信息量的以概率为权的平均值。用H表示。四.

H(X)pilogI

(bit/消息p(xi)=1/m,i=1,…,m Hmax=logf(x)= 221f(x) exp(x2/2σ2)，1

log(2πeσ2).H1f(xlogf(x)dx比特/样.量，用C表示。

R=r[H(X)－H(X/Y) CmaxRmaxrH(X)H(X/Y)P(X P(X

CmaxRmaxf( f(

(YH1N)(bit/样值 八.香农

CBlog(1SNCBlog(1S

相转换，I=C·T。SoNo(Si/Ni)BfH2习不定度为0，对吗？p10.2，p20.19，p30.18，p40.17，p50.16，p60.15 pilogpi的值。并解释为什么pilogpilog p(x1)=p(x2)=p(x1)=0.48，p(x2)=p(x1)=0.45，p(x2)=0.55 试求，该信道的最大信息Rmax，以及此时的p(x1)试证：H(X)－H(X/Y)=H(Y)－H(Y/X) 60%1012051日的天气预

传送这张至少需要多少小时若信道带宽增加到原来的4比为30分贝）（其中：x1~缺席，x2~出席，y1~吸烟，y2~不吸烟。p(x1)=0.1，p(x2)=0.9，p(y1)=.)=（一）概

2A运算中用到 p(xy)=p(x)p(y/x)=p(y)p(x/xy相互独立时，p(xy)=p(x)p p(y)p(x)p(y/Xp(x/y) p(x)p(y/p(x)p(y/X I(x)=－logp( H(X)p(x)logX I(x/y)=－logp(x/y H(X/Y)p(xy)logp(x/X I(xy)=－logp

H(XY)p(xy)logXI(x；y)logp(x/I(X；Y)p(xy)logp(x/X I(X；Y)=H(X)－H(X/Y)=H(Y)－H(Y/X2B熵函数计算熵函数的计算：H(p)=－plogp－(1－p)p-plog(1-—2C线性可加的连续函数是可微则f(x)是可微的。b又已知x＞0，y＞0，不妨设b

af(x)dx af(xy)dyaf(x)dyaf(y)dy(ba)f(x)Af(x)bf(xy)dyA(ba) 为此，令xy=t，得xdy=dtbf(xy)dybxf(t) 10f(t)dt f

x 1bxf(t)dtaxfx 2D信息熵与热universe孔的分子，让快速分AB，慢速分BA，这样就把气体按照速度分成了两个部多的系统是开放的；当第二定律认为这种封闭的系统由于熵增的结果会无序、2E互熵的凸凹IX；Yp(xylogp(x/X p(xy)logp(y/X p(p(x)p(y/x)X

p(y/p(x')p(y/x'X

(2E-)I(X；YI(P；Q)Q(y/xP(y/x))先证明(A)：I(X；Y)是信源概率分布P(x)的凸函数。)*I(P1；Q)＋(1－λ)I(P2；Q)≤I[λP1＋(1－λ)P2；Q](2E-式中 P2]也是信源概率分布 I(P；Q)=H(Y)－H(Y/X H(Y)p(y)logp(Y p(y)p(x)p(y/X

(2E-(2E-H(Yp(x) p(x)=λp1(x)＋(1－λ)p2 p1(y)p1(x)p(y/Xp2(y)p2(x)p(y/X [－plogp]″=[－1－logp]′= H(Y)λp1(y)(1λ)p1(y)logλp1(y)(1λ)p1(Yλp1(y)logp1(y)(1λ)p2(y)logp2( λH(Y1)(1λ)H(Y2 H(Y/X)p(xy)logp(y/Xp(x)p(y/x)logp(y/X

(2E-)(2E-6)，(2E-7)，(2E-8)(2E-3)(2E-2)I(X；Y)P(x)的凸函数。再证明(B)：I(X；Y)是信道转移概率P(y/x)的凹函数。.I[P；λQ1＋(1－λ)Q2]≤Λi(P；Q1)＋(1－λ) ] p(y)p(x)Q(y/Xp(x)λQ1(y/x)(1λ)Q2(y/Xλp(x)Q1(y/x)(1λ)p(x)Q2(y/ λp1(y)(1λ)p2( I(P；Q)p(x)Q(y/x)logQ2(y/ X p2( I(P；Q)p(x)Q(y/x)logQ1(y/ X p1( pilogpipilog loga≤ I(P；Q)λI(P；Q)(1λ)I(P；Q p(x)λQ(y/x)(1

(y/x)logQ(y/1XY

Q1(y/

p( p(x)Q(y/x) X p1((1λ)p(x)Q(y/x)logQ2(y/x) p( X 1λp(x)Q(y/x)logQ(y/x)p1(y)1X Q1(y/x)p((1λ)p(x)Q(y/x)logQ(y/x)p2(2X Q2(y/x)p(2 p(x)Q(y/x)Q(y/x)p1(y)

Q(y/x)p(X (1λ)p(x)Q(y/x)Q(y/x)p2(y) X

(y/x)p( p(x)Q(y/x λ p1(y)p(x)Q1(y/x)Y

p(y (1λ)

p(x)Q(y/xp(y) p(x

(y/xY

p(y λp1(y)p1(y)(1λ)p2(y)p2(y) 附录 转移概率矩阵可逆时信道容量的计 q1m Q

(q

2mji qm

qmmm hjqjiH(Y/xi

meh dkq j

m Clnj

(nat符号而此时的信源概率分布为：p(xk)=dke－Ck=1,2,mRI(X；Y)H(Y)H(Y/X mp(yj)lnp(yj)p(xiyj)lnp(yj/xi (2F-j i1jm p(xi)1i

i=1,2,…,m (2F-

Y)λmp(x)

I(

i

∵I(X；Y)P(x) 0p(xk

k=1,2,…,mH(Y/X) p(x)H(Y/x)H(Y/x

i i1 )H(Y) jp(x p(x)p(j

)lnp(

j k j m p(yj)p(xi)p(yj/xi H(Y)H(Y)p(yjp(xk p(yj)p(xkmj

m

lnp(yj

p(yj/xk

1p(yj/xk)lnp(yjjm

1p(yj/xk)lnp(yj)H(Y/xk)λk)jk)

；k=1,2,…,mm 1λp(yj/xk)lnp(yj)H(Y/xkj

m 1λp(yj/xk)lnp(yj)H(Y/xkj此式两边乘以p(xk)，并k1~m求和，可得 m (1λ)p(xk)p(yjxk)lnp(yj)p(xk)H(Y/xkk k1j k 1－λ=max[H(Y)－H(Y/X)]=maxI(X；Y)= (2F-m将式(2F-5)代入式(2F- p(yj/xk)1j其中：k1,2,…m

mmj

p(yj/xk)Clnp(yj)H(Y/xk

(2F- p(y1/x1 p(y2/x1 p(ym/x1)p( PP(y/x)

1/x2 p(y2/x2 p(ym/x2) p(y/

p(

/x) p(

/x m∴式(2F-6)又可写为

Clnp(y1) Clnp(y

H(Y/x1) H(Y/x P 2 2 Clnp(

H(Y/x m m Clnp(y1) H(Y/x1) h1Clnp(y) H(Y/x) h 2Q 22 Clnp(ym H(Y/xm hm C＋lnp(yj)=hj；j=1,2,…,m p(yj)= (2F-两边同乘以eC

1ehjCj1mmmeCejm Clnehj

ln(eh1eh2ehm 将式(2F-5)代入式(2F-7)可求得pyj)，j1,2,…mm p(yj)p(xi)p(yj/xii

，j=1,2,…,m [p(y1),p(y2),…,p(ym)]=[p(x1), [p(x1),p(x2),…,p(xm)]=[p(y1),m p(xk)p(yj)qj

(2F- p(x) ehjCj

e ehjj

eC (2F-2G信道容量计算程/*name:channel_capacity#include<stdio.h>#include<math.h>constfloatln2=0.;{ /*printf("\n\nentern<10:");

for(j=1;j<=m;}}for(j=1;j<=m;j++)}for(k=1;k++){for(i=1;i<=m;i++){if(i!=}}}if(fabs(det)<=1e-6{printf("\nerror1");}c2:elsea[i][j]=0.0;}/*inversematrix*/for(k=1;k<=m;k++){for(i=1;i<=m;i++){if(i!=}}}printf("\ninversematrix");fprintf(fp,"\ninversematrix");for(j=1;j<=m;j++){q[i][j]=a[i][m+j];}}}

s1=s1+p[i][k]*(p[i][k]>0?log(p[i][k]):0.0);} j]=exp(h[j]);s=s+}if(d[k]<=1e-6){printf("\nerror}c5:for(j=1;j<=m;j++) printf("\nC=%f(nat)=%f(bit)",c1,c2);fprintf(fp,"\nC=%f } for(j=1;j<=m;j++){}}/*maininverse--h1=-h2=h3=h4=-d1=d2=d3=d4=C=0.916291(nat)=1.321928px1=0.133333px2=0.366667px3=0.366667px4=0.133333py1=0.100000py2=0.400000py3=0.400000py4=0.100002H复合信道的信道容中信1的转移概率矩阵为P(y/x)2的转移概率矩阵为P(z/y)，可求得串联信道的转移概率矩阵为：P(z/x)=P(y/x)·P(z/y).

XXZAAB因：p(z/xy)=p(z/y)（p(xyz)＞0） p(x/zy)p(xyz)p(z/xy)p(xy)p(z/y)p(zy)p(xy)p(x/y)p(y)

H(X1)≥H(X1/X2)≥H(X1/X2X3)≥…≥ H(Z/XY)H(Z/Y)p(xyz)logp(z/

p(z/p(z/

p(z/ p(xy)p(z/y)p(y)p(z/y) 11 H(Z/XY)≤H(Z/) I(XY；Z)≥I H(Z/XY)≤ H(Z)－H(Z/XY)≥ I(XY；Z)≥I)3XY,Z形成马氏链I(X；Z)≤I(XY；Z)=I) p(z/y)p(z/xy)XY I(XY；Z)=I I(X；Z)=I(Z；X)≤I(ZY；X)=I(Y；X)=I(X；Y (X；Z)≤I(X；Y I(X；Z)I(X；YI(Y；Zp(y/ux)=p(y/x)，p(v/xy)= p(v/ux)p(yv/ux)p(yv/ux)p(v/ p(y/ux)p(v/uxy)p(yv/x)p(v/ p(yv/x)p(v/Y I(U；V)≤I(X；Y 2H-2为两个信道并联的情况。当信I(U,V)p(v/u)lnp(v/

U p(xx')p(y/x)p(y'/x')lnp(y/x)p(y'/x' (2H-U p( I(X；Y)p(x)p(y/x)lnp(y/X p(p(xx')p(y/x)p(y'/x')lnp(y/ (2H-U

p(I(X'；Y')p(xx')p(y/x)p(y'/x')lnp(y'/x' (2H-

UI(U；V)I(X；Y)I(X'；Y'p(xx')p(y/x)p(y'/x')lnp(y)p(y'U p(

p(y'p(yy')lnp(y)p(y')p(yy')p(y)p(y') p(yy'

p(yy' (2H-

(2H-Ci)C≥附录2I反相对称法原反相对称法（phaseinversionsymmetricmethod,互反的信号s1(t)和s2(t)=-s1(t)，通过相邻信道

xCH1CH2CH1和CH2的增益都为1，n1(t)和n2(t)为加性噪声。假定噪声的均值

2I-1PISM xo(t)=x1(t)-x2(t)= 其中x1(ts1(t)+n1(t)，x2(tso(t)=s1(t)-s2(t)，no(t)=n1(t)-

ρ=E[n1(t)n2(t)]/{E[n E[n 可得到输出的信号So和噪声功率No如下So=E[s2(t)]=4E[s oNo=E[n2(t)]=E[n1(t)-n2(t)]2=2(1- oGPISM=(So/No)/(S1/N1)=2/(1- (2I-信噪比So/No。这是PISM抑制强噪声的理论依据[5]。s1(t)=s2(t)=……=m2，接收端采用等增益合并时，其原2I-22I-1的区别是CH2两侧没有反相器。

GDT=(So/No)/(S1/N1)=2/(1+ 有GDT2。在现有的DT中我们希望ρ→0，以GDT→2；而在PISM中则希望ρ越大越好K=GPISM/GDT=(1+ρ)/(1- 设信道噪声为BLGN，CH1和CH2为相邻时隙，采用最佳，则有ρ=0.167；带入式(2I-6)K≈1.40。它表明在输入信噪比相4020lg4020lgK0此较容易用PISM抑制[5]。表明，现有0.8由式(2I-6)K≈9。这说明，在相同件下，PISM

2I-3Kρ第3 基本概编编图3-1编的数学模X为消息集，Xx1x2,xm}xi为消息，i1,2,,m；Y为代码集，Yy1y2yn}yj为代码，j=1,2,n；D为符号集，D={d1d2,,dq}dk为符号，k=1,2,q。yj，而且所有的代码都是按规定的编码方法构成的。归纳起来编的作用有两点的，从而使信源的实际熵H小于信源的最大熵Hm，我们用H/Hm表示信源的有效度，用HmH表示信源的冗余，用HmH/Hm3-14.70bit。但是，由于字母的出现不是等概的，所以，据有关资料统计：在不考虑关联的4.02bit10～15%.当考虑了字母之间前后关联时，平均每个字母的熵还会二态检验与最佳编号每次都是等概出现时，才能获得最大的信息量(1bit)。我们把每接收到一个二进制符号，3-3I(平均)=p(是)·I(X；是)＋p(否)·I(X；否)=0.811 (3-))I（X；是）=H（X）－H（X/是 I（X；否）=H（X）－H（X/否 ·g 证：把概率空间X和概率分布P(X)写成：X={x1,…,xs,xs＋1P(X)={p1,…,ps,p(是p(否I(平均)=p(是)I(X；是)＋p(否)I(X；否=H(X)－p(是)H(X/是)－p(否)H(X/否

pi

pilogpi＋p(是

p(是 i

p(否

p(否 pilogp(是pilogp(否 i=I(平均)=p(是logp是)p(否logp否)=Hp(是),p(否)]当且仅当p(是)=p(否)时，上式右端取等号。 p(否)=1－p(是)I(平均)只是p(是)的函数，即：I(平均)=－p(是)logp(是)－[1－p(是)]log[1－p(是 为整数，称为码长niIi分别取统计平均值mpini

i(3-mpiIiH(Xi_

(3-_其中n为平均码长，H(X)为熵

n≥H _)_qI(平均p(ilogp(ilogi

(3-p1p2)==p(q1q时，上式右端取等号。Hlog83bit，而一次二态检验最多检验所能提供的最大信息量为：log31.585bit两次为：2×1.5853.17bit3bit所以，费诺（Fano）编码ABCDEFGHC02B02A103F103G1104E1104D1114H1114∵信源的熵为 HpilogpiI

(比特/消息 (3- nFpiniI

(码元/消息 (3- H(X ∴编码效率为 96.6%

(3-FηH(Xnlog_

比特/码元。当q=2时，logq=1(比特/码元)，所以计算就变成了：_η=H(X)/n哈夫曼（Huffman）编码3-63-5中的数据为例，按哈夫曼编码法进行编码（3-2

10001000 13-2I nHpiniI

(码元/消息H H

n nH

.效率相等，但在任何情况下，都不会有ηH＜ηF的现象。香农（Shannon）编码p1≥p2≥…≥p0=0iQik

，i1,2,, —logpi≤ni＜－logpi＋ C020B301A4100F4101G4110E51101D51110H51111 nspiniI

(码元/消息 (3-sηH2.55snn

CBAFGEDH10连在一起就无法区分了。而这样的代码是三进制代码，logq=1.585比特/码元。可以证明，例如Y001单义代码，又是续长 3-3哈夫曼码树信源编码定莫尔斯电报就是按照这个原则来编码的。莫尔斯本是一位在历史上享有盛誉的画家，1835年晋升为教授。1832年，在他旅欧学习美术的归途上，一位旅伴在闲聊中无意和他谈E··MT——F·－·AWIY·NGOPSBHVR·KD——Q·－·L－·－·J·UX·－·CZ－－个字母（ORLCFYPQJXZ）的代码发生了变动，其他字母的代码均未改变。而概率的大26个英文字母电报是1845年1月1日，在到巴尔迪摩的电报线传送的。1963年8月23日， 证：假定对信源消息集X={x1x2,,xm}进行了匹配编码，根据匹配编码的规则，应p1≥p2≥…≥pm，n1≤n2≤…≤nm npiIΔn=(pana＋pbnb)－(panb＋pbna)= (3-因为当pa≥pb时 (pa－pb)(na－nb)≤ (pana＋pbnb)≤(panb＋pbna 第二章中的香农定理，在信道容量为C的信道中，传信率R可以趋近于C。由于在一个码符才能携带最大的信息量，使H(X)=1比特/符号。于是我们得到：C=max[rH(X)]=1由于编码效率η没有达到100%，所以每符所携带的信息量并未达到1比特/码元。那么有没有办法使η→100%，使每符携带1比特的信息量呢？下面将要介绍的信源编码例3-7,即X={x1,x2},P(X)={p1,p2}={0.9,0.1},_Hp1logp1p2logp20.469比特/消 np1n1p2n21码元/消 编码效率为:η

46.9% 组进行编码。这些消息组所构成的集合称为二维延长信源，记为X2，即：X2={x1x1,x1x2,x2x1,x2x2}P(X2)={p1p1,p1p2,p2p1,p2p2}={0.81,0.09,0.09,0.01}0013-4X2 n(2) piniI

(码元/消息组 __ η(2)=H(X2)/n(2)=0.938/1.29=

_平均每一个消息的码长为：n(330.533码元/消息_ η(3)=H(X3)/n(3)=88 _3-8个脉冲，信道容量C=1bit/秒。 H(X)=log10=3.322(比特/消息 _C/n=1/4(消息/秒) _ η(1)=H(X)/n(1)=3.322/3.4= _/_η(K)=H(XK)/n(K) _则可使n→HC/H1/3.322消息/秒)。其中pijk=pipjpk；ijk0,1_H(X)1n(K)H(X) 式中H(X)表示信源的熵，单位为：比特/消息_n(K)K,单位为：码符/_n(K)/K,单位为：码符/在二进制编码中，q=2，logq=1，上式又可写成：H(X)n(K)H(X) _

(3-_n(K)/K=证：根据匹配编码的原则，我们总能找到一个nii个消息的pi相匹配，只logpinilogpi logpinlogpilog

log H(X)nH(X) X2p(xixjp(xip(xj),于是可H(X22H(X进而可证明K为任意整数时有：H(XK)KH(X 式(3-39)中的X换成XK后仍然成立：H(XKlog

n(K)

H(XKlog

(3-

KH(X)n(K)KH(X) _ n(K)/K→H(X)

利用关联压缩压缩码长。下面我们就来讨论有关联时信源的联合熵与条件熵，并相应的编码方法。Xx1xm}Yy1,…yn}，作为信源消息的集合。相应的概率为乘积，记作XY．XYxiyji1,,m；j1,,iP(XY)p(xy)i1,,m；j1,,i

XYxyxX，yYP(XY)p(xy)xX，yY.一节所说的延长信源，或X的延长，长2。还可以延长K，称K维消息XK，其中的每个元素都是K元消息组，或叫K元组。K=2pxixj)p(xi)p(xj)。但是在K元组中各消息间存在着关联时这种算法就不正确了。K=2，p(xixjp(xi)/p(xi/xj)。[联合熵定理]设两个基本信源X和Y，它们的熵为H(X)和H(Y)。则它们的联合熵H(XY)≤H(X)＋H( 当且仅当pxy)=px)py) p(x)Y

，p(y)X H(X)p(x)logp(x)p(xy)log

XH(Y)p(y)logp(y)p(xy)logp( Yp(xy)1，p(x)p(y)X XH(XY)p(xy)logXp(xy)logp(x)p(Xp(xy)logp(x)p(xy)logp(X XH(X) 当且仅当p(xy)=p(x)p(y)时，上式才取等号。 在定理中令X=Y，即得： H(X2)≤2H(X)。K的延长信源：HXK)≤KH(X)由此看到，如果消息间有关联，即p(xy≠p(x)p(y),,H(X)p(x)logp(x)X

(比特/消息p(XABCYA0BC0 0BAC13-5X 其平均码长为：n1.5码元/消息。编码效率ηH/n100% _) 23233333324 24 3-6X2

n2)=2.75(码符/消息组

n2)/2=1.375(码符/消息H(XY)=2.686(比特/消息组 H(XY)/2=1.343(比特/消息)_ η(2)=H(XY)/n(2)=0.977=97.7%(均值，称为q阶条件熵。下面我们以一阶马尔科夫信源为例，讨论条件熵的计算方法。p(x1/ p(x2/ p(xm/p(x/y p(x/y), p(x/yP(x/y) 2 p(x/y p(x/y

p(x/y nm其中第j行是信源处于yj这种状态时，各xi出现的概率。且有：p(xi/yj) mi H(X/yj)p(x/yj)logp(x/yjX

(3-p(yj)(,H(X/Y)p(y1)H(X/y1)p(yn)H(X/ynp(y)p(x/y)logp(x/y) Y p(xy)logp(x/Y

(3-3-10设有一个三阶马尔科夫信源。它的基本信源X={全部中文单字}。则某个中文3-11X白，黑}p(白/白)=0.9，p(黑/白)=0.1，p(白/黑)=0.2，p(黑/黑)=0.8。 H(X/白)=－0.9log0.9－0.1log0.1=0.469(比特/消息)HX/黑)=－0.2log0.2－0.8log0.80.722(比特/消息H(XY)=H(X)＋H(Y/X H(XY)p(xy)logXp(xy)logp(x)p(xy)logp(y/X XH(X)H(Y/X

这个定理的含义是十分清楚的，它告诉我们，对元偶(xy)进行猜测的平均程度出现的平均程度H(Y/X)。如果令Y=X，上述定理变成：H(X2)=H(X)＋H(X/X).H(XK)=H(XK－1)＋H(X/XK－1 H(Y/X)≤H(Y H(XY)≤H(X)＋H(YH(XY)=H(X)＋H(Y/X H(Y/X)≤H p(xy)=p(x)p(y)。 H(X)≥H(X/X)≥H(X/X2)≥…≥H(X/Xq H(X/XK－1)≤H(XK) 从以上各种压缩码长和提高效率的方法来看，基本上都是靠信源的延长来实现的。但是信源的延长受到客观条件的限制。对于K维消息组来说，XK中的元素个数将随K按指数规律增加。比如X={一万个汉字}，那么别说K取较大值，即使K=2，也将会使X2中的元不能任意加大的。X的元素个数为2，因此XK的元素个数就有2K个。当K较大时，2K的增642i1i1,2,64)11粒米，第2个格2粒米，第三个格中放4粒米，…，第i个格中放2i－1粒米，…。可以算出，2641= 1019实用编码方法X(ω)，然后对X(ω)编码而不是对x(n)。如果X(ω)有某些特征可供利用，将会使码长得到压的方法作为例子。一种叫做关联识别，另一种叫做逻辑识别。 ,Xixi1xi2…xin}i01,…9nm×kxij假定待识别的信号是Y={y1,y2,…,yn}，其y1,y2,…,yn的取值为有几种比较方法其中常用的法是把Y的序列与Xi的序列逐2加。得到：Ei=(ei1,ei2,…,ein).其中

3-70，xijyjeijxijyj1，x

.

3-8待识别的nnDij

(3-如果与十个样本相比的结