代数系统的应用.

Presentation on theme: "代数系统的应用."— Presentation transcript:

1 代数系统的应用

2 为什么要研究代数系统？ 在一个非空集合上，确定了某些运算以及这些运 算满足的规律，于是该非空集合中的元素就说是 有了一种代数结构。
现实世界中可以有许多具体的不相同的代数系统。但 事实上，不同的代数系统可以有一些共同的性质； 我们要研究抽象的代数系统，并假设它具有某一类具 体代数系统共同拥有的性质。任何在这个抽象系统中 成立的结论，均可适用于那一类代数系统中的任何一 个。

3 为什么要研究代数系统？ 代数是专门研究离散对象的数学，是对符号的操 作，是现代数学的三大支柱之一。
代数从19世纪以来有惊人的发展，带动了整个数学的 现代化； 随着信息时代的到来，计算机、信息都是数字（离散 化）的，甚至电视机、摄像机、照相机都在数字化。 另两个：分析、几何

4 抽象代数学的应用简介 100多年来，随着科学的发展，抽象代数越来越 显示出它在数学的各个分支、物理学、化学、力 学、生物学等科学领域的重要作用。 在许多实际问题的研究中都离不开数学模型，而 构造数学模型就要用到某种数学结构，而抽象世 代数研究的中心问题就是一种很重要的数学结构- -代数系统：半群、群、格与布尔代数等等。 抽象代数的概念和方法也是研究信息科学（计算 机、通信等）的重要数学工具。

5 应用举例 半群理论在自动机理论和形式语言中发挥了重要作用； 有限域理论是编码理论的数学基础，在通讯中起过重 要的作用；
格和布尔代数则是电子线路设计、电子计算机硬件设 计和通讯系统设的重要工具； 描述机器可计算的函数、研究算术计算的复杂性、刻 画抽象数据结构、描述作为程序设计基础的形式语义 学，都需要抽象代数知识。

6 “群”的起源 法国数学家，近代代数学的创始人----伽罗瓦 (E. Galois，1811-1832) 方程的根式求解 一元一次方程：
一元二次方程： 一元三次方程：

7 一元三次方程经过适当的变量替换后化为如下方程：
三个根是:(意大利数学家卡尔达诺《大术》1545年) 其中 是3次单位根，

8 一元四次方程： 移项： 两边加上 得： 令右边的判别式为零，求得 y 的一个三次方程，求其根，代入上式，求得根x。(卡尔达诺学生----费拉里发现，记载于《大术》中)

9 问题：一般一元n次方程是否有类似的根式解？
高斯(Gauss C.F. 德国数学家， )于1799年哥丁根大学完成的博士论文证明了代数基本定理： 每一个次数大于等于1的n次复系数多项式恰有n个根 法国数学家：拉格朗日( )(预解式)， 德国数学家：高斯(分圆方程 ) 挪威数学家：阿贝尔( )

10 伽罗瓦的最主要功绩： 首先提出根的置换概念，每一个方程都可以与一个置换群联系，从而用群论方法彻底解决的方程根式解问题，更重要的是，群论的引入，为现代代数学的发展奠定了基础。 方程与群的联系：给定多项式 f(x), 称为 f 的分裂域， 伽罗瓦群 ，其元素是 的所有置换。

11 群为什么要这样定义？ 群是为了解方程提出的 对群的定义，是一个可以解方程的最简单的定义。

12 群在化学中的应用 化学分子对称群（分子对称群仅有32种） 研究分子的对称性加深人们对物质性质的认识 氨分子： (1个氮原子N和3个氢原子H)
比较分子结构图与正四面体图的对称 变换区别： 1) A为不动点 2) a,b,c在一个平面上为正三角 形，作它们的对称变换 3) 习惯上记氨的分子对称群记 为 ，由6个元素组成。 A a b c

13 各种晶体中原子排列是一个有一定规则的多面体，可以利用空间格点加以表述。例：氯化纳晶体原子排列模型：
19世纪后半叶，科学家发现： 1. 晶体外形的全部对称形式为对称点群，共32种 2. 晶体内部构造一切可能的对称形式为空间群，230种 晶体分类的数学理论是由俄国数学家E.C.费多罗夫应用 群的结构理论于1891年创立。1912年德国物理学家冯. 劳厄利用X射线的衍射实验证实了晶体对称群的存在性， 为此他获得1914年度的诺贝尔物理奖。 随后英国科学家布拉格父子利用劳厄方法和空间群的 计算，给出了晶体中原子的固有排列形状，为此获得 1915年诺贝尔物理学奖。 白：钠原子 氯：氯原子

14 群和魔方 1974 年春天， 匈牙利布达佩斯应用艺术学院 的建筑学教 授厄尔诺·鲁比克（Ernő Rubik） 设计了一个教学工具来 帮助学生直观地理解空间几何的各种转动； 由小方块组成、各个面能随意转动的 3×3×3的立方体；  方便演示各种空间转动。 魔方：Rubik's Cube 

15

16 三阶魔方简介 魔方总的变化数： 块数：3x3x3-1=26 面数：6 每个面有3x3=9个小面 其中8个角块，12个边块，6个中心块

17 定义1 说明： “转动”是指将魔方的某个面上的所有块顺时针（面对该面）旋转90度，“逆转动”是逆时针旋转90度。
不考虑中间层的转动，以为可以通过相邻两侧的转动代替，这样可以简化； 不对中间层转动，则各个面的中心块都是固定的，因此，涉及魔方各个面的时候，总是指其中心块代表的那个面，即提供一个固定的参考系。

18

19 定理：由魔方所有转动生成的集合，以“转动”的合成作为运算，构成一个群，称为魔方群。 说明：转动的合成运算不可交换；
如果把魔方拆开，再随机拼装，并不是每种拼装方法都可以还原的，其实可以分成12类，同类中任意两个状态可以相互转换，但不同类之间不可以。 12其实就是计算总状态数的公式中的分母； 可看作12个等价类。

20 上帝之数 问题：将任意三阶魔方打乱后，最小还原步数 究竟是多少？
这一问题1978年芬兰首都赫尔辛基的一次国际 数学家代表会议上提出，困扰了数学家长达三 十多年； 这个最小还原步数也被称为“上帝之数”。

21 研究历史 1995年，里德通过计算发现，最多经过30次转动，就可以将魔方的任意一种颜色组合复原。
2006年，奥地利博士生拉杜将结果推进到27。 2007年，美国科学家孔克拉和库伯曼又将结果推进到26。 2008年，研究“上帝之数”15年的计算机高手罗基奇将它的估计值从25压缩到22，这是全世界范围内的最佳结果。罗基奇的计算得到索尼影像的支持，这家公司向罗基奇提供了相当于50年不停歇计算所需的计算机资源。

22 美国加利福尼亚州科学家2010年7月利用计算机破解了这 一谜团，他们证明任意组合的魔方均可以在20步之内还原。 上帝之数=20

23 思路 为了让问题简单化，研究团队采用了“群论” ； 首先将魔方所有可能的起始状态集分成22亿个集合， 每个集合包含了195亿个可能的状态；
集合的分配原则是这些可能的状态是如何应对一组10个可能的 还原步骤； 再通过魔方不同的对称性，这种分组技术使得研究团 队将集合数减少到5600万个； 研究人员所采用的算法可以快速将这些还原步骤与恰 当的起始点匹配起来，从而实现在20秒内处理一个集 合中的195亿种可能。

24 公钥密码体制 对称加密方法 主要工作方式： 工作条件： (1) 位移式 (2) 置换式 (1) 通信双方都要拥有（相同的）密钥
(2) 密钥交换要安全

25 公钥密码体制 对称加密方法的不足 对称密码体制的优点是计算速度快，有较强的保密性。 缺点： 1）密钥管理量的困难
传统密钥管理：两两分别用一个密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。 n=100 时， C(100,2)=4,995； n=5000时，C(5000,2)=12,497,500

26 从对称算法到非对称算法 对称密钥加密中的密钥 当通信的某一方有n个通信关系,那么他就要维护“n”个专用密钥( 即每把密钥对应一通信 )

27 从对称算法到非对称算法 2）密钥必须通过某一信道协商，对这个信道的安全性的要求比正常的传送消息的信道的安全性要高；
3）数字签名：传统加密算法无法实现抗抵赖的需求； 数字签名就是在信息的后面再加上一段内容，可以证明信息没有被修改过。 4）在进行保密通信时，发送者与接收者需要使用一个安全信道来建立会话密钥。会话密钥的取得可以通过两种方式实现： (1) 通过共享密钥加密传输会话密钥（人工方式获得） (2) 通过密钥分配中心获得会话密钥，分配成本很高。

28 公钥密码体制的起源 1976年，Standford Uni. Diffie博士和其导师Hellman在 IEEE Trans. on IT 上发表划时代的文献： W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP 这一体制的出现为解决计算机信息网中的安全提供了新的 理论和技术基础，被公认为现代够公钥密码学诞生的标志。 1978年，MIT三位数学家R.L.Rivest， A.Shamir和L.Adleman 发明了一种用 数论构造双钥体制的方法，称作MIT体 制，后来被广泛称之为RSA体制。

29 非对称密码体制也叫公钥加密技术，该技术就是针对私钥 密码体制的缺陷被提出来的； 公钥加密系统也可称为公钥密码体制
加密和解密是相对独立的，加密和解密会使用两把不同的密钥； 加密密钥(公开密钥)向公众公开，谁都可以使用； 解密密钥(秘密密钥)只有解密人自己知道； 非法使用者根据公开的加密密钥无法推算出解密密钥。 公钥密码体制的算法中最著名的代表是RSA系统，此外还有：背包密码、McEliece密码、Diffe_Hellman、Rabin、零知识证明、椭圆曲线、EIGamal算法等。

30 公钥密码体制的基本原理 公钥密码学与其他密码学完全不同： 公钥算法基于数学函数而不是基于替换和置换 使用两个独立的密钥
公钥密码学的提出是为了解决两个问题： 密钥的分配 数字签名

31 公钥密码体制的基本原理 基本思想和要求 用户拥有自己的密钥对(KU,KR)，即（公开密钥public key，私有密钥private key） 公钥KU公开，用于加密； 私钥KR保密，用于解密； 只有信息的预期接收者才能解密； 通过加密密钥不可能（或者至少在很长一段时间内不 可能）找到解密密钥（通过大量运算） 如果一个人用私钥加密，别人可以用相应的公钥解密， 即可以实现认证。

32 公钥密码体制的加密解密过程 Bob: Plain Text Cipher Text D Network E Alice Bob
Secret Key

33 公钥密码体制的基本原理 公钥体制的主要特点： 加密和解密能力分开； 多个用户加密的消息只能由一个用户解读；
用于公共网络中实现保密通信； 只能由一个用户加密消息而使多个用户可以解读 可用于认证系统中对消息进行数字签字； 无需事先分配密钥； 密钥持有量大大减少； 提供了对称密码技术无法或很难提供的服务 如与哈希函数联合运用可生成数字签名，可证明的安全伪随机 数发生器的构造，零知识证明等。

34 公钥密码体制的基本原理 基本思想和要求 涉及到各方 涉及到数据 公钥算法的条件： 发送方、接收方、攻击者 公钥、私钥、明文、密文
产生一对密钥是计算可行的 已知公钥和明文，产生密文是计算可行的 接收方利用私钥来解密密文是计算可行的 对于攻击者，利用公钥来推断私钥是计算不可行的 已知公钥和密文，恢复明文是计算不可行的 (可选)加密和解密的顺序可交换

35 公钥密码体制的基本原理 如何设计一个公钥算法 公钥和私钥必须相关，而且从公钥到私钥不可推断
必须要找到一个难题，从一个方向走是容易的，从另一个方向走是困难的 如何把这个难题跟加解密结合起来 一个实用的公开密钥方案的发展依赖于找到一个陷阱门单向函数f： (1)给定x，计算y=fk(x)是容易的； (2)给定y，计算x使x=fk-1(y)是不可行的。 (3)存在k，已知k时,对给定的任何y，若相应的x存在，则计算x使fk-1(y)是容易的。

36 公钥密码体制的基本原理 非对称密钥加密的原理 使用数学上的理论； 数学上某些复杂的计算问题：正向计算容易，反向计 算困难。 例如：
计算机不可能在有效的时间内算出反向结果（从而不可能破解 密码）。 例如： 计算两个大数的乘积，非常容易。 分解一个很大的数（如200多位）非常困难，假如这个大数只 含有两个非常大的素数（各100多位）作为因子。

37 公钥密码体制的基本原理 公钥密码所依赖的数学难题 背包问题
大整数分解问题（The Integer Factorization Problem, RSA体制） 二次剩余问题 模n的平方根问题 离散对数问题： 有限域的乘法群上的离散对数问题（The Discrete Logarithm Problem, ELGamal体制） 定义在有限域的椭圆曲线上的离散对数问题（The Elliptic Curve Discrete Logarithm Problem，类比的ELGamal体制）

38 公钥密钥的应用范围 加密/解密 数字签名(身份鉴别) 密钥交换
公钥密码体制的基本原理 公钥密钥的应用范围 加密/解密 数字签名(身份鉴别) 密钥交换 算法 加/解密 数字签名 密钥交换 RSA 是 Dieffie-Hellman 否 DSS

39 RSA算法描述 原理：依据于两个大素数的乘积为模数，对指数取模 每个人都有一个加密的密钥，密钥由两个部分组成 (1) 模数n = pq
(2) 与(n)=(p-1)(q-1)互素的指数e 由于n是很大的素数p、q的乘积，则对n的分解很难快速完成，这是很难破解解密密钥的一个重要原因。

40 RSA算法描述 加密： 把明文翻译成数字，比如用两位数字代替一个字母； 则明文会转换成一个很长的整数；
将这个整数分组，各个组是一个大整数，代表一个字母段，用M表示； 加密时，将M转换成为密文C C = Me mod n 公钥

41 RSA算法描述 例：设明文为STOP，取p=43，q=59，e=13 则n=43x59=2537
gcd(e,(p-1)(q-1))=gcd(13,42x58)=1 把STOP翻译为整数，并分组，得到 C = Me mod n=M13 mod 2537 则 mod 2537=2081 mod 2537=2182 即密文： 最大公约数

42 RSA算法描述 Cd ≡M(mod pq)，即M=Cd(mod n) de≡1(mod (p-1)(q-1)) 解密
私钥 解密 解密密钥d为 e mod (p-1)(q-1)=1的逆数 由于gcd(e,(p-1)(q-1))=1，可知这个逆数一定存在 如果de≡1(mod (p-1)(q-1)) 则存在整数k，使得de=1+k(p-1)(q-1) 则Cd=(Me)d=Mde=M1+k(p-1)(q-1) Cd ≡M(mod pq)，即M=Cd(mod n) 互素 例：以上例中的加密信息为目标，d=937 为 13 mod 42x58=2436的逆数，即d=937为解密指数 解密： 计算p=C937 mod 2537 mod 2537=1819， mod 2537=1415

43 RSA算法的安全性 RSA安全性依据： RSA的安全性是基于加密函数ek(x)=xe(mod n)是一个单向函数，所以对攻击的人来说求逆计算不可行。而Bob能解密的陷门是分解n=pq，根据(n)=(p-1)(q-1)，从而用欧氏算法解出解密私钥d。 大部分对RSA密码分析的讨论都集中在对n进行素因子分解上，给定n确定(n)就等价于对n进行因子分解。给定e和n时使用目前已知的算法求出d在时间开销上至少和因子分解一样大。 因此可以把因子分解性能作为一个评价RSA安全性的基准。

44 Million Instructions Per Second
RSA算法的安全性 RSA安全性依据： 每个合数都可以唯一地分解出素数因子： 6 = 2*3， = 131*121 因子分解复杂度 Million Instructions Per Second 密钥长(bit) 所需的MIPS-年 116(Blacknet密钥) ,000 ,000 ,000,000 ,000,000,000 ,000,000,000,000,000,000

45 RSA算法的安全性 RSA安全性依据： 若使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来。
EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位之间，但必须是128的倍数。 国际数字签名标准ISO/IEC 9796中规定n的长度位512比特位至1996年，建议使用768位的模n。

46 对RSA算法的攻击方法 对RSA算法的攻击方法： 对RSA的具体实现存在一些攻击方法： 强力攻击（穷举法）：尝试所有可能的私有密钥
数学分析攻击：各种数学方法，等价与两个素数乘积 的因子分解 对RSA实现的攻击 对RSA的具体实现存在一些攻击方法： 对RSA的选择密文攻击 对RSA的公共模攻击 对RSA的小加密指数攻击 对RSA的小解密指数攻击 时间性攻击：取决于解密算法的运算时间

47 对称加密的优缺点 对称加密的优点 对称加密的缺点 速度快，处理量大，适用于对应用数据的直接加密；
加密密钥长度相对较短,如40比特～256比特； 可构造各种加密体制 如产生伪随机数、HASH函数等。 对称加密的缺点 密钥在双方都要一致、保密，传递较难； 大型网络中密钥量大，难以管理； 密钥需要经常更换。

48 公钥算法优缺点 公钥加密的优点 只有秘密钥保密，公开钥公开。 密钥生命周期相对较长。 许多公钥方案可以产生数字签名机制。
在大型网络上，所需的密钥相对较少。 公钥加密的缺点 速度慢，处理量少，适用于密钥交换。 密钥长度相对较长。 安全性没有得到理论证明。

49 误区 公开密钥密码算法更安全 公钥的分发是简单和一目了然的 公开密钥密码使对称密钥密码过时了
安全程度基于密钥长度和计算工作量，二者并不比对方优越。 其实公开钥算法天生具有更大的危险性。 公钥的分发是简单和一目了然的 对称密钥算法密钥分配是比较复杂，但是公开钥算法存在如 何保证一个问题，即如何确认一个公开钥与其拥有者的对应 问题。 公开密钥密码使对称密钥密码过时了 公开钥算法因速度问题更适合密钥交换。 实际应用是公开钥算法和对称钥算法的结合。 公钥算法用于签名和认证； 用公钥算法传输会话密钥； 用会话密钥/对称算法加密批量(bulk)数据

50 数字证书（Digital Certificate）
数字证书就是互联网通讯中标志通讯各方身份信息的 一系列数据，提供了一种在Internet上验证您身份的方 式，其作用类似于司机的驾驶执照或日常生活中的身 份证； 数字证书是由一个由权威机构--证书中心（Certificate Authority，CA）发行的，人们可以在网上用它来识别 对方的身份。

51 数字证书（Digital Certificate）
数字证书是一个经证书授权中心数字签名的包含公开 密钥拥有者信息以及公开密钥的文件； 最简单的证书包含一个公钥、身份名称以及证书授权 中心的数字签名； 相当于把一个人和他的公钥绑定到一起，并经过权威机构审 核盖章确认。 目前数字证书的格式普遍采 用的是X.509 v3国际标准， 内容包括：证书序列号、证 书持有者名称、证书颁发者 名称、证书有效期、公钥、 证书颁发者的数字签名等。

52 数字证书（Digital Certificate）
原理 数字证书绑定了公钥及其持有者的真实身份； 当使用数字证书进行身份认证时，它将随机生成 128位的身份码，每份数字证书都能生成相应但每 次都不可能相同的数码，从而保证数据传输的保密 性； 数字证书类似于居民身份证，所不同的是数字证书 不再是纸质的证照，而是一段含有证书持有者身份 信息并经过认证中心审核签发的电子数据，可以更 加方便灵活地运用在电子商务和电子政务中。

53

54 群论在编码理论中的应用 将信源的信息转化为数字信息传送给收信者称为数字通信，编码在数字通讯、计算机和数据处理等科学技术中有广泛应用。
工程上最易实现的是二元数字信息的传送，二元数字信息就是有限长的二元n元数组(c1,…,cn). 二元n元数组可以表达2n种不同的符号，因此英文字母、数字及有关号码可用适当的二元n元数组表示之， 为解决数字传输过程中可能出现的干扰，除采用各种技术处理外，常采用抗干扰编码的方法。

55 设Z2n是信息源的原始数字信息集合。取自然数m>n, 作 单射E: Z2n → Z2m
设Z2n是信息源的原始数字信息集合。取自然数m>n, 作 单射E: Z2n → Z2m. ImE称为码，ImE中元素称为码字，m 称为码长，码字的分量称为码元。 显然 Z2m 是域Z2上的向量空间，如果ImE是Z2m的子空间, 称ImE是二元线性码，由于(Z2m,+)的子群与子空间一致， 因此二元线性码也称为群码。特别地，当对某些特殊的 编码函数E : Z2n → Z2m,可以使E成为群同态。比如，E : Z2n → Z2m使E(X)=XG，其中G是一个nm矩阵。 数字通信 群的问题

56 编码理论 编码是指为了达到某种目的而对信号进行的一种变换； 研究信息传输过程中信号编码规律的数学理论；
编码理论与信息论、数理统计、概率论、随机过程、线性代数、近世代数、数论、有限几何和组合分析等学科有密切关系，已成为应用数学的一个分支； 编码的逆变换称为译码或解码。 1928年美国电信工程师H.奈奎斯特提出著名的采样定理，为 连续信号离散化奠定了基础。 1948年美国应用数学家C.E.香农在《通信中的数学理论》一 文中提出信息熵的概念，为信源编码奠定了理论基础。 1949年C.E.香农在《有噪声时的通信》一文中提出了信道容 量的概念和信道编码定理，为信道编码奠定了理论基础。

57 编码理论历史 莫尔斯码 1843年美国著名画家S.F.B.莫 尔斯精心设计出莫尔斯码；
根据编码理论可以证明，莫尔 斯码与理论上可达到的极限只 差15％； 但是直到20世纪30～40年代 才开始形成编码理论。

58 编码理论的基本问题 如何提高一般通信系统的有效性和可靠性 如何提高加密通信系统的安全性 编码问题可以分为三类：
以提高数字信息传输、存储处理的有效性为宗旨的信源编码（Source coding）； 以保证数字信息传输和处理的可靠性为目的的信道编码（channel coding），又称为差错控制编码（error-control coding）； 以增加数字信息传输、存储的安全性为目标的数据加密编码（data encryption）。

59 信源编码 主要是利用信源的统计特性，解决信源的相关性，去掉信源冗余信息，从而达到压缩信源输出的信息率，提高系统有效性的目的。
信源编码要求尽量去掉冗余信息。 通信中的信源编码 语音压缩编码； 各类图像压缩编码； 多媒体数据压缩编码。

60 信源编码的主要目标 经典信源编码技术 现代编码压缩技术
提高通信系统的有效性，它通过对信源输出的消息进行适当的变换和处理，以达到提高传输效率的目的； 经典信源编码技术 主要依据信源本身的固有统计特性； 现代编码压缩技术 注重对人类感知特性的利用，使得编码效率得以极大提高； 比如一个图片中，对人不感兴趣的内容采用高压缩率。

61 信道编码 为了保证通信系统的传输可靠性，克服信道中的噪声和 干扰；
根据一定的（监督）规律在待发送的信息码元中（人为 的）加入一些必要的（监督）码元，在接受端利用这些 监督码元与信息码元之间的监督规律，发现和纠正差错， 以提高信息码元传输的可靠性； 信道编码的目的是试图以最少的监督码元为代价，以换 取最大程度的可靠性的提高； 信道编码需要适当增加冗余信息。

62 信道中的干扰使通信质量下降，也就是使信息传送不可靠。 对于模拟信号，表现在收到的信号的信扰比下降； 对于数字信号，表现在误码率增大。
信道编码的主要目标 研究如何提高信息传送的可靠性； 它通过对信源编码进行适当的变换和处理使其具有自动检错和纠错功能； 信道中的干扰使通信质量下降，也就是使信息传送不可靠。 对于模拟信号，表现在收到的信号的信扰比下降； 对于数字信号，表现在误码率增大。

63 信道编码从功能上可分为3类： 信道编码从结构和规律上分两大类： 仅具有发现差错功能的检错码，如循环冗余校验码、自动请求重传ARQ；
具有自动纠正差错功能的纠错码，如循环码中的BCH 码、RS 码及卷积码、级联码、Turbo码等； 既能检错又能纠错功能的信道编码，最典型的是混合ARQ。 信道编码从结构和规律上分两大类： 线性码：监督关系方程是线性方程的信道编码； 非线性码：监督关系方程是非线性的，FEC 是前向就错码，在不同系统中，不同信道采用的FEC 都不一样，有卷积码，Turbo 码等。

64 密码编码 密码编码是通信系统中的另一类编码问题，它的目的是通过加密或隐藏防止非授权用户对重要或机密信息的窃取、伪造和篡改，以保证通信的安全性、真实性和完整性 发送端的明文信息经过编码后成为密文，当授权者收到后，可用已有的密钥正确地译成明文； 对于非授权者，因没有密钥而无法取得该信息，从而保证通信的安全性。

65 例子： 要运一批碗到外地，首先在装箱的时候，将碗摞在一起，这就类似于信源编码：压缩以便更加有效率。
然后再箱子中的空隙填上报纸，泡沫，做保护，就像信道编码：保证可靠。 思考：信源编码要求尽量去掉冗余信息，而信道编码 需要适当增加冗余信息，这两者矛盾吗？

66 例： 信源编码信号： 例如语音信号（频率范围 Hz)、图象信号（频率范围0-6MHz)、基带信号（基带：信号的频率从零频附近开始）。 在发送端把连续消息变换成原始电信号，这种变换由信源来完成。 信道编码信号： 如二进制信号、2PSK信号、已调信号（即带通信号、频带信号）。 这种信号有两个基本特征：一是携带信息；二是适应在信道中传输，把基带信号变换成适合在信道中传输的信号完成这样的变换是调制器。

67 通信模型 按功能分为信源、编码器、信道、译码器、信宿 信 源 译 码 信 源 编 码 信 道 编 码 信 道 译 码 解 密 信 源 加 密
钥 源 密 钥 源 噪声

68 信源编码和信道编码总结 信源编码： 信道编码： 对视频、音频、数据进行的编码，即对信息进行编码以便处理；
作用一：设法减少码元数目和降低码元速率，即通常所说的数据压缩。码元速率将直接影响传输所占的带宽，而传输带宽又直接反映了通信的有效性； 作用二：当信息源给出的是模拟语音信号时，信源编码器将其转换成数字信号，以实现模拟信号的数字化传输。 信道编码： 在信息传输的过程中对信息进行的处理； 数字信号在信道传输时，由于噪声、衰落以及人为干扰等，将会引起差错。为了减少差错，信道编码器对传输的信息码元按一定的规则加入保护成分（监督元），组成所谓“抗干扰编码”； 接收端的信道译码器按一定规则进行解码，从解码过程中发现错误或纠正错误，从而提高通信系统抗干扰能力，实现可靠通信。

69 纠错码 在计算机中和数据通信中，经常需要将二进制数字信号进行传递，这种传递的距离近则数米、数毫米，远则超过数千公里。
在传递住处过程中，由于存在着各种干扰，可能会使二进制信号产生失真现象，即在传递过程中二进制信号0可能会变成1，1可能会变成0。 表示0和1的电平衰减或者被干扰后发生变化

70 由于存在着干扰对传输介质的影响，因而接收端收到的二进制信号串 中的 可能不一定就与xi相等，从而产生了二进制信号的传递错误。 发送端 接收端
二进制信号传递的简单模型 有一个发送端和一个接收端，二进制信号串X=x1x2…xn 从发送端发出经传输介质而至接收端。 由于存在着干扰对传输介质的影响，因而接收端收到的二进制信号串 中的 可能不一定就与xi相等，从而产生了二进制信号的传递错误。 发送端 接收端 X=x1x2 …xn 干扰

71 解决数据通信系统中传输错误问题的途径。 途径一： 途径二： 提高设备的抗干扰能力和信号的抗干扰能力，如提高天线增益。
从物理角度去提高抗干扰能力并不能完全消除错误的出现。 途径二： 采用纠错码（Error Correcting Code）以提高抗干扰能力。 纠错码的方法是从编码上下功夫，使得二进制数码在传递过程 中一旦出错，在接收端的纠错码装置就能立刻发现错误，并将 其纠正。 由于这种方法简单易行，因此目前在计算机中和数据通信系统 中被广泛采用。

72 为什么纠错码具有发现错误、纠正错误的能力呢？ 纠错码又是按什么样的原理去编码的呢？
一些基本概念： 由0和1组成的串称为字（Word）； 一些字的集合称为码（Code）； 码中的字称为码字（Code Word）； 不在码中的字称为废码（Invalid Code）； 码中的每个二进制信号0或1称为码元（Code Letter）。

73 例： 设有长度为2的字，它们一共可有22=4个，它们所组成 的字集S2={00，01，10，11}；
因为当S2中的一个字如10，在传递过程中其第一个码 元1变为0，因而整个字成为00时，由于00也是S2中的 字，故我们不能发现传递中是否出错。 即：变为其它的字，因此不能分辨

74 当选取S2的一个子集如C2={01，10}作为编码时就会发生另一种完全不同的情况。
不能任意选取 当选取S2的一个子集如C2={01，10}作为编码时就会发生另一种完全不同的情况。 因为此时00和11均为废码，而当01在传递过程中第一个码元由0变为1，即整个字成为11时，由于11是废码，因而我们发现传递过程中出现了错误。对10也有同样的情况。 没有在C2中出现 第一个码元错成11 第一个码元错成00 01 10 第二个码元错成00 第二个码元错成11

75 但是，这种编码有一个缺点，它只能发现错误而不 能纠正错误，因此我们还需要选择另一种能纠错的 编码。
例：考虑长度为3的字 它们一共可有23=8个，它们所组成的字集： S3={000，001，010，011， 100，101，110，111} 选取编码C3={101，010}。

76 纠错码的纠错能力 此编码不仅能发现错误而且能纠正错误 但是，上述编码有一个缺点： C2编码仅能发现错误，按C3编码可发现并纠正单个错误；
因为码字101出现单个错误后将变为：001，111，100；而码字 010出现错误后将变为110，000，011。 故如码字101在传递过程中任何一个码元出现了错误，整个码字只 会变为111、100或001，但是都可知其原码为101；对于码字010 也有类似的情况。 编码C3不仅能发现错误而且能纠正错误。 但是，上述编码有一个缺点： 只能发现并纠正单个错误，当错误超过两个码元时，它就既不能 发现错误，更无法纠正了。 C2编码仅能发现错误，按C3编码可发现并纠正单个错误； 可见：不同的编码具有不同的纠错能力。

77 编码方式与纠错能力之间的联系 设Sn是长度为n的字集，即： Sn={x1x2…xn|xi=0或1,i=1,2,…,n}
ⱯX，Y∈Sn, X=x1x2…xn, Y=y1y2…yn Z=X ◦ Y=z1z2…zn 其中，zi=xi +2 yi(i=1,2,…,n)，运算符+2为模2加运算， 称 运算“◦”为按位加； 即：0+21 = 1+20 = 1, 0+20 = 1+21 = 0 （Sn, ◦）是一个群 （Sn, ◦）是代数系统，运算“◦”满足结合律，单位元为00…0， 每个元素的逆元都是它自身。

78 定义：Sn的任一非空子集C，如果<C,ο>是群，即C是Sn的子群，则称码C是群码(Group Code)。
定义：设X=x1x2 … xn 和Y=y1y2 …yn 是Sn中的两个元素，称 为X与Y的汉明距离（Hamming Distance）。 思考其实际意义

79 从定义可以看出，X和Y的汉明距离是X和Y中对应位码元不同的个数； S3中两个码字000和011的汉明距离为2，000和111的汉明距离为3。
关于汉明距离，有以下结论： （1）H(X,X) = 0 （2）H(X,Y) = H(Y,X) （3）H(X,Y) + H(Y,Z) ≥ H(X,Z)

80 （3）H(X,Y) + H(Y,Z) ≥ H(X,Z)的证明
证明：定义 　　　 H(xi,yi)= 则：H(xi,zi)≤H(xi,yi)+H(yi,zi)，从而： 0 xi=yi 1 xi≠yi

81 定义：一个码C中所有不同码字的汉明距离的最小值称为码C的最小距离（Minimum Distance）,记为dmin(C)，即：
例如： dmin(S2)= dmin(S3)=1， dmin(C2)=2， dmin(C3)=3。

82 利用编码C的最小距离，可以刻画编码方式与纠错能力之间的关系：
〖定理1〗一个码C能检查出不超过k个错误的充分必要条件为dmin(C)≥ k+1。 〖定理2〗 一个码C能纠正k个错误的充分必要条件是dmin(C)≥ 2k+1。

83 例： 对于C2={01，10}，因为dmin(C2)=2=1+1,所以C2可以检查出单个错误；
对于S2和S3分别包含了长度为2、3的所有码，因而dmin(S2)= dmin(S3)=1，从而S2、S3既不能检查错误也不能纠正错误。 从而我们知道：一个编码如果包含了某个长度的所有码字，则此编码一定无抗干扰能力。 此时dmin=1

84 例：奇偶校验码（Parity code）的编码
编码S2={00，01，10，11}没有抗干扰能力。 但可以在S2的每个码字后增加一位（叫奇偶校验位）， 这一位是这样安排的，它使每个码字所含1的个数为偶 数，按这种方法编码后S2就变为： S2′={000，011，101，110} 而S2′的最小距离dmin(S2′)=2，故可知，它可检出单个错 误。即，当传递过程中发生单个错误，则码字就变为 含有奇数个1的废码。 只能检错，不能纠错， 因此称为校验码

85 类似地，增加奇偶校验位使码字所含1的个数为奇 数时也可得到相同的效果。
我们可以把上述结果推广到Sn中去，不管n多大，只要 增加一奇偶校验位总可能查出一个错误。 这种方法在计算机中是使用很普遍的一种纠错码，它 的优点是所付出的代价较小（只增加一位附加的奇偶 校验位），而且这种码的生成与检查也很简单，它的 缺点是不能纠正错误。 最小距离从1增大为2

86 纠错码的选择 前面分析发现： 从这里可以看出，如何从一些编码中选取一些码字组成新码，使其具有一定的纠错能力是一个很重要的课题；
S2无纠错能力，但在S2中选取C2后，C2具有发现单错的能力； S3无纠错能力，但在S3中选取C3后，C3具有纠正单错的能力。 从这里可以看出，如何从一些编码中选取一些码字组成新码，使其具有一定的纠错能力是一个很重要的课题； 下面我们介绍一种很重要的编码 — 汉明编码，这种编码能发现并纠正单个错误。

87 汉明编码 设有编码S4，S4中每个码字为a1a2a3a4，若增加三位校验位a5a6a7，从而使它成为长度为7的码字a1a2a3a4a5a6a7； 其中校验位a5a6a7应满足：　　　　　 也就是说要满足： a5 = a1 +2 a2 +2 a3 a6 = a1 +2 a2 +2 a4 a7 = a1 +2 a3 +2 a4 a1 +2 a2 +2 a a5 = 0 （1） a1 +2 a2 +2 a a6 = 0 （2） a1 +2 a3 +2 a a7 = 0 （3） 思考：为什么要这样设计？

88 a1,a2,a3,a4一旦确定，校验位a5,a6,a7可根据上述等式唯一确定。这样我们由S4就可以得到一个长度为7的编码C。
1

89 当C中码字发生单错后，不同的字位错误可使不同的等式不成立：
当a1发生错误时有且只有等式（1）（2）（3）不成立； 当a2发生错误时有且只有等式（1）（2）不成立； 当a3发生错误时有且只有等式（1）（3）不成立； 当a4发生错误时有且只有等式（2）（3）不成立； 当a5、a6、a7发生错误时，有且只有对应的等式（1）（2）（3）中的一个不成立； 设计的三个等式的8种（正确/错误）组合可对应a1~a7的七个码元每个码的错误以及一个正确无误的码字。

90 出错码元 等式（1） 等式（2） 等式（3） a1 不成立 a2 成立 a3 a4 a5 a6 a7 无

91 为讨论方便，建立三个命题： P1(a1,a2,…,a7): a1 +2 a2 +2 a a5 = 0 　　　P2(a1,a2,…,a7): a1 +2 a2 +2 a a6 = 0 　　　P3(a1,a2,…,a7): a1 +2 a3 +2 a a7 = 0 这三个命题的真假与对应等式是否成立相一致。 建立三个集合S1，S2，S3分别对应P1，P2，P3，令： S1＝｛a1,a2,a3,a5｝ S2＝｛a1,a2,a4,a6｝ S3＝｛a1,a3,a4,a7｝ 显然，Si是使Pi为假的所有出错（单错）字的集合。

92 从这七个集合可以决定出错位。例如 即表示a3∈S2， a3∈S1， a3∈S3，所以a3出错，则必有P2为真，P1、P3为假，反之亦然。
构造下面7个非空集合： 根据是该元素否在S1，S2，S3中 从这七个集合可以决定出错位。例如 即表示a3∈S2， a3∈S1， a3∈S3，所以a3出错，则必有P2为真，P1、P3为假，反之亦然。 如此类推，可得到下表所示的纠错对照表。从表中可看出这种编码C能纠正一个错误。 Pi和Si一一对应

93 纠错对照表 P1 P2 P3 出错码元 a1 1 a2 a3 a4 a5 a6 a7 无

94 X＝(a1,a2,a3,a4,a5,a6,a7), Θ=(0,0,0)，XT、 ΘT分别是X、Θ的 转置矩阵，这里加法运算为＋2。
1　1　1　0　1　0　0 (1) H·XT＝ΘT，其中H＝ 1　1　0　1　0　1　0 (2) 1　0　1　1　0　0　1　 (3) X＝(a1,a2,a3,a4,a5,a6,a7), Θ=(0,0,0)，XT、 ΘT分别是X、Θ的 转置矩阵，这里加法运算为＋2。 可见：一个编码可由矩阵H确定，而它的纠错能力可由H的 特性决定，下面讨论矩阵H。 a1 a2 a3 a4 a5 a6 a7

95 两个码的汉明距离等于两个码按位加后与Θ的汉明距离，也等于两个码按位加后的重量
定义：重量（Weight） 一个码字X所含1的个数称为此码字的重量，记为W(X)。 例：码字001011的重量为3，码字100000的重量为1，码字00…0的重量为0，通常将00…0记为0′或Θ。 利用码字的重量，有如下结论： 1）设有码C，对任意X,Y∈C，有 H(X,Y)=H(X◦Y, Θ)=W(X◦Y)； 两位相同，按位加结果为0，不同，结果为1 两个码的汉明距离等于两个码按位加后与Θ的汉明距离，也等于两个码按位加后的重量

96 （2）群码C中非零码字的最小重量等于此群码的最小距离。
（3）设H是k行n列矩阵，X=x1x2…xn， 并设集合G＝｛X｜H·XT＝ΘT｝，这里加法运算为＋2， 则＜G，◦＞是群，即G是群码。 上述介绍的汉明码就是群码。 由结论（1）可得

97 定义：群码G＝｛X｜ H·XT＝ΘT ｝称为由H生成的群码，而G中每一个码字称为由H生成的码字，矩阵H称为一致校验矩阵（Uniform Check Matrix） 。
hi是矩阵H的第i个列向量，按位与可表示为：

98 结论： （1）一致校验矩阵H生成一个重量为p的码字的充分必要条件是在H中存在p个列向量，它们的按位加为ΘT； Θ=(0,0,…,0)
（2）由H生成的群码的最小距离等于H中列向量按位加为ΘT的最小列向量数。 对应于所有码 元都不出错

99 这个结论建立了最小距离与列向量之间的联系
一个码的纠错能力由其最小距离决定； 一个群码的纠错能力可由其一致校验矩阵H中列向量按位加为ΘT的最小列向量数决定； 只要选取适当的H，就可使其生成的码达到预定的纠错能力。 汉明码的一致校验矩阵H中没有零向量，且各列向量之间均互不相同，但它的第二、三、四列向量的按位加为ΘT，由此结论可知汉明码的最小距离为3，而且可知此群必能纠正单个错误。

100 将汉明码推广到一般情况，码C的每一码字X由信息位x1x2…xm及附加校验位xm+1xm+2…xm+k组成；
xm+i=qi1x1+2qi2x2+2···+2qimxm,(i=1,2,…,k) qij∈｛0,1｝（i=1,2,…,k;j=1,2,…,m), 作矩阵H为：H＝（Qk×m Ik×k）

101 其中 则： H·XT＝ΘT 令n=m+k，称这种码为（n,m）码； 要使码C能纠正单个错误，由前面结论可知，只要对H作适当赋值，使得H的列向量均不相同且无零列向量，这样可保证C的最小距离大于2，即要求H中的Q的列向量均不为Θ，不出现I中的k个向量且互不相同。

102 故可在这些列向量中任选m个列向量组成Q，所以m与k必须满足：
Q的列向量是k维的，故可有2k个不同的列向量，而供Q选择的列向量是这2k 个列向量中除去I中的k个列向量及零列向量以外的所有2k-k-1个列向量； 故可在这些列向量中任选m个列向量组成Q，所以m与k必须满足： m≤2k-k-1 或：2k≥m+k+1=n+1 或：k≥log2(n+1)　 因此只要码C中校验位位数k满足： k≥log2(n+1)，总可以在2k-k-1个列向量任选m个列向量组成Q，而使C具有纠正单个错误的能力。

103 从上述分析也可看出如何设计具有一定要求的纠错能力的纠错码。
例：设n=7，k≥log2(n+1)=log28=3，取k=3，则m=4，所以一致校验矩阵H中Q应有四个列向量。而2k-k-1＝23-3-1=4，故Q可由四个列向量唯一确定，它们是： 即H为上述的汉明码。