计算机组成与系统结构PPT完整全套教学课件

目录

第1章绪论第2章计算机系统中的数据表示第3章运算方法与运算器第4章存储系统第5章指令系统第6章中央处理器第7章流水线技术第8章总线与输入/输出系统第9章并行体系结构第1章绪论1.1计算机的发展历史1.2计算机的基本组成1.3计算机的层次概念1.4计算机分类及性能描述

1.1计算机的发展历史

电子数字计算机无疑是人类社会科学技术发展史上最伟大的发明之一,它的出现深刻影响着人类精神文明和物质文明的发展。所谓电子数字计算机,是指能对离散逻辑符号表示的数据或信息进行自动处理的电子装置,简称计算机。

1.1.1发展历史

电子数字计算机的发展根据所使用的电子元器件划分为如下几个阶段。

1.第1代:电子管计算机(1946—1957年)

第一代计算机是由电磁继电器、电子管等器件构成的,直接使用机器语言编程。

2.第2代:晶体管计算机(1958—1964年)

第二代计算机由晶体管、磁芯存储器等构成。软件上采用监控程序对计算机进行管理,并且开始使用高级语言。

与电子管相比,晶体管体积更小,功耗更低,可靠性更高。晶体管计算机中的电子线路也随之更加小型化,具有更高的可靠性和更快的速度,成本也进一步降低。

3.第3代:中小规模集成电路计算机(1965—1971年)

第3代计算机由小规模及中规模集成电路芯片、多层印刷电路板及磁芯存储器等构成,具有更高的可靠性、更小的体积以及更低的成本。在软件上,高级语言迅速发展,出现了分时操作系统,具有分时共享和多道程序处理(即多个人同时使用一台计算机)的能力。在这个时期,计算机的应用领域不断扩展,开始向国民经济各部门及军事领域渗透。

4.第4代:大规模和超大规模集成电路计算机(1972—2010年)

第4代计算机由大规模、超大规模集成电路构成,在结构上有了很大的变化,得益于芯片集成度的提高,在性能上有了很大的提升。

这一代计算机所使用的电子元器件具有以下两方面的特点:

(1)计算机中的存储器由半导体存储器实现。

(2)微处理器的广泛使用。

5.第5代:巨大规模集成电路计算机(2010年至今)

如何定义第5代计算机,目前说法不一。由于计算机性能的持续提升,软件和通信变得与硬件同等重要。

第5代计算机具有如下特点:

(1)体积小,功耗低,性能高,无处不在。

(2)通过并行处理技术实现高性能。

(3)目前计算机的性能已经足够强,人工智能、机器学习技术快速发展,使得计算机更加人性化、智能化,能听,会看,会说,有感情。

(4)虚拟化技术广泛应用,使得各种开发工具软件也更加自动化、智能化。

1.1.2摩尔定律

1965年4月,《电子学》杂志刊登了戈登•摩尔(GordonMoore)撰写的一篇文章。摩尔当时是仙童半导体公司研发部门的主管。摩尔在该文中讲述了他如何将50个晶体管集成在一块芯片中,并且预言,到1975年,就可能将6.5万只这样的元件密植在一块芯片上,制成高度复杂的集成电路。

摩尔的预言不仅对他本人,而且对整个社会都是意义深远的。后来摩尔与其他人共同成立了英特尔(Intel)公司,并通过他所开创的技术创造了无数的财富。

摩尔定律并不是一个物理定律(物理定律是放之四海皆准的),而是一种预言,它鞭策着工业界不断地改进,并努力去实现它。从人们认识摩尔定律开始,无论是Intel公司、AMD公司,还是其他半导体器件公司,无一不是在不断地努力去实现摩尔定律,不断地推出集成度更高的产品。

图1.1为典型微处理器集成度随时间(年)的增长情况。由图1.1可见,到目前为止,微处理器芯片的集成度仍然随时间呈指数级增长。图1.1微处理器集成度的增长情况(1971—2018年)

随着芯片集成度的提高,计算机的性能及可靠性大大提高,价格大大降低。正是摩尔定律使得计算机日新月异地发展,其影响体现在如下几个方面:

(1)虽然芯片的集成度快速提高,但单个芯片的成本变化不大,这意味着可以用更少的芯片来实现计算机逻辑电路和存储电路,在相同性能的情况下,价格显著下降;在相同价格的情况下,新一代的计算机功能更强,性能更好。

(2)随着芯片集成度的提高,芯片中电路各部分之间的信号传输路径显著缩短,信号传输延时小,微处理器的主频得以提高,计算机的速度更快。

(4)通过提高芯片的集成度,降低工作电压,可显著降低芯片的功耗,使得便携式、嵌入式计算机用电池供电成为可能,也降低了高性能计算机对散热的要求。

(5)芯片内部电路各部分之间的连接比外部连接更加可靠。随着芯片集成度的增加,构成计算机所需的芯片数量越来越少,芯片之间所需的连线(焊点)也越来越少,计算机的可靠性越来越高。

1.2计算机的基本组成

1.2.1硬件系统硬件系统是指计算机中那些看得见、摸得着的物理实体。

1.硬件组成图1.2所示的计算机结构是冯·诺依曼在1946年提出的。他基于此硬件结构提出计算机是依据存储程序、程序控制的方式工作的。这就是冯·诺依曼计算机的设计思想。图1.2早期计算机(硬件)的组成

2.冯·诺依曼计算机的特点

冯·诺依曼计算机工作的基本思想就是:将计算机要处理的问题用指令编成程序,并将程序存放在存储器中,在控制器的控制下,从存储器中逐条取出指令并执行,通过执行程序最终解决计算机所要处理的问题。尽管经历了几十年的发展,也出现了新的设计思想,但冯·诺依曼的这种存储程序控制原理直到今天仍然在广泛地应用。

冯·诺依曼计算机的特点可归纳如下:

(1)计算机由运算器(算术逻辑部件ALU)、存储器、控制器、输入设备和输出设备五大部件组成。

(2)指令和数据以二进制形式表示,以同等地位存放在存储器中,并可按地址访问。用二进制不仅电路简单,使用方便,而且抗干扰能力强。

(3)指令由操作码和地址码组成。操作码指明指令的功能,地址码指明操作数与运算结果的存放位置(地址)。

(4)将计算机要处理的问题用指令编成程序。

(5)在控制器的控制下,指令被逐条(顺序)从存储器中取出来执行,产生控制流,在控制流的驱动下完成指令的功能。在此过程中,数据(流)则是被动地调用。

(6)在特定条件下,可由跳转类指令根据运算结果或设定的条件改变程序中指令的执行顺序。

(7)早期的冯·诺依曼计算机以运算器为中心,输入/输出设备通过运算器与存储器传送数据。

3.计算机硬件结构的发展

目前,在冯·诺依曼体系结构思想的基础上,计算机硬件体系结构已经得到了很大的发展,主要有以下几个方面:

(1)不断扩充硬件及功能:增加了更多通用寄存器、多种寻址方式,支持浮点数据类型、中断和异步I/O结构。

(2)存储器分层:引入高速缓存(Cache)、虚拟存储器等,在程序执行之前,将程序与数据存放在速度慢、容量大、成本低的存储介质(比如磁盘)中;在程序执行时,将即将(或正在)执行的程序和所需的数据复制到速度快、容量小、成本高的存储介质(比如主存、高速缓存)中。

(3)总线结构:通过总线连接计算机系统中的各个模块。总线信号根据传输的信息类型,分为地址线、控制线、数据线。地址线用来选择要访问的存储单元或I/O接口,控制线传输相应的读写控制信号,数据线用来传输数据。总线大大简化了计算机系统各模块之间的连接,增强了计算机系统硬件的扩展能力。

图1.3为微型计算机(PC)的硬件结构框图。微处理器、主存、各种外部设备的接口通过系统总线连接在一起,构成了计算机系统的硬件。随着芯片集成度的进一步提高,图1.3中用虚线标出的A、B部分可以分别集成在两块芯片中,分别称为芯片组的北桥芯片(MemoryControllerHub,MCH)和南桥芯片(I/OControllerHub,ICH)。目前,北桥芯片的大部分电路和图形处理单元可以集成在微处理器中,北桥芯片余下的电路与原来的南桥芯片合为一块芯片,称为平台控制中枢(PlatformControllerHub,PCH)。图1.3的C部分称为主机;主机以外的称为输入/输出设备(I/O设备),也称为外部设备,简称外设。图1.3微型计算机(PC)结构框图

1.2.2软件系统

1.系统软件

系统软件是一系列保障计算机能很好地运行的程序集合。它们的功能是对系统的各种资源(硬件和软件)进行管理和调度,使计算机能有条不紊地工作,为用户提供有效的服务,充分发挥其效能。系统软件包括:

1)操作系统

操作系统是最重要的系统软件,它是管理计算机硬、软件资源,控制程序运行,改善人机交互并为应用软件提供支持的一种软件。通常,操作系统包括五大功能:处理器管理、存储管理、文件管理、设备管理及作业管理。

2)语言处理程序

每一台计算机都会配置多种语言以利于用户编程,从各种高级语言到汇编语言均会涉及。当用户使用某种语言编写程序后,在该语言编译程序的支持下,可将用户的源程序转换为计算机可执行的目的程序。

3)各种服务支持软件

各种服务支持软件是指一些帮助用户使用和维护计算机的软件,如各种调试程序、诊断程序、提示警告程序等。

2.应用软件

应用软件是指用户在各自的应用中,为解决自己的任务而编写的程序。这是一类直接以用户的需求为目标的程序。用户的多样性(各行各业、各种部门)和用户需求的多样性,使得这类软件也具有多样性。例如,应用软件包括用于办公自动化、视频编辑、图形图像处理、科学计算、信息管理、过程控制、武器装备等方面的软件。

1.2.3指令集体系结构

计算机系统底层硬件只能识别机器语言,也就是存储在主存中的指令。CPU从主存中取指令,执行指令,每条指令可实现计算机系统内最基本的操作,比如基本的算术运算(加、减)、逻辑运算(与、或、异或、移位)、数据传送(装载、存储)、跳转(条件转移、无条件转移),这些指令被编码为一个字或多个字节组成的二进制格式。

1.指令集体系结构(ISA)概述

处理器支持的指令和指令的字节级编码称为指令集体系结构(Instruction-SetArchitec-ture,ISA)。ISA是软件和硬件的分界面,软件(程序)是由ISA规定的“指令”组成的,指令通过二进制编码规定其功能、源操作数和目的操作数的位置等信息。计算机中的控制器在执行指令时,根据上述信息产生相应的控制信号,控制计算机系统各硬件模块完成指令要求的功能。

为了让程序员可以编写底层软件,ISA不仅要规定指令集,还要定义任何系统程序员需要了解的硬件信息。因此,ISA需要规定计算机中程序员可见的所有组件及操作,包括以下几方面的内容:

(1)指令集:处理器可执行的指令的集合。

①指令格式、操作种类以及每种操作对应的操作数的相应规定。

②数据类型,即指令可以接受的操作数的类型。

③寻址方式,即指令获取操作数的方式。

(2)软件可见的处理器状态:

①寄存器的个数、名称(编号)、长度和用途,包括通用寄存器和特殊用途寄存器。

②指令执行过程的控制方式,包括程序计数器、条件码定义以及每条指令对状态的影响。

(3)存储模型:

①主存组织,即主存最大寻址空间和编址方式。

②字节次序,即操作数在存储空间存放时按照大端还是小端方式存放。

③存储保护。

④虚拟存储器的管理方式。

⑤输入/输出接口的访问与管理方式

(4)系统模型:

①处理器状态。

②特权级别。

③中断和异常的处理方式。

2.典型的ISA

1)x86

x86由Intel公司推出,于1978年首次用于8086处理器。随着个人计算机的兴起和飞速发展,x86从最初的16位架构发展到32位、64位架构,越来越多的指令和功能被添加进来,使得x86越来越臃肿。但是,保持软件的向后兼容远比技术更重要,这使得x86拥有了广泛的软件资源和越来越多开发基于x86的软件的程序员。如今,x86已成为个人计算机的标准处理器架构,成为桌面计算机和高性能计算领域最成功的ISA。

2)ARM

ARM(AdvancedRISCMachines)公司诞生于英国,总部位于英国剑桥,主要业务是设计ARM架构的处理器,同时提供与ARM处理器相关的配套软件,以及各种SOC系统IP、GPU、物联网平台等。

3)POWER

POWER(PerformanceOptimizationWithEnhancedRISC,增强RISC性能优化)是IBM公司设计开发的指令集体系结构,最早于1990年推出,性能卓越。

4)MIPS

MIPS(MicroprocessorwithoutInterlockedPipedStages,无内部互锁流水线微处理器)是一款经典的精简指令集架构,由美国斯坦福大学的JohnL.Hennessy教授领导的研究小组于1981年开始设计。他们在1984年创立了MIPSComputerSystem公司,推出了商用的MIPS处理器。此后,MIPS指令集体系结构不断扩充与改进,从MIPSⅠ、MIPSⅡ、MIPSⅢ、MIPSⅣ、MIPSⅤ发展到了MIPS32、MIPS64。

5)SPARC

从1980年开始,美国加州大学伯克利分校的DavidA.Patterson教授领导了RISC-I的设计与实现工作,这是一台超大规模集成电路精简指令集计算机,为商业SPARC体系结构奠定了基础。

6)RISC-V

RISC-V架构是一款袖珍的、开源的ISA,于2011年推出,由美国加州大学伯克利分校的KrsteAsanovi'c教授、AndrewWaterman和YunsupLee等开发人员发明,并得到了DavidA.Patterson教授的大力支持。“RISC”表示精简指令集,“V”表示伯克利分校从RISC-I开始设计的第五代指令集。

基于上述原因,加州大学伯克利分校的研发人员决定发明一种全新、简单且开放免费的指令集架构,即RISC-V架构。计算机体系结构经过多年的发展,其技术日趋成熟,在发展过程中暴露的问题都已经被研究透彻并得以解决。所以,新的RISC-V架构能够规避曾经出现过的各种问题,并且没有背负向后兼容的历史包袱,做到简洁,低成本,高性能(或低功耗),架构和具体实现分离,并预留一定的扩展空间。

当前可用的RISC-V软件工具包括GNU编译器集合(GCC工具链和GDB调试器)、LLVM工具链、OVPsim仿真器(以及RISC-V快速处理器模型库)、Spike仿真器和QEMU模拟器。当前支持该指令集架构的操作系统包括Linux、FreeRTOS、SylixOS、RT-Thread等。

1.2.4高级语言程序的执行过程

程序员通常用某种高级语言(比如C语言)设计软件,而计算机硬件只能识别并执行其指令集体系结构(ISA)所规定的指令(也称作机器指令、机器码)。

图1.4为用C语言实现的插入排序函数源代码。该C语言程序可运行在基于x86处理器的Windows操作系统下,使用MicrosoftVisualC++2017编译,目标平台设置为Intelx86的32位指令集(IA-32),通过设置优化参数以减小输出代码,提高运行速度,同时使生成的代码更简洁,更容易理解。生成的机器语言代码如表1.1所示。图1.4插入排序的C语言源代码

指令“subeax,4”(表1.1第21行)的功能为:寄存器eax的内容与立即数4(符号位扩展至32位)相减,结果存入寄存器eax。该指令的机器语言代码为三个字节,内容为十六进制数83E804,其二进制编码各部分含义如图1.5所示。图1.5“subeax,4”的二进制编码含义

使用gcc编译器,将目标平台设置为RISC-VRV32I指令集,通过设置优化参数以减少输出代码的大小,使得生成的代码更简洁,更容易理解。插入排序的C语言源代码经过gcc编译后,生成的汇编语言及机器语言代码如表1.2所示。

指令“addia2,a2,-4”的功能为:源1(a2寄存器的内容)与源2(立即数“-4”,符号位扩展至32位)相加,结果存入目的寄存器a2。该指令的机器语言代码为十六进制数ffc60613,其二进制编码各部分含义如图1.6所示。图1.6“addia2,a2,-4”的二进制编码含义

图1.6中,操作码规定指令的基本功能与格式;功能码规定指令具体的操作类型;源1与目的寄存器编码为“01100”,即寄存器x12,其别名为a2(RISC-V基础指令集(RV32I)规定了32个寄存器(x0~x31),因此寄存器编号用5位二进制数进行编码。RISC-V汇编语言根据各寄存器的功能和使用方式的不同,规定了相应的别名);源2为立即数“-4”,直接存储在指令中,用补码表示。

1.3计算机的层次概念

1.3.1计算机系统的层次结构计算机系统的层次结构如图1.7所示。图1.7计算机系统的层次结构

1.3.2计算机体系结构、组成与实现

1.计算机体系结构

计算机体系结构的概念是在20世纪60年代提出的。计算机体系结构是程序员所看到的计算机系统的属性,即概念性结构及功能特性。不同层次上的程序员所看到的计算机系统的属性是不尽相同的,低的机器语言级上的概念性结构及功能特性,高级语言以上级别的程序员可能是看不见的。在定义计算机体系结构的年代里,计算机的属性、概念性结构及功能特性主要是指低层的硬件。今天的计算机体系结构所指的计算机的属性主要包括:

•数据的表示形式;

•寻址方式;

•内部寄存器组;

•指令集;

•中断系统;

•处理器工作状态及其切换;

•存储系统结构;

•输入/输出结构;

•信息保护及特权;

•高性能设计等。

2.计算机组成

计算机组成也被称为计算机组织,是计算机系统的逻辑实现,包括最底层内部算法、数据流、控制流的逻辑实现。利用这一概念可以对计算机进行逻辑设计。计算机组成的设计主要包括:

•数据通路的宽度;

•专用部件(如乘除法专用部件、浮点运算专用部件等)的设置;

•各功能部件的并行程度;

•各种操作的相容性与互斥性;

•控制器的组成方式;

•存储器使用的技术;

•缓冲与排队技术的应用;

•预估、预判方法;

•高可靠性技术等。

3.计算机实现

计算机实现就是指计算机组成的物理实现。在上述计算机体系结构及计算机组成的基础上,利用具体的集成电路芯片、电子元器件、部件、插头、插座等,根据计算机组成的逻辑设计,即可实现物理计算机。

综上可以看到,计算机体系结构、计算机组成与计算机实现三者在概念上是不同层次的,但是它们的联系是十分紧密的。体系结构决定了计算机的总体属性,组成是体现这些属性的逻辑设计,而实现则是用物理器件来实现逻辑设计。相同的体系结构可以有不同的组成,相同的组成可以有不同的实现。

1.4计算机分类及性能描述

1.4.1计算机分类1.按用途分类按照用途可将计算机分为通用计算机和嵌入式计算机(专用计算机)。

1)通用计算机

通用计算机的硬件系统及系统软件均由有关的计算机公司设计制造,其用途不是针对某一个或某一类用户的,而是可以满足许多用户的。例如,目前国内外广泛使用的台式PC或笔记本电脑,用户可直接在市场上购买,在厂家提供的软件支持下工作。也许用户只需配上少量的软件或硬件,即可满足用户的需求。

除了个人计算机(PC)外,具有更高性能的各种服务器或高性能计算机因可以适用于许多领域或部门,故也可以看作通用计算机。

(1)个人计算机。个人计算机也称为电脑,是一种面向个人使用的计算机,可以完成办公、上网、编程、看电影、玩游戏等。

(2)服务器。服务器是用于高性能实现某种服务的计算机,如Web服务器、FTP服务器、Mail服务器、文件共享服务器、数据库应用服务器、域名服务器、网关服务器、DNS服务器、流媒体服务器等。

(3)超级计算机。超级计算机是计算机中功能最强、运算速度最快、存储容量最大的一类计算机,多用于国家高科技领域和尖端技术研究,对国家安全、经济和社会发展具有举足轻重的意义,是国家科技发展水平和综合国力的重要体现。目前的超级计算机是由几十万至上千万个处理器核组成的超大规模多处理器系统,其优势是具有超强的计算能力,运算速度已达到每秒1018次浮点运算的量级。

2)嵌入式计算机

嵌入式计算机可定义为:以应用为目标,以计算机技术为基础,软硬件可裁减,对功能、实时性、可靠性、安全、体积、重量、成本、功耗、环境、安装方式等方面有严格要求的专用计算机系统。

2.Flynn分类法

Flynn分种类信法息是流按:照计算机在执行程序的过程中信息流的特征进行分类的。在程序执行中存在三种信息流:

(1)指令流(IS):机器执行的指令序列,它由存储器流入控制单元(CU)。

(2)数据流(DS):指令流所使用的数据,包括输入数据、中间数据和结果。数据在处理单元(PU)中进行处理。

(3)控制流(CS):指令流进入CU,由CU产生一系列控制流(信号),在控制流的控制下完成指令的功能。

按照Flynn分类法,可将计算机分为四类,如图1.8所示。图1.8按照Flynn分类法的计算机分类

(1)单指令流单数据流(SingleInstructionSingleData,SISD):计算机结构如图1.8(a)所示。该计算机由单一控制单元、单一处理单元和单一主存储器组成。控制器控制从存储器逐条获取指令,对指令译码,产生控制信号,并控制处理单元完成指令规定的功能。这是最简单的一类计算机,但已充分展示了计算机的基本组成与工作原理,是本书后续章节的重点内容。

(2)单指令流多数据流(SingleInstructionMultipleData,SIMD):计算机结构如图1.8(b)所示。它由一个控制单元、多个处理单元和多个主存储器组成。控制器控制从存储器获取一条指令,对指令译码,产生控制信号,并用相同的控制信号控制多个处理单元,执行相同的操作,完成这条指令对多个数据的相同处理,最终实现一条指令所规定的功能。这类计算机将在本书第9章予以描述。

(3)多指令流单数据流(MultipleInstructionSingleData,MISD):实现的是多个控制单元同时执行多条指令对同一数据进行处理,其结构如图1.8(c)所示。这种计算机尚无实例。

(4)多指令流多数据流(MultipleInstructionMultipleData,MIMD):计算机结构如图1.8(d)所示。它由多个控制单元、多个处理单元和多个主存储器构成,实际上是由多处理机用各种方式连在一起构成的计算机系统,通常称为多处理机系统。这类计算机中各个处理机分别执行不同的指令,处理不同的数据,并行工作而实现某种功能。

1.4.2计算机系统性能描述

1.计算机系统配置

根据计算机系统的配置,可以了解计算机系统的基本性能。下面以高性能计算机为例做简单说明。不同时期,对高性能计算机有不同的解释。目前,高性能计算机是指能够在可接受的时间内处理一般个人计算机无法处理的大量数据,执行一般个人计算机无法完成的密集型运算的计算机,也称为超级计算机。高性能计算机的性能一般用其浮点数运算能力衡量,通常可达到或超过几百TFlops(1TFlops即每秒钟可进行1×1012次浮点运算)。

例如,超级计算机神威·太湖之光的配置如下:

•系统峰值性能:125.436PFLOPS(1PFLOPS即每秒钟可进行1×1015次浮点运算)。

•实测持续运算性能:93.015PFLOPS。

•处理器型号:“申威26010”众核处理器(260核,申威64指令集,主频为1.45GHz)。

•整机处理器个数:40960个。

•整机处理器核数:10649600个。

•系统总主存:1310720GB。

•操作系统:RaiseLinux。

•编程语言:C、C++、Fortran。

•并行语言及环境:MPI、OpenMP、OpenACC等。

•SSD存储:230TB。

•在线存储:10PB,带宽为288GB/s。

•近线存储:10PB,带宽为32GB/s。

•功耗:15.371MW。

神威·太湖之光超级计算机由中国国家并行计算机工程技术研究中心研制,安装在国家超级计算无锡中心,由40个运算机柜和8个网络机柜组成。

2.计算机系统性能计算

时间是测量计算机性能的重要指标。一个性能良好的计算机应是快速的,而最快的计算机则是完成相同任务用时最少的那一台。吞吐量和执行时间是描述计算机系统性能常用的参数,也是用户所关心的。

执行时间(ExecutionTime)也称响应时间,定义为一个任务从开始到完成所用的时间或计算机完成一个任务所用的总时间。

吞吐量(Throughput)定义为在给定时间内(并行)完成的总任务数。

在许多实际的计算机中,减少执行时间通常会改善吞吐量。对多处理机系统而言,虽然每个任务的完成并没有加快,但增加了吞吐量。在计算机系统中使用更快的CPU,可以改善执行时间和吞吐量。

如果用时间来定义计算机系统的性能,则有

这意味着,如果计算机X的性能好于计算机Y,则有

也即如果计算机X比计算机Y速度快,则在Y上的执行时间比X的长。从上述定义也可以得到

也即计算机的性能与其吞吐率成正比。

在设计计算机时经常要进行计算机性能比较,相对性能(RelativePerformance)或性能比(PerformanceRatio)被定义:

这意味着,计算机X的性能是计算机Y的n倍,或在Y上的执行时间是X的n倍。

例1.1计算机A的性能是计算机B的性能的4倍,B完成一个指定的任务用时20s,那么A完成该任务用时多长?

解因为

所以TA=5s,即A完成该任务用时5s。

3.用测试程序来测评计算机系统性能

以往对计算机的测试采用如下几种程序:

(1)实际应用程序,即计算机工作的真实程序。

(2)修正的实际应用程序,即对真实程序进行某些修改构成的测试程序。

(3)核心程序,即提取真实程序中的核心部分构成的测试程序。

(4)小测试程序,即具有特定目的的100行以内的测试程序。

(5)合成测试程序,即选择具有各种代表性的一系列测试程序,将它们组合在一起的测试程序,称为测试程序组件或基准测试程序。

1.4.3Amdahl定律

Amdahl定律是20世纪60年代由IBM360系列计算机的主要设计者Amdahl提出的。其内容为:计算机系统中某一部件采用某种更快的执行方式后,整个系统性能的提高与这种执行方式的使用频率或占总执行时间的比例有关。Amdahl定律给出了加速比的定义:

从Amdahl定律所描述的内容可以看到,加速比即性能之比。对计算机的某一部分进行改进后,在处理相同任务的情况下,改进前总执行时间是改进后总执行时间的多少倍,就是加速比。计算机系统的加速比取决于下面两个因素:

(1)可改进部分在原系统总执行时间中所占的比例:称为可改进比例,用fe表示。例如,程序的总执行时间为100s,可改进的部分是其中的20s,则fe=0.2。可见,fe总是小于或等于1的。

(2)可改进部分改进后性能提高的程度:通常用部件加速比re来表示某部件改进后性能提高的比例。例如,某部件改进后,执行时间由原来的20s减少到5s,则部件加速比re=20/5=4。可见,re一般是大于1的。

根据上述分析,若假设改进前的系统总执行时间为T0,可以得出改进后的系统总执行时间Tn为

若加速比用Sp表示,则根据式(1.4)和式(1.5),加速比Sp可表示为

式中,1-fe为不可改进(或未改进)的部分,当可改进(或已改进)部分为0时,系统的加速比Sp就是1。随着可改进部分的增加(fe加大)和改进效果的提升(re增加),系统的加速比Sp就会增加。当系统可改进的部分fe确定后,即使这一部分改进后不再需要执行时间,即re→∞,仍存在Sp=1/(1-fe)。可见,系统性能的改善受可改进部分fe的限制。

例1.2升级某文件共享服务器,采用新的CPU以提高其性能,新CPU的运行速度是原来CPU的10倍。该服务器工作时,CPU有35%的时间用于计算(实现各种网络协议、文件共享协议,将文件级访问转换为磁盘的块级访问),另外65%的时间用于等待磁盘(磁盘延迟大,读写速度慢)。请问进行这一升级后,该服务器所得到的总的加速比是多少?

解由题意可知,fe=0.35,re=10,则

由计算可见,即使某一部件的加速比已达10倍,但若该部件仅影响到总执行时间的小部分,则对整个计算机系统的贡献也是有限的。所以,改进后系统的加速比只有1.46倍左右。

例1.3若计算机系统有三个部件a、b、c是可改进的,各部件改进后的加速比分别为30、30、20。它们在总执行时间中所占的比例分别是30%、30%、20%。试计算这三个部件同时改进后系统的加速比。

解在多个部件可同时改进的情况下,Amdahl定律可表示为

将已知条件代入式(1.7),得

例1.4某基准测试程序中包含一定比例的卷积运算、点积运算、矩阵运算和数字滤波器运算,实现这些运算需要大量的乘法、累加操作,即乘积累加运算:a←a+b×c。假设乘积累加运算占用该基准测试程序15%的执行时间。为了改进某计算机执行该基准测试程序时的性能,提出以下两种解决方案:

方案1新增乘积累加运算向量指令。为了实现该指令,增加专用硬件,采用单指令流多数据流(SIMD)结构,实现快速并行乘积累加运算。采取上述措施后,执行乘积累加运算的速度可以提高到原来的15倍。

方案2改进原来的运算器(包括原来的加法器与乘法器),使得所有算术运算指令的执行速度达到原来的1.6倍。已知算术运算指令(包括普通加法指令、乘法指令)占用该基准测试程序40%的执行时间。

经过评估,实现方案1与实现方案2的工作量、成本相同。

试比较这两种设计方案中采用哪种改进方案执行该基准测试程序时的性能更高。

解方案1的加速比

方案2的加速比

可见,采用方案2改进原来的运算器电路性能会稍好一些,因为普通的算术运算指令使用的频度更高。

采用方案2,原来的基准测试程序无须修改和重新编译,可以直接运行。如果采用方案1,需要升级编译程序以支持新增的指令,原基准测试程序需要用新的编译器重新编译,才可使用新增的指令以提高性能。所以方案2的软件兼容性也更好。第2章计算机系统中的数据表示2.1概述2.2定点数2.3浮点数2.4BCD码2.5非数值数据2.6检错与纠错码

2.1概述

2.1.1数的进制及转换

常见的进位计数制有十进制、二进制、八进制和十六进制。十进制数中有0~9十个数码,其计数特点及进位原则为“逢十进一”。十进制的基数为10,位权为10i(i是整数)。十进制数的后面常用字母D标记或不加标记。计算机中常用的计数制还有二进制、八进制、十六进制。

任何一种进位计数制表示的数都可以写成按权展开的多项式之和,即任意一个r进制数N可表示为

其中,Di为该数制采用的基本数码,ri

是权,r是基数。数值数据是表示数量多少和数值大小的数据,即在数轴上能找到其对应点的数据。

各种数值数据在计算机中表示的形式称为机器数。机器数对应的实际数值称为数的真值。

2.1.2无符号数与有符号数的定义

1.无符号数

所谓无符号数,即没有符号的数,数中的每一位均用来表示数值。所以8位二进制无符号数所表示的数值范围是0~255,而16位无符号数的表示范围为0~65535。

2.有符号数

由于机器无法直接识别“+”(正)、“-”(负)符号,而“正”“负”恰好是两种截然不同的状态,因此若用“0”表示“正”,用“1”表示“负”,则符号可被数字化,再按规定将符号放在有效数字的前面就组成了有符号数。

2.1.3定点数与浮点数的定义

1.定点数

在机器数表示中,若约定小数点的位置固定不变,则称为定点数。有两种形式的定点数,即定点整数(纯整数,规定小数点在数据最低有效数位之后)和定点小数(纯小数,规定小数点在数据最高有效数位之前),如图2.1所示。图2.1有符号定点数的表示形式

2.浮点数

基数为2的数F的浮点表示为

其中,M称为尾数,E称为阶码。尾数为带符号的纯小数,阶码为带符号的纯整数。

按式(2.2)表示的数据既可以是纯整数,也可以是纯小数,还可以是同时含有整数和小数的数据,其小数点的位置是不固定的,故称为浮点数。计算机中常用的一种浮点数的编码格式如图2.2所示,其中数符(即数据的符号)就是尾符(即尾数的符号)。图2.2浮点数的编码格式之一

2.2定点数

2.2.1原码原码是机器数中最简单的一种表示形式,其符号位为0表示正数,符号位为1表示负数,数值位即真值的绝对值。

1.整数原码的定义

根据图2.1(a),若整数用二进制n位表示,则整数原码的定义为

式中,X为真值,n-1为整数数值位的位数。

原码可用定义表示,也可用符号位后面紧跟数的绝对值表示。

例2.1当X=+35或X=-35时,若采用8位二进制编码,其原码如何表示?

解当X=+35时,有

当X=-35时,有

从本例可以看到,符号位总是在最高位。原码又称作带符号的绝对值表示,即在符号的后面跟着的就是该数据的绝对值。

2.小数原码的定义

根据图2.1(b),若小数用二进制n位表示,则小数原码的定义为

根据式(2.4),纯小数的原码可以表示为

值得注意的是,在计算机中小数点是隐含的,是不用出现的,上面编码中出现小数点是为了强调小数点的位置。在本书各章节中,所有编码中若出现小数点,其作用与此处相同,都仅仅是为了提示。

例2.2若纯小数X=0.46875或X=-0.46875,试用包括符号位在内的8位定点原码表示。

解当X=0.46875时,有

当X=-0.46875时,有

3.原码的特点

(1)数值原码表示法简单直观,但加减运算很麻烦。

(2)对于数值0,用原码表示不是唯一的。以8位原码表示,有

(3)n位原码(包括一位符号位)纯整数可表示的数值范围为-(2n-1-1)~+(2n-1-1),纯小数可表示的数值范围为-(1-2-(n-1))~+(1-2-(n-1))。

2.2.2补码

1.补数的概念

在日常生活中,常会遇到补数的概念。例如,当前时钟指针指示在6点,欲使它指示3点,既可按顺时针方向将分针转9圈,也可按逆时针方向将分针转3圈,其结果是一致的。由于时钟的时针转一圈能指示12个小时,因此时钟指针两个方向转动产生的效果在数学上称为模12运算,写作mod12。

2.补码的定义

1)整数补码的定义根据图2.1(a),若整数用二进制n位表示,则整数补码的定义为

由式(2.5)可以看到,对正数来说,补码与原码的定义完全一样。

2)小数补码的定义

若小数用二进制n位表示,则小数补码的定义为

根据式(2.6),纯小数的补码同样可以表示为

同样地,小数点是隐含的。

例2.4若纯小数X=0.46875或X=-0.46875,试用包括符号位的8位定点补码表示。

解当X=0.46875时,有

对于负数纯小数,构成补码表示所采用的方法与整数一样。因此,当X=-0.46875时,[X]补=1.1000100。

3.补码的特点

(1)n位补码表示的整数数值范围为-2n-1~+(2n-1-1),n位补码表示的小数数值范围为-1~+(1-2-n+1)。

(2)0的表示是唯一的。以8位小数编码为例,有

(3)变形码。当模数为4时,可形成双符号位补码,如X=-0.1001B,对mod22而言,有

这种双符号位补码又叫作变形补码,它在阶码运算和溢出判断中有其特殊作用。

(4)求补运算。许多处理器中设置有求补指令,其功能是对操作数取负数(即正数变负数,负数变正数)。可以采用上述的负数补码的3种编码方法之一实现。

(5)简化加减法。利用补码实现两数相加是很方便的,补码加法的运算规则为

即两数和的补码就等于两数补码之和。

因此,减法运算就可以用加法运算来实现,即

这样在运算器中就可以不设置减法器,从而简化了运算器的结构。

(6)算术或逻辑左移。对补码表示的数值做算术或逻辑左移一位(即编码各位依次向左移动一位,最高位移出,最低位补0),如果移位结果没有超出所规定的数值范围,则相当于该数值乘2。

(7)算术右移。对补码表示的数值做算术右移一位(即编码各位依次向右移动一位,最低位移出,最高位保持原符号不变),相当于该数值除以2。

2.2.3反码

反码通常用来作为由原码求补码或者由补码求原码的中间过渡。

1.反码的定义

1)整数反码的定义

整数反码的定义为

2)小数反码的定义

小数反码的定义为

2.2.4移码

1.移码的由来

当真值用补码表示时,由于符号位和数值部分一起编码,与习惯上的表示法不同,因此人们很难从补码的形式上直接判断其真值的大小。例如:

十进制数X=+31,对应的二进制数为+11111,若用8位表示,则[X]补=00011111；

十进制数X=-31,对应的二进制数为-11111,若用8位表示,则[X]补=11100001。

上述补码表示中,从代码形式看,符号位也是一位二进制数。如果按这8位二进制代码比较其大小,会得出11100001>00011111,而实际情况恰恰相反。

2.移码的定义

由于移码多用于浮点数中表示阶码,均为整数,因此这里只介绍定点整数的移码表示。当用包括符号位在内的n位字长时,整数移码的定义为

要获得整数的移码表示,可以利用定义计算,也可以先求出该数的补码后将符号位取反。

3.移码的特点

(1)移码就是在其真值上加一个常数2n-1。移码在数轴上所表示的范围恰好对应其真值在数轴上的范围向轴的正方向移动2n-1个数据,如图2.3所示。图2.3移码在数轴上的表示

(2)移码与补码的关系。由图2.4可知,移码与补码间的关系十分密切,只要将补码的符号位取反,补码就转换成了相应的移码;同样,只要将移码的符号位取反,移码就转换成了相应的补码。进而可以想到,只要字长相同,补码与移码所能表示的数值范围是相同的。图2.4移码与补码的关系

(3)移码码值的大小反映了数值的大小,因此,正数移码的码值一定大于负数移码的码值。也就是说,大码值所表示的数值一定大于小码值所表示的数值。

由于具有上述突出优点,移码目前已被广泛采用。

2.2.5不同编码的比较

原码表示很直观。若采用原码做乘除运算,可取其绝对值(原码的数值部分)直接运算,并按同号相乘除取正,异号相乘除取负的原则,单独处理符号位,比较方便。但原码加减运算时,其运算比较复杂。例如,当两个操作数符号不同且要作加法运算时,先要判断两个数的绝对值的大小,然后用绝对值大的数减去绝对值小的数,结果的符号以绝对值大的数为准,运算步骤既复杂又费时,且本来是加法运算却要用减法器实现。

而机器数采用补码,找到一个与负数等价的正数来代替该负数,即可用加法代替减法操作,这样在计算机中就可以只设加法器。但是根据补码的定义,在形成补码的过程中又出现了减法,因此引入了反码,作为由原码求补码或者由补码求原码的中间过渡,这样由真值通过原码求补码就可避免减法运算。

因此,原码、反码、补码、移码的特点可归纳如下:

(1)当真值为正时,原码、补码和反码的表示形式均相同,即符号位用“0”表示,数值部分与真值相同。

(2)当真值为负时,原码、补码和反码的表示形式不同,但其符号位都用“1”表示,而数值部分的关系为:反码是原码“每位取反”,补码是反码“加1”,补码是原码“求反加1”。

(3)移码较为特殊,当符号位为“0”时,表示真值为负数;当符号位为“1”时,表示真值为正数。移码与补码编码仅符号位相反。

表2.1列出了8位字长的二进制编码与无符号整数及定点整数的原码、补码、反码和移码所代表真值的对应关系。

2.3浮点数

2.3.1浮点数的表示方法由于计算机字长的限制,当需要表示的数据有很大的数值范围(如电子的质量为9×10-28克,太阳的质量为2×1033克)时,它们不能直接用定点小数或定点整数表示,而必须用浮点数表示。由于计算机采用二进制,所以浮点数的一般表示形式为式(2.2)。

例如,二进制数F=11.0101,用浮点数可表示为下列不同形态,即

其中,尾数与阶码均用二进制数表示,基数(为2)用十进制数表示。这里可以看到,一个包含整数与小数的数据用浮点数表示时有多种形态,那么计算机中采用哪种形态来表示这个浮点数呢?

1.浮点数的编码表示

根据浮点数的一般表示式(2.2),只要确定了尾数M和阶码E(基数是固定值),浮点数即被确定。但同一个浮点数又有多种表现形态,如上述例子,所以需要对M和E的形态做出合理选择,浮点数才能在计算机中有效编码。

浮点数编码的规则如下:

(1)尾数M必须为小数,用n+1位有符号定点小数表示,可以采用的编码有原码、补码。阶码E必须为整数,用k+1位有符号定点整数表示,可以采用的编码有原码、补码、移码。浮点数编码位数为m=(n+1)+(k+1)。

(2)浮点数编码格式有多种,使用较多的格式如图2.2和图2.5所示,格式的选择可由计算机设计人员决定。图2.5浮点数的编码格式之二

需要强调的是:

(1)阶码是整数,其位数k+1决定了浮点数表示的数值范围,也就是决定了数据的大小,或小数点在数据中的真实位置。阶符决定阶码的正负。

(2)尾数是小数,其位数n+1决定了浮点数的精度。如果尾数采用小数且位数n足够长,则当浮点数运算需要对尾数运算结果舍入时,造成的数据精度损失会比较小。

(3)尾数的符号表示浮点数的正负。

2.非规格化浮点数

当对尾数M只要求是小数而无其他限制时,此时的浮点数被称为非规格化浮点数。设浮点数为非规格化数,阶码数值位取k位,阶符为1位,且采用补码表示,尾数数值位取n位,尾符为1位,同样采用补码表示,则阶码和尾数可以表示的数值范围如表2.2所示。

此时,在数轴上表示的非规格化浮点数范围如图2.6所示。因为非规格化浮点数的尾数可以为0,也就是非规格化浮点数可以为0,因此非规格化浮点数范围为图2.6非规格化浮点数的数值范围

3.规格化浮点数

由于非规格化浮点数对小数形式的尾数没有进一步的限制,因此造成同一数据有不同的编码,使数据表示的通用性变差。为了使有限字长的二进制尾数能表示更多的有效数位,同时使浮点数有统一的表示形式,浮点数通常采用规格化形式来表示。

所谓规格化浮点数,就是将尾数的绝对值限定在规定的数值范围内,即1/2≤M<1。要使尾数的绝对值在此范围内,通过改变小数点的位置(相应地改变阶码)便可以做到。

若尾数M用补码表示,则当M≥0时,规格化尾数的形式必须为

其中,×为任意二进制值。

当M<0时,规格化尾数的形式必须为

其中,×为任意二进制值。

根据规格化浮点数的定义,可以得到规格化尾数的数值范围如表2.3所示。

对于规格化浮点数来说,其阶码所表示的数值范围与非规格化浮点数的是一样的。因此,可以确定规格化浮点数所能表示的数值范围如图2.7所示。图2.7规格化浮点数的数值范围

比较图2.6和图2.7可以发现,非规格化浮点数和规格化浮点数所能表示的数值范围的主要不同是绝对值最小的有效数值。由图2.7可知,规格化浮点数的数值范围如下:

当浮点数阶码大于最大阶码时,称为“上溢”,此时机器停止运算,进行溢出中断处理;当浮点数阶码小于最小阶码时,称为“下溢”,此时“溢出”的数的绝对值很小,通常将尾数各位强置为零,按机器零处理,机器可以继续运行。图2.7表示了浮点数所能表示的数值范围及溢出的情况。

一旦浮点数的位数确定后,不同的阶码和尾数位数划分将直接影响浮点数的表示范围和精度,所以需要合理分配阶码和尾数的位数。利用数值的浮点数表示,可实现用有限字长的二进制编码表示更大的数值范围。

4.规格化处理

浮点数在运算前和运算后,若其尾数不是规格化数,就要通过修改阶码并同时左右移动尾数使其变成规格化数。将非规格化数转换成规格化数的过程叫作规格化。

当尾数M用二进制补码编码时,规格化数应符合[M]补=0.1××…×和[M]补=1.0××…×的规定。规格化时,尾数左移1位,阶码减1,这种规格化叫作向左规格化,简称左规;尾数右移1位,阶码加1,这种规格化叫作向右规格化,简称右规。

5.定点数和浮点数的比较

(1)当浮点计算机和定点计算机中数据的位数相同时,浮点数的表示范围比定点数大得多。

例如,对于16位二进制编码,无符号数的范围为0~65535,补码定点整数的范围为-32768~+32767。对于浮点数,可有多种表示方案。假定阶码7位(含阶符1位),用移码表示,尾数9位(含数符1位),用补码表示,则该非规格化浮点数所能表示的数值范围是-263~+(1-2-8)×263。可见,同样字长的浮点数所能表示的数值范围要大得多。

(2)当浮点数为规格化数时,其精度比相同位数的定点数高。

(3)浮点数运算分为阶码部分和尾数部分,而且运算结果要求规格化,故浮点运算步骤比定点运算步骤多,运算速度比定点低,运算电路比定点复杂。

(4)在溢出的判断方法上,浮点数对规格化数的阶码进行判断,而定点数对数值本身进行判断。

总之,浮点数在数的表示范围、数的精度、溢出处理和程序编程方面(不取比例因子)均优于定点数。但在运算规则、运算速度及硬件成本方面又不如定点数。因此,究竟选用定点数还是浮点数,应根据具体应用综合考虑。一般来说,通用的大型计算机大多采用浮点数,或同时采用定点数和浮点数;小型、微型及某些专用机、控制机则大多采用定点数。当需要作浮点运算时,可通过软件实现,也可外加浮点扩展硬件(如协处理器)来实现。

例2.8将十进制数x=+13/128写成二进制定点数和浮点数(尾数数值部分取7位,阶码数值部分取7位,阶符和数符各取1位,阶码采用移码,尾数用补码表示),并分别写出该数的定点数和浮点数的编码(采用图2.2所示的编码格式)。图2.8例2.8中浮点数的表示形式

例2.9设浮点数字长为16位,其中阶码为6位(含1位阶符),尾数为10位(含1位数符),阶码用移码,尾数用补码,写出十进制数x=-(53/512)对应的规格化浮点数编码(采用图2.5所示的编码格式)。图2.9例2.9中浮点数的表示形式

例2.10已知规格化浮点数字长16位,其中7位阶码(含一位阶符),用移码表示,9位尾数(含一位数符),用补码表示,其格式及编码值如图2.10所示,请写出该数的真值。图2.10例2.10中浮点数的编码

解该浮点数尾数为1.01011001,真值为-0.10100111。阶码为1000111,真值为7,因此浮点数的真值为

2.3.2IEEE754标准

1985年,IEEE发表了一份关于单精度和双精度浮点数的表示标准,这个标准官方称为IEEE7541985。以后又不断加以发展,SUN公司于2005年推出《数值计算指南》(中译本名),对该标准进行了更加详细和深入的讨论,给出了多种格式及程序。因此,《数值计算指南》更加全面、实用。目前IEEE754标准已获得了广泛的认可,并已用于当前所有处理器和浮点协处理器中。

IEEE754规定了单精度和双精度两种基本的浮点格式以及双精度扩展等多种浮点格式。常用的IEEE754格式参数如表2.4所示。

1.单精度浮点数

1)编码IEEE754标准规定,单精度浮点数的真值一般表示为

IEEE754单精度浮点数的编码格式如图2.11所示。其编码格式由三个字段构成:数符s为1位,尾数编码f为23位,阶码编码e为8位(含1位阶符),每字段的位模式如表2.5所示。图2.11IEEE754单精度浮点数的编码格式

由表2.5可以看到,正规数尾数有效数字的前导位(小数点左侧的位)为1,与23位尾数一起提供了24位的精度。次正规数有效数字的前导位为0,在IEEE754标准中,单精度格式次正规数也称为单精度格式非规格化数。表中符号u为任意值。

2)说明

根据上述描述,可以得到关于IEEE754标准单精度浮点数的如下结论:

(1)由于规定阶码真值E=e-127,并且0<e<255(即规定编码e在+1~+254内为正规数),因此阶码真值E的取值范围为-126~+127。

(2)所能表示的正规数范围:正数为+2+127×(1+1-2-23)~+2-126×(1+0),负数为-2+127×(1+1-2-23)~-2-126×(1+0)。

(3)当e=0或e=255时,在IEEE754标准中表示特殊的数。

例2.11利用IEEE754标准将十进制数176.0625表示为单精度浮点数。．

解首先将该十进制数转换成二进制数,有

对二进制数规格化,有

(1)单精度浮点数的23位尾数f为01100000001000000000000;

(2)单精度浮点数阶码真值E=e-127=7,即e=(7+127)10=(134)10=(10000110)2,则e就是阶码编码;

(3)将(176.0625)10表示为IEEE754标准的单精度浮点数,有

例2.12若浮点数x的IEEE754编码为(41360000)16,求其浮点数的十进制值。解将十六进制数展开为二进制数,有

2.对双精度浮点数的说明

下面简要说明一下IEEE754标准双精度浮点数。

(1)阶码真值E的取值范围为-1022~+1023,将其偏移+1023即得编码e,e编码值为+1~+2046。

(2)双精度浮点规格化数表示N为

(3)所能表示的规格化数范围:正数为+2+1023×(1+1-2-52)~+2-1022×(1+0),负数为-2+1023×(1+1-2-52)~-2-1022×(1+0)。

(4)当e=0或e=2047时,在IEEE754标准中表示特殊的数。

2.4BCD码

在计算机中,采用4位二进制编码来表示1位十进制数,这种编码称为BCD码(Binary-CodedDecimal,二十进制数)。4位二进制有16种编码,从中取出10种表示十进制数的0~9十个数字,有多种方案。因此有多种BCD码,其中使用最多的是8421码。

在8421码中,表示1位十进制数的4位二进制编码,从最高位到最低位的权值依次为8、4、2、1。因此可用0000、0001、0010、…、1001这十个编码分别表示十进制数0、1、2、…、9,剩余的6个编码对8421码而言是非法的,是不允许出现的。

例如十进制数49,用8421码表示为01001001。

8421码为有权码,即4个二进制位上有确定的权值。其他的有权码还有5421码、2421码、5211码、4311码、8421码等。另外还有无权码,即二进制各位上没有确定的权值,如余3码、格雷码等。

2.5非数值数据

2.5.1ASCII码现代计算机不仅处理数值领域的问题,而且处理大量非数值领域的问题。这样,必然要引入文字、字母以及某些专用符号,以便表示文字语言、逻辑语言等信息。例如,人机交互信息时使用英文字母、标点符号、十进制数以及诸如$、%、+等符号。然而,计算机只能处理二进制数据,上述信息应用到计算机时,都必须表示成二进制数据,即字符信息也要用数据表示,称为符号数据。

ASCII码编码格式如图2.12所示,低4位组d3d2d1d0用作行编码,高3位组d6d5d4用作列编码,可表示128个符号。ASCII编码表见表2.6。图2.12ASCII码的编码格式

字符串是指连续的一串字符。通常方式下,它们占用主存中连续的多个字节单元,每个字节单元存储一个字符。当主存字由2个或4个字节组成时,在同一个主存字中,既可按从低位字节向高位字节的顺序存放字符串内容,也可按从高位字节向低位字节的顺序存放字符串内容。这两种存放方式都是常用方式。

2.5.2汉字编码

英文是一种拼音文字,只需要配备26个字母键,并规定26个字母的编码(比如通用的ASCII码)就能方便地输入英文信息了。汉字字形结构复杂,仅部首就有数百种,汉字的字数也很多,因此汉字的计算机处理技术远比拼音文字复杂。

从ASCII、GB2312—80、GBK到GB18030—2005,这些字符集是向下兼容的,即同一个字符在这些方案中总是有相同的编码,后面的标准支持更多的字符。中英文被统一处理,区分中文、英文的方法是看最高字节的最高位,为0即是ASCII码,为1则为中文(双字节或四字节)。

2.5.3Unicode与UTF-8

为了统一表示世界各国的文字,1993年国际标准化组织公布了国际标准ISO/IEC10646,简称UCS。这一标准为包括汉字在内的各种正在使用的文字规定了统一的编码方案,因此又称为Unicode。Unicode已获得了一些程序设计语言(如Java)和操作系统(如Windows)的支持。

Unicode的基本思路是给每一个字符和符号分配一个永久的、唯一的16位值,称为码点(CodePoint)。例如,汉字“计”的码点为0x8BA1,记为U+8BA1。Unicode系统最多有65536个码点,而全世界的语言大概有20万个符号,因此码点就成为一种稀缺资源,不能随意分配。Unicode的编码空间大概分为六部分,如表2.7所示。其中,ASCII字符的码点定义为0~127,因此ASCII码与Unicode之间的转换规则十分简单。

为此又设计出了Unicode字符集的编码方案,如UTF-8、UCS-2、UTF-16、UCS-4和UTF-32,其中最常用的是UTF-8。UTF-8以8位一个字节为单位,是一种可变长度的编码。它将Unicode的码点编码为1~4个字节,具体编码方案如表2.8所示

例如,汉字“计”的码点为U+8BA1,属于表2.8的第三行范围,编码为三个字节,“计”的UTF-8的编码为E8AEA1,其编码方法如图2.13所示。图2.13汉字“计”的UTF-8编码方法

UTF-8的优点在于:编码0~127分配给了ASCII码,并且用一个字节表示,因此纯ASCII码的字符串也是UTF-8的合法字符串,两者一致,这样原先以ASCII码存储的文件或处理ASCII码的程序,不用改动即可兼容UTF-8;UTF-8编码中的第一个字节指明了这个字符一共有几个字节,若第一个字节最高位是“0”,则该字符只有一个字节,若第一个字节最高位是“1”,则有几个连续“1”就表明该字符有几个字节。后面的字节都以“10”开头,这样在传输或存储中出错时,很容易跳过出错字节,直接找到下一个字符的起始字节,即拥有自同步能力。当前UTF-8在互联网上被广泛使用。

2.6检错与纠错码

元件故障、噪声干扰等各种因素常常导致计算机在传输、存储或处理信息的过程中出现错误。例如,将一位1从部件A传送到部件B,可能由于传送信道中的噪声干扰而受到破坏,以至于接收部件B收到的是0而不是1。为了防止这种错误,可采用专门的逻辑电路对信号进行编码以便于检测错误,甚至校正错误。

2.6.1码距与校验位位数

假设数据有n位,为了具备检错或纠错能力,必须增添k位校验位,则数据加校验位一共有m=n+k位,称为m位码字。

任意两个m位的码字,其对应位不同的数目称为这两个码字的海明码距。设码字x=xm-1xm-2…x0和y=ym-1ym-2…y0,则x与y的海明码距d定义为

例如,两个8位码字为01001000与11001011,其码距为3。求海明码距只需将两个码字异或后看有多少位是1即可。

对于n位数据,所有的2n个编码都是合法编码。而增加k位校验位变成m=n+k位的码字后,在2m个码字中,仍然只有2n个码字是合法的。在这2n个合法码字之间,两两码字之间海明码距的最小值dmin,称为这种编码的海明码距。

编码的检错与纠错能力取决于其海明码距dmin。如果要检测r位错,则编码的码距dmin至少应为r+1,使得一个合法码字的r位出错时不会成为另一个合法码字。而要纠正r位错,则编码的码距dmin至少应为2r+1,使得一个合法码字r位出错时,得到的码字与原合法码字的码距(为r)一定比它与其他合法码字间的码距(大于等于r+1)要小,因此,只要选取与该错误码字码距最小的合法码字作为正确的码字,就实现了纠错。

例如,一种只有4个合法码字的编码为000000、000111、111000、111111,其海明码距为3,则可以纠1位错误。对于非法码字010111来说,码距最近的合法码字为000111,所以000111就是010111的纠错结果。这是假定只出现1位错误的前提下做出的纠错结果。如果允许出现两位错误,比如码字111111变成了010111,则无法纠错,因为没办法判断到底是一位出错还是两位出错,所以无法确定应该纠错为000111还是111111。

对于n位数据,为使其具有纠一位错的能力,增添k位校验位组成m=n+k位编码。在2n个合法的码字中,其m个二进制位中任何一位出错都会得到一个非法码字,从而可以发现错误。为了能纠正这个一位错误,这些非法码字彼此必须是不同的(反之,如果一个非法码字可能从两个合法码字分别错一位得到,则无法纠错)。因此,每个合法码字对应了m个与之码距为1的非法码字,再加上其自身,每个合法码字对应了m+1个码字,则总的码字数目至少为2n×(m+1)个。而m位编码至多有2m种码字组合,因此要满足2m≥2n×(m+1),将m=n+k代入,可得

在确保具有一位纠错能力时,由式(2.16)可求得数据长度n所需的校验位位数k,如表2.9所示。

2.6.2奇偶校验码

例2.13试确定二进制数X=01010100和Y=01010101的奇校验编码。

解当X=01010100时,奇校验位c必须为0,则加了奇校验的数据X'=001010100。

当Y=01010101时,奇校验位c必须为1,则加了奇校验的数据Y'=101010101。

2.偶校验

偶校验的概念与奇校验是一样的,就是加上偶校验后,必须保证数据(包括偶校验位在内)的n+1位中1的个数为偶数,即必须保证:

当数据X=x0x1…xn-1加上偶校验时,可利用下式求出偶校验位c:

也就是说,偶校验位等于数据各位的模2加。

同样,当数据加上偶校验后,便可以存储或传输。在从存储器读出或通信对方收到该数据后,可利用式(2.19)进行计算。若式(2.19)成立,则认为在存储或传输过程中未发生1位出错。

例2.14试确定二进制数X=01010100和Y=01010101的偶校验编码。

解当X=01010100时,偶校验位c必须为1,则加了偶校验的数据X'=101010100。

当Y=01010101时,偶校验位c必须为0,则加了偶校验的数据Y'=001010101。

由上述分析可见,当数据位中有1位变化时,校验位也会跟着变化,因此奇偶校验码的码距为2,可以检测出1位错误(或奇数位错误,但多于1位错误的概率很小),无法检测出2位或偶数位错,也无法定位错误位置,从而无法纠错。由于奇偶校验原理简单,实现容易,因此这种方法得到了广泛应用。

2.6.3海明校验码

RichardHamming于1950年提出的海明码可以达到满足式(2.16)的最少的校验位数。

1.海明码的编码

设有效信息为16位数据,用D15~D0表示由高到低的各位。根据式(2.16)计算或查表2.7可知,若要纠正1位错误,需要在有效信息中添加5个校验位H4~H0。此时海明码的码长为m=n+k=16+5=21。表2.10所示为21位海明码的生成及校验方程的构建。

(1)构建海明码编码格式。先将21位码的位置编号列于表2.10第1行中,编号从1开始,在表中按顺序排列。在十进制位置编号为2i之处放置各校验位Hi,i从0开始,见表2.10中第2行。在除Hi之外的剩余位置编号之处,将数据D15~D0的各位从低位到高位在表2.10中第3行从右到左按顺序填入,然后合并第2、3行得到海明码编码格式,如图2.14所示。图2.14海明码编码格式

(2)对表2.10第4~8行进行打“√”操作。第4行从位置1(即20,对应H0)开始,从右到左每打1个“√”空1个位置,直到最高位置。第5行从位置2(即21,对应