运算方法与运算电路 • Atri Website

加法器#

结构#

接下来讨论使用门电路设计全加器的电子结构

考察一个两位 8 bit 数的加法，并且定义图中的几个参量。实际上，两个 8 bit 数的加法可被看作“8 次 1 bit 数的加法”，因此只考虑第一位（单比特）的情况。

当 $A_i$ 为 1， $B_i$ 为 0 时，此时低位 $C_{i-1}$ 是 0，那么该位比特位（本位）加法运算后的值 $S_i$ 为 1。稍微推理一下不难发现，当 A、B 都是 1，且 C = 0 时，S 为 0。这三者满足异或运算。

异或：相同为 0，不同为 1

S_i = A_i\oplus B_i \oplus C_i

由此可得到全加器的部分结构：两个异或门连接三个输入。

接下来考察第 i 位比特的进位情况 $C_i$ ：

$C_i$ 是本位向高位进位的输出。很容易知道，这两种情况下， $C_i$ 是等于 1 的：

$A_i\ , B_i$ 都是 1
$A_i$ 和 $B_i$ 其中一个是 1，且低位进位 $C_{i-1}$ 也是 1

本质上就是 1+ 1 = 2 然后进位

那么可以得到 $C_i$ 的表达式：

C_i = A_iB_i + (A_i \oplus B_i )C_{i-1}

由此可以得到 $C_i$ 的门电路结构：

将以上两个门电路合并：

由此可以得到一位全加器的数字电路。然后使用一个逻辑符号“FA”简化内部电路逻辑，用其表示全加器。

串行进位加法器#

那么以上我们得到了一位加法器的电路，只需要将 N 个全加器串联（输出 $C_i$ ）起来，就可得到 n 位比特数的相加。

为方便研究，一般会把内部电路封装，用一个符号来表示这 n 位全加器。

电路缺点：

进位信息是串行产生的，计算速度取决于进位产生和传递的速度。位数越多，运算速度越慢。

电信号到达稳态需要一定时间，因此进位产生速度会有延迟。

串行进位又称为行波进位，每一级进位直接依赖于前一级的进位，即进位信号是逐级形成的。

由于两个输入端允许并行输入 n bit，因此这种加法器属于并行加法器。

由于进位信息是串行产生的，因此从“进位方式”看，这种加法器属于串行进位加法器。

综上，很多教材把这种加法器称为 ‘串行进位的并行加法器”。

并行进位加法器（了解即可）#

由上述可知，串行进位加法器运算速度与串联位数成反比，因此加入一些电路逻辑，将其改造为并行进位。

实现方式则是使用 n 位 CLA 部件实现：

并行进位并行加法器所有进位信息都是同时产生的，几乎没有延迟，因此运算速度比 “串行进位的并行加法器”更快。

我们不关心逻辑电路怎么实现，只需要知道它是用来做加法进位的即可。也就是说，只需要知道这元件可以把两个 n 位比特数做加法，输出 n 位比特位的结果

带标志位的加法器#

数电的内容

一般加法器会带四个标志位，方便我们判断输出结果的性质：溢出、正负、是否为 0，进位。

OF（Overflow Flag）：溢出标志，用于判断有符号数加减运算是否溢出。OF = 1 溢出；OF = 0 未溢出
SF（Sign Flag）：符号标志，用于判断有符号数加减运算结果的正负性。SF = 1 结果为负；SF = 0 结果为正
ZF（Zero Flag）：零标志，用于判断加减运算结果是否为 0。ZF = 1 表示结果为 0；ZF = 0 表示结果不为 0
CF（Carry Flag）：进位/借位标志，用于判断无符号数加减运算是否溢出。CF = 1 溢出；CF = 0 未溢出

标志位怎么生成的不细说了，重点是四个标志位的表达式：

总结#

重点：四个标志位

算数逻辑单元 ALU#

考点：

在计算机的作用
功能
实现原理
ALU 图示

ALU 即 Arithmetic and Logic Unit

作用#

红色三角部分可能选择题考

功能#

ALU 的功能自然就是进行一系列运算，这会涉及一个操作数 op，它用于指示 ALU 本次运算的类型。

考试重点：op 由 m 位比特位构成，如果 ALU 支持 k 种功能，容易知道只需要 $2^m > k$ ，就能够表示 k 种功能（可能）

“求补码” 功能：对单个 n 位比特输入 $B$ ，在 op 指令的指示下， ALU 输出 $F$ 输出 B 的补码

“直送”：不改变输入的比特流，原样输出

实现原理（了解即可，不考）#

如果该 ALU 支持 k 种功能，那么每个功能对于一种门电路，然后这 K 个门电路进行并联，通过操作数 op 控制多路选择器 MUX 输出哪一路的门电路结果

ALU 图示#

考试重点如图，以下补充说明。

与其说 ALU 的运算数与机器字长相同，不如说是：ALU 的运算数决定了机器的字长

重点概括为：

控制信号（操作数/码）位数 m 与 ALU 功能种类 K 的关系。
ZF、OF、SF、CF 四个标志位

小结#

定点数的移位运算#

在计算机中，左移一位相当于乘 2，右移一位相当于除 2（很自然的事）。移位分为逻辑移位和算数移位两种。

逻辑移位：服务于无符号数。左移时，高位移出，低位补 0；若高位移出 1，则为溢出（OF=1）；右移时，高位补 0，低位移出。

因此对于无符号整数，每逻辑左移 1 位，相当于 x 2。例如 0001(1)，0011(3)。

逻辑右移时，如果低位的 1 被移出，那么会丢失精度（不保留小数部分，例如 1/2 = 0.5 = 0）

算数移位：有符号数需要考虑符号位，且补码表示。

左移时，高位移出，低位补 0；若移出的高位与原符号不同，则发生符号溢出（即 SF 标志位发生改变）
右移时，高位补符号位，低位移出；若低位的 1 被移除，则精度受到影响

示例

逻辑右移：低位移出丢弃，高位补 0
算数右移:：低位移出丢弃，高位补符号位
逻辑/算数左移：高位移出丢弃，低位补 0

逻辑移位常用于处理无符号整数，算数移位常用于处理带符号整数，是“常用于”，而不是“只能用于”。对于计算机硬件来说，只要给出二进制串，无论是什么数值类型，都可以通过指令进行逻辑移位、算数移位

考试技巧：

移位运算与乘除之间的关系：

用左移 $r$ 位等效： $\times 2^r$
用右移 $r$ 位等效： $\div 2^r$

并且注意溢出和精度丢失问题

定点数的加减运算#

补码加减法#

补码加减法运算极其简单，公式如下（设字长 n + 1）：

[A+B]_{补}=[A]_补 + [B]_补 \\ [A-B]_补 = [A]_补 + [-B]_补

就这么简单，遇到减法，把减数变为相反数即可。

note：符号位一起参与运算，结果字长仍为 n + 1 位，高位截断，且以补码形式保存结果。

溢出判断#

补码加减法的溢出一定发生在：同号相加、异号相减。同时，只有“正数+正数”才会上溢出，负数 + 负数才会下溢出

图中为 3 + 3 发生上溢出

计算机判断溢出的方法：

1. 采用一位符号位的方式：

设 A 的符号位为 $A_s$ ，B 的符号为 $B_s$ ，运算结果的符号为 $S_s$ ，则溢出逻辑表达式为

V = A_sB_s\bar{S_s} + \bar{A_s}\bar{B_s}S_s

如果 V = 1，表示有溢出。

以图中的 $[A+C]_补$ 为例，A、B 的符号位都是 0，运算结果符号位 $S_s=1$ ，则计算得知 V = 1，有溢出。

由此可得到结论：

$A_s$	$B_s$	V	结果
0	0	1	溢出
1	1	0	溢出

也就是前文的：正数（1）+ 正数（1）= 负数（0）和负数（0）+负数（0）=正数（1）的时候会溢出

2. 采用一位符号位加数据进位情况的方法：

设符号位（最高位）的进位为 $C_n$ ，数值最高位（次高位）进位 $C_{n-1}$ ，当二者不同时，发生溢出。

此时可得到溢出的逻辑表达式：

V = C_s\oplus C_1

V = 1 代表有溢出

3. 采用双符号位

对原先的单符号位进行扩展，以两个符号位 $S_1S_2$ ，“00” 表示正数，“11”表示负数。若运算结果的两个符号位不同（ $S_1 \neq S_2$ ），则发生溢出。

当然，如果没溢出，那么两个符号位不可能发生变化。这个方法就是把溢位的数考虑进来了（原先高位截断抛弃了第 n+2 位）。

Note：实际存储时只存储 1 个符号位，运算时会复制一个符号位

逻辑表达式：

V = S_2\oplus S_1

小结#

无符号数的加减运算#

无符号整数的加法：从最低位开始，按位相加，并往更高位进位

例如 99 + 9 = 108：

		01100011
+		00001001
---------------------
		01111100

bash

减法：

“被减数”不变，“减数”全部位按位取反、末位+1（补数的定义），减法变加法
从最低位开始，按位相加，并往更高位进位

以 8 位的 99 - 9 = 90 为例：

9：1001，其“补数”为：256 - 9 = 247

所以为：

99 - 9 = [99 + (256 - 9)]Mod (256) = 90

无符号数天然有取模的特性，例如 8 bit 就是模 256，16 bit 是模 65536

溢出判断方法：

n bit 无符号可表示范围不是 0 到 $2^n-1$ 嘛，超过范围自然就溢出了。把两个量的原码弄出来，比对一下是否超出范围即可。

可以看一下快速判断方法，但是最稳妥的自然是手算

补码加减运算电路#

实际上是使用一个 Sub 信号控制选择加减法：加法时信号为 0，减法为 1。

通过 MUX 实现 Y 的取反与否
通过 $C_{in}$ 信号连接 Sub 控制末位是否 + 1

无符号整数的乘法原理#

计算逻辑：将符号位和数值位分开计算，乘积的符号位进行异或操作，数值部分采用两个数的绝对值的乘积。

这是考试手算的计算逻辑，以下是计算机硬件的实现方法。

观察手算乘法的过程可知，这是一个重复工作：

设被乘数是 A，乘数是 B，都是 n 位，那么一共要进行 n 轮乘法和加法。因为每一次都是 A 和 B 的一个比特位进行乘积，设每一轮的乘积结果为 $P_i$ ，A 和 B 的单比特乘积为 $S_i$ ，具体为：

初始时 $P_0$ = 0000，计数器 $C_n = n$ （一共进行 n 轮运算）
A 和 B 的一个比特位进行乘积（从低位开始），得到首轮的结果 $S_1$
然后 $S_i$ 和 $P_0$ 相加，得到 $P_1$
进行逻辑右移（因为最低位在后续的乘法中用不到了）
计数器 $n--$
重复到 $C_n = 0$

最终得到乘积的结果（2 n 位）。

硬件实现如下：

使用三个寄存器和一个 ALU 实现。控制逻辑依据 Y 中最低位的比特来判断操作：如果是 1（图中），那么执行加法操作；如果是 0 ，不操作（空操作）。

先给出溢出标志的判断（考点）：

对于无符号数：当寄存器 P 中的值不全为 0 （即存在数值）时溢出，因为乘法结束后，最高位应该全是 0（计数器控制要逻辑 4 位）
对于有符号数：当 P 中的数不是低位寄存器 Y 的最高位（符号位）的符号扩展时，出现溢出

硬件的工作流程如下：

1. 初始时

X：存储 4 位被乘数 A
Y：存储乘数 B
P：存储 $P_0 = 0000$
$C_n$ ：存储循环次数 4

2. 执行过程：

计数器的控制逻辑检测 Y 中最低位，得到 1 信号，因此指示 ALU 执行加法
ALU 将 P 和 X 相加，得到相加结果 $S_0$ 和进位 $C = 0$ ，控制逻辑给出写使能，允许 ALU 将结果存入 P 中
然后对 C、P、Y 整体执行逻辑右移一位， Y 中最低位被移出
计数器数值 $C_n$ 减一

这是首轮，接下来是第二轮：

控制逻辑读取 Y 最低位比特，得到信号“1“，通知 ALU 执行加法

由于执行了逻辑右移，所以 P 中内容为 0110，此时执行 0110 + 1101，得到 0011且产生进位 1

			0 1 1 0  1(Y中最高位)
+			1 1 0 1
----------------------------------------------
    (进位) 1 0 0 1 1  1（Y中最高位）

plaintext

然后逻辑右移一位，并且计数器计数 -1

重复上述步骤即可得最终结果。

注意：最终结果只保留低位的 n 位比特（Y 中内容），因此运算结果可能存在溢出（P 中值不为 0），此时 OF =1

有符号整数的乘法原理#

先给出溢出标志的判断（考点）：

对于无符号数：当寄存器 P 中的值不全为 0 （即存在数值）时溢出，因为乘法结束后，最高位应该全是 0（计数器控制要逻辑 4 位）
对于有符号数：当 P 中的数不是低位寄存器 Y 的最高位（符号位）的符号扩展时，出现溢出

有符号乘法运算中，符号位和数值位一起以补码的形式参与运算。

相较于无符号数电路的改变：

在 Y 最低位加了个辅助位 $y_{-1}$ ，用于决定执行加法还是减法操作。

设 Y 最低位 $y_0$ ，辅助位 $y_{-1}$ ，其执行加减法的信号如图中所示。（底下的记忆技巧别看，错的）

流程和无符号一样，只是在控制逻辑进行操作（加、减、空）的判断的标志不一样。

例题（手算捏，别跟个计算机一样蠢）：

无符号整数的除法运算#

重点：

电路太 sb 了，主要关注三个考点就行：

电路的初始状态
结束状态
除法异常判断

余数的手算

设两个数 A、B（n 位）进行除法，它们有四种情况：

A\div B = C ··· D

$A = 0，B \neq 0\ 或\ |A| < |B|$ ：C = 0，D = A
$A \neq 0，B = 0$ ：除数为 0，抛出”除 0“异常
$A =0，B = 0$ ：抛出除法异常
$A \neq 0，B \neq 0\ 且\ |A| > |B|$ ：除法正常进行

在除法正常进行的情况下，我们重点关注除法的初始状态和结束状态，过程后续补充：

1. 初始：

Y：存储 n 位除数
Q：存储 n 位被除数，在执行过程中存储商
R：对 Q 完成符号扩展，图中 Y 存的是 + 15，因此符号位是 0
异常预检：
1. 若除数是 0，抛出”除 0“异常
2. 若 $|B |> |A|$ ，则 C = 0，D=A，不需要进入循环

2. 结束：最终商存在 Q 中，余数存在 R 中

除法异常判断：

$A \neq 0，B = 0$ ：除数为 0，抛出**”除 0“异常**
商溢出
$A =0，B = 0$ ：抛出除法异常