(完整word版)通信的数学理论_香农_中文版1

1、香农通信的数学理论近年来像PCM和PPM这些交换信号噪音比带宽等的多种调制方法的发展已经增强了我们对一般通信理论的兴趣。这种理论的基础包在重要的报纸Nyquist1 and Hartley 2中关于此学科的内容。 在当今的报纸中我们将延伸这种理论从而包括许多新的因素，特别是噪声通道的影响，和存储可能的基于最初信息统计的结构和基于数据的最后目的性性质。通信的基本问题是再制造一点或者准确地或者近似地一个从别处挑选的信息。通常信息有意义；那是他们提到的或是依照一些特定物质或概念上实体的系统的相互关联。这些与语意有关的通信方面是不切题的工程问题。重要的方面是真实的信息是从一组可能的信息挑选来的。系统一

2、定要有计划的操作每个可能的选择，而不仅仅是哪一个因为在设计的时候是未知者将会被选择。如果设备的信息数目是有限的，那么这组数字或一些具有单调功能的数字可以被当做对信息被关闭后再创造的测度，所有的选择有相同的可能。像 Hartley所指出的，最自然的选择 是对数的功能。虽然当我们考虑统计信息的影响力以及对信息的持续排列这个定义必须被凝 练地概括，我们将在所有情况下用一个本质为对数的量度标准。对数的测度更方便，主要有以下多方面的理由：1 .它在实践上更有用。工程的重要参数，像时间、带宽、数字的分程传递等等，趋向 于随可能数字的对数线性改变。举例来说，增加一个继电器到小组会加倍数字的可能情形。它加1到

3、以2为底的对数。加倍时间大致得到可能信息数目的平方，或加倍其对数，等等。2 .它以适当的尺寸接近我们的直觉感观。如果我们直觉地用共同的标准线性比较测量实体，它将接近相关到（1）。有一个想法，举例来说，二张穿孔卡片与一张相比有两倍 的信息储藏能力，并且二个通道与一个相比有两倍的传输数据的能力。3 .它在数学方面更合适。许多极限运算在对数方式下很简单，但是在普通数字下却需要笨拙的重述。对数底的选择对应测量信息单位的选择。 如果以2为底，产生的单位 可以叫二进位数字，或比较简要地叫比特，一个由J.W.Tukey建议的词。一个拥有两个 稳定位置的设备，像一个继电器或一个双稳态多谐振荡器，可以存储一比特

4、的信息。N个如此的装置能存储 N比特的信息，因为可能情形的总数是logb a信息来源传达者接受者目的地干扰源图1一个常规信息系统原理图并且log 2=N 。如果以10为底产生的单位可以叫十进制数字。因为log2 M =log10 M/log102 =3.32log 10 M 。1 一 ,Nyquist , “某些影响通报速度的因素”贝尔系统科技刊物，1924年4月，第324页；“电报传输理论中某些总联机程序和信息控制系统”,A.I.E.E. Trans.v.47,1924年4月，第617页。Hartley, R. V. L , “信息传输”，贝尔系统科技刊物，1928年7月，第535页2一个十

5、进制数大约31比特。书桌上的一个阿拉伯数字计数器有十个稳定的位置并且因 3此拥有存储十进制数字的能力。有时在综合和区分的解析工作中底数e很有用处。以此为底的信息结果将被叫做自然对数。将底数由a改为b仅仅需要乘以10gb a。对于通信系统我们想要用一个系统的示意图图1阐明。它包括五个重要的部分：1 .一个制造信息或排序信息的信息源将被传达到终端。信息可能有各种不同类型：(a)电传打字系统的电报中的字母序列 ；(b)无线电话中的一个单一时间函数f(t);(c) 一个时间函数和其它应用在黑白电视机中的变量一在这里信息可能被当做一个二个空间坐标和时间的函数 f(x,y,t);在点(x,y)的光强度，在

6、光的金属板上获得的时间t;(d)二或更多的时间函数，分别为f(t)、g(t),h(t)这是“三维”声音传播的情形，或者若系统有意维修个别多元通道；(e)一些变量的一些函数一在彩色电视机中有三个函数f(x,y,t),g(x,y,t),h(x,y,t),定义在一个三维空间的闭联集中一我们也可能想像这三个函数作为一个定义在区域矢量场的向量分量一同样地，个别黑白电视机消息来源是许多三个变量的函数；不同的混合物也会发生，例如在电视机中有联合的音频信道。2 .用一些方法操作信息以产生在信道上传输的合适信号的传达者。在电话制造中这种操作包括的仅仅是替换躁声压力为电流。在电信技术中我们有产生一系列点、莫尔斯电

7、码、空间等相关信息信道的编码、译码的操作。在一个多元的PCM系统不同的语音函数必须被取样压缩，量子化和编码，而且最后完全交叉存取地构造信号。声音传播机系统、电视和频率调制器是其他的联合体操作应用于信息以获取信号的例子。3 .信道只是用来从传达者到接收者传送信号的媒介。它可能是一双电线、一个同桥电缆、一 条无线电电波，一个光束，等等。4 .接收者通常完成由传达者做的反运算，重建来自信号的信息。5 .目的地是信息对其有意的人 (或者事物)。我们希望考虑特定的一般问题用于信息系统。这 首先需要描述不同数学实体的相关原理，将他们的物理副本合理的理想化。我们大致把通信系统分为三大类：离散的，连续的和混和

8、的。离散系统对于我们就意味着信息和信号是一系 列的离散符号。一个典型的情形是在电信技术中消息是一系列的字母和信号点、莫尔斯电码及空间。连续型的系统就是一个信息和信号都被看作是连续函数的系统，例如无线电通信或电视机。混合系统中既有离散的又有连续的变量，例如PCM语言传输。我们首先考虑离散的情形。这种情形不仅应用于通信理论，而且应用于计算机理论，电话局和其他领域的设计。 另外离散的情形构成在下半页要处理的连续和混合情形的基础。第一部分：离散的无噪声系统1 .离散的无噪声信道电传打字机和电信技术是离散信道上信息传输的两个简单例子。一般来讲，一个离散信道就意味着一个系统怎么从可以从一个点传到另一个点被

9、传输的有限集合元素符号S),.,Sn选择次序。每一个符号Si被假定有确定的连续时间ti秒(对于不同的Si没必要相同，例如电信技术中的点和莫尔斯电码)。这不需要有可能传输到系统的Si的所有可能排序，确定次序仅仅是可能被允许。这将在信道产生可能的信号。这样在电信技术中可以推想符号有：(1) 一个点，包括一个单位时间的关闭和一个单位时间的线性开启；(2) 一个莫尔斯电码，包括三个单位时间的关闭和一个单位时间的开启；(3) 一个包括三个单位时间线性开启的字母空间；(4) 一个包括六个单位时间线性开启的词空间。我们可能放置约束在允许的无间隔的次序(因为如果两个字母的间隔是接近的，它同一个字空间是一样的)

10、。我们现在要考虑 的问题是如何测量这样一个信道传输信息的能力。在电传打字的情况下所有符号有同样的持续时间，并且32个符号任何排序答案是简单的。每个符号拥有5比特的信息量。如果系统每秒传输 n个字符，那么自然来说信道有一个 每秒5n比特的传输能力。这并不意味电传打字信道总是这个传输速度，这是可能的最大值 并且实际比率能否达到最大值取决于进入信道不久将会出现的信息源。在不同长度的符号和约束的允许序列的更普通情形中，我们作以下定义：定义：一个离散信道容量 C由此公式给出：C = Lim log N(T)tt：T其中N(T)是持续时间为T时允许信号数目。很容易看出在电传打字的情形下降低了当前的结果。可

11、以看出问题中的极限在多数情况的影响下存在一个最终的数目。假使所有符号的次序 S,，Sn都可能发生，并且这些符号的持续时间为ti,tn。信道容量是多少？如果N(T)代表为期t的次序数目，我们就有N(t)=N(t- t 1)+N(t-t 2)+.+N(t-t n).总数目等于以Si,，Sn为结尾的序列数目的总和并且是N(t- ti),N(t-t 2),N(t-t n)。根据一个著名的有限差结果，N(t)于是渐进大数t到X0t,其中Xo是特征方程式的最大解：X-t1 +X* +.X 上=1 因止匕 C=logX 0.在允许序列受限制的情况下我们也有一个此种类型的不同方程式并且从特征方程式中得到Co在

12、以上提到的电信技术我们知道依照最后或几乎最后出现的序列计算符号序列。N(t)=N(t- 2)+N(t-4)+N(t-5)+N(t- 7)+N(t-8 )+N(t-10)因此C等于log与。其中%是方程1 =卜2 +卜4+卜5+卜7+卜8+川°的根。我们可以解得C=0.539。一个置于允许序列约束的普通类型如下：我们想象一个可能的数字序列 ai,a2,.,am。对于每一种情形仅仅设置S,S2,., Sn中的某些符号可以被传输(不同的子集有不同的情形)。当其中之一被传输，就产生一个取决于老状态和当前传输信号的新状态。发电报就是这其中的一个简单例子。存在两个取决于是否是一个空间最后传输信号

13、的状态。如果这样的话，那么仅仅一个点或一个莫尔斯电码可以被发送并且状态经常改变。如果不是的话，一些信号可以传输并且若空间被发送状态将改变，否则它保持不变。这种情形可以在线状图图2中阐明。莫尔斯电码母空”/莫尔斯电码司空间图2 电报符号约束的图表状态和线相应的那些连接点指示着状态中的可能符号和结果状态。在附录1中可以看出如果允许序列的条件可以被描述在形态C中，结果将存在并且计算出它与以下结果一致：定理1：以bijs)为从状态i到状态j的允许符号sth的周期。那么信道容量 C等于logW ,其中W是行列式方程式白最大实根：4 w对) _、可| =0s其中若i=j则aj =1,否则乐=0 O ,一

14、，-1(W2 +W”)例如，在电报情形(图 2)中行列式是：=0。(W +W) (W +W-1)在扩充式中这将导出以上这种情形所给的方程式。2.信息的离散信源我们已经看到在普通情况下可能信号的数目的对数在离散信道中随时间线性增长。信道容量可以由给出的增长率说明，每秒的比特数目需要详细说明所用的特殊符号。我们现在考虑信息源。如何将信息源用数学方式描述，在所给信源每秒产生多少信息位 呢？这个问题的关键是关于降低信源必需的信道容量的统计知识的影响，通过利用适当的信息编码。在电信技术中，例如，包括字母序列的被传输信息。然而，这些序列并不是完全随 意的。一般而言，他们组成句子并且有所谓英文的统计结构。字

15、母 E比字母F出现的频繁， 序列TH比序列XP出现的频繁，等等。这个结构的存在通过适当地编码信息序列到信号序 列能节省时间(或信道容量)。这已经被用来通过利用最短的符号信道、点、最常见的英文 字母E限制宽度，然而少见的字母 Q, X, Z用长点的点和莫尔斯电码表示。这个方法还被广泛应用于商业编码，其中常见字和短语是由极大地缩短平均时间的4或5位信码群表示。现在运用的标准问候和周年纪念电报扩充这一点到编码一到两个句子为 相关的短的数字序列。我们可以考虑一个离散信源作为由符号产生的信息、符号。它通过某些可能的依靠选 择连续的符号，一般的，在前述的选择，像问题中的特殊符号。一个物理系统，或是一个产

16、生由可能集合支配的符号序列的系统的数学模型，叫做随机过程。3我们可以考虑一个离散信源，因此，将通过一个随机过程描述。相反地，有一些随机过程，它们产生离散的选自被 认为是离散信源的有限集的符号序列。这将包括如下情形：1 .自然书写语言如英语、德语、汉语。2 .由量子化过程离散呈递的连续信息源。例如由 PCM发射机发送的量子化演说，或 者一个量化电视信号。3 .在数学情形中我们仅仅定义抽象的产生符号序列的随机过程。如下是最终资源类型的例子。(A)假设我们有5个都以0.2的可能性被选择的字母 A、RC、D、E连续选择是不受约束的。这将产生一个序列，如下就是一个典型例子。它利用随机数字表格构造的。4B

17、 D C B C E C C C A D C B D D A A E C E E AA B B D A E E C A C E E B A E E C B C E A D3See,例如，S. Chandrasekhar,物理学和天文学中随机问题 ，现代物理学的回顾，v.15,No.1,1943年一月， 第一页.4 .Kendall and Smith，随机取样数子的表格，剑桥,1939.(B)用五个发生概率分别为0.4,0.1,0.2,020.1的同样字母，连续选择是不受约束的。一个来自信源的典型如下：A A A C D C B D C E A A D A D A C E D AE A D C

18、 A B E D A D D C E C A A A A A D 。(C)如果连续的符号没有被独立地选择，但是他们的概率取决于在前的字母，一个更复杂的 结构将会获得。在简单的情况下，这种类型的选择取决于在前的字母并且不是它们之前的。统计结构然后就通过一个跃进概率集合Pi (j)描述，字母j的发生概率在i之后。复数i和jp(i, j),也就是两涉及所有的可能符号。第二个相等方法的指定结构是给出两个字母的概率Pi(j)和连字概率p(i,j)个字母i,j的相关概率。字母频率 p(i),(字母i的概率)，跃进概率 有如下公式的关系：P(i) = P(i, j) = P( j,i)=" P(

19、j)P j(i)P(i, j)=P( i)Pi(j)Pi(j)八P(i)- p(i, j) =1.i,j举一个具体的例子，假设有三个如下概率表所示的字母A,B,C:Pi(j)P(i)P(i, j)ABC512210271627227827 12715827413515135一个消息源的典型信息如下：A B B A B A B A B A B A B A B B B A B B B B B A B A B A B A B A B B B A C A C A BB A B B B B A B B A B A C B B B A B A.其次，复杂性的增加将包括最多三组字母的频率。字母的选择将依赖在

20、前的两个字母而不是之前的信息点。一个三组字母频率p(i,j,k)的集合或者等同的蜕变概率pj (k)的集合是必需n元情形中用一个 n的。这种方法持续进行将获得更多持续的复杂的随机过程。在普通的 元概率P(i1,i2,in)或者转变概率Pi1,i2,.,in-1(in)的集合来指定统计结构是必需的。(D)随机过程也可以由产生一段包括序列“字”的正文来定义。假设有语言中的五个字母A, B, C, D, E和16个“字”，且它们的联合概率如下:10 A16 BEBE11CABED04DEB04ADEB05ADEE01BADD04BED02BEED05CA05CEED08DAB04DAD15DEED0

21、1EAB05EE假设连续的“字”被独立地选择并且被空间隔离。一个典型可能信息为:DAB EE A BEBE DEED DEB ADEE ADEE EE DEB BEBE BEBE BEBE ADEE BED DEED DEED CEED ADEE A DEED DEED BEBE CABED BEBE BED DAB DEED ADEB 。 如果所有的字长度有限，这个过程就相当于前述类型的其中之一，但是如果按照字结构和概率描述可以更简单。我们也在此归纳并且介绍字之间的蜕变概率，等等。人工语言在构造简单的问题和说明不同可能性的例子是有用的。我们也可以通过一系列简单的人造语言的方法接近自然语言。零

22、号近似值可以通过等可能并且独立地选择字母来获得。一号近似值可以通过独立地选择连续的字母获得，但是每个字母像自然语言5那样拥有同等的发生概率。这样在一号近似值中对于英语来说，E以0.12（它在标准英语中出现的频率）的概率被选择并且 W的发生概率为 0.02,但是邻接字母之间没有影响并且没有形成像 TH, ED这样的首选连字，等等。在二号近似值中介绍了连字结构。一个字母被选择后，下 一个字母与频率被一致地选择，其中不同的字母跟随第一个字母。这需要一个连字频率Pi（j）的表格。在三号近似值中介绍了三组字母结构。每个字母被等可能选择并且取决于前两个字母。3.英文近似值的连续性给一个这个系列过程如何接近

23、一门语言的形象想法，英文近似值的典型序列已经被构造并且在下面给出。在所有情形中我们假定一个27字符的“字母表” ，26个字母和一个空格。1 .零号近似值（符号独立且等可能出现）XFOML RXKHRJFFJUJ ZLPWCFWKCYJ FFJEYVKCQSGHYD QPAAMKBZAACIBZL- HJQD.2 . 一号近似值（符号独立但是以英语原文的频率出现）OCRO HLI RGWR NMIELWIS EU LL NBNESEBYA TH EEI ALHENHTTPA OOBTTVA NAH BRL.3 .二号近似值（英语中的连字结构）ON IE ANTSOUTINYS ARE T INC

24、TORE ST BE S DEAMY ACHIN D ILONASIVE TUCOOWEAT TEASONARE FUSO TIZIN ANDY TOBE SEACE CTISBE.4 .三号近似值（英语中的三组字母结构）IN NO IST LAT WHEY CRATICT FROURE BIRS GROCID PONDENOME OF DEMONSTURES OF THE REPTAGIN IS REGOACTIONA OF CRE.5 .一号字近似值。胜于连续的四个字母，.，n元结构更简单并且更好地接受点到字单元，在此字被独立地选择，不过是以它们适当的频率被选择。REPRESENTING

25、AND SPEEDILY IS AN GOOD APT OR COME CAN DIFFERENT NATURALHERE HE THE A IN CAME THE TOOF TO EXPERT GRAY COME TO FURNISHES THE LINE MESSAGE HAD BE THESE.6 .二号字近似值。字蜕变概率是恰当的，但是不包括更深的结构。THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE CHARACTEROF THIS POINT IS THEREFORE ANOTHER METHOD FOR TH

26、E LETTERS THATTHE TIME OF WHO EVER TOLD THE PROBLEM FOR AN UNEXPECTED.普通英语原文的类同之处在以上每步显著增加。注意这些样品有适度优良的结构， 计算它们的造句，表现出两倍的范围。这样在 （3）中对于两字母次序统计过程确保了合理的原文 ，但是5 、 一 .、 一 .一 、一 ,一 、. . 一一 、,一字母，连字和二组字母频率在 1939年由Fletcher Pratt, Blue Ribbon Books 所著的紧急秘密。字频率在由G. Dewey所著、哈佛大学出版社印刷的英语语言的相关频率中被列成表格。样品中四字母次序通常

27、适用于好句子。在(6)中四个或更多的字可以很容易地放在句子中而没有不平常的、做作的句子。十个词的详细次序 “"attack on an English writer that the character of this (抨击这种特征的英国作家)”根本不合理。由此看来一个十分复杂的随机过程将会 给离散信源一个满意的表示法。头两个例子是应用随意数字的一本书构造的，其中随意数字关联一个字母频率表格(对于例2)。这种方法可能已经延续到(3), (4)和(5),虽然连字、三组字母和字母频率表格是有用的，但是一个更简单的等价方法正被应用。比如构造(3)，一个人随机地才T开一本书，并且在该页随机

28、地选择一个字母。 将此字母记录。然后打开该书的另外一页并且读到这个字母出现时， 随后的字母然后被记录。翻到另外一页找到第二个字母并随后记录，等等。一个简单的过程被用在(4),(5)(6)中。如果深一层近似值被构造，那将会是有趣的。但是下一阶段相关的详细 分析变得庞大。4 .一个马尔可夫过程的图形表示法以上描述的这种类型的随机过程在数学中叫做离散的马尔可夫过程，并且在文献6中广阔地研究。大体情况可以描述为如下：存在一个有限个数的系统的可能状态；S1,S2,.,Sn。另外有一套蜕变概率，如果此刻系统状态是 Si,将达到状态Sj的概率是Pi(j)。要将马尔可夫过程转变为信息源我们仅仅需要假定字母是由

29、每次从一个状态转变到另一个状态时产生 的。状态符合来自前述字母的“剩余物的影响”。该情形可以被描述为图表，在图3, 4和5中显示。图3一个符合例B中信源的图表此状态是图中的连接点， 并且概率和字母产生的转变在旁边的相应直线给出。 图3对应 第2部分的例Bo而图4符合例C。在图3中，因为连续字母不受约束，只有一个状态。图4一一个符合例C中消息源的图表在图4中有字母数目相等数目的状态。如果构造一个三组字母的例子，将出现至多n2个状态，符合前述被选择的可能出现的字母对。图5是一个说明在例 D中词结构情形的曲6 了解详细的处理见 M.Frechet,数据加密，巴黎，高塞尔 -维拉斯，1938年8月线图

30、。这里S代表“间隔”符号。5 .遍历信源和混合信源正如我们以上已经说明的，按我们意原的离散信源可以被看作是由马尔可夫过程描述。在可能的离散马尔可夫过程中有一个在通信理论中有意义的特殊性质的组。特殊类包括“遍历”过程，我们把相应的信源叫做遍历信源。尽管一个遍历过程的严格定义有些棘手，其常规思想是简单的。在一个遍历过程中由此过程产生的序列的统计特性是相同的。这样的字母频率、连字频率等等从特殊序列在获得，将随着序列长度的增加，接近不受特殊序列约束的确定极限。事实上这对每个序列并不全对，但是错误的概率几乎为零。大致上遍历性意味着统计一致性。以上所给的所有人工语言的例子是遍历的。这种特性涉及到相应图表的

31、结构。如果图表有如下两个性质7 ,相应过程将被遍历：1 .这个图表不包括两个独立的部分A和B,这样就不可能顺着图中曲线的箭头方向从A部分的连接点到B部分的连接点，也不可能从 B部分的连接点到 A部分的连接点。2 .图表中的封闭谱线系伴随线上的所有箭头指向同样的方位叫做一个“回路”。回路的“长 度”是其中直线数目的个数。这样在图5中系列BEBES是长度为5的回路。第二个需要的特性是图表中所有回路长度的最大公约数是一。图5一个符合例D中消息源的图表如果满足第一个条件，但是由于最大公约数等于d>1而不满足第二个条件，序列将有一个确定的周期结构类型。不同的序列分成d种类型，它们统计上相同，除了起

32、源的变化（也 就是，序列中的字母被叫做字母1）。通过从0到d-1的移位一些序列可以统计上等于其它的构造。d=2时的一个简单例子如下：有三个可能的字母a,b,c。a后出现b或c的可能性分1一2别为1和2。a后面跟随着b或c。这样的一个典型序列是33a b a c a c a c a b a c a b a b a c a c °这种情形的类型对我们的工作不太重要。这些根据在Fr'echet中给出的图表条件被重述如果不满足第一种条件，图表可能被分成一系列满足第一种条件的子图。我们假定每个子图也满足第二种条件。 我们有这种由许多纯粹成分组成的叫做“混合”信源的情形。其成分符合各种各

33、样的子图。如果 Ll,L2,L3是信源成分，我们可以写出L = p1L1 + p2L2 + p3L3 + 其中Pi是信源成分Li的概率。自然的描绘情形如下：有几个不同的信源Li, L2,L3每个都有同类的统计结构(也就是,它们是遍历的)。我们不知道预先将被用到的，但是一旦序列以所给的纯信源成分Li开始，它依照那种成分的统计结构不确定地延续。作为一个例子我们可以获得两个以上定义的过程，并且假定p1 = 0.2, p2 = 0.8。一个来自混合信源的序列 L =0.2Li +0.8L2将通过首先以0.2和0.8的概率选择L1和L2此选择 之后产生来自任意一个被选择的序列。除了当反面是一定的， 我们

34、设想信源将被遍历。 假设能够让我们顺着一个伴随全体可能 序列平均数(差异的概率为零)的序列确定平均数。例如在一个特殊无限字母序列中A的相关概率将可能等于序列全体中它的相关频率。如果P是状态i的发生概率并且 pi (j)是到状态j的蜕变概率，然后过程将会固定，显然P必须满足均衡条件：Pj =£ PPi(j)。在遍历情形中可以看出伴随着一些起动条件状态j在N个符号后的概率是 R(N),当Nt空时逼近平衡价值。6.选择、不确定性和嫡我们已经将离散信源描绘为一个马尔可夫过程。我们能否定义一个参量，它在某种意义上测量这样一个过程或字母产生多少信息，以什么样的比率产生信息。假如我们有一组发生概率

35、为pi, P2,，Pn的可能事件。这些概率是知道的，但是那是我们所有知道的关于将发生的事件。我们能否找到一个相关事件有多少“选择”或结果有多少不确定性的量度标准呢？如果有这样一个量度标准，比方说 H ( Pi, P2,，Pn),如下所需的性质是合理的：1 .在概率Pi下H是连续的。12 .如果所有的概率 P1等于一，那么H应该是一个关于n的单倜递增函数。当存在更多可能 n的事件时，等可能事件有更多选择或不确定性。3 .如果一个选择被分为两个连续的选择，最初的H应该是H的个体价值的加权和。 这句话的1 11思义会在图6中举例说明，在左图中我们有二个概率P1 = , P2 =, P3 =。在右图我

36、们2 361/21/21/31/61/2, 2/3 -1/21/31/3 1/6图6三个可能选择事件的分解,1,一一 * 八,2 1, ，一 先以-的概率选择两个可能事件，如果第二步以-,-的概率做另一步选择。最后的结果有23 3同以前同样的概率。我们在这种特殊情况下得出1111112 1H （一，一，一）= H （ 一，一）十 H （一，一）。2 3 62 223 2一，1 1系数-是因为第二个选择以一半的时间发生。在附录2,有如下确定结果:2n定理2：满足以上三个假设的 H有如此形式：H = -KZ pi log pi i/其中K是一个确定的常数。这个理论，和对其进行证明所需的假设，对于当

37、前理论并不需要。这首先给出一些我 们稍后定义的有确定理由的参与。然而这些定义的真正理由隐藏在暗示中。形态H = -£ pi log pi的数量（恒量 k仅仅等于度量单位的选择）作为信息、选择和不确定性的测度在情报理论中起到了一个中心的作用。形态H被认作是嫡，作为定义在一如H是Boltzmann的著名的的嫡。如果x是一个机遇数,定的用公式表示的统计力学 8,其中pi是它的拓扑空间中系统处于单元i的概率。然后，例H定理。我们把H = £ pi log pi叫做一系列概率p1, p2,，pnH（x）是它的嫡，这样的x不是一个函数的自变量而是一个数字标志，区别于 H（y）来说是概率

38、y的嫡。嫡的两种情形的概率分别为p和q =1 - p ,即H =-（plog p+qlogq）作为p的一个函数在图7中绘出。H值有许多有趣的性质，更深层地证实它是一个衡量选择和信息的合理量度标准。1.如果除了一个pi,所有的概率都为 0,那么H=0,这个pi具有联合价值。这样仅仅是当我们确定H为0结果，否则H是正的。1 12 .对于一个给出的n,H在所有pi相等,也就是（一，一）时取得最大值logn。这也是一个直 nn观的最不确定的情形。3 .假设有两个事件x和y,问题中前者有m种可能，后这有n种可能。若事件一发生的概率是i ,事件二发生的概率是 j ,其联合事件的概率是p（i, j）,那么联

39、合事件的嫡是8审视，实例R. C. Tolman ,统计力学原理牛津大学出版部，19380.10图7一两种概率分别为p和q =1- p的情形的嫡H(x,y) = p(i, j)log p(i, j)i.jH(x)二一"p(i,j)log% p(i,j)i.jH(y) =，p(i,j)log% p(i,j)i. j很容易知道H ( x, y)三 H ( X )H(Y)仅仅当事件独立时等号成立(也就是p(i, j) = p(i)p(j)。联合事件的不确定性小于等于个体不确定性的总和。4 .对均等概率 R, p2,. pn的一些改变会使 H增大。这样如果pi < p2并且我们等量地增

40、加pi和p2 ,从而使 pi和p2更接近，那么 H将会增大。一般地，如果我们执行形态r =£ aij pj中均衡pi的操作，其中工 间=工jaj =1，并且所有的aj之0,那么H将 j会增大。(除了转变总数不超过pj的排列伴随着H保持不变的特殊情形)。5 .假设有两个像3中的可能事件x和y,而且它们没必要独立。对任何事件x的值i ,可以假定有一个条件概率pi(j),其中事件y的值为j 。这由等式pi(j)= p(i,j)给出。1p(i,j)我们定义y的条件嫡Hx(y)作为对于每一个 x值，y的嫡的平均数，通过获得特殊事件x 的概率权衡。即 Hx(y)=£ p(i, j)lo

41、gi(j)。i.j这个量测试当我们知道事件x时y的平均值的不确定性。取代pi(j)的值我们得到Hx(y)=，p(i, j)log p(i, j) % p(i,j)log" p(i,j) i.ji.jj= H(x, y卜 H(x)或 H (x, y” H( x) xH (oy)联合事件x, y的不确定性(或嫡)等于事件x的不确定性加上当知道事件x时事件y的不确定性。6 .从 3 至U 5 我们得出 H(x)+H(y)至 H(x,y)= H(x)+H x(y)因此 H(y) >Hx(y) o事件y的不确定性不会由于知道事件x而增加。除非事件x和y是独立事件这种不确定性不变的情形，它

42、将会减少。7、信源嫡考虑一个有限离散信源的所有情况，对于每一个可能的状态i ,会有一系列可能发生 j的概率为pi(j)。由此得到对于每一个可能的状态 i下的嫡Hi ,对所有发生的状态的嫡 Hi进 行加权平均得到该信源的信源嫡为：H八PH一 Pi pi(j)10gpi(j)i.j这是符号集里每个符号所携带的信息量，如果马尔科夫过程在单位时间内发生，则它为每秒的平均信息量., - -一 ，一 . H =£ 1Hi ( 左为状态i出现的平均概率)显然有：H ' = mH (m为平均每秒钟产生的符号数)H(H )表示信源平均每个符号(每秒)产生的信息量。如果选取以2为基数，则单位为比

43、特每符号(每秒)。如果所有的符号相互独立，则H可简单的表示为-Z pi 10gpi(pi为i发生的概率)。理所当然，在这种情况下，我们考虑一个由N个符号组成的长序列信息，它由出现概率相对高的字符组成，其第一个字符出现的次数为p1N ,第二个字符出现的次数为p2N这种信息出现的概率为:PiNp r 6p2NpnNp2 pnlog p : N" Pi log Pilog p : -NHu log1/p HN即H大约等于这一序列信息的概率的倒数的对数除以序列的符号个数，且对任意的信源都有这一结果。更精确的表达如下(见附录3):定理3:对任意给点的e>0和6>0,存在N0,使得当

44、这一序列信息的长度 N > N0 时有如下两点成立：1、其发生的概率小于e；2、所有的参数满足不等式叱-H <6N也就是说当N足够大时，可以确定10g P 可以无限的接近 H。N大量序列的不同概率会无限的接近某个结果，再考虑序列的长度N ,对它们按概率的递减顺序进行排列。我们定义 n(q)为的那些序列中最有可能发生的概率且用来计算。定理4:当q不等于0或i时，有Lim 10g n(q) = HN N当我们只考虑最有可能发生序列的总概率q时，我们可以将n(q)解释为指定某序列时所需要的比特数，因此10g n(q)即为平均每个符号所需要的比特数，这定理表明对于较大N的数N ,发生概率q

45、和嫡H相互独立。所有可能序列数的对数的增长率由N确定，与发生的可能性无关。结果的证明过程在附录 3中。对于长序列中，仅有2HN个是最常用的，每一个被使用的概率为2*N。下面的两个定理表明 H和H 可以通过信息序列的统计数据直接算出来，不涉及状态转移概率。定理5：设：p(Bi)为消息中符号序列 Bi的发生概率，1Gn = -Z p(Bi)log p(Bi),(求和中要遍及所有含 N个符号的序列Bi) N i则：Gn关于n单调递减，且(imGN=H。定理 6：设：p(Bi,Sj)为 Bi,Bj 同时发生的概率,PBi(Sj) = P(Bi,Sj)/ p(Bi)为在 Bi条件下Sj发生的概率。设(求

46、和中要遍及所有含 N -1个符号白序列Bi和Sj )Fnp(Bi,Sj)logpBi(Sj)i.j= NGn -(N -1)Gn,1 NFn，N n 4-Gn,则：Fn关于N单调递减，FnGnFnUm Fn =H上述结果的证明过程在附录3中，这表明一系列近似计算 H的方法可以通过仅考虑序列中的第1、2、N个符号的统计数值表得到，Fn是一个比较精确的近似值。实际上，Fn为所有信源类型的 N个次序的近似值，也就是说下一个字符的产生只与前面的N - 1个符号相关，与再前面的符号无关，则Fn = H。Fn即为下一个符号产生的条件嫡，当前面 的N -1个符号已确定时， Gn则为N个符号中平均每个符号的嫡

47、。当重复出现相同的字符时，信源嫡的比率得到最大值，叫做相对嫡。这就是对字母进行 编码时的最大压缩。不考虑超过8个字母长度的统计数值表，普通英语的冗余度大约为 50% 这也就是当我们写英语时，我们所写的一半被语言结构所决定，另一半可以自由选择。50%的数字是通过相邻的结果再利用一些独立的方法得到。一是通过计算英文的近似嫡；第二种方法是从一个简单的英文文章中删掉一些确定的字母片，然后尝试恢复它们，如果删掉的 50%TB能被恢复出来，则冗余度就会大于50%第三种方法是依靠密码系统的已知结果。英语散文的两种极端冗余度代表为基础英语和詹姆斯乔伊斯的书“芬尼根的苏醒”。基础英语词汇限制在 850个单词，且

48、冗余度较高。当一段落翻译成基础英语时会出现反射性 的扩充。乔伊斯在另一方面扩充词汇，并且声明实现压缩的内容。语言的冗余度与纵横字谜的存在有关，若冗余度为0,字母的任何次序在语言中都时合理的正文，并且任意的二维字符排列形成一个纵横字谜。如果冗余度太高，这语言就可能会为比较多的纵横字谜强派大量的约束，通过更多的明细分析得出：如果我们被语言强行约束会更加混乱、更无规则。当冗余度为50%寸，大的纵横字谜游戏仅仅成为可能，如果冗余度为33%三位的字谜游戏就可成为可能。8.表小编码和解码的运算我们仍然需要用编码和解码信息给传输者和接受者表示数学操作。它们中的任何一个都将被称作传感器。一连串的输入标号被输入

49、进传感器并且一连串的输出标号被传感器输出。这个传感器可能有一个内存输出，不但依靠当前的输入标号，而且依靠过去的标号。 我们假设内存有限，例如：存在一个有限的m代表传感器，然后输出一个函数表示当前的状态和当前的标号。下一个状态将有第二个函数和两个变量。因此，这个传感器可以用如下的两个函数描述：yn f （xn , yn ）an 1 = g（Xn, yn）这里：Xn代表nth的输入标号，an代表nth的提出的输入标号的传感器状态，yn代表如果状态是an的已知Xn的输出标号（或者一连串的输出标号）。如果这个传感器的输出标号可以在一秒内辨认出输入标号，它们可以连接到的结果也是一个传感器。如果存在第二个

50、传感器，它操作输出第一个并恢复原有的输入，那么第一个传感器将被称作反向的。定理7：被一个有限状态统计资源促使的有限状态传感器的输出是一个有限的状态统计 资源，嫡（每单位时间）少于或者等于输入。如果这个传感器是单个的，那么它们相等。让口代表资源的状态，它产生一连串的标号Xi ；让P代表状态统计资源，它产生、输出封闭的标号yj。这个链接的系统可以被“生产状态区间”的“（G,P ）”所代表。这两点的区间（, 3）和（三邛2）被一条线连接，如果 巴可以得出X,从久到良，这条线是 给出的在这种情况下可能的X。这条线是一个标签的标号yj。这个输出的嫡可以像重量和等状态那样被计算出来。如果这个和的结果P少于

51、或者等于a ,那么嫡不会增加。如果这 一 、 一 一 _ _ ' _ _ ' '个传感器不是单个的，它输出与反向的传感器相一致。如果 Hi , H2和H3是输出的这个资源的嫡，那么 Hi - H2 - H3 = Hi,所以H1 = H2。假如我们有一个约束可能序列的系统，其类型由像图2的线状图描述。如果概率p（s）被分配到多样的连接状态i到状态j的线条，这将变为一个信源。存在一个使嫡结果取得最大 值的特殊分配（见附录 4）。定理8：将约束系统考虑为一个容量为C = logW的信道。如果我们指派心 Bi一个）此一p s） =W j 其中：.：）是符号sth从状态i到状态j

52、的周期，并且Bi满足BijBi =£ BjW j 然后H取得最大值并且等于 C。 s, j通过蜕变概率的适当指派，一个信道的符号嫡可以在信道容量上取得最大值。9.无躁声信道的基本原理我们现在证明对 H的解释正如通过证明 H确定信道容量需要用最有效的译码产生信 息的比率。定理9:取一个嫡值为 H （比特每符号）的信源和一个容量为C （比特每秒）的信道。C而后就有可能编码信源的输出，在信道上以这样一种名符号每秒的平均传输速率传输，HC其中名是一个任意小的域。不可能以大于 C的速率传输。HC定理的相反部分， C不可能被超越，可以记录每秒输入的信道嫡等于信源来证明，因H为传达者必须是非单一的

53、，并且嫡不能超越信道容量。因此 H MC,并且每秒的符号数目等于 H / H EC /H。定理的第一部分将以两种不同的方法证明。第一种方法是考虑一系列由信源产生的N个字符的所有序列。对一个大数N,我们可以分成两组，一组包括少于2（H*）N个成员，另一组包括少于2RN个成员（其中R是不同符号数目的对数），并且有一个小于 N的总概率。随着N的增加”和N趋向于0。信道中信号数目的周期 T大于2（C-aT , T大的时候日小。如H果我们选择T=（H-）NC然后当N和T充分大（尽管 人很小）且有一些增量时对于高概率的组将有足够的信道 符号的序列数目。高概率组任意的一对一的方式编码到集合。保留序列被大的序

54、列描述，以不被用在高概率组的一个序列开始和结束。这个特殊序列为一个不同的编码担当起始和结束的信号。在中间一个充分的时间被允许对所有低概率信息给出足够不同的序列。这需要T1 =（ ）NC其中邛很小。符号信息每秒的平均传输速度将会大于（1 -）TT广二（1 - '）（H） , （R ：）"N NCC当N增加时，6,九和平趋向于0且速度趋向于 C。H还有另一个履行译码的方法，因此定理的证明可以描述如下：以概率递减的顺序安排长度为N的信息，且假设它们的概率是 p1 > p2 > p3.,> pnos取PS =£ 1 Pi ,也就是Ps是累积概率的结果，但不

55、包括PS。我们首先编码成一个二进制数，信息s的二进制码是通过展开 PS为二进制数获得的。 扩展式被执行到 ms位，其中ms是11整数且满足：log 2 Wms<1+log2。PsPs这样高概率的信息由短代码描述，而低概率的信息由长代码描述。从这些不等式我们有1 ,1-ms- - ps ：- -ms L2 2 一1在一个或更多的 ms位，Ps的编码将不同于所有继后编码，因为所有剩余P至少 二2这么大，并且它们的二进制扩展因此在第一个ms处不同。从而所有的编码是不同的，并且有可能从它的编码重新获得信息。如果信道序列还不是二进制数字序列，它们可以以任意的方式被归因于二进制数，并且这样二进制码就转化为适合信道的信号。二进制数字所用原始信息的每个符号的平均数目H是容易估计的。我们有.1 H =一m msP