信息论与通信、密码、信息隐藏(一)

1、 五、五、Shannon信息论在研究方法上的启示信息论在研究方法上的启示 参考文献参考文献 信信 源源 编码器编码器 信信 道道 译码器译码器 信信 宿宿 干扰源干扰源 信信 源源 编码器编码器 信信 道道 译码器译码器 信信 宿宿 干扰源干扰源 信信 道道 等效离散信道等效离散信道 信信 源源 信信 源源 编码器编码器 纠纠 错错 编码器编码器 调制器调制器 干扰源干扰源 信信 源源 译码器译码器 纠纠 错错 译码器译码器 信信 宿宿 解调器解调器 等效信宿等效信宿 信道编码器信道编码器 信道译码器信道译码器 等效离散信源等效离散信源 细化的通信系统模型细化的通信系统模型 消息或数据中含有信

2、息、内容、知识。消息或数据中含有信息、内容、知识。 I yx p yx y jk jk j (;)log (|) () );( ik yxI )( )|( log k jk a xq yxp 被称作是事件与事件之间的被称作是事件与事件之间的互信息量互信息量。上式正反。上式正反 映了互信息的映了互信息的对称性对称性。两个事件之间的互信息量可正、。两个事件之间的互信息量可正、 可负、也可能为可负、也可能为0 0。 )( k xI )(log )( 1 log k k xq xq )( )( 1 log )( )( 1 log );( j j k k jk yI y xI xq yxI 它是对信源输

3、出它是对信源输出直接直接做观察（不经传输、存储和处做观察（不经传输、存储和处 理，没有干扰和失真下）所能获得的理，没有干扰和失真下）所能获得的最大最大信息量。它由信息量。它由 信源本身的统计特性所决定，因此称之为信源本身的统计特性所决定，因此称之为信源输出符号信源输出符号 的自信息的自信息。 自信息量自信息量I(xk)是为了确定事件是为了确定事件xk的出现所必须提供的出现所必须提供 的信息量，它也是任何其它事件所能提供的关于事件的信息量，它也是任何其它事件所能提供的关于事件xk 的最大信息量，即任何两个事件之间的互信息量不可能的最大信息量，即任何两个事件之间的互信息量不可能 大于其中任一事件的

4、自信息量。大于其中任一事件的自信息量。 由由0q(xk)1可得，可得， I(xk)0， 即自信息量即自信息量是非负的。是非负的。 自信息量还可解释成出现事件自信息量还可解释成出现事件xk的的先验不确定性先验不确定性的的 大小。一个事件不常出现，它的概率就小，当我们知道大小。一个事件不常出现，它的概率就小，当我们知道 该事件出现时获得的信息就多，它的自信息就大，反之该事件出现时获得的信息就多，它的自信息就大，反之 就小。所以自信息可以认为是随机事件的一种固有特征。就小。所以自信息可以认为是随机事件的一种固有特征。 平均自信息量平均自信息量熵熵 )(log)()()()()(xqxqxIxqxMI

5、XH Xx 集X的平均自信息量平均自信息量，又称作是集X的信息熵信息熵，简称 作熵熵。描述集X中事件出现的平均不确定性平均不确定性。 某次通信所获得的信息量通常是非平均的，它可以是某次通信所获得的信息量通常是非平均的，它可以是 正面的，有助于对某一特定事件做出判定；也可以是负面正面的，有助于对某一特定事件做出判定；也可以是负面 的，使我们更难对某一特定事件做出判定。的，使我们更难对某一特定事件做出判定。 对于通信系统设计来说，关心的是对信源输出对于通信系统设计来说，关心的是对信源输出集集的传的传 输和处理，因此需要研究统计平均量。输和处理，因此需要研究统计平均量。 Shannon Shanno

6、n信息论研究的是消息或数据的群体行为，信息论研究的是消息或数据的群体行为， 而不是孤立的个别消息或数据的行为，正如我们从宏观而不是孤立的个别消息或数据的行为，正如我们从宏观 来看物质或材料时，我们所关心的是大量原子或分子的来看物质或材料时，我们所关心的是大量原子或分子的 群体行为一样。群体行为一样。 当我们关心个别消息的传输问题时，或当我们不掌当我们关心个别消息的传输问题时，或当我们不掌 握整个消息空间的统计特性时，我们就需要求助于其他握整个消息空间的统计特性时，我们就需要求助于其他 的信息定义或理论了。的信息定义或理论了。 热熵热熵 在在1919世纪，统计力学的奠基者们发展了后来称为世纪，统

7、计力学的奠基者们发展了后来称为热熵热熵 的知识，以解释热力学的诸定律。乍一看，热力学和信息的知识，以解释热力学的诸定律。乍一看，热力学和信息 论是两个分离的范畴：一个用来描述蒸汽机，另一个使通论是两个分离的范畴：一个用来描述蒸汽机，另一个使通 信最优化；然而，熵这个热力学量又正比于物质内由分子信最优化；然而，熵这个热力学量又正比于物质内由分子 的位置与速度所记录的比特数。的位置与速度所记录的比特数。 2020世纪的量子力学将这一发现置于坚实的定量基础世纪的量子力学将这一发现置于坚实的定量基础 之上，并使科学家具有明确的量子信息概念。组成宇宙的之上，并使科学家具有明确的量子信息概念。组成宇宙的

8、各比特值是量子力学比特，或称各比特值是量子力学比特，或称 “昆比特昆比特”（qubitsqubits），）， 较之于普通比特，它具有远为丰富的性质。较之于普通比特，它具有远为丰富的性质。 平均互信息量平均互信息量熵差熵差 非负性非负性 I I( (X X；Y Y) ) 0 0 当且仅当集合当且仅当集合X X和集合和集合Y Y统计独立时，上式等号成立。统计独立时，上式等号成立。 对称性对称性 I I( (X X；Y Y)=)=I I( (Y Y；X X) ) 平均互信息可用平均互信息可用熵和条件熵之差表示熵和条件熵之差表示如下如下: : I I( (X X；Y Y)=)=H H( (X X) )

9、H H( (X X| |Y Y) ) = =H H( (Y Y) )H H( (Y Y| |X X) ) = =H H( (X X)+)+H H( (Y Y) )H H( (YXYX) ) x yX xq yxp yxpyxIMyXI )( )( log)()();( | ； 当把当把X X 作为系统的输入集，作为系统的输入集，Y Y 作为系统的输出集时，作为系统的输出集时， 互信息互信息I I( (X X；Y Y) )等于输入集的平均不确定性等于输入集的平均不确定性H H( (X X) )减去在观减去在观 察到输出察到输出Y Y后，集后，集X X还保留的不确定性还保留的不确定性H H( (X

10、 X| |Y Y) )。H H( (X X| |Y Y) )常称常称 作作含糊度含糊度、疑义度疑义度或或存疑度存疑度。在给定集。在给定集X X下，含糊度越大，下，含糊度越大， 得到的信息量就越小。得到的信息量就越小。 注意，互信息是注意，互信息是熵差熵差，而不是熵。熵是不确定性的，而不是熵。熵是不确定性的 量度，而量度，而熵差熵差经过通信所解除的不确定性才是所能经过通信所解除的不确定性才是所能 得到的信息量。得到的信息量。 熵熵是潜在的是潜在的可以产生可以产生和和可以提取可以提取的最大信息量。的最大信息量。 凸函数与互信息的凸性凸函数与互信息的凸性 互信息的定义式互信息的定义式 它是输入分布它

11、是输入分布q q( (x x) )及转移概率分布及转移概率分布p p( (y y| |x x) )的函数。的函数。 当条件分布当条件分布( (或条件密度或条件密度) )给定时，平均互信息是输入给定时，平均互信息是输入 分布分布( (或密度或密度) )的凸的凸函数。函数。 当集当集X X的概率分布的概率分布( (或概率密度或概率密度) )保持不变时，平均互保持不变时，平均互 信息量是集信息量是集R R上所有条件概率分布上所有条件概率分布( (或密度函数或密度函数) )的凸的凸函函 数。数。 xy y xyp xypxqYXI )( )( log)()()( ； ),(vudEd );()( mi

12、n VUIDR Dij PP 由由I(X; Y)是集是集R R上所有条件概率分布上所有条件概率分布( (或密度函数或密度函数) ) 的凸的凸函数知此极值存在。函数知此极值存在。R R( (D D) )不小于不小于0 0，但小于，但小于H H( (U U) )。 有失真时的有失真时的逆信源编码定理逆信源编码定理：当速率：当速率R R小于率失真函小于率失真函 数时；我们无论采用什么编译码方式，其平均失真必大数时；我们无论采用什么编译码方式，其平均失真必大 于于D D。 有失真时的离散无记忆有失真时的离散无记忆信源编码定理信源编码定理：给定失真给定失真D D， 令令P P* *为使且为使且I I(

13、(P P) )达到极小的条件概率，则存在长度为达到极小的条件概率，则存在长度为N N的的 分组码分组码C C，它的平均失真，它的平均失真d d( (C C) )满足满足 ),( 0 )( DRNE edDCd ),(DRE*),;(max 01 PRE 它当它当R R R R( (D D) )时恒大于零。定理表明，随着分组长度时恒大于零。定理表明，随着分组长度N N 的增加，我们总能找到一种编码方式，它在速率时可使的增加，我们总能找到一种编码方式，它在速率时可使 失真任意接近失真任意接近D D。 Shannon的率失真理论在连续消息和离散消息之间的率失真理论在连续消息和离散消息之间 架上了一座

14、桥梁，从而给数字化提供了一个基础和有效架上了一座桥梁，从而给数字化提供了一个基础和有效 的工具。的工具。(Shannon 1959, Berger 1971)。 关键理论进展关键理论进展：关键理论进展的十个里程碑：关键理论进展的十个里程碑Kieffer 1993 (1) 无扰信源编码的诞生无扰信源编码的诞生(1948, C. E. Shannon, B. S. T. J. Vol.27, pp.379-423 pp.623-656. 1948)。 (2) Huffman算法的发现算法的发现(1952, D. A. Huffman, Proc. IRE, Vol.40 pp.1098-1101,

15、 1952)。 (3) 建立建立Shannon-McMillan定理定理(1953, B. McMillan, Ann, Mach. Stat. Vol.24, pp.196-219, 1953)。 (4) 发现发现Lloyd算法算法(1957, S. P. Lloyd 1957年写出，年写出， 1982年发表在年发表在IT-28, pp.129-137, 1982)。 (5) 率失真理论系统化率失真理论系统化(1959, C. E. Shannon, IRE Nat, Conv, Rec, Part.4 pp.142-163, 1959)。 (6) Kolmogorov Complexity

16、概念诞生概念诞生(1964, A. N. Kolmogorov, Problem of Information Transmission, Vol . 1, pp.4-7, 1965)。 (7) 通用信源编码理论系统化通用信源编码理论系统化(1973, L. D. Davission, IT-19, pp.783-795 1973)。 (8) 多端信源编码理论诞生多端信源编码理论诞生(1973, D. Slepian和和J. K. Wolf, IT-19, pp. 471-480, 1973)。 (9) 第一个实际的算术编码方案第一个实际的算术编码方案(1976, J. Rissannen和和

17、 R. Pasco 1976博士论文博士论文, IBM Res Dev, Vol.20 pp.198-203, 1976)。 (10) 发现发现Lempel-Ziv码码(1977, J. Ziv和和A. Lempel, IT- 23 pp.337-343 1977)。 技术进展和标准技术进展和标准 技术进展：解决了传输和存储资源所需要的数据压技术进展：解决了传输和存储资源所需要的数据压 缩方案。缩方案。 (1) 未压缩时各类信号所需的数据率。参见表未压缩时各类信号所需的数据率。参见表1 表表1 未压缩时各类信号所需的数据率未压缩时各类信号所需的数据率 类类 型型 频频 率率 范范 围围 采采

18、样样 速速 率率 bit/样点或象元样点或象元 未压缩未压缩bit率率 语音语音 窄带语音窄带语音 2003200 Hz 8 khz 16 128 kb/s 宽带语音宽带语音 507000 Hz 16 kHz 16 256kb/s 声频声频 CD声频声频 2020000 Hz 44.1 kHz 162路路 1.41Mb/s 静止静止 FAX 17002200 1 3.74 Mb/页页 VGA 640480 8 2.46 Mb/页页 图像图像XVGA 1024768 24 18.87 Mb/页页 NTSC(4:3) 480483 29.97帧帧/s 16# 111.2 Mb/s 电电 PAL(4

19、:3) 576576 25 帧帧/s 16 132.7 Mb/s CIF(4:3) 352288 14.98 帧帧/s 12# 18.2 Mb/s QCIF(4:3)176144 9.99 帧帧/s 12 3.0 Mb/s 视视 HDTV(16:9)1280720 59.94 帧帧/s 12 622.9 Mb/s HDTV(16:9) 19201080 29.97 帧帧/s 12 745.7 Mb/s * 基于基于4:2:2彩色子样格式，每彩色子样格式，每4个亮度采样中对个亮度采样中对Cb和和Cr各有两个各有两个 色度样点色度样点 # 基于基于4:1:1彩色子样格式，每彩色子样格式，每4个亮度

20、采样对个亮度采样对Cb和和Cr各有一个各有一个 色度样点色度样点 (2) 已制定的有关话音编码标准和压缩已制定的有关话音编码标准和压缩后后bit率率 PCM(G.711)，64 kb/s高质量话音编码。高质量话音编码。 ADPCM(G.726, G.727)，32 kb/s话音编码。话音编码。 宽带编码器宽带编码器(G.722)，2-band ADPCM，用于，用于7 kHz带宽话路，高质量低延时带宽话路，高质量低延时, 64, 56和和48 kb/s。 LD-CELP(G.728)，低时延、编码激励、线性预，低时延、编码激励、线性预 测声码器，测声码器，3个差分线性预测器，第个差分线性预测器

21、，第50阶预测下一个采阶预测下一个采 样值，第样值，第10阶引导量化过程，一个感知加权滤波器用来阶引导量化过程，一个感知加权滤波器用来 选择声带激励信号，选择声带激励信号，16kb/s。 CS-ACELP(G.729)，共轭结构、代数，共轭结构、代数CELP，为，为 前 向 自 适 应 分 析前 向 自 适 应 分 析 / 综 合 声 码 器 。综 合 声 码 器 。 8 k b / s ， 用 于， 用 于 SVD(Simultaneous Voice and Data)Modem。 MPC-MLQ(G.723.1)，多脉冲编码，最大似然译，多脉冲编码，最大似然译 码，自适应分析码，自适应分

22、析/综合声码器，但速率较综合声码器，但速率较G.729低，为低，为6.4 和和5.3 kb/s，已用于，已用于Internet电话中。电话中。 VSELP(IS-54)矢量和激励线性预测声码器，前向矢量和激励线性预测声码器，前向 自适应分析自适应分析/综合声码器，是北美数字蜂窝电话编码标综合声码器，是北美数字蜂窝电话编码标 准，准，8 kb/s。 这些标准的恢复语音质量如图这些标准的恢复语音质量如图1所示。其中纵座标所示。其中纵座标 为为MOS (Mean Opinion Scores)值，从图值，从图1可以看出，自可以看出，自 1980年到年到1990年话音压缩声码器的质量有相当大的进步。年

23、话音压缩声码器的质量有相当大的进步。 目前目前2.4kb/s的声码器已有多家产品，如的声码器已有多家产品，如Qualcomm的的Q 4413，可从，可从1000b/s到到13.3 kb/s，固定速率为，固定速率为6.2 kb/s和和 13.3 kb/s，全双工，全双工，4.8 kb/s以上达长话水平。又如以上达长话水平。又如 DVSI(Digital Voice System, Inc)的的IMBE-1000 TM可提可提 供供2.49.6 kb/s，MOS达达3.4左右左右(1995年年)。 GOOD(4) G723.1 IS-127 G.726 G.711 G.729 FAIR(3) ME

24、LP FS1016 1990 FS10 POOR(2) BAD (1) 1980 1 2 4 8 16 32 64 图图2 话音编码的主观质量与话音编码的主观质量与bit率的关系率的关系 (3) 声频编码标准和压缩后数据率声频编码标准和压缩后数据率 MPEG-1声频编码器，采用感知编码法，单声道声频编码器，采用感知编码法，单声道 信号信号96 kb/s时可提供高质量恢复信号。时可提供高质量恢复信号。 MPEG-AAC声频编码器，每路为声频编码器，每路为8 kb/s192 kb/s在在64 kb/s时的立体声编码可以达到原始声频信号的时的立体声编码可以达到原始声频信号的 CD质量。质量。 (4)

25、 图像编码标准和压缩后数据率图像编码标准和压缩后数据率 Group 3 FAX，采用游程长度编码，逐行扫描。，采用游程长度编码，逐行扫描。 一维编码，一维编码，200 dpi，压缩比为，压缩比为20:1，Group 4 FAX，采，采 用游程长度编码，二维编码，较用游程长度编码，二维编码，较G3 FAX改善改善25%。 JBIG-1，根据局部相邻元进行像元预测，采用算，根据局部相邻元进行像元预测，采用算 术编码法，有动态自适应性，用于术编码法，有动态自适应性，用于FAX可与可与G4 FAX相相 竞争。竞争。 JBIG-2分段软图样匹配方式，用于字母图像组合分段软图样匹配方式，用于字母图像组合

26、文件。文件。 JPEG，采用，采用DCT、感知量化、熵编码，、感知量化、熵编码，8(像像 素素)8(像素像素)组，保证恢复图像质量好的条件下，压缩组，保证恢复图像质量好的条件下，压缩 比可达比可达32:1。 JPEG-2000，已有软件产品，可提供低，已有软件产品，可提供低bit率图像，率图像， 质量优于已有质量优于已有JPEG标准。标准。 (5) 电视标准电视标准 H.261(p64，p为正整数为正整数)，H.262和和H.263，采，采 用动态补偿帧内编码，用动态补偿帧内编码，H.261为基准为基准(baseline)编码器。编码器。 变长编码器的熵编码。变长编码器的熵编码。 MPEG-1

27、分组传递和压缩声频视频和数据。类似分组传递和压缩声频视频和数据。类似 于于H.26X，主要差别是采用了全向和双向运动补偿。用，主要差别是采用了全向和双向运动补偿。用 于于CDROM媒体存储动态图像，媒体存储动态图像，1.4 Mb/s。 MPEG-2，可适应于多信道，宽带网传送多媒体，可适应于多信道，宽带网传送多媒体 信号。信号。 MPEG-4，面向对象的、适用于多媒体信号传送，面向对象的、适用于多媒体信号传送 的压缩和处理的标准。各对象可独立编码、交互组合、的压缩和处理的标准。各对象可独立编码、交互组合、 综合集成于一体。综合集成于一体。Video的码速率可从的码速率可从8k b/s1 Mb/

28、s。 MPEG-7，增加了多媒体大型数据库中对于对象，增加了多媒体大型数据库中对于对象 的搜索、索引和认证的能力，尚在修订过程中。的搜索、索引和认证的能力，尚在修订过程中。 信道容量定义为信道容量定义为 C=Max I(X; Y) p(x) 即即C为改变输入分布时，使每个符号所能含有的平为改变输入分布时，使每个符号所能含有的平 均互信息量的最大值。相应的输入分布称为最佳分布。均互信息量的最大值。相应的输入分布称为最佳分布。 I(X；Y)是输入分布的凸是输入分布的凸函数，因而上述极大值函数，因而上述极大值 一定存在。一定存在。 信道容量表示了信道传送信息的最大能力，这个量信道容量表示了信道传送信

29、息的最大能力，这个量 在信息论研究中有重要意义。在信息论研究中有重要意义。 信道编码定理信道编码定理：传送的信息速率：传送的信息速率R R 必须小于信道容必须小于信道容 量量C C，否则传送过程中将会造成信息损失，出现错误。，否则传送过程中将会造成信息损失，出现错误。 若若R R 和和|1表示的一个矢量表示的一个矢量 |0+ |1，其中，其中| |2| |2=1。 一个有一个有N个不相同的两状态存储单元的系统可由个不相同的两状态存储单元的系统可由N个不同个不同 的二维的二维Hilbert空间的张量积实现，故可引出矢量空间的张量积实现，故可引出矢量 其中其中V=V=Z Z2 2N N，。当，。当

30、 |0+|0+ |1|1是相对于基是相对于基|0|0和和|1|1的度量时，的度量时， 量子量子bitbit在特定状态被发现的概率就是相应幅度绝对值的在特定状态被发现的概率就是相应幅度绝对值的 平方。一个孤立的量子系统就以这种方式保持其叠加性、平方。一个孤立的量子系统就以这种方式保持其叠加性、 不可区分性，数学上用酉不可区分性，数学上用酉( (unitary)unitary)或幺正变换或幺正变换( (即线性和即线性和 内积保持内积保持) )，HilbertHilbert空间则类似于欧氏空间中的刚体旋转。空间则类似于欧氏空间中的刚体旋转。 酉变换和叠加性是量子力学的中心原理。酉变换和叠加性是量子力

31、学的中心原理。 |v v V 量子硬币量子硬币(QCFquantum coin flip)： |0 |1 |0 1 1 系数系数1：破坏性干涉：破坏性干涉(interfere destructively) |1 1 1 系数系数0：建设性干涉：建设性干涉(interfere constructively) 而普通硬币连续抛掷等价于一次掷硬币。图而普通硬币连续抛掷等价于一次掷硬币。图4给出抛给出抛 两次量子硬币的结果，两次量子硬币的结果，(QCF)2=NOT。 |1 |0 |1 |0 |1 |0 |1 1/2 1/2 1/2 1/2 图图4 抛掷两次量子硬币的结果抛掷两次量子硬币的结果 12/

32、12/ 1 2/ 2/ 11 2/1 2/1 2/ 1 2/ IBM的的T. J. Watson研究室的研究室的Rolf Landauer和和 Charles Bennett最先将信息论与量子力学联系起来，其最先将信息论与量子力学联系起来，其 背景是背景是Moore定律：在过去定律：在过去50年中，计算机的速度每两年中，计算机的速度每两 年翻一番，而元器件的体积每两年缩小一倍。当器件的年翻一番，而元器件的体积每两年缩小一倍。当器件的 尺寸小到可以用量子力学描述时就遇到了量子效应造成尺寸小到可以用量子力学描述时就遇到了量子效应造成 的障碍。的障碍。Bennett和和Landauer想搞清楚器件可

33、以做得多小，想搞清楚器件可以做得多小， 运转所需的能量要多大。运转所需的能量要多大。1994年年Peter Shor发现量子重叠发现量子重叠 可用于寻求快速分解整数的算法。这是表明量子计算机可用于寻求快速分解整数的算法。这是表明量子计算机 可比经典计算机更强有力。量子计算的有效性基于相关可比经典计算机更强有力。量子计算的有效性基于相关 量子叠加性或纠缠性，它可以同时处理指数量级的特例。量子叠加性或纠缠性，它可以同时处理指数量级的特例。 但是量子系统不可能完全从其它现实世界孤立出来，它但是量子系统不可能完全从其它现实世界孤立出来，它 与环境的相互作用造成散屑，即环境测量量子系统使波与环境的相互作

34、用造成散屑，即环境测量量子系统使波 包塌陷包塌陷(collapsing)。 经典计算机采用重复纠错码提高可靠性，而量子经典计算机采用重复纠错码提高可靠性，而量子bit 不能克隆不能克隆(clone)因因而不能用类似方法提高可靠性。量子而不能用类似方法提高可靠性。量子 计算首先需要考虑海森堡测不测原理计算首先需要考虑海森堡测不测原理(HUPHeisenberg Uncertainly Principle)，在量子系统中无论采用多么精细，在量子系统中无论采用多么精细 的操作，都不可能获得观测以前系统的完整信息。例如的操作，都不可能获得观测以前系统的完整信息。例如 我们不可能通过放大单个量子为许多它

35、的复本来获取有我们不可能通过放大单个量子为许多它的复本来获取有 关它的极性的更多信息。关它的极性的更多信息。HUP正是在对复制正是在对复制(daughter)光光 子的极性中引入足够随机性，使为测量而制作的更多个子的极性中引入足够随机性，使为测量而制作的更多个 光子所带来的任何优点化为乌有。起初人们相信量子的光子所带来的任何优点化为乌有。起初人们相信量子的 非克隆定理非克隆定理(quantum no-cloning theorem)可使量子可使量子bit加加 倍。但事实并非如此，它仅仅是排除了重复码。奥妙之倍。但事实并非如此，它仅仅是排除了重复码。奥妙之 处在于量子叠加散屑效应不会得到有关原来

36、叠加的任处在于量子叠加散屑效应不会得到有关原来叠加的任 何信息，因而也得不到被测散屑的信息。有关量子纠错何信息，因而也得不到被测散屑的信息。有关量子纠错 码的研究可参看码的研究可参看Calderbank等等1998。 量子理论认为，量子理论认为，离散是自然的本性；一个自然系统离散是自然的本性；一个自然系统 可以用有限的比特值来描述。在系统内，每个粒子的行可以用有限的比特值来描述。在系统内，每个粒子的行 为正像一台计算机的逻辑门。它的自旋为正像一台计算机的逻辑门。它的自旋 “轴轴”能指向两能指向两 个方向中的一个，因此可以编码一个个方向中的一个，因此可以编码一个量子力学量子力学比特，比特，或或

37、称称 “昆比特昆比特”（qubitsqubits），），并且可以翻转，由此执行一并且可以翻转，由此执行一 个简单的计算操作。个简单的计算操作。 昆比特较之于普通比特，它具有远为丰富的性质。昆比特较之于普通比特，它具有远为丰富的性质。 量子物理观还认为，量子物理观还认为，系统在时间上也是离散的。系统在时间上也是离散的。 Normam Margolus声称，传递一个比特所需的时间声称，传递一个比特所需的时间 t 依依 赖于所施与的能量赖于所施与的能量E，施加的能量越多，则需时可能越，施加的能量越多，则需时可能越 短。数学表达式是短。数学表达式是 Th/4E 其中其中h是普朗克常数是普朗克常数(量子

38、理论的方根参数量子理论的方根参数)。实验量子计。实验量子计 算机用质子来在存储信息比特，而用磁场来翻转各比特算机用质子来在存储信息比特，而用磁场来翻转各比特 值。值。 物理学与信息论（源于量子力学的中心原理）合流物理学与信息论（源于量子力学的中心原理）合流 了。了。 在最近几年内，越来越多的物理学家认为，在最近几年内，越来越多的物理学家认为，所有自然所有自然 系统都是计算机。岩石、原子弹及星系可能不运行系统都是计算机。岩石、原子弹及星系可能不运行LinuxLinux 程序，但它们也记录和处理信息。每个电子、光子及其他程序，但它们也记录和处理信息。每个电子、光子及其他 基本粒子都存储数据比特值。

39、大自然与信息是纠缠在一起基本粒子都存储数据比特值。大自然与信息是纠缠在一起 的，正如美国普林斯顿大学的物理学家的，正如美国普林斯顿大学的物理学家John WheelerJohn Wheeler所说，所说， “它来自比特它来自比特” 物质、黑洞和宇宙都可看作是量子计算机。黑洞的本物质、黑洞和宇宙都可看作是量子计算机。黑洞的本 质、时空的精细尺度结构、宇宙暗能量的行为以及自然界质、时空的精细尺度结构、宇宙暗能量的行为以及自然界 的某些终极的规律等无不以量子力学为基础。宇宙不仅是的某些终极的规律等无不以量子力学为基础。宇宙不仅是 一个巨型计算机，正如意大利帕多瓦（一个巨型计算机，正如意大利帕多瓦（P

40、adovaPadova）大学的物）大学的物 理学理学Paola ZizziPaola Zizzi所说，所说，“它来自量子比特它来自量子比特”。 普通的掌上计算机普通的掌上计算机：速度为速度为10109 9；存储量为；存储量为101012 12。 。 终终极掌上计算机极掌上计算机：达到普通物质的计算能力极限的计：达到普通物质的计算能力极限的计 算机。取占有一升体积的一千克物质，如果将这些物质按算机。取占有一升体积的一千克物质，如果将这些物质按 公式公式E=MC2所转换成的能量全数投入到翻转的比特位中，所转换成的能量全数投入到翻转的比特位中， 可达可达101051 51次运算，熵正比于能量除以温度

41、，相应地达到一 次运算，熵正比于能量除以温度，相应地达到一 个新的水平比特的信息量。实现的是并行计算。个新的水平比特的信息量。实现的是并行计算。 黑洞计算机黑洞计算机：黑洞的尺寸：黑洞的尺寸(称为称为Schwarzschild半径半径)正正 比于它的质量，一千克质量的黑洞有着大约比于它的质量，一千克质量的黑洞有着大约1010-27 -27米（为塞 米（为塞 米米Xennometer级级 ）的半径）的半径(一个质子的半径是一个质子的半径是1010-15 -15 米米) 。执行。执行101051 51次运算。 次运算。Bekenstein计算一千克质量的黑洞计算一千克质量的黑洞 能够记录大约能够记

42、录大约101016 16个比行的信息。 个比行的信息。 它传递一个比特的时间是它传递一个比特的时间是1010-35 -35秒，等于光从计算机一 秒，等于光从计算机一 边传到另一边的时间。因此，较之高度并行的极端掌上计边传到另一边的时间。因此，较之高度并行的极端掌上计 算机，黑洞是个串行计算机，它的行为如同一个独立的单算机，黑洞是个串行计算机，它的行为如同一个独立的单 元。元。 信息的逃逸呈纠缠态信息的逃逸呈纠缠态(entanglement)两个或多个两个或多个 系统的性质能跨越时空而相关联的一种量子现象。纠缠可系统的性质能跨越时空而相关联的一种量子现象。纠缠可 以离物传态以离物传态 (tele

43、portation)，信息被高度可靠地从一个粒，信息被高度可靠地从一个粒 子传送到另一个粒子；这一传输是超越光速的。子传送到另一个粒子；这一传输是超越光速的。 宇宙计算机宇宙计算机：黑洞的各种性质是与时空的性质相互纠：黑洞的各种性质是与时空的性质相互纠 缠在一起的。因此如果黑洞能够被认为像一台计算机，那缠在一起的。因此如果黑洞能够被认为像一台计算机，那 么时空自身也应可以这样看待。量子力学预言时空与其他么时空自身也应可以这样看待。量子力学预言时空与其他 的自然系统一样都是离散的。距离与时间不能被测量到无的自然系统一样都是离散的。距离与时间不能被测量到无 限的精度，在很小的尺度上，时空是一些泡沫

44、。限的精度，在很小的尺度上，时空是一些泡沫。 物理学家推测时空泡沫单元的尺度是普朗克长度物理学家推测时空泡沫单元的尺度是普朗克长度(lp)， 即即1010-35 -35米。这些泡沫单元实际上要大得多，而且的确没有 米。这些泡沫单元实际上要大得多，而且的确没有 固定的尺寸：时空区域越大，它的构成单元也越大。固定的尺寸：时空区域越大，它的构成单元也越大。 绘制时空几何图形的过程就是一种计算，在这种计算绘制时空几何图形的过程就是一种计算，在这种计算 中，通过传递和处理信息，距离得以规范。中，通过传递和处理信息，距离得以规范。 计算的原理，不仅应用于最致密的计算机计算的原理，不仅应用于最致密的计算机(

45、黑洞黑洞)和最和最 微小的可能计算机微小的可能计算机(时空泡沫时空泡沫)。最大的计算机：整个宇宙。最大的计算机：整个宇宙。 把可见物质、暗物质以及引宇宙加速膨胀的所谓能量把可见物质、暗物质以及引宇宙加速膨胀的所谓能量 等都考虑进去。宇宙能量密度大约是每立方米等都考虑进去。宇宙能量密度大约是每立方米1010-9 -9焦耳， 焦耳， 宇宙包含的能量为宇宙包含的能量为101072 72焦耳。宇宙每秒钟可执行高达 焦耳。宇宙每秒钟可执行高达1010106 106 次运算，自宇宙诞生以来它总共已完成了次运算，自宇宙诞生以来它总共已完成了1010123 123次运算。 次运算。 这些粒子是指中微子和光子，

46、它们的熵密度正比于其这些粒子是指中微子和光子，它们的熵密度正比于其 温度的立方。粒子的能量密度温度的立方。粒子的能量密度(决定它能完成的运算数决定它能完成的运算数)表表 现为其温度的现为其温度的4次幂。信息比特的总数恰是其运算数的次幂。信息比特的总数恰是其运算数的3/4 次方。次方。 信息的感知属性信息的感知属性感知信息感知信息感知的信息感知的信息 理论；理论； 信息的美学属性信息的美学属性美学美学信息信息信息的信息的美美 学学理理论。论。 五、五、Shannon信息论在研究方法上的启示信息论在研究方法上的启示 1理论与实际的关系理论与实际的关系。五十年信息论发展的历史证。五十年信息论发展的历

47、史证 明，理论必须结合明，理论必须结合(扎根于扎根于)实际才有旺盛的生命力，实际实际才有旺盛的生命力，实际 可以帮助人们正确地提出问题和猜想；实际需要理论的指可以帮助人们正确地提出问题和猜想；实际需要理论的指 导才能建立更好的系统，才能迅速向前发展。理论用于不导才能建立更好的系统，才能迅速向前发展。理论用于不 断变化的实际过程中，又常常提示和激励我们探索新的理断变化的实际过程中，又常常提示和激励我们探索新的理 论问题，并以新的方法重新检验已有的理论结论。可以有论问题，并以新的方法重新检验已有的理论结论。可以有 数不胜数的例子说明这点。数不胜数的例子说明这点。 多分辩率编码即多分辩率或逐步多分辩

48、率编码即多分辩率或逐步(Progressive)传送源传送源 编码在过去十年有很大进展。这是因为在编码在过去十年有很大进展。这是因为在WWW移动通信移动通信 系统、分集编码卫星系统都需要嵌入大范围变速源的描述系统、分集编码卫星系统都需要嵌入大范围变速源的描述 ，因而鼓励人们研究多分辩率编码并得到了相应的理论结，因而鼓励人们研究多分辩率编码并得到了相应的理论结 果。另一方面它也是信息论指导和自然的发展结果。果。另一方面它也是信息论指导和自然的发展结果。 2简化模型简化模型。理论的作用是浓缩知识之树，而不。理论的作用是浓缩知识之树，而不 是膨胀它是膨胀它(the role of theory is

49、 to shrink the tree rather t han to grow itB. Gallager)，由基本例子建立正确的，由基本例子建立正确的 、可以包容广泛现象的、概括性的模型，正确地提出问、可以包容广泛现象的、概括性的模型，正确地提出问 题，发展一套描述和处理问题的方法，达到明确回答所题，发展一套描述和处理问题的方法，达到明确回答所 提问题的目的。这是提问题的目的。这是Shannon信息论所提供的成功例证信息论所提供的成功例证 。“简单模型胜于繁琐的现象罗列简单模型胜于繁琐的现象罗列”， “简单化才能简单化才能 显现出事物的本质，它表现了人的洞察力显现出事物的本质，它表现了人的

50、洞察力”。华罗庚先。华罗庚先 生所提倡的生所提倡的 “由厚到薄由厚到薄”也是这个道理。也是这个道理。Shannon在在 研究问题中尽量简化到不能再简的程度。马克思在研究研究问题中尽量简化到不能再简的程度。马克思在研究 资本主义社会的复杂现实中，抓住资本主义社会的复杂现实中，抓住 “商品商品”这个最本这个最本 质的东西建立了质的东西建立了 “资本论资本论”的宏伟大厦。的宏伟大厦。 好的性能量度和复杂性的量度（信息量、熵、信道好的性能量度和复杂性的量度（信息量、熵、信道 容量、商品等），常会引导出优秀的理论结果和令人满容量、商品等），常会引导出优秀的理论结果和令人满 意的实际应用。意的实际应用。 3基础的重要性基础的重要性。切莫近视、急功近利。切莫近视、急功近利。 4对偶性对偶性。Shannon在在1959年的逼真度准则一文中年的逼真度准则一文中 说说 : 对偶性可以更进一步，并且可以和过去与未来之间对偶性可以更进一步，并且可以和过去与未来之间 的对偶性相关连起来，并以控制与知识表示。我们可以的对偶性相关连起来，并以控制与知识表示。我们可以 有关于过去的知识，但已不能控制它；我们可以控制未有关