一. 计算机习题概述

计算机概述：计算机系统$=$$=$硬件$+$$+$软件

硬件：计算机的物理性能，决定计算机性能天花板在哪

软件：计算机的虚拟性能，决定硬件性能可以发挥到什么程度。可分为系统软件和应用软件：

• 系统软件：用来管理整个计算机系统。如：操作系统，DBMS，服务程序等。
• 应用软件：按任务需要编制成的各种程序。如：微信，QQ等。

计算机功能好坏取决于"软"，"硬"件功能的总和。计算机组成原理重点讨论硬件内容。

计算硬件发展：

计算机目前的发展趋势：一方面向更微型、多用途方向发展；另一方面向更巨型，超高速方向发展。

1.计算机硬件的基本组成

1.1 冯诺依曼结构

提出设想：

提出"存储程序的概念"：将指令以二进制的形式先输入计算机的主存储器，然后按其在存储中的首地址执行程序的第一条指令，以后就按该程序的规定顺序执行其他指令，直到程序执行结束。

冯诺依曼机

处理步骤：

1. 输入设备：将信息转化成机器能识别的形式
2. 存储器：存放数据和程序
3. 运算器：算术运算和逻辑运算
4. 控制器：指挥程序运行
5. 输出设备：将结果输出

在计算机系统中，软件和硬件在逻辑上是等效的。对于同一个功能，既可以用软件实现也可以用硬件实现，但用软件实现成本低，效率也低；而用硬件实现成本高，效率也高。如：对于乘法运算，可以设计一个专门的硬件电路实现乘法运算也可以用软件的方式，执行多次加法运算来实现。

冯诺依曼计算机的特点：

1. 计算机由五大部件组成
2. 指令和数据以同等地位存于存储器，可按地址寻访
3. 指令和数据用二进制表示
4. 指令由操作码(如：加减乘除)和地址码组成
5. 存储程序：会提前将指令和程序存放到存储器中
6. 以运算器为中心：输入$/$$/$输出设备与存储器之间的数据传送通过运算器完成。由于运算器还要完成数据中转操作，所以执行效率会降低。

1.2 现代计算机结构

现代计算机结构本质上是冯诺依曼结构的优化。

优化后的冯诺依曼结构：

传统冯诺依曼结构是以运算器为中心，数据传输都需要通过运算器作为中转。而现代计算机通常以存储器为中心，同时运算器和控制器之间的联系也十分紧密，所以将其结合起来就是CPU。即CPU$=$$=$运算器$+$$+$控制器。

现代计算机结构：

$I/O$$I/O$设备会直接和主存储器进行数据交换。

控制器控制运算器进行数据操作(如：加减乘除)，另外也会控制主存储对CPU的读写，及输入输出设备的停止和启动。

主存储器会和CPU之间进行数据交换：一种是参与运算的数据(如：$x,y$$x,y$之类的变量)。另一种是放在控制器中的指令，指令会由控制器解析其含义。

主存储器和CPU统称为主机。

现代计算机硬件结构：

上面比较混淆的是主存和辅存：这两个都是存储器，主存就是主存储器(如：运行内存)，包含在主机内；而辅存指辅助存储器(如：机械硬盘)，属于$I/O$$I/O$设备。

现代冯诺依曼结构

总结：

2.各个硬件功能概况

2.1 主存储器

主存储器由三个部分构成：

1. 存储体：相当于"货架"部分，存储二进制数据，并根据$MAR$$MAR$发送的数据地址，取出数据。
2. MAR(存储地址寄存器)：CPU将想要的数据地址存放到MAR中，即数据地址。
3. MDR(存储数据寄存器)：将存储体中取出的数据，写入MDR中，CPU可以通过数据线路从MDR中拿走数据。

存储步骤是：CPU将数据地址放入MAR中，将数据放入MDR中，之后存储体根据CPU指令将MDR中数据放入MAR指定的存储体地址中。

读取步骤是：CPU将读取地址放入MAR，存储体根据CPU指令将MAR中对应地址在存储体中找到并写入MDR中，CPU再从MDR中读取数据。

重点在存储体上：数据按地址存放在存储体中。

存储体结构：

存储单元：每个存储单元存放一串二进制代码。

存储字(word)：存储单元中二进制代码的组合。

存储字长：存储单元中二进制代码的位数（如：8bit，16bit，32bit，64bit）。

存储元：存储二进制的电子原件，每个存储元可存1bit。

数据在存储体中按地址存储，类似于Excel的一列表格。每个表格代表一个存储单元，每个存储单元存放一串二进制代码称为存储字，每个存储字包含多少个二进制位称为存储字长。

注：MAR位数反映存储单元的个数，MDR位数$=$$=$存储字长。

例1：MAR$=$$=$4位$⟹$$\Longrightarrow$总共有$2^4$$2^4$个存储单元。(4位的排列组合：4！=4*3*2*1=24)

例2：MDR$=$$=$16位$⟹$$\Longrightarrow$每个存储单元可存放$16bit$$16bit$，1个字(word) $=16bit$$=16bit$。

计算机基本单位：

• 位$/$$/$字（bit）：最小的数据单位
• 字节（Byte）：如果计算机硬件是$8$$8$位，那么：$8$$8$个字(bit)组成一个字节(1B$=$$=$8b)，存储空间的最小单位。
• B：1B=8b，K：1KB = 1024B，M：1MB=1024KB，G：1GB=1024MB，T,P,E

2.2 运算器

用于实现算术运算(如：加减乘除)、逻辑运算(如：与或非)

有四部分构成：

• ACC：累加器，用于存放操作数，或运算结果。
• MQ：乘商寄存器，在乘除运算时，用于存放操作数或运算结果。
• X：通用的操作数寄存器，用于存放操作数。
• ALU(核心部件)：算术逻辑单元，通过内部复杂的电路实现算术运算、逻辑运算。是运算器的核心单元。

ACC、MQ、X在进行加减乘除操作区别：

2.3 控制器

指挥各个部件，使程序可以正常运行

主要有三部分构成：

• CU(核心元件)：控制单元，分析指令，给出控制信号。是控制器核心元件。
• IR：指令寄存器，存放当前执行的指令
• PC：程序计数器，存放下一条指令的地址，有自动加$1$$1$的功能

代码相当于指令，每完成一条指令过程：

1. 取指令(PC)

   根据PC中所记录的指令地址，从内存中取出该指令。

2. 分析指令(IR)

   将取出的指令由IR进行分析这条指令可以干什么。

3. 执行指令(CU)。

   分析完成后CU会控制其他部件完成指令具体执行。

程序在计算机中的运行过程：

运行顺序：PC$⟹$$\Longrightarrow$MAR$⟹$$\Longrightarrow$MDR$⟹$$\Longrightarrow$IR$⟹$$\Longrightarrow$CU$⟹$$\Longrightarrow$IR$⟹$$\Longrightarrow$MAR$⟹$$\Longrightarrow$MDR$⟹$$\Longrightarrow$ACC

例：给定以下高级语言分析其在计算机内执行过程。

1
int a=2,b=3,c=1,y=0;
2
void main(){
3
    y=a*b+c;
4
}

代码在主存结构如下：

地址$0\sim 4$$0\sim4$是y=a*b+c这段程序对应的机器指令；地址$5\sim 8$$5\sim8$是四个变量$a,b,c,y$$a,b,c,y$的的存储情况。这里存储字长为$16bit$$16bit$。

运行步骤：

• 首先PC$=0$$=0$，执行主存地址为$0$$0$的第一行的指令

  

  （1）$PC$$PC$存放的内容会通过地址总线传送到$MAR$$MAR$中，即$(PC)\stackrel{0}{\to }MAR$$(PC)\xrightarrow{0}MAR$，此时$(MAR)=0$$(MAR)=0$。也就是控制器向主存指明接下来要访问的是$0$$0$号地址所对应的指令。同时控制器会通过控制总线向主存发送读操作指令。

  （3）接着主存会根据$MAR$$MAR$记录的地址到存储体中取出$0$$0$号地址对应的二进制数据，并将二进制数据放入$MDR$$MDR$当中。即$\text{主}\text{存}(MAR)\to MDR$$主存(MAR)\rightarrow MDR$，此时$(MDR)=0000010000000101$$(MDR)=000001\quad 0000000101$

  （4）$(MDR)$$(MDR)$中存放的数据就是指令，所以这条指令会通过数据总线放入$IR$$IR$中。即$(MDR)\to IR$$(MDR)\rightarrow IR$，导致$(IR)=0000010000000101$$(IR)=000001\quad 0000000101$

  （5）$(IR)\stackrel{000001}{\to }CU$$(IR)\xrightarrow{000001}CU$，$IR$$IR$将前六位的指令操作码($000001$$000001$)发送到$CU$$CU$中，$CU$$CU$分析后得知，这是取数指令。

  （6）$(IR)\stackrel{0000000101}{\to }MAR$$(IR)\xrightarrow{0000000101}MAR$，将$IR$$IR$中的数据地址码发送给$MAR$$MAR$，导致$(MAR)=5$$(MAR)=5$。因为$0000000101$$0000000101$转化十进制是$5$$5$

  （8）$\text{主}\text{存}(MAR)\stackrel{5}{\to }MDR$$主存(MAR)\xrightarrow{5}MDR$，导致$(MDR)=0000000000000010=2$$(MDR)=0000000000000010=2$。主存根据$MAR$$MAR$地址找到数据放入$MDR$$MDR$中

  （9）最后在控制单元的指挥下$MDR$$MDR$中的数据会被存放到$ACC$$ACC$中。$(MDR)\stackrel{0000000000000010=2}{\to }ACC$$(MDR)\xrightarrow{0000000000000010=2}ACC$，导致$(ACC)=0000000000000010=2$$(ACC)=0000000000000010=2$

  上面七步操作完成后$a=2$$a=2$代码执行完毕。其中$1,3,4$$1,3,4$是取指令；$5$$5$是分析指令；$6,8,9$$6,8,9$执行取数指令。

• 在上述取指令动作完成后，由于$PC$$PC$具有自动加$1$$1$的功能，所以$(PC)=1$$(PC)=1$，即执行主存地址为$1$$1$的第二行的指令

  

  此时$(PC)=1$$(PC)=1$，$(ACC)=\{a=2\}$$(ACC)=\{a=2\}$

  （1）$PC\stackrel{1}{\to }MAR$$PC\xrightarrow{1}MAR$，导致$(MAR)=1$$(MAR)=1$

  （3）$\text{主}\text{存}(MAR)\to MDR$$主存(MAR)\rightarrow MDR$，导致$(MDR)=0001000000000110$$(MDR)=000100\quad0000000110$

  （4）$(MDR)\to IR$$(MDR)\rightarrow IR$，导致$(IR)=0001000000000110$$(IR)=000100\quad0000000110$

  （5）$(IR)\stackrel{000100}{\to }CU$$(IR)\xrightarrow{000100}CU$，$IR$$IR$将前六位指令操作码$(000100)$$(000100)$发送给$CU$$CU$，$CU$$CU$分析后得知，这是乘法指令

  （6）$(IR)\stackrel{0000000110}{\to }MAR$$(IR)\xrightarrow{0000000110}MAR$，将$IR$$IR$中数据的地址吗发送到$MAR$$MAR$，导致$(MAR)=0000000110=6$$(MAR)=0000000110=6$

  （8）$\text{主}\text{存}(MAR)\stackrel{6}{\to }MDR$$主存(MAR)\xrightarrow{6}MDR$，导致$(MDR)=0000000000000011=3$$(MDR)=0000000000000011=3$

  （9）$\text{主}\text{存}(MDR)\stackrel{3}{\to }MQ$$主存(MDR)\xrightarrow{3}MQ$，将$MDR$$MDR$中的值放入乘商寄存器$MQ$$MQ$当中

  （10）将$(ACC)\stackrel{a=2}{\to }X$$(ACC)\xrightarrow{a=2}X$，将$ACC$$ACC$中$a$$a$的值$2$$2$放入通用寄存器$X$$X$当中。导致$(X)=2$$(X)=2$

  （11）$CU$$CU$通过控制线向$ALU$$ALU$发送相乘指令。$(MQ)\ast (X)\stackrel{2\ast 3=6}{\to }ACC$$(MQ)*(X)\xrightarrow{2*3=6}ACC$，导致$(ACC)=6$$(ACC)=6$，如果乘积太大，需要$MQ$$MQ$辅助存储。

  上面九步操作完成后$a\ast b$$a*b$代码执行完毕。其中$1,3,4$$1,3,4$是取指令；$5$$5$是分析指令；$6,8,9,10,11$$6,8,9,10,11$执行乘法指令。

• 在上述取指令动作完成后，由于$PC$$PC$具有自动加$1$$1$的功能，所以$(PC)=2$$(PC)=2$，即执行主存地址为$2$$2$的第三行的指令

  

  此时$(PC)=2$$(PC)=2$，$(ACC)=\{6\}$$(ACC)=\{6\}$

  （1）$PC\stackrel{2}{\to }MAR$$PC\xrightarrow{2}MAR$，导致$(MAR)=2$$(MAR)=2$

  （3）$\text{主}\text{存}(MAR)\to MDR$$主存(MAR)\rightarrow MDR$，导致$(MDR)=000011000000011$$(MDR)=000011\quad000000011$

  （4）$(MDR)\to IR$$(MDR)\rightarrow IR$，导致$(IR)=000011000000011$$(IR)=000011\quad000000011$

  （5）$(IR)\stackrel{000011}{\to }CU$$(IR)\xrightarrow{000011}CU$，$IR$$IR$将前六位指令操作码$(000011)$$(000011)$发送给$CU$$CU$，$CU$$CU$分析后得知，这是加法指令

  （6）$(IR)\stackrel{000000011}{\to }MAR$$(IR)\xrightarrow{000000011}MAR$，将$IR$$IR$中数据的地址吗发送到$MAR$$MAR$，导致$(MAR)=000000011=7$$(MAR)=000000011=7$

  （8）$\text{主}\text{存}(MAR)\stackrel{7}{\to }MDR$$主存(MAR)\xrightarrow{7}MDR$，导致$(MDR)=0000000000000001=1$$(MDR)=0000000000000001=1$

  （9）当进行加法运算的时候$(ACC)$$(ACC)$中会先存入被加数，通用寄存器会存放加数。$(MDR)\stackrel{1}{\to }X$$(MDR)\xrightarrow{1}X$，$(X)=1$$(X)=1$

  （10）$CU$$CU$向$ALU$$ALU$发送相加指令。$ALU$$ALU$将$(ACC)$$(ACC)$中的值与$(X)$$(X)$中的值相加，再放回$(ACC)$$(ACC)$。$(ACC)+(X)\stackrel{6+1=7}{\to }ACC$$(ACC)+(X)\xrightarrow{6+1=7}ACC$。导致$(ACC)=7$$(ACC)=7$。

  上面八步操作完成后$a\ast b+c$$a*b+c$代码执行完毕。其中$1,3,4$$1,3,4$是取指令；$5$$5$是分析指令；$6,8,9,10$$6,8,9,10$执行相加指令。

• $PC$$PC$自动加$1$$1$，所以$(PC)=3$$(PC)=3$，即执行主存地址为$3$$3$的第四行的指令

  

  此时$(PC)=3$$(PC)=3$，$(ACC)=\{7\}$$(ACC)=\{7\}$

  （1）$PC\stackrel{3}{\to }MAR$$PC\xrightarrow{3}MAR$，导致$(MAR)=3$$(MAR)=3$

  （3）$\text{主}\text{存}(MAR)\to MDR$$主存(MAR)\rightarrow MDR$，导致$(MDR)=000010000001000$$(MDR)=000010\quad000001000$

  （4）$(MDR)\to IR$$(MDR)\rightarrow IR$，导致$(IR)=000010000001000$$(IR)=000010\quad000001000$

  （5）$(IR)\stackrel{000010}{\to }CU$$(IR)\xrightarrow{000010}CU$，$IR$$IR$将前六位指令操作码$(000010)$$(000010)$发送给$CU$$CU$，$CU$$CU$分析后得知，这是存数指令

  （6）$(IR)\stackrel{000001000}{\to }MAR$$(IR)\xrightarrow{000001000}MAR$，将$IR$$IR$中数据的地址吗发送到$MAR$$MAR$，导致$(MAR)=000001000=8$$(MAR)=000001000=8$

  （7）将$ACC$$ACC$中的结果通过数据总线送到$MDR$$MDR$中。$(ACC)\stackrel{7}{\to }MDR$$(ACC)\xrightarrow{7}MDR$，$(MDR)=7$$(MDR)=7$

  （9）由于是存数指令，所以$CU$$CU$会将$MDR$$MDR$中的数据，存放在$MAR$$MAR$所指定的地址中。$(MDR)\stackrel{7}{\to }\text{地}\text{址}\text{为}8\text{的}\text{存}\text{储}\text{单}\text{元}$$(MDR)\xrightarrow{7}地址为8的存储单元$。故$y=7$$y=7$

  上面七步操作完成后$y=a\ast b+c$$y=a*b+c$代码执行完毕。其中$1,3,4$$1,3,4$是取指令；$5$$5$是分析指令；$6,7,9$$6,7,9$执行存数指令。

• $PC$$PC$自动加$1$$1$，所以$(PC)=4$$(PC)=4$，即执行主存地址为$4$$4$的第五行的指令

  

  此时$(PC)=4$$(PC)=4$

  （1）$PC\stackrel{4}{\to }MAR$$PC\xrightarrow{4}MAR$，导致$(MAR)=4$$(MAR)=4$

  （3）$\text{主}\text{存}(MAR)\to MDR$$主存(MAR)\rightarrow MDR$，导致$(MDR)=000110000000000$$(MDR)=000110\quad000000000$

  （4）$(MDR)\to IR$$(MDR)\rightarrow IR$，导致$(IR)=000110000000000$$(IR)=000110\quad000000000$

  （5）$(IR)\stackrel{000110}{\to }CU$$(IR)\xrightarrow{000110}CU$，$IR$$IR$将前六位指令操作码$(000110)$$(000110)$发送给$CU$$CU$，$CU$$CU$分析后得知，这是停机指令

  利用中断机制通知操作系统终止该进程。

总结：

OP：操作码

AD：地址码

CPU区分指令和数据的依据：根据指令周期的不同阶段

运行汇总

汇总二

2.4 计算机层次结构

最底层：由传统机器(机器语言的机器)和微程序机器(微指令系统)组成。

这一层传统机器执行二进制机器指令，而机器指令可以分解为多个微指令，微程序机器就是执行这些微指令的。

再上一层是：虚拟机器(汇编语言机器)

汇编语言编写的代码需要翻译成机器码，所以是虚拟机器。

再上一层是：虚拟机器(高级机器语言)

需要用编译程序翻译成汇编语言。

而我们编写的程序往往需要用到操作系统的调用，向上提供广义指令。

所以总的计算机层次：

计算机层次结构特点：下层是上层的基础，上层是下层的扩展

计算机硬件层：微程序机器MO(微指令系统)------>传统机器M1(用机器语言的机器)

计算机软件层：虚拟机器M2(操作系统机器)------>虚拟机器M3(汇编语言机器)------>虚拟机器M4(高级语言机器)

硬件层位于最底层，具有下层是上层的基础，上层是下层的扩展的特点。

编译型程序：将高级语言编写的源程序全部语句一次全部翻译成机器语言程序，而后再执行机器语言程序（只需翻译一次)

解释型程序：将源程序的一条语句翻译成对应于机器语言的语句，并立即执行。紧接着再翻译下一句(每次执行都要翻译)

注意：编译、汇编、解释程序可以统称为翻译程序。

3. 计算机的性能指标

3.1 存储器的性能指标

主寄存器的容量$=$$=$存储单元的个数$\times$$\times$存储字长bit

例：MAR为$32$$32$位，MDR为$8$$8$位，总容量$=2^{32}\ast 8=4GB$$=2^{32}*8=4GB$

3.2 CPU的性能指标

• CPU的主频：CPU内数字脉冲信号震荡的频率，很大程度上反映了CPU的性能。如：$2.9GHZ$$2.9GHZ$，$3.7GHZ$$3.7GHZ$

  可以理解为指挥CPU内部部件工作的节奏。

  CPU震荡图：

  

  其中每个脉冲信号的时间称为CPU的时钟周期(微秒，纳秒)

  CPU主频与时钟周期关系：CPU主频(时钟频率)$=\frac{1}{CPU\text{时}\text{钟}\text{周}\text{期}(\text{赫}\text{兹})}$$=\frac{1}{CPU时钟周期(赫兹)}$ 。即时钟周期$=$$=$CPU主频的倒数

  $2.9GHZ$$2.9GHZ$代表CPU在一秒可以执行$2.9\ast {10}^9$$2.9*10^{9}$个周期。

• CPI

  CPI：指执行一条指令所需的时钟周期数

  CPI性能是变化的：不同的指令，CPI不同。甚至相同的指令，CPI也可能有变化。

  执行一条指令的耗时$=$$=$ $CPI\ast CPU\text{时}\text{钟}\text{周}\text{期}$$CPI*CPU时钟周期$

  例：某CPU主频为1000Hz，某程序包含100条指令，平均来看指令的$CPI=3$$CPI=3$。该程序在该CPU上执行需要多久?

  $$\begin{array}{r}\\ \text{解}：\\ & \text{总}\text{耗}\text{时}=CPI\ast \frac{1}{CPU\text{主}\text{频}(\text{时}\text{钟}\text{频}\text{率})}\\ \\ & \therefore 100\times \frac{1}{1000}\times 3=0.3s\end{array}$$

  CPU执行时间(一个程序的耗时)$=\frac{(\text{指}\text{令}\text{条}\text{数}\ast CPI)}{\text{主}\text{频}(\text{时}\text{钟}\text{周}\text{期})}=\frac{CPU\text{时}\text{钟}\text{周}\text{期}\text{数}}{\text{主}\text{频}}$$=\frac{(指令条数*CPI)}{主频(时钟周期)}=\frac{CPU时钟周期数}{主频}$

• IPS

  每秒执行多少条指令

  $IPS=\frac{\text{主}\text{频}}{\text{平}\text{均}CPI}$$IPS=\frac{主频}{平均CPI}$

  单位：单位一般在指标名称前。如：KIPS、MIPS

• FLOPS

  每秒执行多少次浮点运算

  单位：单位一般在指标名称前。如：KPS、MPS、KFLOPS…………

  注：此处K、M、G、T为数量单位。即$K=\text{千}={10}^3$$K=千=10^3$、$M=\text{百}\text{万}={10}^6$$M=百万=10^6$、$G=\text{十}\text{亿}={10}^9$$G=十亿=10^9$、$T=\text{万}\text{亿}={10}^{12}$$T=万亿=10^{12}$

3.3 系统整体性能指标

• 数据通路带宽

  是数据总线一次所能并行传送信息的位数（各硬件部件通过数据总线传输数据)

  CPU与内存和$I/O$$I/O$设备之间的信息传输都是通过数据总线传输的。如：一台计算机的数据通路带宽为$8bit$$8bit$要从存储体中读出$16bit$$16bit$信息需要两次。所以数据通路带宽会直接影响到各个部件之间传输的效率。

• 吞吐量

  吞吐量：指系统在单位时间内处理请求的数量。如：网站处理用户请求。

  它取决于信息能多快地输入内存，CPU能多快地取指令，数据能多快地从内存取出或存入，以及所得结果能多快地从内存送给一台外部设备。这些步骤中的每一步都关系到主存，因此，系统吞吐量主要取决于主存的存取周期。

• 响应时间

  响应时间:指从用户向计算机发送一个请求，到系统对该请求做出响应并获得它所需要的结果的等待时间。

  通常包括CPU时间(运行一个程序所花费的时间）与等待时间（用于磁盘访问、存储器访问、$I/O$$I/O$操作、操作系统开销等时间)。

• 基准程序

  基准程序是用来测量计算机处理速度的一种实用程序，以便于被测量的计算机性能可以与运行相同程序的其它计算机性能进行比较。常见的基准程序有各类跑分软件。

注：

1. 主频高的CPU不一定比主频低的CPU快。如两个CPU，$A$$A$的主频为$2GHz$$2GHz$，平均$CPI=10$$CPI=10$；$B$$B$的主频$1GHz$$1GHz$，平均$CPI=1$$CPI=1$。所以$B$$B$虽然主频低，但是$CPI$$CPI$处理快，总体比$A$$A$快。
2. 若两个CPU的平均CPI相同，频率高的CPU也不一定快。还要看指令系统，如$A$$A$不支持乘法指令，只能用多次加法实现乘法；而$B$$B$支持乘法指令。
3. 基准程序(跑分软件)执行得越快也不能说明机器性能越好：基准程序中的语句存在频度差异，运行结果也不能完全说明问题

3.4 总结

计算机性能指标

二. 数据的表示与运算

1. 进位计数制

十进制

如：$975.36$$975.36$

其可以表示为：$9\times {10}^2+7\times {10}^1+5\times {10}^0+3\times {10}^{-1}+3\times {10}^{-2}$$9\times10^2+7\times10^1+5\times10^{0}+3\times10^{-1}+3\times10^{-2}$

由十进制可以推广到多进制。

1.1 $r$$r$进制转化为十进制

基数：每个数码位所用到的不同符号的个数，十进制基数是$0\sim 9$$0\sim9$，$r$$r$进制的基数为$0\sim r$$0\sim r$。

下面是一些常见进制的基数：

二进制：$0,1$$0,1$

八进制：$0,1,2,3,4,5,6,7$$0,1,2,3,4,5,6,7$

十进制：$0,1,2,3,4,5,6,7,8,9$$0,1,2,3,4,5,6,7,8,9$

十六进制：$0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F$$0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F$

$r$$r$进制转化为十进制例题：

1. 二进制($B$$B$)：$101.1\stackrel{\text{转}\text{换}\text{为}\text{十}\text{进}\text{制}}{\to }$$101.1\xrightarrow{转换为十进制}$$1\times 2^2+0\times 2^1+1\times 2^0+1\times 2^{-1}=5.5$$1\times2^2+0\times2^1+1\times2^0+1\times2^{-1}=5.5$
2. 八进制(O)：$5.4\stackrel{\text{转}\text{换}\text{为}\text{十}\text{进}\text{制}}{\to }$$5.4\xrightarrow{转换为十进制}$$5\times 8^0+4\times 8^{-1}=5.5$$5\times8^0+4\times8^{-1}=5.5$
3. 十进制($D$$D$)：$5.5\stackrel{\text{转}\text{换}\text{为}\text{十}\text{进}\text{制}}{\to }$$5.5\xrightarrow{转换为十进制}$$5\times {10}^0+5\times {10}^{-1}=5.5$$5\times10^0+5\times10^{-1}=5.5$
4. 十六进制($0X/H$$0X/H$)：$5.8\stackrel{\text{转}\text{换}\text{为}\text{十}\text{进}\text{制}}{\to }$$5.8\xrightarrow{转换为十进制}$$5\times {16}^0+8\times {16}^{-1}=5.5$$5\times16^0+8\times16^{-1}=5.5$

计算机用二进制好处是：

1. 可使用两个稳定状态的物理器件表示。
2. $0$$0$，$1$$1$正好对应逻辑值假、真。方便实现逻辑运算。
3. 可很方便地使用逻辑门电路实现算术运算。

1.2 二进制转化为八进制和十六进制

• 二进制转化为八进制

  从小数点开始向两端三位一组(因为最大排列为八)，不够补零：小数点左边不够三位向左边补零；右边不够三位向右边补零。每组转换成十进制，再由十进制得到对应的八进制符号

  例：1111000010.01101

  001 111 000 010 . 011 010

  1 7 0 2 . 3 2

  八进制转化为二进制

  每位八进制对应三位的二进制

  $(251.5{)}_8$$(251.5)_8$$\stackrel{\text{转}\text{换}\text{为}\text{二}\text{进}\text{制}}{\to }$$\xrightarrow{转换为二进制}$(010 101 001.101)₂

  具体：$2\stackrel{\text{二}\text{进}\text{制}}{\to }010$$2\xrightarrow{二进制}010$、$5\stackrel{\text{二}\text{进}\text{制}}{\to }101$$5\xrightarrow{二进制}101$、$1\stackrel{\text{二}\text{进}\text{制}}{\to }001$$1\xrightarrow{二进制}001$、$5\stackrel{\text{二}\text{进}\text{制}}{\to }101$$5\xrightarrow{二进制}101$

• 二进制转化为十六进制

  四位一组(最大的排列为十六)，每组转换成十进制，再由十进制得到对应的十六进制符号

  例子：1111000010.01101

  0011 1100 0010 . 0110 1000

  3 C 2 . 6 8

• 十六进制转化为二进制

  每位十六进制对应四位二进制

$(AE86.1{)}_{16}\stackrel{\text{转}\text{换}\text{为}\text{二}\text{进}\text{制}}{\to }$$(AE86.1)_{16}\xrightarrow{转换为二进制}$(1010 1110 1000 0110.0001)₂

具体是：$A\stackrel{\text{转}\text{换}\text{为}\text{二}\text{进}\text{制}}{\to }1010$$A\xrightarrow{转换为二进制}1010$、$E\stackrel{\text{转}\text{换}\text{为}\text{二}\text{进}\text{制}}{\to }1110$$E\xrightarrow{转换为二进制}1110$、$8\stackrel{\text{转}\text{换}\text{为}\text{二}\text{进}\text{制}}{\to }1000$$8\xrightarrow{转换为二进制}1000$、$6\stackrel{\text{转}\text{换}\text{为}\text{二}\text{进}\text{制}}{\to }0110$$6\xrightarrow{转换为二进制}0110$、$1\stackrel{\text{转}\text{换}\text{为}\text{二}\text{进}\text{制}}{\to }0001$$1\xrightarrow{转换为二进制}0001$

• 八进制与十六进制互换

  这两者之间的转换可以借助十进制或者二进制完成，可以先将八进制转换成十进制或二进制，再转换成十六进制。通过间接转换来实现。

1.3 十进制转化任意进制

• 整数部分转换（除基取余法）：$\frac{\text{十}\text{进}\text{制}\text{数}}{r\text{进}\text{制}}=\text{商}\cdots \text{余}\text{数}$$\frac{十进制数}{r进制}=商\cdots 余数$，之后一直除$r$$r$直到商为$0$$0$，再将余数倒叙排列即可。

  75转二进制：

  

• 小数部分转化（乘基取整法）：$\text{十}\text{进}\text{制}\text{数}\times r\text{进}\text{制}=\text{小}\text{数}D$$十进制数\times r进制=小数D$，再取走小数的整数部分再乘$r$$r$进制，直到最后小数$D=\text{原}\text{十}\text{进}\text{制}\text{数}\text{或}\text{者}\text{等}\text{于}0.0$$D=原十进制数或者等于0.0$即可，最后正序排序取走整数部分即可。

  注意：有的十进制小数无法用二进制精确表示，我们一般当$D=\text{原}\text{十}\text{进}\text{制}\text{数}$$D=原十进制数$时停止。

  $0.3$$0.3$转换为二进制：

  

• 也可以将十进制转换为二进制，然后二进制再转换为八进制或十六进制。

  进制速查表：

  

1.4 真值和机器数

十进制$+15$$+15$转换为二进制需要再前面加一位符号位，正号用$0$$0$，负号用$1$$1$。所以$+15\stackrel{\text{二}\text{进}\text{制}}{\to }01111$$+15\xrightarrow{二进制}0\quad1111$，$-15\stackrel{\text{转}\text{换}\text{为}\text{二}\text{进}\text{制}}{\to }11000$$-15\xrightarrow{转换为二进制}1\quad1000$

真值：实际的带正负号的数值(人类习惯的样子)。如上面的$+15$$+15$和$-15$$-15$

机器数︰把正负号数字化的数(存到机器里的样子)。如上面的$01111$$0\quad1111$和$11000$$1\quad1000$

2. BCD码

BCD码指：用二进制编码的十进制数。主要有：$8421$$8421$码、余$3$$3$码、$2421$$2421$码。

由于机器数(二进制)转换为真值(十进制)过程较为麻烦，而BCD码就是为了解决这个问题。

BCD码原理：可以用$4bit$$4bit$对应一个十进制位。因为$4bit$$4bit$对应有$2^4=16$$2^4=16$种状态，完全可以表示$0\sim 9$$0\sim9$这十种情况。同时也会与六种状态是冗余的。

2.1 8421码

$8421$$8421$码是指四位二进制位，来表示一个十进制。这四个二进制位的权重分别是$8、4、2、1$$8、4、2、1$。如表示$5\stackrel{8421\text{码}}{\to }0101$$5\xrightarrow{8421码}0101$，因为从左至右第二位$4$$4$和最后一位$1$$1$相加等于$5$$5$

$0\sim 9$$0\sim9$的$8421$$8421$码表：

根据上面表$985\stackrel{8421\text{码}}{\to }100110000101$$985\xrightarrow{8421码}1001\quad1000\quad0101$。可以用三个$8421$$8421$码表示$985$$985$这个数字

$8421$$8421$码的加法运算：

$5(0101)+8(1000)=13(00010011{)}_{8421\text{码}}$$5(0101)+8(1000)=13(0001\quad0011)_{8421码}$

计算机做法是首先将两个码二进制相加$5(0101)+8(1000)=13(1101)$$5(0101)+8(1000)=13(1101)$，显然$1101$$1101$已经超出$8421$$8421$码$0\sim 9$$0\sim9$的范围，即不在映射表中。实际上当结果处于$10(1010)\sim 15(1111)$$10(1010)\sim15(1111)$内是没有定义的，是一个非法$8421$$8421$码区间。解决做法是让结果码$13(1101)+6(0110)$$13(1101)+6(0110)$，由于加$6$$6$后这四个数肯定会向高位进$1$$1$，此时低位部分就是我们需要个位数$3$$3$。所以$13(1101)+6(0110)=19(10011)$$13(1101)+6(0110)=19(1\quad0011)$，低位$0011\stackrel{\text{转}\text{换}\text{为}\text{十}\text{进}\text{制}}{\to }3$$0011\xrightarrow{转换为十进制}3$。而高位$1$$1$我们只需要在前面补上$3$$3$个$0$$0$，即$0001$$0001$，最终$1(0001)3(0011)$$1(0001)\quad 3(0011)$正好可以表示$13$$13$这个数，所以上面$5+8$$5+8$用$8421$$8421$表示是$00010011$$0001\quad0011$。

再看一种情况：对于$9(1001)+9(1001)=18(10010)$$9(1001)+9(1001)=18(10010)$结果已经大于$8421$$8421$码定义的四位。处理方法同样是后四位加$6$$6$，即$0010+0110=11000$$0010+0110=1\quad1000$。低位的$(1000{)}_{8421\text{码}}\stackrel{\text{十}\text{进}\text{制}}{\to }8$$(1000)_{8421码}\xrightarrow{十进制}8$，即个位。前面高位$1$$1$前面补足三个$0$$0$。最终$00011000$$0001\quad1000$。所以$9(1001)+9(1001)=18(00011000{)}_{8421\text{码}}$$9(1001)+9(1001)=18(0001\quad1000)_{8421码}$

总结：只要相加结果处于$10(1010)\sim 18(10010)$$10(1010)\sim18(10010)$这个区间都需要加$6$$6$修正。如果在合法范围内无需修正。

2.2 其他码

• 余$3$$3$码

  在$8421$$8421$码基础上每个数$+3(0011{)}_2$$+3(0011)_{2}$

  

  余$3$$3$码每个进制位并没有权值。

• $2421$$2421$码

  和$8421$$8421$码一样是一个有权码，四位二进制码的权值分别是$2,4,2,1$$2,4,2,1$

  

  需要注意的是对于$2421$$2421$码，其$0\sim 4$$0\sim4$第一位都是$0$$0$，而$5\sim 9$$5\sim9$第一位都是$1$$1$。这是因为要避免歧义性。

3. 无符号整数的表示和运算

无符号整数即自然数，有$0,1,2\cdots$$0,1,2\cdots$

无符号整数的表示：假设现在机器字长是$8$$8$位，那么其通用寄存器只能存$8$$8$位。

如：$255\stackrel{\text{二}\text{进}\text{制}}{\to }11111111$$255\xrightarrow{二进制}11111111$，刚好八位，可以存放在机器字长是$8$$8$位的寄存器中。

但$256\stackrel{\text{二}\text{进}\text{制}}{\to }100000000$$256\xrightarrow{二进制}100000000$，二进制是九位，而机器字长$8$$8$位，其在计算机中只能保存低八位，即$00000000$$00000000$。

而这八位都有权值，没有符号位，所以称为无符号整数。

无符号整数特点：

1. 全部二进制位都是数值位，没有符号位，第$i$$i$位的位权是$2^i-1$$2^i-1$
2. $n$$n$比特的无符号整数表示范围是$0\sim 2^n-1$$0\sim2^{n}-1$，超出则溢出，意味着该计算机无法一次处理这么多位
3. 可以表示的最小的数是：所有位全是$0$$0$，最大的的数是：所有位全是$1$$1$。

无符号整数的加法：从最低位开始，按位相加，并往更高位进位。如：$99(01100011{)}_2+9(00001001)$$99(01100011)_{2}+9(00001001)$，其实二进制位相加即可。

无符号整数的减法：

• 首先"被减数"不变，"减数"全部位按位取反、最后一位$+1$$+1$，减法变加法
• 从最低位开始，按位相加，并往更高位进位

如：$99(01100011{)}_2-9(00001001)$$99(01100011)_{2}-9(00001001)$

首先减数$00001001\stackrel{\text{按}\text{位}\text{取}\text{反}}{\to }11110110$$00001001\xrightarrow{按位取反}11110110$，之后$11110110$$11110110$的最后一位$+1$$+1$，即$11110111$$11110111$

最后计算$01100011+11110111=90(101011010)$$01100011+11110111=90(101011010)$，由于计算结果是九位，寄存器只能存储八位，所以舍弃高位的$1$$1$，结果是$01011010$$01011010$

4. 带符号整数在计算机中应用

带符号整数，如：$-2,-1,0,1,2\cdots$$-2,-1,0,1,2\cdots$

带符号整数可以用原码、反码、补码三种不同编码方式来表示。

带符号整数的表示：假设现在机器字长是$8$$8$位，那么其通用寄存器只能存$8$$8$位。最多只能同时进行$8$$8$位运算

4.1 原码表示法

开头第一位是符号位：正号用$0$$0$，负号用$1$$1$，剩下后七位是数值位。

如：真值$+19\stackrel{\text{二}\text{进}\text{制}}{\to }+10011$$+19\xrightarrow{二进制}+10011$，在$8bit$$8bit$寄存器中存储方式是$0,0010011$$0,0010011$

真值$-19\stackrel{\text{二}\text{进}\text{制}}{\to }-10011$$-19\xrightarrow{二进制}-10011$，在$8bit$$8bit$寄存器中存储方式是$1,0010011$$1,0010011$

原码特性：

1. 若机器字长是$n+1$$n+1$位，带符号整数的原码表示范围：$-(2^n-1)\le x\le 2^n-1$$-(2^n-1)\le x\le2^n-1$
2. 符号位$0/1$$0/1$对应$\text{正}/\text{负}$$正/负$，剩余的数值位表示真值的绝对值
3. 真值$0$$0$有两种形式：$+0$$+0$和$-0$$-0$。$[+0{]}_{\text{原}}=0,0000000$$[+0]_{原}=0,0000000$；$[-0{]}_{\text{原}}=1,0000000$$[-0]_{原}=1,0000000$

原码缺点：符号位不能参与运算，需要设计复杂的硬件电路才能处理。

4.2 原码计算方式

原码加法计算方式是：先将原码$\stackrel{\text{转}\text{换}}{\to }$$\xrightarrow{转换}$反码$\stackrel{\text{转}\text{换}}{\to }$$\xrightarrow{转换}$补码。在进行正常二进制计算即可。

正数转换为补码不变

负数(原码)$\stackrel{\text{符}\text{号}\text{位}\text{不}\text{变},\text{数}\text{值}\text{位}\text{取}\text{反}}{\leftrightarrow }$$\xleftrightarrow{符号位不变,数值位取反}$反码$\stackrel{\text{末}\text{位}+1}{\to }$$\xrightarrow{末位+1}$补码

原码转换为补码快速技巧：原码从右往左找到第一个$1$$1$，这个$1$$1$左边的数值位按位取反就可以变为补码。同样补码转换为原码方式一样。

如：$[-19{]}_{\text{原}}=1,0010011$$[-19]_{原}=1,0010011$转换为补码$[-19{]}_{\text{补}}=1,1101101$$[-19]_{补}=1,1101101$

计算机硬件如何做补码的加法：从最低位开始，按位相加(符号位参与运算)， 并往更高位进位。

注意：负数补码的数值为不能解读成位权。我们需要将其转换为原码。

如上面$[-38{]}_{\text{补}}=1,1011010\stackrel{\text{转}\text{换}\text{为}\text{原}\text{码}}{\to }1,0100110$$[-38]_{补}=1,1011010\xrightarrow{转换为原码}1,0100110$，而$1,0100110\stackrel{\text{十}\text{进}\text{制}}{\to }-38$$1,0100110\xrightarrow{十进制}-38$

而对应原码的减法计算，仍需要将其转换为补码再计算。不同的是计算机只能处理加法运算，所以将减法变为加法即可。如$[A{]}_{\text{补}}-[B{]}_{\text{补}}=[A{]}_{\text{补}}+[-B{]}_{\text{补}}$$[A]_{补}-[B]_{补}=[A]_{补}+[-B]_{补}$

所以只需要解决已知一个补码求其负值的补码。方法是：$[B{]}_{\text{补}}\stackrel{\text{全}\text{部}\text{位}\text{按}\text{位}\text{取}\text{反},\text{末}\text{位}+1}{\to }[-B{]}_{\text{补}}$$[B]_{补}\xrightarrow{全部位按位取反,末位+1}[-B]_{补}$

如：$[19{]}_{\text{补}}\stackrel{\text{全}\text{部}\text{位}\text{按}\text{位}\text{取}\text{反}}{\to }[11101100]\stackrel{\text{末}\text{位}+1}{\to }[11101101{]}_{\text{补}}=[-19{]}_{\text{补}\text{码}}$$[19]_{补}\xrightarrow{全部位按位取反}[11101100]\xrightarrow{末位+1}[11101101]_{补}=[-19]_{补码}$

同样有快速转换的技巧：原码从右往左找到第一个$1$$1$，这个$1$$1$左边的全部位按位取反就可以变为负值补码。

可以看出有符号整数减法和无符号整数减法方法一样，这样就意味着可以用同一套电路就可以实现处理所有加减法。

所以有符号整数的减法：

• 首先"被减数"不变，"减数"全部位按位取反、最后一位$+1$$+1$，减法变加法
• 从最低位开始，按位相加，并往更高位进位

原码计算总结：

注意：计算机内部所有带符号整数的加减法都要先转换为补码形式。

4.3 移码

移码：在补码$[A{]}_{\text{补}}$$[A]_{补}$基础上，符号位取反就可以得到移码$[B{]}_{\text{移}}$$[B]_{移}$。

注意：移码只能表示整数，不能表示小数。且真值$0$$0$只有一种表示形式$10000000$$10000000$，若机器字长为$n+1$$n+1$位，移码整数的范围：$-2^n\le x\le 2^n-1$$-2^n\le x\le2^n-1$

4.4 原码、补码、反码和无符号整数特性

原码和反码的合法表示范围完全相同，都有两种方法表示真值$0$$0$

补码和移码的合法表示范围比原码多一个负数，只有一种方法表示真值$0$$0$

常见考点：两个数$A$$A$和$B$$B$进行某种运算后，是否发生溢出。可以手算做题可以带入十进制验证，是否超出合法范围

如：计算机是$8$$8$位。$A=B=-64$$A=B=-64$，如果其用原码表示$A+b=-128$$A+b=-128$会溢出。而用补码表示则不会溢出。

几种码的表示：

4.5 定点小数表示和运算

之前的定点整数，即带符号的整数，小数点隐含在数值部分末尾。

而定点小数小数点位置是在符号位和数值位中间

定点小数的编码有原码、反码和补码。没有移码。并且定点小数各个位权与定点整数不一样。除符号位，由高位到低位$2^{-1},2^{-2},2^{-3}\cdots$$2^{-1},2^{-2},2^{-3}\cdots$

如：$[x{]}_{\text{原}}=1.1100000$$[x]_{原}=1.1100000$

定点小数原码、反码补码转换和定点整数一样。其计算方法也一样。

定点小数和定点整数对比：

4.6 奇偶校验码

数据在计算机内部进行计算存取过程中可能会发生错误，所以要用到校验。

奇校验码：整个校验码(有效信息位和校验位)中$1$$1$的个数为奇数。

偶校验码：整个校验码(有效信息位和校验位)中$1$$1$的个数为偶数。

一般高位是校验位，剩下$n$$n$位是信息位

如：$1001101$$1001101$奇校验码：$11001101$$11001101$，因为是奇校验而信息位的$1$$1$有$4$$4$个，所以在首位添加$1$$1$，整体$1$$1$个数位$5$$5$是奇数。

$1001101$$1001101$偶校验码：$01001101$$01001101$，信息位$1$$1$个数是$4$$4$，所以不用补$1$$1$，首位添加个$0$$0$即可。

如果是奇校验码，计算会校验$1$$1$个数，如果个数是偶数，则证明发生错误，会要求重新发送。如果是奇数，这没有问题。

奇偶校验码可能检测不出来错误。特别是在发生多位跳变时候。

偶校验的硬件实现：各信息进行异或 (模2加)运算，得到的结果即为偶校验位。

如：$1001101\stackrel{\text{偶}\text{校}\text{验}\text{码}}{\to }01001101$$1001101\xrightarrow{偶校验码}01001101$，对校验码各个位两两进行异或，若结果为$0$$0$则说明正确。

5. 字符与字符串

字母，数字和字符等都是以ascll码的数字形式存储再电脑中

补充：字符数字转整型数字：'1'—'0'=1

整型数字转字符数字：1+'0'='1'

ASCLL码：

• 字母表示

  字母加上各种符号，总共128个。具体如上ASCLL码

• 汉字表示

  国标码：专门用于汉字的ASCLL码，为了防止与字母冲突ASCLL值从128开始。

  输入(拼音)：输入法会将输入的拼音转换为国标码，再将国标码转换为与之相对应的汉字内码。

  输出：用到汉字字形码具体如下：

字形码：

总结：

6. 算术逻辑单元

主要是算术逻辑单元$ALU$$ALU$的构成。

$ALU$$ALU$可以实现算术运算：加、减、乘、除等；逻辑运算：与、或、非、异或等；辅助功能：移位、求补等。

上图是ALU大致图像，$A_i$$A_i$和$B_i$$B_i$是输入信号，如要实现两个数加法，这两个数一个从$A_i$$A_i$输入，一个从$B_i$$B_i$输入。

$F_i$$F_i$是输出信号，运算结果从这里输出。

$K_i$$K_i$是控制信号，控制信号是由控制单元$CU$$CU$发出的，控制信号主要用于解析指令是加法减法等。

下面是$ALU$$ALU$实例图

右边五个控制单元就是上图的$K_i$$K_i$，是用于接收运算符号的。如：$M=1$$M=1$、$S_3\sim S_0=1001$$S_3\sim S_0=1001$时，做逻辑运算$A\oplus B$$A\oplus B$

由于上图$ALU$$ALU$有$4$$4$位，所以可以支持$16$$16$种运算状态。

最下方输入信号，可以反映机器字长。通常与上面输出信号位数保持一致。如上图都是$4$$4$位。

所以$ALU$$ALU$至少需要有控制信号、输入信号和输出信号。

6.1 最基本的逻辑运算

常见的有：与、或、非。与或非三种逻辑运算对应的门电路如下：

假设，$A$$A$端输入$5V$$5V$电信号代表$1$$1$，$B$$B$端输入$1V$$1V$电信号代表$0$$0$，两个信号做与运算结果为$1V$$1V$的$0$$0$。只有两端输入都是高电平信号$5V$$5V$时候结果才会是$1$$1$。

如果非门$A$$A$端输入$5V$$5V$高电平，则会输出$1V$$1V$低电平。

如果一个运算涉及到多个逻辑运算，那么执行顺序要看优先级。与运算可以看作乘法， 而或运算可以看作加法。

如：$AB+CD$$AB+CD$，要先算与运算$AB,CD$$AB,CD$；再算或运算$+$$+$。同样的这样的运算也符合分配律和结合律。

上面意义在于，设计门电路本质上逻辑表达式是对电路的数学化描述，简化逻辑表达式，就是在简化优化电路，就是在省钱。

如：实现$AC+AD$$AC+AD$。其门电路可以设计如下方式：

这里我们用两个$\text{与}$$与$门，$AC$$AC$与$AD$$AD$进行与运算后，两个电信号再通过上面的$\text{或}$$或$门做最后一次运算，最后输出。

同时由于运算遵循分配律，所以$AC+AD\stackrel{\text{分}\text{配}\text{律}}{\to }A(C+D)$$AC+AD\xrightarrow{分配律}A(C+D)$。$A(C+D)$$A(C+D)$设计的门电路如下：

可以看到这里只用了一次或运算计算$C+D$$C+D$；一次与运算计算$A(C+D)$$A(C+D)$。所以这样设计相当于优化了门电路。

6.2 复合逻辑运算

常见的复合逻辑运算有：与非(先进行与运算，再进行非运算)、或非(先进行或运算，再进行非运算)、异或

其表达式表示如下：

其门电路符号如下：

上面运算遵循反演律(德摩根律)：

重点介绍异或运算：即$A$$A$和$B$$B$不同时，输出$1$$1$。详细可以理解为$A=0$$A=0$且$B=1$$B=1$或者$A=1$$A=1$且$B=0$$B=0$时输出$1$$1$

表示式表示为$\bar{A}·B+A·\bar{B}$$\overline{A}·B+A·\overline{B}$。其电路图如下：

假设$A=0,B=1$$A=0,B=1$，$A$$A$的上路输入$0$$0$，下路经过非运算后是$1$$1$；$B$$B$的上路经过非运算后是$0$$0$，下路输入$0$$0$。所以上面的与门$\mathrm{\&}$$\&$输入两个数是$0,0$$0,0$运算后是$0$$0$，下面的与门$\mathrm{\&}$$\&$输入两个数是$1,1$$1,1$结果是$1$$1$，最后两个运算结果$1,0$$1,0$再做或运算结果是$1$$1$。

组后补充一个复合逻辑：同或。其就是异或运算取反。

逻辑运算实现偶校验位

求$1001101$$1001101$的偶校验位

方法一：整体异或$1\oplus 0\oplus 0\oplus 1\oplus 1\oplus 0\oplus 1=0$$1\oplus0\oplus0\oplus1\oplus1\oplus0\oplus1=0$

方法二：部分异或再整体异或$((1\oplus 0)\oplus (1\oplus 1))\oplus ((1\oplus 0)\oplus 1)=0$$((1\oplus0)\oplus(1\oplus1))\oplus((1\oplus0)\oplus1)=0$

与之对应电路如下：

方法三：

从上面三种方法可以看出逻辑表达式是对电路的数学化描述。

逻辑运算实现一位全加器

可以使用异或运算实现全加器。

上面$A_i,B_i$$A_i,B_i$表示两个数相加的第$i$$i$位，$C_{i-1}$$C_{i-1}$来自低位的进位，当前正在运算位称为本位。

计算步骤：

1. 当输入$A_i$$A_i$和$B_i$$B_i$时，可以用异或运算，输入中有奇数个$1$$1$时为$1$$1$(异或)，偶数异或为$0$$0$。$S_i=A_i\oplus B_i\oplus C_{i-1}$$S_i=A_i\oplus B_i\oplus C_{i-1}$
2. 有两种情况会产生进位，如果$A_i{B}_i=1$$A_iB_i=1$表示$A_i{B}_i$$A_iB_i$都是$1$$1$，则要向高位进$1$$1$。另一种情况是两个本位中有一个$1$$1$，且来自低位的进位是$1$$1$，即$(A_i\oplus B_i)C_{i-1}=1$$(A_i\oplus B_i)C_{i-1}=1$。

综上其进位逻辑表示式为$A_i{B}_i+(A_i\oplus B_i)C_{i-1}=1$$A_iB_i+(A_i\oplus B_i)C_{i-1}=1$。对应门电路如下：

其简化图就是一位全加器：

上面门电路图可以理解为一个函数具体实现。而下面简化图可以理解为函数对外暴露的接口。

可以将多个一位全加器串联起来形成串行加法器：只有一个全加器，数据逐位串行送入加法器中进行运算。进位触发器用来寄存进位信号，以便参与下一次运算。

串行加法器本质是一位一位运算进位。所以如果操作数长$n$$n$位加法就要分$n$$n$次进行，每次只能产生一位和，并且串行逐位地送回寄存器。效率较低。

与之对应的是并行全加器。把$n$$n$个全加器串接起来，就可进行两个$n$$n$位数的相加。

这样特点是只有低位的运算结束后，才能进行高位的运算。电信号传递需要大量时间。其效率取决于每一位进位产生速度。

6.3 并行加法器优化

上面介绍的串行进位的并行加法器，特点是其速度依赖于来自低位的进位。接下来要探究的是如何让每个进位产生的更快。

进位$C_i=A_i{B}_i+(A_i\oplus B_i)C_{i-1}$$C_i=A_iB_i+(A_i\oplus B_i)C_{i-1}$，其中$C_{i-1}$$C_{i-1}$又可以进一步展开为$C_{i-1}=A_i{B}_i+(A_i\oplus B_i)C_{i-2}$$C_{i-1}=A_iB_i+(A_i\oplus B_i)C_{i-2}$

还可以进一步对$C_{i-1}$$C_{i-1}$进行展开，当展开到一定次数时会得到最后$C_0$$C_0$。而$C_0$$C_0$是一开拥有的信息。所以第$i$$i$位向更高位的进位$C_i$$C_i$可根据被加数、加数的第$1\sim i$$1\sim i$位信息，再结合$C_0$$C_0$即可确定。即可以利用刚开始被加数和加数每一位信息，和$C_0$$C_0$信息直接求$C_i$$C_i$。这就是其优化思路。

为了方便，记$A_i{B}_i=G_i$$A_iB_i=G_i$，$A_i\oplus B_i=P_i$$A_i\oplus B_i=P_i$，即$C_i=G_i+P_i{C}_{i-1}$$C_i=G_i+P_iC_{i-1}$

所以第一位进位：$C_1=G_1+P_1{C}_0$$C_1=G_1+P_1C_0$

第二位进位：$C_2=G_2+P_2{C}_1=G_2+P_2{G}_1+P_2{P}_1{C}_0$$C_2=G_2+P_2C_1=G_2+P_2G_1+P_2P_1C_0$

以此类推。可以算出$C_i$$C_i$位的进位信息。

从上面可以看出$G_i$$G_i$和$P_i$$P_i$值是经常用到的，只要是角标大于$2$$2$的进行$C_i$$C_i$都要用到$G_i,P_i$$G_i,P_i$。所以可以根据加数和被加数对应的两个比特位算出$G_i$$G_i$和$P_i$$P_i$，这两个信息可以通过线路送往更高位的运算中。所以我们在计算$C_4$$C_4$这一位进位信息时，其各个值都是确定的，只需要根据表达式设计出对应的线路，就可以在$C_4$$C_4$这里直接算出$C_4$$C_4$进位值。也就是说采用这种优化方式，每一位的进位信息几乎都是同时产生的。不需要像之前那样等待后一位进位信息往后传。

这种方式的加法器称为并行进位的并行加法器：各级进位信号同时形成，又称为先行进位、同时进位。