信息论武汉计算机学院一讲

张焕国武汉大学计算机学院信息论博士课程：

目录

第一部分密码1、通信系统的数学模型2、自信息和熵3、互信息4、信源编码5、完善保密6、唯一解距离7、乘积密码

目录

第二部分纠错编码1、纠错编码的基本概念2、线性分组码的基本理论3、线性分组码在计算机系统中的应用4、循环码的基本理论5、典型循环码及应用

为了表彰信息论的创始人Shannon的伟大功绩，2000年10月6日IEEEInformationSociety的25名成员，在Shannon儿童时代的老家Michigan的Gaylord举行了Shannon塑像落成典礼。 著名信息论和编码学者Dr.RichardBlahut在典礼上致辞说：

“在我看来，两三百年之后，当人们回过头来看我们这个时代的时候，他们可能不会记得谁曾经是美国总统，他们也不会记得谁曾经是影星或摇滚歌星，但是仍然会知道Shannon的名字，学校里仍然会讲授信息论。”一、信息论概论

普遍认为：能源、材料和信息是支撑现代社会大厦的三根支柱。其中能源、材料是物质的。而信息是逻辑的，抽象的。控制论创始人维纳说：“信息就是信息，不是物质，也不是能量。”信息不能脱离载体（如语音、文字、图象等）而孤立存在。信息蕴涵在载体之中，并随载体而传输和处理。因此，不能脱离信息系统而孤立地谈论信息安全。换句话说，每当我们谈论信息安全时，都不可避免地要谈论信息系统安全。反之，每当我们谈论信息系统安全时，也就必然要谈到信息安全。一、信息论概论

信息是蕴涵在载体之中对用户具有不确定性的内涵。消息是载体,信息是内涵。信息的三种状态：存储，传输，处理信息论是信息科学的理论基础之一信息论是信息科学领域的哲学本课程将从信息安全角度来讨论信息论，这是本课程的出发点。一、信息论概论二、通信系统的数学模型

1、概论①信息论是研究信息传输、存贮和处理中一般规律的科学。②信息论可分为狭义信息论和广义信息论。狭义信息论主要研究信息传输（通信）的一般规律，因此又可以称为通信论。信息论的奠基之作：Shannon,C.D.,AMathematicalTheoryofCommunication,BSTJ,27(4),1948.

用概率统计的观点研究了随机干扰下的信息传输问题,奠定了通信的理论，使信息论成为通信的理论基础。Shannon,C.D.,CommunicationTheoryofSecrecySystem,BSTJ,28(4),1949.

用信息论的观点研究了信息保密问题，奠定了信息保密的理论，使信息论成为密码学和信息隐藏的理论基础。二、通信系统的数学模型

狭义信息论主要研究内容：信息度量：熵理论信源编码：压缩编码，信号理论信道编码：纠错码、密码、同步码信息传输：调制解调，失真理论，信号检测广义信息论超出狭义信息论的范围，不仅研究信息传输，而且研究信息的表示、获取、存储和处理。③Shannon，C.D.是信息论的奠基人之一。哈特莱、冯诺伊曼、维纳等学者都作出重要贡献。④信息论的新发展：量子信息论；量子通信，量子密码，量子计算光信息论；光存储，光通信，光计算生物信息论：生物存储，生物通信，生物计算二、通信系统的数学模型

量子信息

量子通信

2008年8月4日《自然》报道，日内瓦大学的物理学家试验发现：即使将两个纠缠态亚原子粒子分隔宇宙距离，它们之间的通信也几乎不需要时间，其速度比光速快1万倍。

2009年我国宣布：国际上首个量子通信网络由我国科学家在安徽芜湖地区测试运行成功，用于地区电子政务。目前世界上量子通信距离达到250公里。

量子计算信息量大：1位的二进制数含有1bit信息，而1个qubit含有1bit以上的信息，因为它除了0和1之外还有其他的内容。

具有天然的并行性:n位的量子计算,一次计算2n个量子状态.二、通信系统的数学模型

量子信息

量子计算机2001年IBM公司率先研制成功了7qbit的示例性量子计算机2007年2月加拿大的D-WaveSystem公司宣布研制出世界上第一台商用16量子位(qubit)的量子计算机。2007年11月，Dwave宣布研制成功28qubit量子计算机。

2008年5月，Dwave研制成功48qubit量子计算机系统。Dwave同时公布了128qubit的量子处理器的CAD图。

量子计算机的影响指数级的计算能力，使得量子计算机能够用多项式时间解决在电子计算机上无法解决的指数复杂度问题直接的影响是对现有公要密码（RSA、ELGamal、ECC等）构成严重威胁量子计算机的出现是伟大的，而计算规模的提升只是时间问题。二、通信系统的数学模型

量子信息

二、通信系统的数学模型

生物信息

生物计算1994年美国加州大学的L.Adleman提出DNA计算的思想，并在液体中进行实验。DNA计算的基本思想： 以DNA碱基序列为信息编码的载体，利用现代分子生物学技术，在试管内控制酶的作用下，进行DNA序列反应。反应前的DNA为输入，反应后的DNA为输出。具有并行性：运算速度快，1.2

1018次/s，是目前最快的计算机1.2

106倍。高存储密度：每（纳米）3存储1bit，而现在的存储介质每（纳米）12存储1bit。节省能源：能耗是目前超级计算机的1/1018。二、通信系统的数学模型

生物信息

生物计算机2003年以色列研制出可玩游戏的人机交互DNA计算机L.Adleman用DNA计算机求解了一个24个未知数、100万种可能性的数学难题 注意:能求解数学难题，就可能破译密码。DNA计算与量子计算类似，具有天然并行性，具有指数级处理能力，所以可以用多项式时间解决指数复杂度问题。二、通信系统的数学模型

生物信息

生物计算输入DNA生物化学反应输出DNA信息输出信息输入控制酶三、通信系统的数学模型

2、通信系统的数学模型

信源编码器信道信宿译码器mm’干扰①信源：产生信息的源人或机器；离散的或连续的；如果离散信源的输出符号彼此统计独立，则称为无记忆信源。cc二、通信系统的数学模型

②编码器：将信源发出的消息m变换成适于在信道上传输的信号c信源编码：减少数据冗余，提高信息传输的有效性。信道编码：纠错码、密码和同步码，分别确保信息传输的可靠性、安全性和同步。

③信道：用于信息传输、存储和计算的媒质或通道传输信道：有线、无线。存储信道：纸、磁盘、光盘、半导体存储器等。计算信道：运算器。④干扰：外界干扰和内在干扰外在干扰：由外界引入的干扰（如天电干扰），称之为加性干扰。内在干扰：信号在传输过程中由于物理条件（如温度）的变化而引起器件参量的随机变化，称为乘性干扰。

二、通信系统的数学模型

⑤译码器：编码的逆变换把受干扰的信道输出,尽可能精确地恢复成原来的信源输出。⑥信宿：消息的接收者可以是人或机器。

三、保密系统的数学模型

1、保密系统框图

信源加密器信道信宿解密器mm分析者cc加密钥解密钥安全信道kekd密钥三、保密系统的数学模型

2、保密系统的数学描述

明文空间M

密文空间C

密钥空间K

加密算法F

解密算法F－1①明文与明文空间设明文字母表为X，

X={a1,a2,…,aN}

字母ai出现的概率为pi，1≥

pi≥0,且。信源产生的长为l的符号序列，称为消息或明文。

m={m1,m2,…,ml}

，mi∈X

消息m的全体称为消息空间或明文空间，记作M。M=Xl={m={m1,m2,…,ml}|mi∈X,1≤i≤l}M含有Nl个元素。密码体制CS＝三、保密系统的数学模型

2、保密系统的数学描述①明文与明文空间若信源无记忆时，各明文符号彼此统计独立，所以明文m出现的概率若信源有记忆，需要考虑P中各元素的概率分布。三、保密系统的数学模型

2、保密系统的数学描述②密钥与密钥空间密钥源是产生密钥的源地。密钥源通常是离散的、无记忆的、且均匀分布的，所以各密钥符号独立等概。设密钥字母表为B，

B={k1,k2,…,ks}字母kt出现的概率为pt，1≥

pt≥0且。密码设计中常使用长为r的密钥，记作：

k=(k1,k2,…,kr),ki∈B,i=1,2,…,r三、保密系统的数学模型

2、保密系统的数学描述②密钥与密钥空间密钥k的全体称为密钥空间，记作K，即

K=Br={k=(k1,k2,…,kr)|

ki∈B,1≤i≤r}K含有Sr个元素。注意：明文空间与密钥空间彼此独立。合法的接收者知道k和K。窃听者不知密钥k，也可能不知道密钥空间K，也可能知道密钥空间K。

三、保密系统的数学模型

2、保密系统的数学描述③密文与密文空间加密变换Ek在密钥k的控制下将明文m变成密文c，即

c=(c1,c2,…,cv)=Ek(m1,m2,…,ml),ci∈Y,i=1,2,…,v其中Y

为密文字母表，通常假设，Y与明文字母表X

相同，明文、密文长度相等，即v=l。密文c的全体称为密文空间，记作C，即

C=Yv={c=(c1,c2,…,cv)|ci∈Y,i=1,2,…,v}C含有NV个元素。

三、保密系统的数学模型

2、保密系统的数学描述④加密算法加密变换Ek是明文空间M

到密文空间C

的映射，即

Ek:M→Cc=(c1,c2,…,cv)=Ek(m1,m2,…,ml),ci∈Y,i=1,2,…,v加密算法是加密变换的集合：

F＝｛Ek｝对于每一个确定的密钥k，F

都确定出一个具体的加密变换Ek。加密变换Ek在密钥k的控制下将明文m

变成密文c

。

三、保密系统的数学模型2、保密系统的数学描述⑤解密算法解密变换Dk是密文空间C到明文空间M

的映射，即

Dk:C→Mm=(m1,m2,…,ml)=Dk(c1,c2,…,cv),mi∈X,i=1,2,…,l

注意：解密变换Dk是加密变换Ek的逆。解密算法是解密变换的集合：

F－1＝｛Dk｝对于每一个确定的密钥k，F－1都确定出一个具体的解密变换Dk。解密变换Dk在密钥k的控制下将密文c变成明文m。三、保密系统的数学模型

3、保密系统的概率特征结论：密文空间的统计特性由明文和密钥的统计特性所决定。设明文m出现的概率为p(m)，密钥k被选择的概率为p(k)。对任意的一个密钥k，用k令加密所有明文，并作密文集合由于明文空间与密钥空间相互独立，对每一个c∈C，都有

(1)三、保密系统的数学模型

3、保密系统的概率特征结论：密文空间的统计特性由明文和密钥的统计特性所决定。又因为所以由Bayes公式可得

(2)(3)3、保密系统的概率特征结论：密文空间的统计特性由明文和密钥的统计特性所决定。公式(1)、(2)、(3)说明，知道了明文空间和密钥空间的概率分布，就可确定出： ①密文空间的概率分布； ②密文空间关于明文空间的概率分布； ③明文空间关于密文空间的概率分布。三、保密系统的数学模型

三、保密系统的数学模型

4、Kerckhoff假设密码分析者能够从信道上截获密文；知道所使用的密码算法；不知道加密密钥。结论：

强密码体制的安全性应当完全取决于所用密钥的安全性，而不取决于对加密算法的保密。注意：Kerckhoff假设仅